1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008, 2009 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"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-pass.h"
41 #include "value-prof.h"
42 #include "pointer-set.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 (void **slot
, void *s ATTRIBUTE_UNUSED
)
63 struct rename_map_elt_s
*entry
= (struct rename_map_elt_s
*) *slot
;
64 debug_rename_elt (entry
);
68 /* Print to stderr all the elements of MAP. */
71 debug_rename_map (htab_t map
)
73 htab_traverse (map
, debug_rename_map_1
, NULL
);
76 /* Computes a hash function for database element ELT. */
79 rename_map_elt_info (const void *elt
)
81 return htab_hash_pointer (((const struct rename_map_elt_s
*) elt
)->old_name
);
84 /* Compares database elements E1 and E2. */
87 eq_rename_map_elts (const void *e1
, const void *e2
)
89 const struct rename_map_elt_s
*elt1
= (const struct rename_map_elt_s
*) e1
;
90 const struct rename_map_elt_s
*elt2
= (const struct rename_map_elt_s
*) e2
;
92 return (elt1
->old_name
== elt2
->old_name
);
97 /* Print to stderr the element ELT. */
100 debug_ivtype_elt (ivtype_map_elt elt
)
102 fprintf (stderr
, "(%s, ", elt
->cloog_iv
);
103 print_generic_expr (stderr
, elt
->type
, 0);
104 fprintf (stderr
, ")\n");
107 /* Helper function for debug_ivtype_map. */
110 debug_ivtype_map_1 (void **slot
, void *s ATTRIBUTE_UNUSED
)
112 struct ivtype_map_elt_s
*entry
= (struct ivtype_map_elt_s
*) *slot
;
113 debug_ivtype_elt (entry
);
117 /* Print to stderr all the elements of MAP. */
120 debug_ivtype_map (htab_t map
)
122 htab_traverse (map
, debug_ivtype_map_1
, NULL
);
125 /* Computes a hash function for database element ELT. */
128 ivtype_map_elt_info (const void *elt
)
130 return htab_hash_pointer (((const struct ivtype_map_elt_s
*) elt
)->cloog_iv
);
133 /* Compares database elements E1 and E2. */
136 eq_ivtype_map_elts (const void *e1
, const void *e2
)
138 const struct ivtype_map_elt_s
*elt1
= (const struct ivtype_map_elt_s
*) e1
;
139 const struct ivtype_map_elt_s
*elt2
= (const struct ivtype_map_elt_s
*) e2
;
141 return (elt1
->cloog_iv
== elt2
->cloog_iv
);
146 /* Record LOOP as occuring in REGION. */
149 sese_record_loop (sese region
, loop_p loop
)
151 if (sese_contains_loop (region
, loop
))
154 bitmap_set_bit (SESE_LOOPS (region
), loop
->num
);
155 VEC_safe_push (loop_p
, heap
, SESE_LOOP_NEST (region
), loop
);
158 /* Build the loop nests contained in REGION. Returns true when the
159 operation was successful. */
162 build_sese_loop_nests (sese region
)
166 struct loop
*loop0
, *loop1
;
169 if (bb_in_sese_p (bb
, region
))
171 struct loop
*loop
= bb
->loop_father
;
173 /* Only add loops if they are completely contained in the SCoP. */
174 if (loop
->header
== bb
175 && bb_in_sese_p (loop
->latch
, region
))
176 sese_record_loop (region
, loop
);
179 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
180 can be the case that an inner loop is inserted before an outer
181 loop. To avoid this, semi-sort once. */
182 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop0
); i
++)
184 if (VEC_length (loop_p
, SESE_LOOP_NEST (region
)) == i
+ 1)
187 loop1
= VEC_index (loop_p
, SESE_LOOP_NEST (region
), i
+ 1);
188 if (loop0
->num
> loop1
->num
)
190 VEC_replace (loop_p
, SESE_LOOP_NEST (region
), i
, loop1
);
191 VEC_replace (loop_p
, SESE_LOOP_NEST (region
), i
+ 1, loop0
);
196 /* For a USE in BB, if BB is outside REGION, mark the USE in the
200 sese_build_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
206 if (TREE_CODE (use
) != SSA_NAME
)
209 ver
= SSA_NAME_VERSION (use
);
210 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
213 || !bb_in_sese_p (def_bb
, region
)
214 || bb_in_sese_p (bb
, region
))
217 bitmap_set_bit (liveouts
, ver
);
220 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
221 used in BB that is outside of the REGION. */
224 sese_build_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
226 gimple_stmt_iterator bsi
;
232 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
233 for (bsi
= gsi_start_phis (e
->dest
); !gsi_end_p (bsi
); gsi_next (&bsi
))
234 sese_build_liveouts_use (region
, liveouts
, bb
,
235 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi
), e
));
237 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
238 FOR_EACH_SSA_USE_OPERAND (use_p
, gsi_stmt (bsi
), iter
, SSA_OP_ALL_USES
)
239 sese_build_liveouts_use (region
, liveouts
, bb
, USE_FROM_PTR (use_p
));
242 /* Build the LIVEOUTS of REGION: the set of variables defined inside
243 and used outside the REGION. */
246 sese_build_liveouts (sese region
, bitmap liveouts
)
251 sese_build_liveouts_bb (region
, liveouts
, bb
);
254 /* Builds a new SESE region from edges ENTRY and EXIT. */
257 new_sese (edge entry
, edge exit
)
259 sese region
= XNEW (struct sese_s
);
261 SESE_ENTRY (region
) = entry
;
262 SESE_EXIT (region
) = exit
;
263 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
264 SESE_LOOP_NEST (region
) = VEC_alloc (loop_p
, heap
, 3);
265 SESE_ADD_PARAMS (region
) = true;
266 SESE_PARAMS (region
) = VEC_alloc (tree
, heap
, 3);
267 SESE_PARAMS_INDEX (region
) = htab_create (10, clast_name_index_elt_info
,
268 eq_clast_name_indexes
, free
);
269 SESE_PARAMS_NAMES (region
) = XNEWVEC (char *, num_ssa_names
);
274 /* Deletes REGION. */
277 free_sese (sese region
)
279 if (SESE_LOOPS (region
))
280 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
282 VEC_free (tree
, heap
, SESE_PARAMS (region
));
283 VEC_free (loop_p
, heap
, SESE_LOOP_NEST (region
));
285 if (SESE_PARAMS_INDEX (region
))
286 htab_delete (SESE_PARAMS_INDEX (region
));
288 /* Do not free SESE_PARAMS_NAMES: CLooG does that. */
293 /* Add exit phis for USE on EXIT. */
296 sese_add_exit_phis_edge (basic_block exit
, tree use
, edge false_e
, edge true_e
)
298 gimple phi
= create_phi_node (use
, exit
);
300 create_new_def_for (gimple_phi_result (phi
), phi
,
301 gimple_phi_result_ptr (phi
));
302 add_phi_arg (phi
, use
, false_e
, UNKNOWN_LOCATION
);
303 add_phi_arg (phi
, use
, true_e
, UNKNOWN_LOCATION
);
306 /* Insert in the block BB phi nodes for variables defined in REGION
307 and used outside the REGION. The code generation moves REGION in
308 the else clause of an "if (1)" and generates code in the then
309 clause that is at this point empty:
318 sese_insert_phis_for_liveouts (sese region
, basic_block bb
,
319 edge false_e
, edge true_e
)
323 bitmap liveouts
= BITMAP_ALLOC (NULL
);
325 update_ssa (TODO_update_ssa
);
327 sese_build_liveouts (region
, liveouts
);
328 EXECUTE_IF_SET_IN_BITMAP (liveouts
, 0, i
, bi
)
329 sese_add_exit_phis_edge (bb
, ssa_name (i
), false_e
, true_e
);
330 BITMAP_FREE (liveouts
);
332 update_ssa (TODO_update_ssa
);
335 /* Get the definition of NAME before the SESE. Keep track of the
336 basic blocks that have been VISITED in a bitmap. */
339 get_vdef_before_sese (sese region
, tree name
, sbitmap visited
)
342 gimple def_stmt
= SSA_NAME_DEF_STMT (name
);
343 basic_block def_bb
= gimple_bb (def_stmt
);
345 if (!def_bb
|| !bb_in_sese_p (def_bb
, region
))
348 if (TEST_BIT (visited
, def_bb
->index
))
351 SET_BIT (visited
, def_bb
->index
);
353 switch (gimple_code (def_stmt
))
356 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); i
++)
358 tree arg
= gimple_phi_arg_def (def_stmt
, i
);
359 tree res
= get_vdef_before_sese (region
, arg
, visited
);
370 /* Adjust a virtual phi node PHI that is placed at the end of the
371 generated code for SCOP:
374 | generated code from REGION;
378 The FALSE_E edge comes from the original code, TRUE_E edge comes
379 from the code generated for the SCOP. */
382 sese_adjust_vphi (sese region
, gimple phi
, edge true_e
)
386 gcc_assert (gimple_phi_num_args (phi
) == 2);
388 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
389 if (gimple_phi_arg_edge (phi
, i
) == true_e
)
391 tree true_arg
, false_arg
, before_scop_arg
;
394 true_arg
= gimple_phi_arg_def (phi
, i
);
395 if (!SSA_NAME_IS_DEFAULT_DEF (true_arg
))
398 false_arg
= gimple_phi_arg_def (phi
, i
== 0 ? 1 : 0);
399 if (SSA_NAME_IS_DEFAULT_DEF (false_arg
))
402 visited
= sbitmap_alloc (last_basic_block
);
403 sbitmap_zero (visited
);
404 before_scop_arg
= get_vdef_before_sese (region
, false_arg
, visited
);
405 gcc_assert (before_scop_arg
!= NULL_TREE
);
406 SET_PHI_ARG_DEF (phi
, i
, before_scop_arg
);
407 sbitmap_free (visited
);
411 /* Returns the name associated to OLD_NAME in MAP. */
414 get_rename (htab_t map
, tree old_name
)
416 struct rename_map_elt_s tmp
;
419 tmp
.old_name
= old_name
;
420 slot
= htab_find_slot (map
, &tmp
, NO_INSERT
);
423 return ((rename_map_elt
) *slot
)->expr
;
428 /* Register in MAP the rename tuple (old_name, expr). */
431 set_rename (htab_t map
, tree old_name
, tree expr
)
433 struct rename_map_elt_s tmp
;
436 if (old_name
== expr
)
439 tmp
.old_name
= old_name
;
440 slot
= htab_find_slot (map
, &tmp
, INSERT
);
448 *slot
= new_rename_map_elt (old_name
, expr
);
451 /* Adjusts the phi nodes in the block BB for variables defined in
452 SCOP_REGION and used outside the SCOP_REGION. The code generation
453 moves SCOP_REGION in the else clause of an "if (1)" and generates
454 code in the then clause:
457 | generated code from REGION;
461 To adjust the phi nodes after the condition, the RENAME_MAP is
465 sese_adjust_liveout_phis (sese region
, htab_t rename_map
, basic_block bb
,
466 edge false_e
, edge true_e
)
468 gimple_stmt_iterator si
;
470 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
473 unsigned false_i
= 0;
474 gimple phi
= gsi_stmt (si
);
476 if (!is_gimple_reg (PHI_RESULT (phi
)))
478 sese_adjust_vphi (region
, phi
, true_e
);
482 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
483 if (gimple_phi_arg_edge (phi
, i
) == false_e
)
489 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
490 if (gimple_phi_arg_edge (phi
, i
) == true_e
)
492 tree old_name
= gimple_phi_arg_def (phi
, false_i
);
493 tree expr
= get_rename (rename_map
, old_name
);
496 gcc_assert (old_name
!= expr
);
498 if (TREE_CODE (expr
) != SSA_NAME
499 && is_gimple_reg (old_name
))
501 tree type
= TREE_TYPE (old_name
);
502 tree var
= create_tmp_var (type
, "var");
504 expr
= build2 (MODIFY_EXPR
, type
, var
, expr
);
505 expr
= force_gimple_operand (expr
, &stmts
, true, NULL
);
506 gsi_insert_seq_on_edge_immediate (true_e
, stmts
);
509 SET_PHI_ARG_DEF (phi
, i
, expr
);
514 /* Rename the SSA_NAMEs used in STMT and that appear in MAP. */
517 rename_variables_in_stmt (gimple stmt
, htab_t map
, gimple_stmt_iterator
*insert_gsi
)
522 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
524 tree use
= USE_FROM_PTR (use_p
);
525 tree expr
= get_rename (map
, use
);
526 tree type_use
= TREE_TYPE (use
);
527 tree type_expr
= TREE_TYPE (expr
);
533 if (type_use
!= type_expr
534 || (TREE_CODE (expr
) != SSA_NAME
535 && is_gimple_reg (use
)))
537 tree var
= create_tmp_var (type_use
, "var");
539 if (type_use
!= type_expr
)
540 expr
= fold_convert (type_use
, expr
);
542 expr
= build2 (MODIFY_EXPR
, type_use
, var
, expr
);
543 expr
= force_gimple_operand (expr
, &stmts
, true, NULL
);
544 gsi_insert_seq_before (insert_gsi
, stmts
, GSI_SAME_STMT
);
547 replace_exp (use_p
, expr
);
553 /* Returns true if NAME is a parameter of SESE. */
556 is_parameter (sese region
, tree name
)
561 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
568 /* Returns true if NAME is an induction variable. */
573 return gimple_code (SSA_NAME_DEF_STMT (name
)) == GIMPLE_PHI
;
576 static void expand_scalar_variables_stmt (gimple
, basic_block
, sese
,
577 htab_t
, gimple_stmt_iterator
*);
579 expand_scalar_variables_expr (tree
, tree
, enum tree_code
, tree
, basic_block
,
580 sese
, htab_t
, gimple_stmt_iterator
*);
583 expand_scalar_variables_call (gimple stmt
, basic_block bb
, sese region
,
584 htab_t map
, gimple_stmt_iterator
*gsi
)
586 int i
, nargs
= gimple_call_num_args (stmt
);
587 VEC (tree
, gc
) *args
= VEC_alloc (tree
, gc
, nargs
);
588 tree fn_type
= TREE_TYPE (gimple_call_fn (stmt
));
589 tree fn
= gimple_call_fndecl (stmt
);
590 tree call_expr
, var
, lhs
;
593 for (i
= 0; i
< nargs
; i
++)
595 tree arg
= gimple_call_arg (stmt
, i
);
596 tree t
= TREE_TYPE (arg
);
598 var
= create_tmp_var (t
, "var");
599 arg
= expand_scalar_variables_expr (t
, arg
, TREE_CODE (arg
), NULL
,
600 bb
, region
, map
, gsi
);
601 arg
= build2 (MODIFY_EXPR
, t
, var
, arg
);
602 arg
= force_gimple_operand_gsi (gsi
, arg
, true, NULL
,
603 true, GSI_SAME_STMT
);
604 VEC_quick_push (tree
, args
, arg
);
607 lhs
= gimple_call_lhs (stmt
);
608 var
= create_tmp_var (TREE_TYPE (lhs
), "var");
609 call_expr
= build_call_vec (fn_type
, fn
, args
);
610 call
= gimple_build_call_from_tree (call_expr
);
611 var
= make_ssa_name (var
, call
);
612 gimple_call_set_lhs (call
, var
);
613 gsi_insert_before (gsi
, call
, GSI_SAME_STMT
);
618 /* Copies at GSI all the scalar computations on which the ssa_name OP0
619 depends on in the SESE: these are all the scalar variables used in
620 the definition of OP0, that are defined outside BB and still in the
621 SESE, i.e. not a parameter of the SESE. The expression that is
622 returned contains only induction variables from the generated code:
623 MAP contains the induction variables renaming mapping, and is used
624 to translate the names of induction variables. */
627 expand_scalar_variables_ssa_name (tree op0
, basic_block bb
,
628 sese region
, htab_t map
,
629 gimple_stmt_iterator
*gsi
)
634 if (is_parameter (region
, op0
)
636 return get_rename (map
, op0
);
638 def_stmt
= SSA_NAME_DEF_STMT (op0
);
640 /* Check whether we already have a rename for OP0. */
641 new_op
= get_rename (map
, op0
);
644 && gimple_bb (SSA_NAME_DEF_STMT (new_op
)) == bb
)
647 if (gimple_bb (def_stmt
) == bb
)
649 /* If the defining statement is in the basic block already
650 we do not need to create a new expression for it, we
651 only need to ensure its operands are expanded. */
652 expand_scalar_variables_stmt (def_stmt
, bb
, region
, map
, gsi
);
657 if (!gimple_bb (def_stmt
)
658 || !bb_in_sese_p (gimple_bb (def_stmt
), region
))
661 switch (gimple_code (def_stmt
))
665 tree var0
= gimple_assign_rhs1 (def_stmt
);
666 enum tree_code subcode
= gimple_assign_rhs_code (def_stmt
);
667 tree var1
= gimple_assign_rhs2 (def_stmt
);
668 tree type
= gimple_expr_type (def_stmt
);
670 return expand_scalar_variables_expr (type
, var0
, subcode
, var1
, bb
,
675 return expand_scalar_variables_call (def_stmt
, bb
, region
, map
, gsi
);
684 /* Copies at GSI all the scalar computations on which the expression
685 OP0 CODE OP1 depends on in the SESE: these are all the scalar
686 variables used in OP0 and OP1, defined outside BB and still defined
687 in the SESE, i.e. not a parameter of the SESE. The expression that
688 is returned contains only induction variables from the generated
689 code: MAP contains the induction variables renaming mapping, and is
690 used to translate the names of induction variables. */
693 expand_scalar_variables_expr (tree type
, tree op0
, enum tree_code code
,
694 tree op1
, basic_block bb
, sese region
,
695 htab_t map
, gimple_stmt_iterator
*gsi
)
697 if (TREE_CODE_CLASS (code
) == tcc_constant
698 || TREE_CODE_CLASS (code
) == tcc_declaration
)
701 /* For data references we have to duplicate also its memory
703 if (TREE_CODE_CLASS (code
) == tcc_reference
)
710 tree op
= TREE_OPERAND (op0
, 0);
711 tree res
= expand_scalar_variables_expr
712 (type
, op
, TREE_CODE (op
), NULL
, bb
, region
, map
, gsi
);
713 return build1 (code
, type
, res
);
718 tree old_name
= TREE_OPERAND (op0
, 0);
719 tree expr
= expand_scalar_variables_ssa_name
720 (old_name
, bb
, region
, map
, gsi
);
722 if (TREE_CODE (expr
) != SSA_NAME
723 && is_gimple_reg (old_name
))
725 tree type
= TREE_TYPE (old_name
);
726 tree var
= create_tmp_var (type
, "var");
728 expr
= build2 (MODIFY_EXPR
, type
, var
, expr
);
729 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL
,
730 true, GSI_SAME_STMT
);
733 return fold_build1 (code
, type
, expr
);
738 tree op00
= TREE_OPERAND (op0
, 0);
739 tree op01
= TREE_OPERAND (op0
, 1);
740 tree op02
= TREE_OPERAND (op0
, 2);
741 tree op03
= TREE_OPERAND (op0
, 3);
742 tree base
= expand_scalar_variables_expr
743 (TREE_TYPE (op00
), op00
, TREE_CODE (op00
), NULL
, bb
, region
,
745 tree subscript
= expand_scalar_variables_expr
746 (TREE_TYPE (op01
), op01
, TREE_CODE (op01
), NULL
, bb
, region
,
749 return build4 (ARRAY_REF
, type
, base
, subscript
, op02
, op03
);
753 /* The above cases should catch everything. */
758 if (TREE_CODE_CLASS (code
) == tcc_unary
)
760 tree op0_type
= TREE_TYPE (op0
);
761 enum tree_code op0_code
= TREE_CODE (op0
);
762 tree op0_expr
= expand_scalar_variables_expr (op0_type
, op0
, op0_code
,
763 NULL
, bb
, region
, map
, gsi
);
765 return fold_build1 (code
, type
, op0_expr
);
768 if (TREE_CODE_CLASS (code
) == tcc_binary
769 || TREE_CODE_CLASS (code
) == tcc_comparison
)
771 tree op0_type
= TREE_TYPE (op0
);
772 enum tree_code op0_code
= TREE_CODE (op0
);
773 tree op0_expr
= expand_scalar_variables_expr (op0_type
, op0
, op0_code
,
774 NULL
, bb
, region
, map
, gsi
);
775 tree op1_type
= TREE_TYPE (op1
);
776 enum tree_code op1_code
= TREE_CODE (op1
);
777 tree op1_expr
= expand_scalar_variables_expr (op1_type
, op1
, op1_code
,
778 NULL
, bb
, region
, map
, gsi
);
780 return fold_build2 (code
, type
, op0_expr
, op1_expr
);
783 if (code
== SSA_NAME
)
784 return expand_scalar_variables_ssa_name (op0
, bb
, region
, map
, gsi
);
786 if (code
== ADDR_EXPR
)
793 /* Copies at the beginning of BB all the scalar computations on which
794 STMT depends on in the SESE: these are all the scalar variables used
795 in STMT, defined outside BB and still defined in the SESE, i.e. not a
796 parameter of the SESE. The expression that is returned contains
797 only induction variables from the generated code: MAP contains the
798 induction variables renaming mapping, and is used to translate the
799 names of induction variables. */
802 expand_scalar_variables_stmt (gimple stmt
, basic_block bb
, sese region
,
803 htab_t map
, gimple_stmt_iterator
*gsi
)
808 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
810 tree use
= USE_FROM_PTR (use_p
);
811 tree type
= TREE_TYPE (use
);
812 enum tree_code code
= TREE_CODE (use
);
815 if (!is_gimple_reg (use
))
818 /* Don't expand USE if we already have a rename for it. */
819 use_expr
= get_rename (map
, use
);
823 use_expr
= expand_scalar_variables_expr (type
, use
, code
, NULL
, bb
,
825 use_expr
= fold_convert (type
, use_expr
);
830 if (TREE_CODE (use_expr
) != SSA_NAME
)
832 tree var
= create_tmp_var (type
, "var");
834 use_expr
= build2 (MODIFY_EXPR
, type
, var
, use_expr
);
835 use_expr
= force_gimple_operand_gsi (gsi
, use_expr
, true, NULL
,
836 true, GSI_SAME_STMT
);
839 replace_exp (use_p
, use_expr
);
845 /* Copies at the beginning of BB all the scalar computations on which
846 BB depends on in the SESE: these are all the scalar variables used
847 in BB, defined outside BB and still defined in the SESE, i.e. not a
848 parameter of the SESE. The expression that is returned contains
849 only induction variables from the generated code: MAP contains the
850 induction variables renaming mapping, and is used to translate the
851 names of induction variables. */
854 expand_scalar_variables (basic_block bb
, sese region
, htab_t map
)
856 gimple_stmt_iterator gsi
;
858 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);)
860 gimple stmt
= gsi_stmt (gsi
);
861 expand_scalar_variables_stmt (stmt
, bb
, region
, map
, &gsi
);
866 /* Rename all the SSA_NAMEs from block BB according to the MAP. */
869 rename_variables (basic_block bb
, htab_t map
)
871 gimple_stmt_iterator gsi
;
872 gimple_stmt_iterator insert_gsi
= gsi_start_bb (bb
);
874 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
875 rename_variables_in_stmt (gsi_stmt (gsi
), map
, &insert_gsi
);
878 /* Remove condition from BB. */
881 remove_condition (basic_block bb
)
883 gimple last
= last_stmt (bb
);
885 if (last
&& gimple_code (last
) == GIMPLE_COND
)
887 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
888 gsi_remove (&gsi
, true);
892 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
895 get_true_edge_from_guard_bb (basic_block bb
)
900 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
901 if (e
->flags
& EDGE_TRUE_VALUE
)
908 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
911 get_false_edge_from_guard_bb (basic_block bb
)
916 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
917 if (!(e
->flags
& EDGE_TRUE_VALUE
))
924 /* Returns true when NAME is defined in LOOP. */
927 defined_in_loop_p (tree name
, loop_p loop
)
929 gimple stmt
= SSA_NAME_DEF_STMT (name
);
931 return (gimple_bb (stmt
)->loop_father
== loop
);
934 /* Returns the gimple statement that uses NAME outside the loop it is
935 defined in, returns NULL if there is no such loop close phi node.
936 An invariant of the loop closed SSA form is that the only use of a
937 variable, outside the loop it is defined in, is in the loop close
938 phi node that just follows the loop. */
941 alive_after_loop (tree name
)
944 imm_use_iterator imm_iter
;
945 loop_p loop
= gimple_bb (SSA_NAME_DEF_STMT (name
))->loop_father
;
947 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
949 gimple stmt
= USE_STMT (use_p
);
951 if (gimple_code (stmt
) == GIMPLE_PHI
952 && gimple_bb (stmt
)->loop_father
!= loop
)
959 /* Return true if a close phi has not yet been inserted for the use of
960 variable NAME on the single exit of LOOP. */
963 close_phi_not_yet_inserted_p (loop_p loop
, tree name
)
965 gimple_stmt_iterator psi
;
966 basic_block bb
= single_exit (loop
)->dest
;
968 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
969 if (gimple_phi_arg_def (gsi_stmt (psi
), 0) == name
)
975 /* A structure for passing parameters to add_loop_exit_phis. */
977 typedef struct alep
{
979 VEC (rename_map_elt
, heap
) *new_renames
;
982 /* Helper function for htab_traverse in insert_loop_close_phis. */
985 add_loop_exit_phis (void **slot
, void *data
)
987 struct rename_map_elt_s
*entry
;
991 bool def_in_loop_p
, used_outside_p
, need_close_phi_p
;
992 gimple old_close_phi
;
997 entry
= (struct rename_map_elt_s
*) *slot
;
1002 if (TREE_CODE (expr
) != SSA_NAME
)
1006 def_in_loop_p
= defined_in_loop_p (new_name
, loop
);
1007 old_close_phi
= alive_after_loop (entry
->old_name
);
1008 used_outside_p
= (old_close_phi
!= NULL
);
1009 need_close_phi_p
= (def_in_loop_p
&& used_outside_p
1010 && close_phi_not_yet_inserted_p (loop
, new_name
));
1012 /* Insert a loop close phi node. */
1013 if (need_close_phi_p
)
1015 basic_block bb
= single_exit (loop
)->dest
;
1016 gimple phi
= create_phi_node (new_name
, bb
);
1017 tree new_res
= create_new_def_for (gimple_phi_result (phi
), phi
,
1018 gimple_phi_result_ptr (phi
));
1020 add_phi_arg (phi
, new_name
, single_pred_edge (bb
), UNKNOWN_LOCATION
);
1021 VEC_safe_push (rename_map_elt
, heap
, a
->new_renames
,
1022 new_rename_map_elt (gimple_phi_result (old_close_phi
),
1026 /* Remove the old rename from the map. */
1027 if (def_in_loop_p
&& *slot
)
1036 /* Traverses MAP and removes from it all the tuples (OLD, NEW) where
1037 NEW is defined in LOOP. Inserts on the exit of LOOP the close phi
1038 node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in
1039 the original code. Inserts in MAP the tuple (OLD_RES, RES). */
1042 insert_loop_close_phis (htab_t map
, loop_p loop
)
1049 a
.new_renames
= VEC_alloc (rename_map_elt
, heap
, 3);
1050 update_ssa (TODO_update_ssa
);
1051 htab_traverse (map
, add_loop_exit_phis
, &a
);
1052 update_ssa (TODO_update_ssa
);
1054 for (i
= 0; VEC_iterate (rename_map_elt
, a
.new_renames
, i
, elt
); i
++)
1056 set_rename (map
, elt
->old_name
, elt
->expr
);
1060 VEC_free (rename_map_elt
, heap
, a
.new_renames
);
1063 /* Helper structure for htab_traverse in insert_guard_phis. */
1067 edge true_edge
, false_edge
;
1068 htab_t before_guard
;
1071 /* Return the default name that is before the guard. */
1074 default_before_guard (htab_t before_guard
, tree old_name
)
1076 tree res
= get_rename (before_guard
, old_name
);
1078 if (res
== old_name
)
1080 if (is_gimple_reg (res
))
1081 return fold_convert (TREE_TYPE (res
), integer_zero_node
);
1082 return gimple_default_def (cfun
, SSA_NAME_VAR (res
));
1088 /* Prepares EXPR to be a good phi argument when the phi result is
1089 RES. Insert needed statements on edge E. */
1092 convert_for_phi_arg (tree expr
, tree res
, edge e
)
1094 tree type
= TREE_TYPE (res
);
1096 if (TREE_TYPE (expr
) != type
)
1097 expr
= fold_convert (type
, expr
);
1099 if (TREE_CODE (expr
) != SSA_NAME
1100 && !is_gimple_min_invariant (expr
))
1102 tree var
= create_tmp_var (type
, "var");
1105 expr
= build2 (MODIFY_EXPR
, type
, var
, expr
);
1106 expr
= force_gimple_operand (expr
, &stmts
, true, NULL
);
1107 gsi_insert_seq_on_edge_immediate (e
, stmts
);
1113 /* Helper function for htab_traverse in insert_guard_phis. */
1116 add_guard_exit_phis (void **slot
, void *s
)
1118 struct rename_map_elt_s
*entry
= (struct rename_map_elt_s
*) *slot
;
1119 struct igp
*i
= (struct igp
*) s
;
1120 basic_block bb
= i
->bb
;
1121 edge true_edge
= i
->true_edge
;
1122 edge false_edge
= i
->false_edge
;
1123 tree res
= entry
->old_name
;
1124 tree name1
= entry
->expr
;
1125 tree name2
= default_before_guard (i
->before_guard
, res
);
1128 /* Nothing to be merged if the name before the guard is the same as
1133 name1
= convert_for_phi_arg (name1
, res
, true_edge
);
1134 name2
= convert_for_phi_arg (name2
, res
, false_edge
);
1136 phi
= create_phi_node (res
, bb
);
1137 res
= create_new_def_for (gimple_phi_result (phi
), phi
,
1138 gimple_phi_result_ptr (phi
));
1140 add_phi_arg (phi
, name1
, true_edge
, UNKNOWN_LOCATION
);
1141 add_phi_arg (phi
, name2
, false_edge
, UNKNOWN_LOCATION
);
1148 /* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1).
1149 If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD,
1150 with NAME1 different than NAME2, then insert in BB the phi node:
1152 | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
1154 if there is no tuple for OLD in BEFORE_GUARD, insert
1156 | RES = phi (NAME1 (on TRUE_EDGE),
1157 | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
1159 Finally register in RENAME_MAP the tuple (OLD, RES). */
1162 insert_guard_phis (basic_block bb
, edge true_edge
, edge false_edge
,
1163 htab_t before_guard
, htab_t rename_map
)
1167 i
.true_edge
= true_edge
;
1168 i
.false_edge
= false_edge
;
1169 i
.before_guard
= before_guard
;
1171 update_ssa (TODO_update_ssa
);
1172 htab_traverse (rename_map
, add_guard_exit_phis
, &i
);
1173 update_ssa (TODO_update_ssa
);
1176 /* Create a duplicate of the basic block BB. NOTE: This does not
1177 preserve SSA form. */
1180 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
, htab_t map
)
1182 gimple_stmt_iterator gsi
, gsi_tgt
;
1184 gsi_tgt
= gsi_start_bb (new_bb
);
1185 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1187 def_operand_p def_p
;
1188 ssa_op_iter op_iter
;
1189 gimple stmt
= gsi_stmt (gsi
);
1192 if (gimple_code (stmt
) == GIMPLE_LABEL
)
1195 /* Create a new copy of STMT and duplicate STMT's virtual
1197 copy
= gimple_copy (stmt
);
1198 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
1199 mark_sym_for_renaming (gimple_vop (cfun
));
1201 maybe_duplicate_eh_stmt (copy
, stmt
);
1202 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
1204 /* Create new names for all the definitions created by COPY and
1205 add replacement mappings for each new name. */
1206 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
1208 tree old_name
= DEF_FROM_PTR (def_p
);
1209 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
1210 set_rename (map
, old_name
, new_name
);
1215 /* Copies BB and includes in the copied BB all the statements that can
1216 be reached following the use-def chains from the memory accesses,
1217 and returns the next edge following this new block. */
1220 copy_bb_and_scalar_dependences (basic_block bb
, sese region
,
1221 edge next_e
, htab_t map
)
1223 basic_block new_bb
= split_edge (next_e
);
1225 next_e
= single_succ_edge (new_bb
);
1226 graphite_copy_stmts_from_block (bb
, new_bb
, map
);
1227 remove_condition (new_bb
);
1228 remove_phi_nodes (new_bb
);
1229 expand_scalar_variables (new_bb
, region
, map
);
1230 rename_variables (new_bb
, map
);
1235 /* Returns the outermost loop in SCOP that contains BB. */
1238 outermost_loop_in_sese (sese region
, basic_block bb
)
1242 nest
= bb
->loop_father
;
1243 while (loop_outer (nest
)
1244 && loop_in_sese_p (loop_outer (nest
), region
))
1245 nest
= loop_outer (nest
);
1250 /* Sets the false region of an IF_REGION to REGION. */
1253 if_region_set_false_region (ifsese if_region
, sese region
)
1255 basic_block condition
= if_region_get_condition_block (if_region
);
1256 edge false_edge
= get_false_edge_from_guard_bb (condition
);
1257 basic_block dummy
= false_edge
->dest
;
1258 edge entry_region
= SESE_ENTRY (region
);
1259 edge exit_region
= SESE_EXIT (region
);
1260 basic_block before_region
= entry_region
->src
;
1261 basic_block last_in_region
= exit_region
->src
;
1262 void **slot
= htab_find_slot_with_hash (current_loops
->exits
, exit_region
,
1263 htab_hash_pointer (exit_region
),
1266 entry_region
->flags
= false_edge
->flags
;
1267 false_edge
->flags
= exit_region
->flags
;
1269 redirect_edge_pred (entry_region
, condition
);
1270 redirect_edge_pred (exit_region
, before_region
);
1271 redirect_edge_pred (false_edge
, last_in_region
);
1272 redirect_edge_succ (false_edge
, single_succ (dummy
));
1273 delete_basic_block (dummy
);
1275 exit_region
->flags
= EDGE_FALLTHRU
;
1276 recompute_all_dominators ();
1278 SESE_EXIT (region
) = false_edge
;
1279 if_region
->false_region
= region
;
1283 struct loop_exit
*loop_exit
= GGC_CNEW (struct loop_exit
);
1285 memcpy (loop_exit
, *((struct loop_exit
**) slot
), sizeof (struct loop_exit
));
1286 htab_clear_slot (current_loops
->exits
, slot
);
1288 slot
= htab_find_slot_with_hash (current_loops
->exits
, false_edge
,
1289 htab_hash_pointer (false_edge
),
1291 loop_exit
->e
= false_edge
;
1293 false_edge
->src
->loop_father
->exits
->next
= loop_exit
;
1297 /* Creates an IFSESE with CONDITION on edge ENTRY. */
1300 create_if_region_on_edge (edge entry
, tree condition
)
1304 sese sese_region
= GGC_NEW (struct sese_s
);
1305 sese true_region
= GGC_NEW (struct sese_s
);
1306 sese false_region
= GGC_NEW (struct sese_s
);
1307 ifsese if_region
= GGC_NEW (struct ifsese_s
);
1308 edge exit
= create_empty_if_region_on_edge (entry
, condition
);
1310 if_region
->region
= sese_region
;
1311 if_region
->region
->entry
= entry
;
1312 if_region
->region
->exit
= exit
;
1314 FOR_EACH_EDGE (e
, ei
, entry
->dest
->succs
)
1316 if (e
->flags
& EDGE_TRUE_VALUE
)
1318 true_region
->entry
= e
;
1319 true_region
->exit
= single_succ_edge (e
->dest
);
1320 if_region
->true_region
= true_region
;
1322 else if (e
->flags
& EDGE_FALSE_VALUE
)
1324 false_region
->entry
= e
;
1325 false_region
->exit
= single_succ_edge (e
->dest
);
1326 if_region
->false_region
= false_region
;
1333 /* Moves REGION in a condition expression:
1341 move_sese_in_condition (sese region
)
1343 basic_block pred_block
= split_edge (SESE_ENTRY (region
));
1344 ifsese if_region
= NULL
;
1346 SESE_ENTRY (region
) = single_succ_edge (pred_block
);
1347 if_region
= create_if_region_on_edge (single_pred_edge (pred_block
), integer_one_node
);
1348 if_region_set_false_region (if_region
, region
);
1353 /* Reset the loop->aux pointer for all loops in REGION. */
1356 sese_reset_aux_in_loops (sese region
)
1361 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1365 /* Returns the scalar evolution of T in REGION. Every variable that
1366 is not defined in the REGION is considered a parameter. */
1369 scalar_evolution_in_region (sese region
, loop_p loop
, tree t
)
1372 struct loop
*def_loop
;
1373 basic_block before
= block_before_sese (region
);
1375 if (TREE_CODE (t
) != SSA_NAME
1376 || loop_in_sese_p (loop
, region
))
1377 return instantiate_scev (before
, loop
,
1378 analyze_scalar_evolution (loop
, t
));
1380 if (!defined_in_sese_p (t
, region
))
1383 def
= SSA_NAME_DEF_STMT (t
);
1384 def_loop
= loop_containing_stmt (def
);
1386 if (loop_in_sese_p (def_loop
, region
))
1388 t
= analyze_scalar_evolution (def_loop
, t
);
1389 def_loop
= superloop_at_depth (def_loop
, loop_depth (loop
) + 1);
1390 t
= compute_overall_effect_of_inner_loop (def_loop
, t
);
1394 return instantiate_scev (before
, loop
, t
);