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 stmt
= SSA_NAME_DEF_STMT (name
);
343 basic_block def_bb
= gimple_bb (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 (stmt
))
356 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
358 tree arg
= gimple_phi_arg_def (stmt
, i
);
361 if (gimple_bb (SSA_NAME_DEF_STMT (arg
))
362 && def_bb
->index
== gimple_bb (SSA_NAME_DEF_STMT (arg
))->index
)
365 res
= get_vdef_before_sese (region
, arg
, visited
);
374 use_operand_p use_p
= gimple_vuse_op (stmt
);
375 tree use
= USE_FROM_PTR (use_p
);
377 if (def_bb
->index
== gimple_bb (SSA_NAME_DEF_STMT (use
))->index
)
378 RESET_BIT (visited
, def_bb
->index
);
380 return get_vdef_before_sese (region
, use
, visited
);
388 /* Adjust a virtual phi node PHI that is placed at the end of the
389 generated code for SCOP:
392 | generated code from REGION;
396 The FALSE_E edge comes from the original code, TRUE_E edge comes
397 from the code generated for the SCOP. */
400 sese_adjust_vphi (sese region
, gimple phi
, edge true_e
)
404 gcc_assert (gimple_phi_num_args (phi
) == 2);
406 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
407 if (gimple_phi_arg_edge (phi
, i
) == true_e
)
409 tree true_arg
, false_arg
, before_scop_arg
;
412 true_arg
= gimple_phi_arg_def (phi
, i
);
413 if (!SSA_NAME_IS_DEFAULT_DEF (true_arg
))
416 false_arg
= gimple_phi_arg_def (phi
, i
== 0 ? 1 : 0);
417 if (SSA_NAME_IS_DEFAULT_DEF (false_arg
))
420 visited
= sbitmap_alloc (last_basic_block
);
421 sbitmap_zero (visited
);
422 before_scop_arg
= get_vdef_before_sese (region
, false_arg
, visited
);
423 gcc_assert (before_scop_arg
!= NULL_TREE
);
424 SET_PHI_ARG_DEF (phi
, i
, before_scop_arg
);
425 sbitmap_free (visited
);
429 /* Returns the name associated to OLD_NAME in MAP. */
432 get_rename (htab_t map
, tree old_name
)
434 struct rename_map_elt_s tmp
;
437 tmp
.old_name
= old_name
;
438 slot
= htab_find_slot (map
, &tmp
, NO_INSERT
);
441 return ((rename_map_elt
) *slot
)->expr
;
446 /* Register in MAP the rename tuple (old_name, expr). */
449 set_rename (htab_t map
, tree old_name
, tree expr
)
451 struct rename_map_elt_s tmp
;
454 if (old_name
== expr
)
457 tmp
.old_name
= old_name
;
458 slot
= htab_find_slot (map
, &tmp
, INSERT
);
466 *slot
= new_rename_map_elt (old_name
, expr
);
469 /* Adjusts the phi nodes in the block BB for variables defined in
470 SCOP_REGION and used outside the SCOP_REGION. The code generation
471 moves SCOP_REGION in the else clause of an "if (1)" and generates
472 code in the then clause:
475 | generated code from REGION;
479 To adjust the phi nodes after the condition, the RENAME_MAP is
483 sese_adjust_liveout_phis (sese region
, htab_t rename_map
, basic_block bb
,
484 edge false_e
, edge true_e
)
486 gimple_stmt_iterator si
;
488 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
491 unsigned false_i
= 0;
492 gimple phi
= gsi_stmt (si
);
494 if (!is_gimple_reg (PHI_RESULT (phi
)))
496 sese_adjust_vphi (region
, phi
, true_e
);
500 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
501 if (gimple_phi_arg_edge (phi
, i
) == false_e
)
507 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
508 if (gimple_phi_arg_edge (phi
, i
) == true_e
)
510 tree old_name
= gimple_phi_arg_def (phi
, false_i
);
511 tree expr
= get_rename (rename_map
, old_name
);
514 gcc_assert (old_name
!= expr
);
516 if (TREE_CODE (expr
) != SSA_NAME
517 && is_gimple_reg (old_name
))
519 tree type
= TREE_TYPE (old_name
);
520 tree var
= create_tmp_var (type
, "var");
522 expr
= build2 (MODIFY_EXPR
, type
, var
, expr
);
523 expr
= force_gimple_operand (expr
, &stmts
, true, NULL
);
524 gsi_insert_seq_on_edge_immediate (true_e
, stmts
);
527 SET_PHI_ARG_DEF (phi
, i
, expr
);
532 /* Rename the SSA_NAMEs used in STMT and that appear in MAP. */
535 rename_variables_in_stmt (gimple stmt
, htab_t map
, gimple_stmt_iterator
*insert_gsi
)
540 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
542 tree use
= USE_FROM_PTR (use_p
);
543 tree expr
= get_rename (map
, use
);
544 tree type_use
= TREE_TYPE (use
);
545 tree type_expr
= TREE_TYPE (expr
);
551 if (type_use
!= type_expr
552 || (TREE_CODE (expr
) != SSA_NAME
553 && is_gimple_reg (use
)))
555 tree var
= create_tmp_var (type_use
, "var");
557 if (type_use
!= type_expr
)
558 expr
= fold_convert (type_use
, expr
);
560 expr
= build2 (MODIFY_EXPR
, type_use
, var
, expr
);
561 expr
= force_gimple_operand (expr
, &stmts
, true, NULL
);
562 gsi_insert_seq_before (insert_gsi
, stmts
, GSI_SAME_STMT
);
565 replace_exp (use_p
, expr
);
571 /* Returns true if NAME is a parameter of SESE. */
574 is_parameter (sese region
, tree name
)
579 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
586 /* Returns true if NAME is an induction variable. */
591 return gimple_code (SSA_NAME_DEF_STMT (name
)) == GIMPLE_PHI
;
594 static void expand_scalar_variables_stmt (gimple
, basic_block
, sese
,
595 htab_t
, gimple_stmt_iterator
*);
597 expand_scalar_variables_expr (tree
, tree
, enum tree_code
, tree
, basic_block
,
598 sese
, htab_t
, gimple_stmt_iterator
*);
601 expand_scalar_variables_call (gimple stmt
, basic_block bb
, sese region
,
602 htab_t map
, gimple_stmt_iterator
*gsi
)
604 int i
, nargs
= gimple_call_num_args (stmt
);
605 VEC (tree
, gc
) *args
= VEC_alloc (tree
, gc
, nargs
);
606 tree fn_type
= TREE_TYPE (gimple_call_fn (stmt
));
607 tree fn
= gimple_call_fndecl (stmt
);
608 tree call_expr
, var
, lhs
;
611 for (i
= 0; i
< nargs
; i
++)
613 tree arg
= gimple_call_arg (stmt
, i
);
614 tree t
= TREE_TYPE (arg
);
616 var
= create_tmp_var (t
, "var");
617 arg
= expand_scalar_variables_expr (t
, arg
, TREE_CODE (arg
), NULL
,
618 bb
, region
, map
, gsi
);
619 arg
= build2 (MODIFY_EXPR
, t
, var
, arg
);
620 arg
= force_gimple_operand_gsi (gsi
, arg
, true, NULL
,
621 true, GSI_SAME_STMT
);
622 VEC_quick_push (tree
, args
, arg
);
625 lhs
= gimple_call_lhs (stmt
);
626 var
= create_tmp_var (TREE_TYPE (lhs
), "var");
627 call_expr
= build_call_vec (fn_type
, fn
, args
);
628 call
= gimple_build_call_from_tree (call_expr
);
629 var
= make_ssa_name (var
, call
);
630 gimple_call_set_lhs (call
, var
);
631 gsi_insert_before (gsi
, call
, GSI_SAME_STMT
);
636 /* Copies at GSI all the scalar computations on which the ssa_name OP0
637 depends on in the SESE: these are all the scalar variables used in
638 the definition of OP0, that are defined outside BB and still in the
639 SESE, i.e. not a parameter of the SESE. The expression that is
640 returned contains only induction variables from the generated code:
641 MAP contains the induction variables renaming mapping, and is used
642 to translate the names of induction variables. */
645 expand_scalar_variables_ssa_name (tree op0
, basic_block bb
,
646 sese region
, htab_t map
,
647 gimple_stmt_iterator
*gsi
)
652 if (is_parameter (region
, op0
)
654 return get_rename (map
, op0
);
656 def_stmt
= SSA_NAME_DEF_STMT (op0
);
658 /* Check whether we already have a rename for OP0. */
659 new_op
= get_rename (map
, op0
);
662 && gimple_bb (SSA_NAME_DEF_STMT (new_op
)) == bb
)
665 if (gimple_bb (def_stmt
) == bb
)
667 /* If the defining statement is in the basic block already
668 we do not need to create a new expression for it, we
669 only need to ensure its operands are expanded. */
670 expand_scalar_variables_stmt (def_stmt
, bb
, region
, map
, gsi
);
675 if (!gimple_bb (def_stmt
)
676 || !bb_in_sese_p (gimple_bb (def_stmt
), region
))
679 switch (gimple_code (def_stmt
))
683 tree var0
= gimple_assign_rhs1 (def_stmt
);
684 enum tree_code subcode
= gimple_assign_rhs_code (def_stmt
);
685 tree var1
= gimple_assign_rhs2 (def_stmt
);
686 tree type
= gimple_expr_type (def_stmt
);
688 return expand_scalar_variables_expr (type
, var0
, subcode
, var1
, bb
,
693 return expand_scalar_variables_call (def_stmt
, bb
, region
, map
, gsi
);
702 /* Copies at GSI all the scalar computations on which the expression
703 OP0 CODE OP1 depends on in the SESE: these are all the scalar
704 variables used in OP0 and OP1, defined outside BB and still defined
705 in the SESE, i.e. not a parameter of the SESE. The expression that
706 is returned contains only induction variables from the generated
707 code: MAP contains the induction variables renaming mapping, and is
708 used to translate the names of induction variables. */
711 expand_scalar_variables_expr (tree type
, tree op0
, enum tree_code code
,
712 tree op1
, basic_block bb
, sese region
,
713 htab_t map
, gimple_stmt_iterator
*gsi
)
715 if (TREE_CODE_CLASS (code
) == tcc_constant
716 || TREE_CODE_CLASS (code
) == tcc_declaration
)
719 /* For data references we have to duplicate also its memory
721 if (TREE_CODE_CLASS (code
) == tcc_reference
)
728 tree op
= TREE_OPERAND (op0
, 0);
729 tree res
= expand_scalar_variables_expr
730 (type
, op
, TREE_CODE (op
), NULL
, bb
, region
, map
, gsi
);
731 return build1 (code
, type
, res
);
736 tree old_name
= TREE_OPERAND (op0
, 0);
737 tree expr
= expand_scalar_variables_ssa_name
738 (old_name
, bb
, region
, map
, gsi
);
740 if (TREE_CODE (expr
) != SSA_NAME
741 && is_gimple_reg (old_name
))
743 tree type
= TREE_TYPE (old_name
);
744 tree var
= create_tmp_var (type
, "var");
746 expr
= build2 (MODIFY_EXPR
, type
, var
, expr
);
747 expr
= force_gimple_operand_gsi (gsi
, expr
, true, NULL
,
748 true, GSI_SAME_STMT
);
751 return fold_build1 (code
, type
, expr
);
756 tree op00
= TREE_OPERAND (op0
, 0);
757 tree op01
= TREE_OPERAND (op0
, 1);
758 tree op02
= TREE_OPERAND (op0
, 2);
759 tree op03
= TREE_OPERAND (op0
, 3);
760 tree base
= expand_scalar_variables_expr
761 (TREE_TYPE (op00
), op00
, TREE_CODE (op00
), NULL
, bb
, region
,
763 tree subscript
= expand_scalar_variables_expr
764 (TREE_TYPE (op01
), op01
, TREE_CODE (op01
), NULL
, bb
, region
,
767 return build4 (ARRAY_REF
, type
, base
, subscript
, op02
, op03
);
771 /* The above cases should catch everything. */
776 if (TREE_CODE_CLASS (code
) == tcc_unary
)
778 tree op0_type
= TREE_TYPE (op0
);
779 enum tree_code op0_code
= TREE_CODE (op0
);
780 tree op0_expr
= expand_scalar_variables_expr (op0_type
, op0
, op0_code
,
781 NULL
, bb
, region
, map
, gsi
);
783 return fold_build1 (code
, type
, op0_expr
);
786 if (TREE_CODE_CLASS (code
) == tcc_binary
787 || TREE_CODE_CLASS (code
) == tcc_comparison
)
789 tree op0_type
= TREE_TYPE (op0
);
790 enum tree_code op0_code
= TREE_CODE (op0
);
791 tree op0_expr
= expand_scalar_variables_expr (op0_type
, op0
, op0_code
,
792 NULL
, bb
, region
, map
, gsi
);
793 tree op1_type
= TREE_TYPE (op1
);
794 enum tree_code op1_code
= TREE_CODE (op1
);
795 tree op1_expr
= expand_scalar_variables_expr (op1_type
, op1
, op1_code
,
796 NULL
, bb
, region
, map
, gsi
);
798 return fold_build2 (code
, type
, op0_expr
, op1_expr
);
801 if (code
== SSA_NAME
)
802 return expand_scalar_variables_ssa_name (op0
, bb
, region
, map
, gsi
);
804 if (code
== ADDR_EXPR
)
811 /* Copies at the beginning of BB all the scalar computations on which
812 STMT depends on in the SESE: these are all the scalar variables used
813 in STMT, defined outside BB and still defined in the SESE, i.e. not a
814 parameter of the SESE. The expression that is returned contains
815 only induction variables from the generated code: MAP contains the
816 induction variables renaming mapping, and is used to translate the
817 names of induction variables. */
820 expand_scalar_variables_stmt (gimple stmt
, basic_block bb
, sese region
,
821 htab_t map
, gimple_stmt_iterator
*gsi
)
826 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
828 tree use
= USE_FROM_PTR (use_p
);
829 tree type
= TREE_TYPE (use
);
830 enum tree_code code
= TREE_CODE (use
);
833 if (!is_gimple_reg (use
))
836 /* Don't expand USE if we already have a rename for it. */
837 use_expr
= get_rename (map
, use
);
841 use_expr
= expand_scalar_variables_expr (type
, use
, code
, NULL
, bb
,
843 use_expr
= fold_convert (type
, use_expr
);
848 if (TREE_CODE (use_expr
) != SSA_NAME
)
850 tree var
= create_tmp_var (type
, "var");
852 use_expr
= build2 (MODIFY_EXPR
, type
, var
, use_expr
);
853 use_expr
= force_gimple_operand_gsi (gsi
, use_expr
, true, NULL
,
854 true, GSI_SAME_STMT
);
857 replace_exp (use_p
, use_expr
);
863 /* Copies at the beginning of BB all the scalar computations on which
864 BB depends on in the SESE: these are all the scalar variables used
865 in BB, defined outside BB and still defined in the SESE, i.e. not a
866 parameter of the SESE. The expression that is returned contains
867 only induction variables from the generated code: MAP contains the
868 induction variables renaming mapping, and is used to translate the
869 names of induction variables. */
872 expand_scalar_variables (basic_block bb
, sese region
, htab_t map
)
874 gimple_stmt_iterator gsi
;
876 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);)
878 gimple stmt
= gsi_stmt (gsi
);
879 expand_scalar_variables_stmt (stmt
, bb
, region
, map
, &gsi
);
884 /* Rename all the SSA_NAMEs from block BB according to the MAP. */
887 rename_variables (basic_block bb
, htab_t map
)
889 gimple_stmt_iterator gsi
;
890 gimple_stmt_iterator insert_gsi
= gsi_start_bb (bb
);
892 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
893 rename_variables_in_stmt (gsi_stmt (gsi
), map
, &insert_gsi
);
896 /* Remove condition from BB. */
899 remove_condition (basic_block bb
)
901 gimple last
= last_stmt (bb
);
903 if (last
&& gimple_code (last
) == GIMPLE_COND
)
905 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
906 gsi_remove (&gsi
, true);
910 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
913 get_true_edge_from_guard_bb (basic_block bb
)
918 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
919 if (e
->flags
& EDGE_TRUE_VALUE
)
926 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
929 get_false_edge_from_guard_bb (basic_block bb
)
934 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
935 if (!(e
->flags
& EDGE_TRUE_VALUE
))
942 /* Returns true when NAME is defined in LOOP. */
945 defined_in_loop_p (tree name
, loop_p loop
)
947 gimple stmt
= SSA_NAME_DEF_STMT (name
);
949 return (gimple_bb (stmt
)->loop_father
== loop
);
952 /* Returns the gimple statement that uses NAME outside the loop it is
953 defined in, returns NULL if there is no such loop close phi node.
954 An invariant of the loop closed SSA form is that the only use of a
955 variable, outside the loop it is defined in, is in the loop close
956 phi node that just follows the loop. */
959 alive_after_loop (tree name
)
962 imm_use_iterator imm_iter
;
963 loop_p loop
= gimple_bb (SSA_NAME_DEF_STMT (name
))->loop_father
;
965 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, name
)
967 gimple stmt
= USE_STMT (use_p
);
969 if (gimple_code (stmt
) == GIMPLE_PHI
970 && gimple_bb (stmt
)->loop_father
!= loop
)
977 /* Return true if a close phi has not yet been inserted for the use of
978 variable NAME on the single exit of LOOP. */
981 close_phi_not_yet_inserted_p (loop_p loop
, tree name
)
983 gimple_stmt_iterator psi
;
984 basic_block bb
= single_exit (loop
)->dest
;
986 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
987 if (gimple_phi_arg_def (gsi_stmt (psi
), 0) == name
)
993 /* A structure for passing parameters to add_loop_exit_phis. */
995 typedef struct alep
{
997 VEC (rename_map_elt
, heap
) *new_renames
;
1000 /* Helper function for htab_traverse in insert_loop_close_phis. */
1003 add_loop_exit_phis (void **slot
, void *data
)
1005 struct rename_map_elt_s
*entry
;
1008 tree expr
, new_name
;
1009 bool def_in_loop_p
, used_outside_p
, need_close_phi_p
;
1010 gimple old_close_phi
;
1015 entry
= (struct rename_map_elt_s
*) *slot
;
1020 if (TREE_CODE (expr
) != SSA_NAME
)
1024 def_in_loop_p
= defined_in_loop_p (new_name
, loop
);
1025 old_close_phi
= alive_after_loop (entry
->old_name
);
1026 used_outside_p
= (old_close_phi
!= NULL
);
1027 need_close_phi_p
= (def_in_loop_p
&& used_outside_p
1028 && close_phi_not_yet_inserted_p (loop
, new_name
));
1030 /* Insert a loop close phi node. */
1031 if (need_close_phi_p
)
1033 basic_block bb
= single_exit (loop
)->dest
;
1034 gimple phi
= create_phi_node (new_name
, bb
);
1035 tree new_res
= create_new_def_for (gimple_phi_result (phi
), phi
,
1036 gimple_phi_result_ptr (phi
));
1038 add_phi_arg (phi
, new_name
, single_pred_edge (bb
), UNKNOWN_LOCATION
);
1039 VEC_safe_push (rename_map_elt
, heap
, a
->new_renames
,
1040 new_rename_map_elt (gimple_phi_result (old_close_phi
),
1044 /* Remove the old rename from the map. */
1045 if (def_in_loop_p
&& *slot
)
1054 /* Traverses MAP and removes from it all the tuples (OLD, NEW) where
1055 NEW is defined in LOOP. Inserts on the exit of LOOP the close phi
1056 node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in
1057 the original code. Inserts in MAP the tuple (OLD_RES, RES). */
1060 insert_loop_close_phis (htab_t map
, loop_p loop
)
1067 a
.new_renames
= VEC_alloc (rename_map_elt
, heap
, 3);
1068 update_ssa (TODO_update_ssa
);
1069 htab_traverse (map
, add_loop_exit_phis
, &a
);
1070 update_ssa (TODO_update_ssa
);
1072 for (i
= 0; VEC_iterate (rename_map_elt
, a
.new_renames
, i
, elt
); i
++)
1074 set_rename (map
, elt
->old_name
, elt
->expr
);
1078 VEC_free (rename_map_elt
, heap
, a
.new_renames
);
1081 /* Helper structure for htab_traverse in insert_guard_phis. */
1085 edge true_edge
, false_edge
;
1086 htab_t before_guard
;
1089 /* Return the default name that is before the guard. */
1092 default_before_guard (htab_t before_guard
, tree old_name
)
1094 tree res
= get_rename (before_guard
, old_name
);
1096 if (res
== old_name
)
1098 if (is_gimple_reg (res
))
1099 return fold_convert (TREE_TYPE (res
), integer_zero_node
);
1100 return gimple_default_def (cfun
, SSA_NAME_VAR (res
));
1106 /* Prepares EXPR to be a good phi argument when the phi result is
1107 RES. Insert needed statements on edge E. */
1110 convert_for_phi_arg (tree expr
, tree res
, edge e
)
1112 tree type
= TREE_TYPE (res
);
1114 if (TREE_TYPE (expr
) != type
)
1115 expr
= fold_convert (type
, expr
);
1117 if (TREE_CODE (expr
) != SSA_NAME
1118 && !is_gimple_min_invariant (expr
))
1120 tree var
= create_tmp_var (type
, "var");
1123 expr
= build2 (MODIFY_EXPR
, type
, var
, expr
);
1124 expr
= force_gimple_operand (expr
, &stmts
, true, NULL
);
1125 gsi_insert_seq_on_edge_immediate (e
, stmts
);
1131 /* Helper function for htab_traverse in insert_guard_phis. */
1134 add_guard_exit_phis (void **slot
, void *s
)
1136 struct rename_map_elt_s
*entry
= (struct rename_map_elt_s
*) *slot
;
1137 struct igp
*i
= (struct igp
*) s
;
1138 basic_block bb
= i
->bb
;
1139 edge true_edge
= i
->true_edge
;
1140 edge false_edge
= i
->false_edge
;
1141 tree res
= entry
->old_name
;
1142 tree name1
= entry
->expr
;
1143 tree name2
= default_before_guard (i
->before_guard
, res
);
1146 /* Nothing to be merged if the name before the guard is the same as
1151 name1
= convert_for_phi_arg (name1
, res
, true_edge
);
1152 name2
= convert_for_phi_arg (name2
, res
, false_edge
);
1154 phi
= create_phi_node (res
, bb
);
1155 res
= create_new_def_for (gimple_phi_result (phi
), phi
,
1156 gimple_phi_result_ptr (phi
));
1158 add_phi_arg (phi
, name1
, true_edge
, UNKNOWN_LOCATION
);
1159 add_phi_arg (phi
, name2
, false_edge
, UNKNOWN_LOCATION
);
1166 /* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1).
1167 If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD,
1168 with NAME1 different than NAME2, then insert in BB the phi node:
1170 | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
1172 if there is no tuple for OLD in BEFORE_GUARD, insert
1174 | RES = phi (NAME1 (on TRUE_EDGE),
1175 | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
1177 Finally register in RENAME_MAP the tuple (OLD, RES). */
1180 insert_guard_phis (basic_block bb
, edge true_edge
, edge false_edge
,
1181 htab_t before_guard
, htab_t rename_map
)
1185 i
.true_edge
= true_edge
;
1186 i
.false_edge
= false_edge
;
1187 i
.before_guard
= before_guard
;
1189 update_ssa (TODO_update_ssa
);
1190 htab_traverse (rename_map
, add_guard_exit_phis
, &i
);
1191 update_ssa (TODO_update_ssa
);
1194 /* Create a duplicate of the basic block BB. NOTE: This does not
1195 preserve SSA form. */
1198 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
, htab_t map
)
1200 gimple_stmt_iterator gsi
, gsi_tgt
;
1202 gsi_tgt
= gsi_start_bb (new_bb
);
1203 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1205 def_operand_p def_p
;
1206 ssa_op_iter op_iter
;
1208 gimple stmt
= gsi_stmt (gsi
);
1211 if (gimple_code (stmt
) == GIMPLE_LABEL
)
1214 /* Create a new copy of STMT and duplicate STMT's virtual
1216 copy
= gimple_copy (stmt
);
1217 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
1218 mark_sym_for_renaming (gimple_vop (cfun
));
1220 region
= lookup_stmt_eh_region (stmt
);
1222 add_stmt_to_eh_region (copy
, region
);
1223 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
1225 /* Create new names for all the definitions created by COPY and
1226 add replacement mappings for each new name. */
1227 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
1229 tree old_name
= DEF_FROM_PTR (def_p
);
1230 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
1231 set_rename (map
, old_name
, new_name
);
1236 /* Copies BB and includes in the copied BB all the statements that can
1237 be reached following the use-def chains from the memory accesses,
1238 and returns the next edge following this new block. */
1241 copy_bb_and_scalar_dependences (basic_block bb
, sese region
,
1242 edge next_e
, htab_t map
)
1244 basic_block new_bb
= split_edge (next_e
);
1246 next_e
= single_succ_edge (new_bb
);
1247 graphite_copy_stmts_from_block (bb
, new_bb
, map
);
1248 remove_condition (new_bb
);
1249 remove_phi_nodes (new_bb
);
1250 expand_scalar_variables (new_bb
, region
, map
);
1251 rename_variables (new_bb
, map
);
1256 /* Returns the outermost loop in SCOP that contains BB. */
1259 outermost_loop_in_sese (sese region
, basic_block bb
)
1263 nest
= bb
->loop_father
;
1264 while (loop_outer (nest
)
1265 && loop_in_sese_p (loop_outer (nest
), region
))
1266 nest
= loop_outer (nest
);
1271 /* Sets the false region of an IF_REGION to REGION. */
1274 if_region_set_false_region (ifsese if_region
, sese region
)
1276 basic_block condition
= if_region_get_condition_block (if_region
);
1277 edge false_edge
= get_false_edge_from_guard_bb (condition
);
1278 basic_block dummy
= false_edge
->dest
;
1279 edge entry_region
= SESE_ENTRY (region
);
1280 edge exit_region
= SESE_EXIT (region
);
1281 basic_block before_region
= entry_region
->src
;
1282 basic_block last_in_region
= exit_region
->src
;
1283 void **slot
= htab_find_slot_with_hash (current_loops
->exits
, exit_region
,
1284 htab_hash_pointer (exit_region
),
1287 entry_region
->flags
= false_edge
->flags
;
1288 false_edge
->flags
= exit_region
->flags
;
1290 redirect_edge_pred (entry_region
, condition
);
1291 redirect_edge_pred (exit_region
, before_region
);
1292 redirect_edge_pred (false_edge
, last_in_region
);
1293 redirect_edge_succ (false_edge
, single_succ (dummy
));
1294 delete_basic_block (dummy
);
1296 exit_region
->flags
= EDGE_FALLTHRU
;
1297 recompute_all_dominators ();
1299 SESE_EXIT (region
) = false_edge
;
1300 if_region
->false_region
= region
;
1304 struct loop_exit
*loop_exit
= GGC_CNEW (struct loop_exit
);
1306 memcpy (loop_exit
, *((struct loop_exit
**) slot
), sizeof (struct loop_exit
));
1307 htab_clear_slot (current_loops
->exits
, slot
);
1309 slot
= htab_find_slot_with_hash (current_loops
->exits
, false_edge
,
1310 htab_hash_pointer (false_edge
),
1312 loop_exit
->e
= false_edge
;
1314 false_edge
->src
->loop_father
->exits
->next
= loop_exit
;
1318 /* Creates an IFSESE with CONDITION on edge ENTRY. */
1321 create_if_region_on_edge (edge entry
, tree condition
)
1325 sese sese_region
= GGC_NEW (struct sese_s
);
1326 sese true_region
= GGC_NEW (struct sese_s
);
1327 sese false_region
= GGC_NEW (struct sese_s
);
1328 ifsese if_region
= GGC_NEW (struct ifsese_s
);
1329 edge exit
= create_empty_if_region_on_edge (entry
, condition
);
1331 if_region
->region
= sese_region
;
1332 if_region
->region
->entry
= entry
;
1333 if_region
->region
->exit
= exit
;
1335 FOR_EACH_EDGE (e
, ei
, entry
->dest
->succs
)
1337 if (e
->flags
& EDGE_TRUE_VALUE
)
1339 true_region
->entry
= e
;
1340 true_region
->exit
= single_succ_edge (e
->dest
);
1341 if_region
->true_region
= true_region
;
1343 else if (e
->flags
& EDGE_FALSE_VALUE
)
1345 false_region
->entry
= e
;
1346 false_region
->exit
= single_succ_edge (e
->dest
);
1347 if_region
->false_region
= false_region
;
1354 /* Moves REGION in a condition expression:
1362 move_sese_in_condition (sese region
)
1364 basic_block pred_block
= split_edge (SESE_ENTRY (region
));
1365 ifsese if_region
= NULL
;
1367 SESE_ENTRY (region
) = single_succ_edge (pred_block
);
1368 if_region
= create_if_region_on_edge (single_pred_edge (pred_block
), integer_one_node
);
1369 if_region_set_false_region (if_region
, region
);
1374 /* Reset the loop->aux pointer for all loops in REGION. */
1377 sese_reset_aux_in_loops (sese region
)
1382 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1386 /* Returns the scalar evolution of T in REGION. Every variable that
1387 is not defined in the REGION is considered a parameter. */
1390 scalar_evolution_in_region (sese region
, loop_p loop
, tree t
)
1393 struct loop
*def_loop
;
1394 basic_block before
= block_before_sese (region
);
1396 if (TREE_CODE (t
) != SSA_NAME
1397 || loop_in_sese_p (loop
, region
))
1398 return instantiate_scev (before
, loop
,
1399 analyze_scalar_evolution (loop
, t
));
1401 if (!defined_in_sese_p (t
, region
))
1404 def
= SSA_NAME_DEF_STMT (t
);
1405 def_loop
= loop_containing_stmt (def
);
1407 if (loop_in_sese_p (def_loop
, region
))
1409 t
= analyze_scalar_evolution (def_loop
, t
);
1410 def_loop
= superloop_at_depth (def_loop
, loop_depth (loop
) + 1);
1411 t
= compute_overall_effect_of_inner_loop (def_loop
, t
);
1415 return instantiate_scev (before
, loop
, t
);