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 def_stmt = SSA_NAME_DEF_STMT (name);
411 basic_block def_bb = gimple_bb (def_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 (def_stmt))
424 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
426 tree arg = gimple_phi_arg_def (def_stmt, i);
427 tree res = get_vdef_before_sese (region, arg, visited);
438 /* Adjust a virtual phi node PHI that is placed at the end of the
439 generated code for SCOP:
442 | generated code from REGION;
446 The FALSE_E edge comes from the original code, TRUE_E edge comes
447 from the code generated for the SCOP. */
450 sese_adjust_vphi (sese region, gimple phi, edge true_e)
454 gcc_assert (gimple_phi_num_args (phi) == 2);
456 for (i = 0; i < gimple_phi_num_args (phi); i++)
457 if (gimple_phi_arg_edge (phi, i) == true_e)
459 tree true_arg, false_arg, before_scop_arg;
462 true_arg = gimple_phi_arg_def (phi, i);
463 if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
466 false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
467 if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
470 visited = sbitmap_alloc (last_basic_block);
471 sbitmap_zero (visited);
472 before_scop_arg = get_vdef_before_sese (region, false_arg, visited);
473 gcc_assert (before_scop_arg != NULL_TREE);
474 SET_PHI_ARG_DEF (phi, i, before_scop_arg);
475 sbitmap_free (visited);
479 /* Returns the name associated to OLD_NAME in MAP. */
482 get_rename (htab_t map, tree old_name)
484 struct rename_map_elt_s tmp;
487 tmp.old_name = old_name;
488 slot = htab_find_slot (map, &tmp, NO_INSERT);
491 return ((rename_map_elt) *slot)->expr;
496 /* Register in MAP the rename tuple (old_name, expr). */
499 set_rename (htab_t map, tree old_name, tree expr)
501 struct rename_map_elt_s tmp;
504 if (old_name == expr)
507 tmp.old_name = old_name;
508 slot = htab_find_slot (map, &tmp, INSERT);
516 *slot = new_rename_map_elt (old_name, expr);
519 /* Adjusts the phi nodes in the block BB for variables defined in
520 SCOP_REGION and used outside the SCOP_REGION. The code generation
521 moves SCOP_REGION in the else clause of an "if (1)" and generates
522 code in the then clause:
525 | generated code from REGION;
529 To adjust the phi nodes after the condition, the RENAME_MAP is
533 sese_adjust_liveout_phis (sese region, htab_t rename_map, basic_block bb,
534 edge false_e, edge true_e)
536 gimple_stmt_iterator si;
538 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
541 unsigned false_i = 0;
542 gimple phi = gsi_stmt (si);
544 if (!is_gimple_reg (PHI_RESULT (phi)))
546 sese_adjust_vphi (region, phi, true_e);
550 for (i = 0; i < gimple_phi_num_args (phi); i++)
551 if (gimple_phi_arg_edge (phi, i) == false_e)
557 for (i = 0; i < gimple_phi_num_args (phi); i++)
558 if (gimple_phi_arg_edge (phi, i) == true_e)
560 tree old_name = gimple_phi_arg_def (phi, false_i);
561 tree expr = get_rename (rename_map, old_name);
564 gcc_assert (old_name != expr);
566 if (TREE_CODE (expr) != SSA_NAME
567 && is_gimple_reg (old_name))
569 tree type = TREE_TYPE (old_name);
570 tree var = create_tmp_var (type, "var");
572 expr = build2 (MODIFY_EXPR, type, var, expr);
573 expr = force_gimple_operand (expr, &stmts, true, NULL);
574 gsi_insert_seq_on_edge_immediate (true_e, stmts);
577 SET_PHI_ARG_DEF (phi, i, expr);
582 /* Rename the SSA_NAMEs used in STMT and that appear in MAP. */
585 rename_variables_in_stmt (gimple stmt, htab_t map, gimple_stmt_iterator *insert_gsi)
590 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
592 tree use = USE_FROM_PTR (use_p);
593 tree expr = get_rename (map, use);
594 tree type_use = TREE_TYPE (use);
595 tree type_expr = TREE_TYPE (expr);
601 if (type_use != type_expr
602 || (TREE_CODE (expr) != SSA_NAME
603 && is_gimple_reg (use)))
607 if (is_gimple_debug (stmt))
609 if (gimple_debug_bind_p (stmt))
610 gimple_debug_bind_reset_value (stmt);
617 var = create_tmp_var (type_use, "var");
619 if (type_use != type_expr)
620 expr = fold_convert (type_use, expr);
622 expr = build2 (MODIFY_EXPR, type_use, var, expr);
623 expr = force_gimple_operand (expr, &stmts, true, NULL);
624 gsi_insert_seq_before (insert_gsi, stmts, GSI_SAME_STMT);
627 replace_exp (use_p, expr);
633 /* Returns true if NAME is a parameter of SESE. */
636 is_parameter (sese region, tree name)
641 for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
648 /* Returns true if NAME is an induction variable. */
653 return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
656 static void expand_scalar_variables_stmt (gimple, basic_block, sese,
657 htab_t, gimple_stmt_iterator *);
659 expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
660 sese, htab_t, gimple_stmt_iterator *);
663 expand_scalar_variables_call (gimple stmt, basic_block bb, sese region,
664 htab_t map, gimple_stmt_iterator *gsi)
666 int i, nargs = gimple_call_num_args (stmt);
667 VEC (tree, gc) *args = VEC_alloc (tree, gc, nargs);
668 tree fn_type = TREE_TYPE (gimple_call_fn (stmt));
669 tree fn = gimple_call_fndecl (stmt);
670 tree call_expr, var, lhs;
673 for (i = 0; i < nargs; i++)
675 tree arg = gimple_call_arg (stmt, i);
676 tree t = TREE_TYPE (arg);
678 var = create_tmp_var (t, "var");
679 arg = expand_scalar_variables_expr (t, arg, TREE_CODE (arg), NULL,
680 bb, region, map, gsi);
681 arg = build2 (MODIFY_EXPR, t, var, arg);
682 arg = force_gimple_operand_gsi (gsi, arg, true, NULL,
683 true, GSI_SAME_STMT);
684 VEC_quick_push (tree, args, arg);
687 lhs = gimple_call_lhs (stmt);
688 var = create_tmp_var (TREE_TYPE (lhs), "var");
689 call_expr = build_call_vec (fn_type, fn, args);
690 call = gimple_build_call_from_tree (call_expr);
691 var = make_ssa_name (var, call);
692 gimple_call_set_lhs (call, var);
693 gsi_insert_before (gsi, call, GSI_SAME_STMT);
698 /* Copies at GSI all the scalar computations on which the ssa_name OP0
699 depends on in the SESE: these are all the scalar variables used in
700 the definition of OP0, that are defined outside BB and still in the
701 SESE, i.e. not a parameter of the SESE. The expression that is
702 returned contains only induction variables from the generated code:
703 MAP contains the induction variables renaming mapping, and is used
704 to translate the names of induction variables. */
707 expand_scalar_variables_ssa_name (tree op0, basic_block bb,
708 sese region, htab_t map,
709 gimple_stmt_iterator *gsi)
714 if (is_parameter (region, op0)
716 return get_rename (map, op0);
718 def_stmt = SSA_NAME_DEF_STMT (op0);
720 /* Check whether we already have a rename for OP0. */
721 new_op = get_rename (map, op0);
724 && gimple_bb (SSA_NAME_DEF_STMT (new_op)) == bb)
727 if (gimple_bb (def_stmt) == bb)
729 /* If the defining statement is in the basic block already
730 we do not need to create a new expression for it, we
731 only need to ensure its operands are expanded. */
732 expand_scalar_variables_stmt (def_stmt, bb, region, map, gsi);
737 if (!gimple_bb (def_stmt)
738 || !bb_in_sese_p (gimple_bb (def_stmt), region))
741 switch (gimple_code (def_stmt))
745 tree var0 = gimple_assign_rhs1 (def_stmt);
746 enum tree_code subcode = gimple_assign_rhs_code (def_stmt);
747 tree var1 = gimple_assign_rhs2 (def_stmt);
748 tree type = gimple_expr_type (def_stmt);
750 return expand_scalar_variables_expr (type, var0, subcode, var1, bb,
755 return expand_scalar_variables_call (def_stmt, bb, region, map, gsi);
764 /* Copies at GSI all the scalar computations on which the expression
765 OP0 CODE OP1 depends on in the SESE: these are all the scalar
766 variables used in OP0 and OP1, defined outside BB and still defined
767 in the SESE, i.e. not a parameter of the SESE. The expression that
768 is returned contains only induction variables from the generated
769 code: MAP contains the induction variables renaming mapping, and is
770 used to translate the names of induction variables. */
773 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
774 tree op1, basic_block bb, sese region,
775 htab_t map, gimple_stmt_iterator *gsi)
777 if (TREE_CODE_CLASS (code) == tcc_constant
778 || TREE_CODE_CLASS (code) == tcc_declaration)
781 /* For data references we have to duplicate also its memory
783 if (TREE_CODE_CLASS (code) == tcc_reference)
790 tree op = TREE_OPERAND (op0, 0);
791 tree res = expand_scalar_variables_expr
792 (type, op, TREE_CODE (op), NULL, bb, region, map, gsi);
793 return build1 (code, type, res);
798 tree old_name = TREE_OPERAND (op0, 0);
799 tree expr = expand_scalar_variables_ssa_name
800 (old_name, bb, region, map, gsi);
802 if (TREE_CODE (expr) != SSA_NAME
803 && is_gimple_reg (old_name))
805 tree type = TREE_TYPE (old_name);
806 tree var = create_tmp_var (type, "var");
808 expr = build2 (MODIFY_EXPR, type, var, expr);
809 expr = force_gimple_operand_gsi (gsi, expr, true, NULL,
810 true, GSI_SAME_STMT);
813 return fold_build1 (code, type, expr);
818 tree op00 = TREE_OPERAND (op0, 0);
819 tree op01 = TREE_OPERAND (op0, 1);
820 tree op02 = TREE_OPERAND (op0, 2);
821 tree op03 = TREE_OPERAND (op0, 3);
822 tree base = expand_scalar_variables_expr
823 (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, region,
825 tree subscript = expand_scalar_variables_expr
826 (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, region,
829 return build4 (ARRAY_REF, type, base, subscript, op02, op03);
833 /* The above cases should catch everything. */
838 if (TREE_CODE_CLASS (code) == tcc_unary)
840 tree op0_type = TREE_TYPE (op0);
841 enum tree_code op0_code = TREE_CODE (op0);
842 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
843 NULL, bb, region, map, gsi);
845 return fold_build1 (code, type, op0_expr);
848 if (TREE_CODE_CLASS (code) == tcc_binary
849 || TREE_CODE_CLASS (code) == tcc_comparison)
851 tree op0_type = TREE_TYPE (op0);
852 enum tree_code op0_code = TREE_CODE (op0);
853 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
854 NULL, bb, region, map, gsi);
855 tree op1_type = TREE_TYPE (op1);
856 enum tree_code op1_code = TREE_CODE (op1);
857 tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
858 NULL, bb, region, map, gsi);
860 return fold_build2 (code, type, op0_expr, op1_expr);
863 if (code == SSA_NAME)
864 return expand_scalar_variables_ssa_name (op0, bb, region, map, gsi);
866 if (code == ADDR_EXPR)
873 /* Copies at the beginning of BB all the scalar computations on which
874 STMT depends on in the SESE: these are all the scalar variables used
875 in STMT, defined outside BB and still defined in the SESE, i.e. not a
876 parameter of the SESE. The expression that is returned contains
877 only induction variables from the generated code: MAP contains the
878 induction variables renaming mapping, and is used to translate the
879 names of induction variables. */
882 expand_scalar_variables_stmt (gimple stmt, basic_block bb, sese region,
883 htab_t map, gimple_stmt_iterator *gsi)
888 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
890 tree use = USE_FROM_PTR (use_p);
891 tree type = TREE_TYPE (use);
892 enum tree_code code = TREE_CODE (use);
895 if (!is_gimple_reg (use))
898 /* Don't expand USE if we already have a rename for it. */
899 use_expr = get_rename (map, use);
903 use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
905 use_expr = fold_convert (type, use_expr);
910 if (is_gimple_debug (stmt))
912 if (gimple_debug_bind_p (stmt))
913 gimple_debug_bind_reset_value (stmt);
920 if (TREE_CODE (use_expr) != SSA_NAME)
922 tree var = create_tmp_var (type, "var");
924 use_expr = build2 (MODIFY_EXPR, type, var, use_expr);
925 use_expr = force_gimple_operand_gsi (gsi, use_expr, true, NULL,
926 true, GSI_SAME_STMT);
929 replace_exp (use_p, use_expr);
935 /* Copies at the beginning of BB all the scalar computations on which
936 BB depends on in the SESE: these are all the scalar variables used
937 in BB, defined outside BB and still defined in the SESE, i.e. not a
938 parameter of the SESE. The expression that is returned contains
939 only induction variables from the generated code: MAP contains the
940 induction variables renaming mapping, and is used to translate the
941 names of induction variables. */
944 expand_scalar_variables (basic_block bb, sese region, htab_t map)
946 gimple_stmt_iterator gsi;
948 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
950 gimple stmt = gsi_stmt (gsi);
951 expand_scalar_variables_stmt (stmt, bb, region, map, &gsi);
956 /* Rename all the SSA_NAMEs from block BB according to the MAP. */
959 rename_variables (basic_block bb, htab_t map)
961 gimple_stmt_iterator gsi;
962 gimple_stmt_iterator insert_gsi = gsi_start_bb (bb);
964 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
965 rename_variables_in_stmt (gsi_stmt (gsi), map, &insert_gsi);
968 /* Remove condition from BB. */
971 remove_condition (basic_block bb)
973 gimple last = last_stmt (bb);
975 if (last && gimple_code (last) == GIMPLE_COND)
977 gimple_stmt_iterator gsi = gsi_last_bb (bb);
978 gsi_remove (&gsi, true);
982 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
985 get_true_edge_from_guard_bb (basic_block bb)
990 FOR_EACH_EDGE (e, ei, bb->succs)
991 if (e->flags & EDGE_TRUE_VALUE)
998 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
1001 get_false_edge_from_guard_bb (basic_block bb)
1006 FOR_EACH_EDGE (e, ei, bb->succs)
1007 if (!(e->flags & EDGE_TRUE_VALUE))
1014 /* Returns true when NAME is defined in LOOP. */
1017 defined_in_loop_p (tree name, loop_p loop)
1019 gimple stmt = SSA_NAME_DEF_STMT (name);
1021 return (gimple_bb (stmt)->loop_father == loop);
1024 /* Returns the gimple statement that uses NAME outside the loop it is
1025 defined in, returns NULL if there is no such loop close phi node.
1026 An invariant of the loop closed SSA form is that the only use of a
1027 variable, outside the loop it is defined in, is in the loop close
1028 phi node that just follows the loop. */
1031 alive_after_loop (tree name)
1033 use_operand_p use_p;
1034 imm_use_iterator imm_iter;
1035 loop_p loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
1037 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
1039 gimple stmt = USE_STMT (use_p);
1041 if (gimple_code (stmt) == GIMPLE_PHI
1042 && gimple_bb (stmt)->loop_father != loop)
1049 /* Return true if a close phi has not yet been inserted for the use of
1050 variable NAME on the single exit of LOOP. */
1053 close_phi_not_yet_inserted_p (loop_p loop, tree name)
1055 gimple_stmt_iterator psi;
1056 basic_block bb = single_exit (loop)->dest;
1058 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1059 if (gimple_phi_arg_def (gsi_stmt (psi), 0) == name)
1065 /* A structure for passing parameters to add_loop_exit_phis. */
1067 typedef struct alep {
1069 VEC (rename_map_elt, heap) *new_renames;
1072 /* Helper function for htab_traverse in insert_loop_close_phis. */
1075 add_loop_exit_phis (void **slot, void *data)
1077 struct rename_map_elt_s *entry;
1080 tree expr, new_name;
1081 bool def_in_loop_p, used_outside_p, need_close_phi_p;
1082 gimple old_close_phi;
1087 entry = (struct rename_map_elt_s *) *slot;
1092 if (TREE_CODE (expr) != SSA_NAME)
1096 def_in_loop_p = defined_in_loop_p (new_name, loop);
1097 old_close_phi = alive_after_loop (entry->old_name);
1098 used_outside_p = (old_close_phi != NULL);
1099 need_close_phi_p = (def_in_loop_p && used_outside_p
1100 && close_phi_not_yet_inserted_p (loop, new_name));
1102 /* Insert a loop close phi node. */
1103 if (need_close_phi_p)
1105 basic_block bb = single_exit (loop)->dest;
1106 gimple phi = create_phi_node (new_name, bb);
1107 tree new_res = create_new_def_for (gimple_phi_result (phi), phi,
1108 gimple_phi_result_ptr (phi));
1110 add_phi_arg (phi, new_name, single_pred_edge (bb), UNKNOWN_LOCATION);
1111 VEC_safe_push (rename_map_elt, heap, a->new_renames,
1112 new_rename_map_elt (gimple_phi_result (old_close_phi),
1116 /* Remove the old rename from the map. */
1117 if (def_in_loop_p && *slot)
1126 /* Traverses MAP and removes from it all the tuples (OLD, NEW) where
1127 NEW is defined in LOOP. Inserts on the exit of LOOP the close phi
1128 node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in
1129 the original code. Inserts in MAP the tuple (OLD_RES, RES). */
1132 insert_loop_close_phis (htab_t map, loop_p loop)
1139 a.new_renames = VEC_alloc (rename_map_elt, heap, 3);
1140 update_ssa (TODO_update_ssa);
1141 htab_traverse (map, add_loop_exit_phis, &a);
1142 update_ssa (TODO_update_ssa);
1144 for (i = 0; VEC_iterate (rename_map_elt, a.new_renames, i, elt); i++)
1146 set_rename (map, elt->old_name, elt->expr);
1150 VEC_free (rename_map_elt, heap, a.new_renames);
1153 /* Helper structure for htab_traverse in insert_guard_phis. */
1157 edge true_edge, false_edge;
1158 htab_t before_guard;
1161 /* Return the default name that is before the guard. */
1164 default_before_guard (htab_t before_guard, tree old_name)
1166 tree res = get_rename (before_guard, old_name);
1168 if (res == old_name)
1170 if (is_gimple_reg (res))
1171 return fold_convert (TREE_TYPE (res), integer_zero_node);
1172 return gimple_default_def (cfun, SSA_NAME_VAR (res));
1178 /* Prepares EXPR to be a good phi argument when the phi result is
1179 RES. Insert needed statements on edge E. */
1182 convert_for_phi_arg (tree expr, tree res, edge e)
1184 tree type = TREE_TYPE (res);
1186 if (TREE_TYPE (expr) != type)
1187 expr = fold_convert (type, expr);
1189 if (TREE_CODE (expr) != SSA_NAME
1190 && !is_gimple_min_invariant (expr))
1192 tree var = create_tmp_var (type, "var");
1195 expr = build2 (MODIFY_EXPR, type, var, expr);
1196 expr = force_gimple_operand (expr, &stmts, true, NULL);
1197 gsi_insert_seq_on_edge_immediate (e, stmts);
1203 /* Helper function for htab_traverse in insert_guard_phis. */
1206 add_guard_exit_phis (void **slot, void *s)
1208 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
1209 struct igp *i = (struct igp *) s;
1210 basic_block bb = i->bb;
1211 edge true_edge = i->true_edge;
1212 edge false_edge = i->false_edge;
1213 tree res = entry->old_name;
1214 tree name1 = entry->expr;
1215 tree name2 = default_before_guard (i->before_guard, res);
1218 /* Nothing to be merged if the name before the guard is the same as
1223 name1 = convert_for_phi_arg (name1, res, true_edge);
1224 name2 = convert_for_phi_arg (name2, res, false_edge);
1226 phi = create_phi_node (res, bb);
1227 res = create_new_def_for (gimple_phi_result (phi), phi,
1228 gimple_phi_result_ptr (phi));
1230 add_phi_arg (phi, name1, true_edge, UNKNOWN_LOCATION);
1231 add_phi_arg (phi, name2, false_edge, UNKNOWN_LOCATION);
1238 /* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1).
1239 If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD,
1240 with NAME1 different than NAME2, then insert in BB the phi node:
1242 | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
1244 if there is no tuple for OLD in BEFORE_GUARD, insert
1246 | RES = phi (NAME1 (on TRUE_EDGE),
1247 | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
1249 Finally register in RENAME_MAP the tuple (OLD, RES). */
1252 insert_guard_phis (basic_block bb, edge true_edge, edge false_edge,
1253 htab_t before_guard, htab_t rename_map)
1257 i.true_edge = true_edge;
1258 i.false_edge = false_edge;
1259 i.before_guard = before_guard;
1261 update_ssa (TODO_update_ssa);
1262 htab_traverse (rename_map, add_guard_exit_phis, &i);
1263 update_ssa (TODO_update_ssa);
1266 /* Create a duplicate of the basic block BB. NOTE: This does not
1267 preserve SSA form. */
1270 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
1272 gimple_stmt_iterator gsi, gsi_tgt;
1274 gsi_tgt = gsi_start_bb (new_bb);
1275 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1277 def_operand_p def_p;
1278 ssa_op_iter op_iter;
1279 gimple stmt = gsi_stmt (gsi);
1282 if (gimple_code (stmt) == GIMPLE_LABEL)
1285 /* Create a new copy of STMT and duplicate STMT's virtual
1287 copy = gimple_copy (stmt);
1288 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
1289 mark_sym_for_renaming (gimple_vop (cfun));
1291 maybe_duplicate_eh_stmt (copy, stmt);
1292 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
1294 /* Create new names for all the definitions created by COPY and
1295 add replacement mappings for each new name. */
1296 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
1298 tree old_name = DEF_FROM_PTR (def_p);
1299 tree new_name = create_new_def_for (old_name, copy, def_p);
1300 set_rename (map, old_name, new_name);
1305 /* Copies BB and includes in the copied BB all the statements that can
1306 be reached following the use-def chains from the memory accesses,
1307 and returns the next edge following this new block. */
1310 copy_bb_and_scalar_dependences (basic_block bb, sese region,
1311 edge next_e, htab_t map)
1313 basic_block new_bb = split_edge (next_e);
1315 next_e = single_succ_edge (new_bb);
1316 graphite_copy_stmts_from_block (bb, new_bb, map);
1317 remove_condition (new_bb);
1318 remove_phi_nodes (new_bb);
1319 expand_scalar_variables (new_bb, region, map);
1320 rename_variables (new_bb, map);
1325 /* Returns the outermost loop in SCOP that contains BB. */
1328 outermost_loop_in_sese (sese region, basic_block bb)
1332 nest = bb->loop_father;
1333 while (loop_outer (nest)
1334 && loop_in_sese_p (loop_outer (nest), region))
1335 nest = loop_outer (nest);
1340 /* Sets the false region of an IF_REGION to REGION. */
1343 if_region_set_false_region (ifsese if_region, sese region)
1345 basic_block condition = if_region_get_condition_block (if_region);
1346 edge false_edge = get_false_edge_from_guard_bb (condition);
1347 basic_block dummy = false_edge->dest;
1348 edge entry_region = SESE_ENTRY (region);
1349 edge exit_region = SESE_EXIT (region);
1350 basic_block before_region = entry_region->src;
1351 basic_block last_in_region = exit_region->src;
1352 void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
1353 htab_hash_pointer (exit_region),
1356 entry_region->flags = false_edge->flags;
1357 false_edge->flags = exit_region->flags;
1359 redirect_edge_pred (entry_region, condition);
1360 redirect_edge_pred (exit_region, before_region);
1361 redirect_edge_pred (false_edge, last_in_region);
1362 redirect_edge_succ (false_edge, single_succ (dummy));
1363 delete_basic_block (dummy);
1365 exit_region->flags = EDGE_FALLTHRU;
1366 recompute_all_dominators ();
1368 SESE_EXIT (region) = false_edge;
1369 if_region->false_region = region;
1373 struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
1375 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
1376 htab_clear_slot (current_loops->exits, slot);
1378 slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
1379 htab_hash_pointer (false_edge),
1381 loop_exit->e = false_edge;
1383 false_edge->src->loop_father->exits->next = loop_exit;
1387 /* Creates an IFSESE with CONDITION on edge ENTRY. */
1390 create_if_region_on_edge (edge entry, tree condition)
1394 sese sese_region = GGC_NEW (struct sese_s);
1395 sese true_region = GGC_NEW (struct sese_s);
1396 sese false_region = GGC_NEW (struct sese_s);
1397 ifsese if_region = GGC_NEW (struct ifsese_s);
1398 edge exit = create_empty_if_region_on_edge (entry, condition);
1400 if_region->region = sese_region;
1401 if_region->region->entry = entry;
1402 if_region->region->exit = exit;
1404 FOR_EACH_EDGE (e, ei, entry->dest->succs)
1406 if (e->flags & EDGE_TRUE_VALUE)
1408 true_region->entry = e;
1409 true_region->exit = single_succ_edge (e->dest);
1410 if_region->true_region = true_region;
1412 else if (e->flags & EDGE_FALSE_VALUE)
1414 false_region->entry = e;
1415 false_region->exit = single_succ_edge (e->dest);
1416 if_region->false_region = false_region;
1423 /* Moves REGION in a condition expression:
1431 move_sese_in_condition (sese region)
1433 basic_block pred_block = split_edge (SESE_ENTRY (region));
1434 ifsese if_region = NULL;
1436 SESE_ENTRY (region) = single_succ_edge (pred_block);
1437 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
1438 if_region_set_false_region (if_region, region);
1443 /* Reset the loop->aux pointer for all loops in REGION. */
1446 sese_reset_aux_in_loops (sese region)
1451 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1455 /* Returns the scalar evolution of T in REGION. Every variable that
1456 is not defined in the REGION is considered a parameter. */
1459 scalar_evolution_in_region (sese region, loop_p loop, tree t)
1462 struct loop *def_loop;
1463 basic_block before = block_before_sese (region);
1465 if (TREE_CODE (t) != SSA_NAME
1466 || loop_in_sese_p (loop, region))
1467 return instantiate_scev (before, loop,
1468 analyze_scalar_evolution (loop, t));
1470 if (!defined_in_sese_p (t, region))
1473 def = SSA_NAME_DEF_STMT (t);
1474 def_loop = loop_containing_stmt (def);
1476 if (loop_in_sese_p (def_loop, region))
1478 t = analyze_scalar_evolution (def_loop, t);
1479 def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
1480 t = compute_overall_effect_of_inner_loop (def_loop, t);
1484 return instantiate_scev (before, loop, t);