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))
239 gimple stmt = gsi_stmt (bsi);
241 if (is_gimple_debug (stmt))
244 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
245 sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
249 /* For a USE in BB, return true if BB is outside REGION and it's not
250 in the LIVEOUTS set. */
253 sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
259 if (TREE_CODE (use) != SSA_NAME)
262 ver = SSA_NAME_VERSION (use);
264 /* If it's in liveouts, the variable will get a new PHI node, and
265 the debug use will be properly adjusted. */
266 if (bitmap_bit_p (liveouts, ver))
269 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
272 || !bb_in_sese_p (def_bb, region)
273 || bb_in_sese_p (bb, region))
279 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
280 are not marked as liveouts. */
283 sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
285 gimple_stmt_iterator bsi;
289 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
291 gimple stmt = gsi_stmt (bsi);
293 if (!is_gimple_debug (stmt))
296 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
297 if (sese_bad_liveouts_use (region, liveouts, bb,
298 USE_FROM_PTR (use_p)))
300 gimple_debug_bind_reset_value (stmt);
307 /* Build the LIVEOUTS of REGION: the set of variables defined inside
308 and used outside the REGION. */
311 sese_build_liveouts (sese region, bitmap liveouts)
316 sese_build_liveouts_bb (region, liveouts, bb);
317 if (MAY_HAVE_DEBUG_INSNS)
319 sese_reset_debug_liveouts_bb (region, liveouts, bb);
322 /* Builds a new SESE region from edges ENTRY and EXIT. */
325 new_sese (edge entry, edge exit)
327 sese region = XNEW (struct sese_s);
329 SESE_ENTRY (region) = entry;
330 SESE_EXIT (region) = exit;
331 SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
332 SESE_LOOP_NEST (region) = VEC_alloc (loop_p, heap, 3);
333 SESE_ADD_PARAMS (region) = true;
334 SESE_PARAMS (region) = VEC_alloc (tree, heap, 3);
335 SESE_PARAMS_INDEX (region) = htab_create (10, clast_name_index_elt_info,
336 eq_clast_name_indexes, free);
337 SESE_PARAMS_NAMES (region) = XNEWVEC (char *, num_ssa_names);
342 /* Deletes REGION. */
345 free_sese (sese region)
347 if (SESE_LOOPS (region))
348 SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
350 VEC_free (tree, heap, SESE_PARAMS (region));
351 VEC_free (loop_p, heap, SESE_LOOP_NEST (region));
353 if (SESE_PARAMS_INDEX (region))
354 htab_delete (SESE_PARAMS_INDEX (region));
356 /* Do not free SESE_PARAMS_NAMES: CLooG does that. */
361 /* Add exit phis for USE on EXIT. */
364 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
366 gimple phi = create_phi_node (use, exit);
368 create_new_def_for (gimple_phi_result (phi), phi,
369 gimple_phi_result_ptr (phi));
370 add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
371 add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
374 /* Insert in the block BB phi nodes for variables defined in REGION
375 and used outside the REGION. The code generation moves REGION in
376 the else clause of an "if (1)" and generates code in the then
377 clause that is at this point empty:
386 sese_insert_phis_for_liveouts (sese region, basic_block bb,
387 edge false_e, edge true_e)
391 bitmap liveouts = BITMAP_ALLOC (NULL);
393 update_ssa (TODO_update_ssa);
395 sese_build_liveouts (region, liveouts);
396 EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
397 sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
398 BITMAP_FREE (liveouts);
400 update_ssa (TODO_update_ssa);
403 /* Get the definition of NAME before the SESE. Keep track of the
404 basic blocks that have been VISITED in a bitmap. */
407 get_vdef_before_sese (sese region, tree name, sbitmap visited)
410 gimple stmt = SSA_NAME_DEF_STMT (name);
411 basic_block def_bb = gimple_bb (stmt);
413 if (!def_bb || !bb_in_sese_p (def_bb, region))
416 if (TEST_BIT (visited, def_bb->index))
419 SET_BIT (visited, def_bb->index);
421 switch (gimple_code (stmt))
424 for (i = 0; i < gimple_phi_num_args (stmt); i++)
426 tree arg = gimple_phi_arg_def (stmt, i);
429 if (gimple_bb (SSA_NAME_DEF_STMT (arg))
430 && def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (arg))->index)
433 res = get_vdef_before_sese (region, arg, visited);
442 use_operand_p use_p = gimple_vuse_op (stmt);
443 tree use = USE_FROM_PTR (use_p);
445 if (def_bb->index == gimple_bb (SSA_NAME_DEF_STMT (use))->index)
446 RESET_BIT (visited, def_bb->index);
448 return get_vdef_before_sese (region, use, visited);
456 /* Adjust a virtual phi node PHI that is placed at the end of the
457 generated code for SCOP:
460 | generated code from REGION;
464 The FALSE_E edge comes from the original code, TRUE_E edge comes
465 from the code generated for the SCOP. */
468 sese_adjust_vphi (sese region, gimple phi, edge true_e)
472 gcc_assert (gimple_phi_num_args (phi) == 2);
474 for (i = 0; i < gimple_phi_num_args (phi); i++)
475 if (gimple_phi_arg_edge (phi, i) == true_e)
477 tree true_arg, false_arg, before_scop_arg;
480 true_arg = gimple_phi_arg_def (phi, i);
481 if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
484 false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
485 if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
488 visited = sbitmap_alloc (last_basic_block);
489 sbitmap_zero (visited);
490 before_scop_arg = get_vdef_before_sese (region, false_arg, visited);
491 gcc_assert (before_scop_arg != NULL_TREE);
492 SET_PHI_ARG_DEF (phi, i, before_scop_arg);
493 sbitmap_free (visited);
497 /* Returns the name associated to OLD_NAME in MAP. */
500 get_rename (htab_t map, tree old_name)
502 struct rename_map_elt_s tmp;
505 tmp.old_name = old_name;
506 slot = htab_find_slot (map, &tmp, NO_INSERT);
509 return ((rename_map_elt) *slot)->expr;
514 /* Register in MAP the rename tuple (old_name, expr). */
517 set_rename (htab_t map, tree old_name, tree expr)
519 struct rename_map_elt_s tmp;
522 if (old_name == expr)
525 tmp.old_name = old_name;
526 slot = htab_find_slot (map, &tmp, INSERT);
534 *slot = new_rename_map_elt (old_name, expr);
537 /* Adjusts the phi nodes in the block BB for variables defined in
538 SCOP_REGION and used outside the SCOP_REGION. The code generation
539 moves SCOP_REGION in the else clause of an "if (1)" and generates
540 code in the then clause:
543 | generated code from REGION;
547 To adjust the phi nodes after the condition, the RENAME_MAP is
551 sese_adjust_liveout_phis (sese region, htab_t rename_map, basic_block bb,
552 edge false_e, edge true_e)
554 gimple_stmt_iterator si;
556 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
559 unsigned false_i = 0;
560 gimple phi = gsi_stmt (si);
562 if (!is_gimple_reg (PHI_RESULT (phi)))
564 sese_adjust_vphi (region, phi, true_e);
568 for (i = 0; i < gimple_phi_num_args (phi); i++)
569 if (gimple_phi_arg_edge (phi, i) == false_e)
575 for (i = 0; i < gimple_phi_num_args (phi); i++)
576 if (gimple_phi_arg_edge (phi, i) == true_e)
578 tree old_name = gimple_phi_arg_def (phi, false_i);
579 tree expr = get_rename (rename_map, old_name);
582 gcc_assert (old_name != expr);
584 if (TREE_CODE (expr) != SSA_NAME
585 && is_gimple_reg (old_name))
587 tree type = TREE_TYPE (old_name);
588 tree var = create_tmp_var (type, "var");
590 expr = build2 (MODIFY_EXPR, type, var, expr);
591 expr = force_gimple_operand (expr, &stmts, true, NULL);
592 gsi_insert_seq_on_edge_immediate (true_e, stmts);
595 SET_PHI_ARG_DEF (phi, i, expr);
600 /* Rename the SSA_NAMEs used in STMT and that appear in MAP. */
603 rename_variables_in_stmt (gimple stmt, htab_t map, gimple_stmt_iterator *insert_gsi)
608 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
610 tree use = USE_FROM_PTR (use_p);
611 tree expr = get_rename (map, use);
612 tree type_use = TREE_TYPE (use);
613 tree type_expr = TREE_TYPE (expr);
619 if (type_use != type_expr
620 || (TREE_CODE (expr) != SSA_NAME
621 && is_gimple_reg (use)))
625 if (is_gimple_debug (stmt))
627 if (gimple_debug_bind_p (stmt))
628 gimple_debug_bind_reset_value (stmt);
635 var = create_tmp_var (type_use, "var");
637 if (type_use != type_expr)
638 expr = fold_convert (type_use, expr);
640 expr = build2 (MODIFY_EXPR, type_use, var, expr);
641 expr = force_gimple_operand (expr, &stmts, true, NULL);
642 gsi_insert_seq_before (insert_gsi, stmts, GSI_SAME_STMT);
645 replace_exp (use_p, expr);
651 /* Returns true if NAME is a parameter of SESE. */
654 is_parameter (sese region, tree name)
659 for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
666 /* Returns true if NAME is an induction variable. */
671 return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
674 static void expand_scalar_variables_stmt (gimple, basic_block, sese,
675 htab_t, gimple_stmt_iterator *);
677 expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
678 sese, htab_t, gimple_stmt_iterator *);
681 expand_scalar_variables_call (gimple stmt, basic_block bb, sese region,
682 htab_t map, gimple_stmt_iterator *gsi)
684 int i, nargs = gimple_call_num_args (stmt);
685 VEC (tree, gc) *args = VEC_alloc (tree, gc, nargs);
686 tree fn_type = TREE_TYPE (gimple_call_fn (stmt));
687 tree fn = gimple_call_fndecl (stmt);
688 tree call_expr, var, lhs;
691 for (i = 0; i < nargs; i++)
693 tree arg = gimple_call_arg (stmt, i);
694 tree t = TREE_TYPE (arg);
696 var = create_tmp_var (t, "var");
697 arg = expand_scalar_variables_expr (t, arg, TREE_CODE (arg), NULL,
698 bb, region, map, gsi);
699 arg = build2 (MODIFY_EXPR, t, var, arg);
700 arg = force_gimple_operand_gsi (gsi, arg, true, NULL,
701 true, GSI_SAME_STMT);
702 VEC_quick_push (tree, args, arg);
705 lhs = gimple_call_lhs (stmt);
706 var = create_tmp_var (TREE_TYPE (lhs), "var");
707 call_expr = build_call_vec (fn_type, fn, args);
708 call = gimple_build_call_from_tree (call_expr);
709 var = make_ssa_name (var, call);
710 gimple_call_set_lhs (call, var);
711 gsi_insert_before (gsi, call, GSI_SAME_STMT);
716 /* Copies at GSI all the scalar computations on which the ssa_name OP0
717 depends on in the SESE: these are all the scalar variables used in
718 the definition of OP0, that are defined outside BB and still in the
719 SESE, i.e. not a parameter of the SESE. The expression that is
720 returned contains only induction variables from the generated code:
721 MAP contains the induction variables renaming mapping, and is used
722 to translate the names of induction variables. */
725 expand_scalar_variables_ssa_name (tree op0, basic_block bb,
726 sese region, htab_t map,
727 gimple_stmt_iterator *gsi)
732 if (is_parameter (region, op0)
734 return get_rename (map, op0);
736 def_stmt = SSA_NAME_DEF_STMT (op0);
738 /* Check whether we already have a rename for OP0. */
739 new_op = get_rename (map, op0);
742 && gimple_bb (SSA_NAME_DEF_STMT (new_op)) == bb)
745 if (gimple_bb (def_stmt) == bb)
747 /* If the defining statement is in the basic block already
748 we do not need to create a new expression for it, we
749 only need to ensure its operands are expanded. */
750 expand_scalar_variables_stmt (def_stmt, bb, region, map, gsi);
755 if (!gimple_bb (def_stmt)
756 || !bb_in_sese_p (gimple_bb (def_stmt), region))
759 switch (gimple_code (def_stmt))
763 tree var0 = gimple_assign_rhs1 (def_stmt);
764 enum tree_code subcode = gimple_assign_rhs_code (def_stmt);
765 tree var1 = gimple_assign_rhs2 (def_stmt);
766 tree type = gimple_expr_type (def_stmt);
768 return expand_scalar_variables_expr (type, var0, subcode, var1, bb,
773 return expand_scalar_variables_call (def_stmt, bb, region, map, gsi);
782 /* Copies at GSI all the scalar computations on which the expression
783 OP0 CODE OP1 depends on in the SESE: these are all the scalar
784 variables used in OP0 and OP1, defined outside BB and still defined
785 in the SESE, i.e. not a parameter of the SESE. The expression that
786 is returned contains only induction variables from the generated
787 code: MAP contains the induction variables renaming mapping, and is
788 used to translate the names of induction variables. */
791 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
792 tree op1, basic_block bb, sese region,
793 htab_t map, gimple_stmt_iterator *gsi)
795 if (TREE_CODE_CLASS (code) == tcc_constant
796 || TREE_CODE_CLASS (code) == tcc_declaration)
799 /* For data references we have to duplicate also its memory
801 if (TREE_CODE_CLASS (code) == tcc_reference)
808 tree op = TREE_OPERAND (op0, 0);
809 tree res = expand_scalar_variables_expr
810 (type, op, TREE_CODE (op), NULL, bb, region, map, gsi);
811 return build1 (code, type, res);
816 tree old_name = TREE_OPERAND (op0, 0);
817 tree expr = expand_scalar_variables_ssa_name
818 (old_name, bb, region, map, gsi);
820 if (TREE_CODE (expr) != SSA_NAME
821 && is_gimple_reg (old_name))
823 tree type = TREE_TYPE (old_name);
824 tree var = create_tmp_var (type, "var");
826 expr = build2 (MODIFY_EXPR, type, var, expr);
827 expr = force_gimple_operand_gsi (gsi, expr, true, NULL,
828 true, GSI_SAME_STMT);
831 return fold_build1 (code, type, expr);
836 tree op00 = TREE_OPERAND (op0, 0);
837 tree op01 = TREE_OPERAND (op0, 1);
838 tree op02 = TREE_OPERAND (op0, 2);
839 tree op03 = TREE_OPERAND (op0, 3);
840 tree base = expand_scalar_variables_expr
841 (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, region,
843 tree subscript = expand_scalar_variables_expr
844 (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, region,
847 return build4 (ARRAY_REF, type, base, subscript, op02, op03);
851 /* The above cases should catch everything. */
856 if (TREE_CODE_CLASS (code) == tcc_unary)
858 tree op0_type = TREE_TYPE (op0);
859 enum tree_code op0_code = TREE_CODE (op0);
860 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
861 NULL, bb, region, map, gsi);
863 return fold_build1 (code, type, op0_expr);
866 if (TREE_CODE_CLASS (code) == tcc_binary
867 || TREE_CODE_CLASS (code) == tcc_comparison)
869 tree op0_type = TREE_TYPE (op0);
870 enum tree_code op0_code = TREE_CODE (op0);
871 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
872 NULL, bb, region, map, gsi);
873 tree op1_type = TREE_TYPE (op1);
874 enum tree_code op1_code = TREE_CODE (op1);
875 tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
876 NULL, bb, region, map, gsi);
878 return fold_build2 (code, type, op0_expr, op1_expr);
881 if (code == SSA_NAME)
882 return expand_scalar_variables_ssa_name (op0, bb, region, map, gsi);
884 if (code == ADDR_EXPR)
891 /* Copies at the beginning of BB all the scalar computations on which
892 STMT depends on in the SESE: these are all the scalar variables used
893 in STMT, defined outside BB and still defined in the SESE, i.e. not a
894 parameter of the SESE. The expression that is returned contains
895 only induction variables from the generated code: MAP contains the
896 induction variables renaming mapping, and is used to translate the
897 names of induction variables. */
900 expand_scalar_variables_stmt (gimple stmt, basic_block bb, sese region,
901 htab_t map, gimple_stmt_iterator *gsi)
906 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
908 tree use = USE_FROM_PTR (use_p);
909 tree type = TREE_TYPE (use);
910 enum tree_code code = TREE_CODE (use);
913 if (!is_gimple_reg (use))
916 /* Don't expand USE if we already have a rename for it. */
917 use_expr = get_rename (map, use);
921 use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
923 use_expr = fold_convert (type, use_expr);
928 if (is_gimple_debug (stmt))
930 if (gimple_debug_bind_p (stmt))
931 gimple_debug_bind_reset_value (stmt);
938 if (TREE_CODE (use_expr) != SSA_NAME)
940 tree var = create_tmp_var (type, "var");
942 use_expr = build2 (MODIFY_EXPR, type, var, use_expr);
943 use_expr = force_gimple_operand_gsi (gsi, use_expr, true, NULL,
944 true, GSI_SAME_STMT);
947 replace_exp (use_p, use_expr);
953 /* Copies at the beginning of BB all the scalar computations on which
954 BB depends on in the SESE: these are all the scalar variables used
955 in BB, defined outside BB and still defined in the SESE, i.e. not a
956 parameter of the SESE. The expression that is returned contains
957 only induction variables from the generated code: MAP contains the
958 induction variables renaming mapping, and is used to translate the
959 names of induction variables. */
962 expand_scalar_variables (basic_block bb, sese region, htab_t map)
964 gimple_stmt_iterator gsi;
966 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
968 gimple stmt = gsi_stmt (gsi);
969 expand_scalar_variables_stmt (stmt, bb, region, map, &gsi);
974 /* Rename all the SSA_NAMEs from block BB according to the MAP. */
977 rename_variables (basic_block bb, htab_t map)
979 gimple_stmt_iterator gsi;
980 gimple_stmt_iterator insert_gsi = gsi_start_bb (bb);
982 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
983 rename_variables_in_stmt (gsi_stmt (gsi), map, &insert_gsi);
986 /* Remove condition from BB. */
989 remove_condition (basic_block bb)
991 gimple last = last_stmt (bb);
993 if (last && gimple_code (last) == GIMPLE_COND)
995 gimple_stmt_iterator gsi = gsi_last_bb (bb);
996 gsi_remove (&gsi, true);
1000 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
1003 get_true_edge_from_guard_bb (basic_block bb)
1008 FOR_EACH_EDGE (e, ei, bb->succs)
1009 if (e->flags & EDGE_TRUE_VALUE)
1016 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
1019 get_false_edge_from_guard_bb (basic_block bb)
1024 FOR_EACH_EDGE (e, ei, bb->succs)
1025 if (!(e->flags & EDGE_TRUE_VALUE))
1032 /* Returns true when NAME is defined in LOOP. */
1035 defined_in_loop_p (tree name, loop_p loop)
1037 gimple stmt = SSA_NAME_DEF_STMT (name);
1039 return (gimple_bb (stmt)->loop_father == loop);
1042 /* Returns the gimple statement that uses NAME outside the loop it is
1043 defined in, returns NULL if there is no such loop close phi node.
1044 An invariant of the loop closed SSA form is that the only use of a
1045 variable, outside the loop it is defined in, is in the loop close
1046 phi node that just follows the loop. */
1049 alive_after_loop (tree name)
1051 use_operand_p use_p;
1052 imm_use_iterator imm_iter;
1053 loop_p loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
1055 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
1057 gimple stmt = USE_STMT (use_p);
1059 if (gimple_code (stmt) == GIMPLE_PHI
1060 && gimple_bb (stmt)->loop_father != loop)
1067 /* Return true if a close phi has not yet been inserted for the use of
1068 variable NAME on the single exit of LOOP. */
1071 close_phi_not_yet_inserted_p (loop_p loop, tree name)
1073 gimple_stmt_iterator psi;
1074 basic_block bb = single_exit (loop)->dest;
1076 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1077 if (gimple_phi_arg_def (gsi_stmt (psi), 0) == name)
1083 /* A structure for passing parameters to add_loop_exit_phis. */
1085 typedef struct alep {
1087 VEC (rename_map_elt, heap) *new_renames;
1090 /* Helper function for htab_traverse in insert_loop_close_phis. */
1093 add_loop_exit_phis (void **slot, void *data)
1095 struct rename_map_elt_s *entry;
1098 tree expr, new_name;
1099 bool def_in_loop_p, used_outside_p, need_close_phi_p;
1100 gimple old_close_phi;
1105 entry = (struct rename_map_elt_s *) *slot;
1110 if (TREE_CODE (expr) != SSA_NAME)
1114 def_in_loop_p = defined_in_loop_p (new_name, loop);
1115 old_close_phi = alive_after_loop (entry->old_name);
1116 used_outside_p = (old_close_phi != NULL);
1117 need_close_phi_p = (def_in_loop_p && used_outside_p
1118 && close_phi_not_yet_inserted_p (loop, new_name));
1120 /* Insert a loop close phi node. */
1121 if (need_close_phi_p)
1123 basic_block bb = single_exit (loop)->dest;
1124 gimple phi = create_phi_node (new_name, bb);
1125 tree new_res = create_new_def_for (gimple_phi_result (phi), phi,
1126 gimple_phi_result_ptr (phi));
1128 add_phi_arg (phi, new_name, single_pred_edge (bb), UNKNOWN_LOCATION);
1129 VEC_safe_push (rename_map_elt, heap, a->new_renames,
1130 new_rename_map_elt (gimple_phi_result (old_close_phi),
1134 /* Remove the old rename from the map. */
1135 if (def_in_loop_p && *slot)
1144 /* Traverses MAP and removes from it all the tuples (OLD, NEW) where
1145 NEW is defined in LOOP. Inserts on the exit of LOOP the close phi
1146 node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in
1147 the original code. Inserts in MAP the tuple (OLD_RES, RES). */
1150 insert_loop_close_phis (htab_t map, loop_p loop)
1157 a.new_renames = VEC_alloc (rename_map_elt, heap, 3);
1158 update_ssa (TODO_update_ssa);
1159 htab_traverse (map, add_loop_exit_phis, &a);
1160 update_ssa (TODO_update_ssa);
1162 for (i = 0; VEC_iterate (rename_map_elt, a.new_renames, i, elt); i++)
1164 set_rename (map, elt->old_name, elt->expr);
1168 VEC_free (rename_map_elt, heap, a.new_renames);
1171 /* Helper structure for htab_traverse in insert_guard_phis. */
1175 edge true_edge, false_edge;
1176 htab_t before_guard;
1179 /* Return the default name that is before the guard. */
1182 default_before_guard (htab_t before_guard, tree old_name)
1184 tree res = get_rename (before_guard, old_name);
1186 if (res == old_name)
1188 if (is_gimple_reg (res))
1189 return fold_convert (TREE_TYPE (res), integer_zero_node);
1190 return gimple_default_def (cfun, SSA_NAME_VAR (res));
1196 /* Prepares EXPR to be a good phi argument when the phi result is
1197 RES. Insert needed statements on edge E. */
1200 convert_for_phi_arg (tree expr, tree res, edge e)
1202 tree type = TREE_TYPE (res);
1204 if (TREE_TYPE (expr) != type)
1205 expr = fold_convert (type, expr);
1207 if (TREE_CODE (expr) != SSA_NAME
1208 && !is_gimple_min_invariant (expr))
1210 tree var = create_tmp_var (type, "var");
1213 expr = build2 (MODIFY_EXPR, type, var, expr);
1214 expr = force_gimple_operand (expr, &stmts, true, NULL);
1215 gsi_insert_seq_on_edge_immediate (e, stmts);
1221 /* Helper function for htab_traverse in insert_guard_phis. */
1224 add_guard_exit_phis (void **slot, void *s)
1226 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
1227 struct igp *i = (struct igp *) s;
1228 basic_block bb = i->bb;
1229 edge true_edge = i->true_edge;
1230 edge false_edge = i->false_edge;
1231 tree res = entry->old_name;
1232 tree name1 = entry->expr;
1233 tree name2 = default_before_guard (i->before_guard, res);
1236 /* Nothing to be merged if the name before the guard is the same as
1241 name1 = convert_for_phi_arg (name1, res, true_edge);
1242 name2 = convert_for_phi_arg (name2, res, false_edge);
1244 phi = create_phi_node (res, bb);
1245 res = create_new_def_for (gimple_phi_result (phi), phi,
1246 gimple_phi_result_ptr (phi));
1248 add_phi_arg (phi, name1, true_edge, UNKNOWN_LOCATION);
1249 add_phi_arg (phi, name2, false_edge, UNKNOWN_LOCATION);
1256 /* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1).
1257 If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD,
1258 with NAME1 different than NAME2, then insert in BB the phi node:
1260 | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
1262 if there is no tuple for OLD in BEFORE_GUARD, insert
1264 | RES = phi (NAME1 (on TRUE_EDGE),
1265 | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
1267 Finally register in RENAME_MAP the tuple (OLD, RES). */
1270 insert_guard_phis (basic_block bb, edge true_edge, edge false_edge,
1271 htab_t before_guard, htab_t rename_map)
1275 i.true_edge = true_edge;
1276 i.false_edge = false_edge;
1277 i.before_guard = before_guard;
1279 update_ssa (TODO_update_ssa);
1280 htab_traverse (rename_map, add_guard_exit_phis, &i);
1281 update_ssa (TODO_update_ssa);
1284 /* Create a duplicate of the basic block BB. NOTE: This does not
1285 preserve SSA form. */
1288 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
1290 gimple_stmt_iterator gsi, gsi_tgt;
1292 gsi_tgt = gsi_start_bb (new_bb);
1293 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1295 def_operand_p def_p;
1296 ssa_op_iter op_iter;
1297 gimple stmt = gsi_stmt (gsi);
1300 if (gimple_code (stmt) == GIMPLE_LABEL)
1303 /* Create a new copy of STMT and duplicate STMT's virtual
1305 copy = gimple_copy (stmt);
1306 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
1307 mark_sym_for_renaming (gimple_vop (cfun));
1309 maybe_duplicate_eh_stmt (copy, stmt);
1310 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
1312 /* Create new names for all the definitions created by COPY and
1313 add replacement mappings for each new name. */
1314 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
1316 tree old_name = DEF_FROM_PTR (def_p);
1317 tree new_name = create_new_def_for (old_name, copy, def_p);
1318 set_rename (map, old_name, new_name);
1323 /* Copies BB and includes in the copied BB all the statements that can
1324 be reached following the use-def chains from the memory accesses,
1325 and returns the next edge following this new block. */
1328 copy_bb_and_scalar_dependences (basic_block bb, sese region,
1329 edge next_e, htab_t map)
1331 basic_block new_bb = split_edge (next_e);
1333 next_e = single_succ_edge (new_bb);
1334 graphite_copy_stmts_from_block (bb, new_bb, map);
1335 remove_condition (new_bb);
1336 remove_phi_nodes (new_bb);
1337 expand_scalar_variables (new_bb, region, map);
1338 rename_variables (new_bb, map);
1343 /* Returns the outermost loop in SCOP that contains BB. */
1346 outermost_loop_in_sese (sese region, basic_block bb)
1350 nest = bb->loop_father;
1351 while (loop_outer (nest)
1352 && loop_in_sese_p (loop_outer (nest), region))
1353 nest = loop_outer (nest);
1358 /* Sets the false region of an IF_REGION to REGION. */
1361 if_region_set_false_region (ifsese if_region, sese region)
1363 basic_block condition = if_region_get_condition_block (if_region);
1364 edge false_edge = get_false_edge_from_guard_bb (condition);
1365 basic_block dummy = false_edge->dest;
1366 edge entry_region = SESE_ENTRY (region);
1367 edge exit_region = SESE_EXIT (region);
1368 basic_block before_region = entry_region->src;
1369 basic_block last_in_region = exit_region->src;
1370 void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
1371 htab_hash_pointer (exit_region),
1374 entry_region->flags = false_edge->flags;
1375 false_edge->flags = exit_region->flags;
1377 redirect_edge_pred (entry_region, condition);
1378 redirect_edge_pred (exit_region, before_region);
1379 redirect_edge_pred (false_edge, last_in_region);
1380 redirect_edge_succ (false_edge, single_succ (dummy));
1381 delete_basic_block (dummy);
1383 exit_region->flags = EDGE_FALLTHRU;
1384 recompute_all_dominators ();
1386 SESE_EXIT (region) = false_edge;
1387 if_region->false_region = region;
1391 struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
1393 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
1394 htab_clear_slot (current_loops->exits, slot);
1396 slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
1397 htab_hash_pointer (false_edge),
1399 loop_exit->e = false_edge;
1401 false_edge->src->loop_father->exits->next = loop_exit;
1405 /* Creates an IFSESE with CONDITION on edge ENTRY. */
1408 create_if_region_on_edge (edge entry, tree condition)
1412 sese sese_region = GGC_NEW (struct sese_s);
1413 sese true_region = GGC_NEW (struct sese_s);
1414 sese false_region = GGC_NEW (struct sese_s);
1415 ifsese if_region = GGC_NEW (struct ifsese_s);
1416 edge exit = create_empty_if_region_on_edge (entry, condition);
1418 if_region->region = sese_region;
1419 if_region->region->entry = entry;
1420 if_region->region->exit = exit;
1422 FOR_EACH_EDGE (e, ei, entry->dest->succs)
1424 if (e->flags & EDGE_TRUE_VALUE)
1426 true_region->entry = e;
1427 true_region->exit = single_succ_edge (e->dest);
1428 if_region->true_region = true_region;
1430 else if (e->flags & EDGE_FALSE_VALUE)
1432 false_region->entry = e;
1433 false_region->exit = single_succ_edge (e->dest);
1434 if_region->false_region = false_region;
1441 /* Moves REGION in a condition expression:
1449 move_sese_in_condition (sese region)
1451 basic_block pred_block = split_edge (SESE_ENTRY (region));
1452 ifsese if_region = NULL;
1454 SESE_ENTRY (region) = single_succ_edge (pred_block);
1455 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
1456 if_region_set_false_region (if_region, region);
1461 /* Returns the scalar evolution of T in REGION. Every variable that
1462 is not defined in the REGION is considered a parameter. */
1465 scalar_evolution_in_region (sese region, loop_p loop, tree t)
1468 struct loop *def_loop;
1469 basic_block before = block_before_sese (region);
1471 if (TREE_CODE (t) != SSA_NAME
1472 || loop_in_sese_p (loop, region))
1473 return instantiate_scev (before, loop,
1474 analyze_scalar_evolution (loop, t));
1476 if (!defined_in_sese_p (t, region))
1479 def = SSA_NAME_DEF_STMT (t);
1480 def_loop = loop_containing_stmt (def);
1482 if (loop_in_sese_p (def_loop, region))
1484 t = analyze_scalar_evolution (def_loop, t);
1485 def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
1486 t = compute_overall_effect_of_inner_loop (def_loop, t);
1490 return instantiate_scev (before, loop, t);