1 /* Single entry single exit control flow regions.
2 Copyright (C) 2008-2014 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"
27 #include "tree-pretty-print.h"
34 #include "hard-reg-set.h"
37 #include "dominance.h"
39 #include "basic-block.h"
40 #include "tree-ssa-alias.h"
41 #include "internal-fn.h"
42 #include "gimple-fold.h"
44 #include "gimple-expr.h"
48 #include "gimple-iterator.h"
49 #include "gimplify-me.h"
50 #include "gimple-ssa.h"
52 #include "tree-phinodes.h"
53 #include "ssa-iterators.h"
54 #include "stringpool.h"
55 #include "tree-ssanames.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-into-ssa.h"
59 #include "tree-chrec.h"
60 #include "tree-data-ref.h"
61 #include "tree-scalar-evolution.h"
62 #include "tree-pass.h"
63 #include "value-prof.h"
65 #include "tree-ssa-propagate.h"
67 /* Helper function for debug_rename_map. */
70 debug_rename_map_1 (tree_node
*const &old_name
, tree_node
*const &expr
,
73 fprintf (stderr
, "(");
74 print_generic_expr (stderr
, old_name
, 0);
75 fprintf (stderr
, ", ");
76 print_generic_expr (stderr
, expr
, 0);
77 fprintf (stderr
, ")\n");
82 /* Hashtable helpers. */
84 struct rename_map_hasher
: default_hashmap_traits
86 static inline hashval_t
hash (tree
);
89 /* Computes a hash function for database element ELT. */
92 rename_map_hasher::hash (tree old_name
)
94 return SSA_NAME_VERSION (old_name
);
97 typedef hash_map
<tree
, tree
, rename_map_hasher
> rename_map_type
;
100 /* Print to stderr all the elements of RENAME_MAP. */
103 debug_rename_map (rename_map_type
*rename_map
)
105 rename_map
->traverse
<void *, debug_rename_map_1
> (NULL
);
109 /* Record LOOP as occurring in REGION. */
112 sese_record_loop (sese region
, loop_p loop
)
114 if (sese_contains_loop (region
, loop
))
117 bitmap_set_bit (SESE_LOOPS (region
), loop
->num
);
118 SESE_LOOP_NEST (region
).safe_push (loop
);
121 /* Build the loop nests contained in REGION. Returns true when the
122 operation was successful. */
125 build_sese_loop_nests (sese region
)
129 struct loop
*loop0
, *loop1
;
131 FOR_EACH_BB_FN (bb
, cfun
)
132 if (bb_in_sese_p (bb
, region
))
134 struct loop
*loop
= bb
->loop_father
;
136 /* Only add loops if they are completely contained in the SCoP. */
137 if (loop
->header
== bb
138 && bb_in_sese_p (loop
->latch
, region
))
139 sese_record_loop (region
, loop
);
142 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
143 can be the case that an inner loop is inserted before an outer
144 loop. To avoid this, semi-sort once. */
145 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop0
)
147 if (SESE_LOOP_NEST (region
).length () == i
+ 1)
150 loop1
= SESE_LOOP_NEST (region
)[i
+ 1];
151 if (loop0
->num
> loop1
->num
)
153 SESE_LOOP_NEST (region
)[i
] = loop1
;
154 SESE_LOOP_NEST (region
)[i
+ 1] = loop0
;
159 /* For a USE in BB, if BB is outside REGION, mark the USE in the
163 sese_build_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
169 if (TREE_CODE (use
) != SSA_NAME
)
172 ver
= SSA_NAME_VERSION (use
);
173 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
176 || !bb_in_sese_p (def_bb
, region
)
177 || bb_in_sese_p (bb
, region
))
180 bitmap_set_bit (liveouts
, ver
);
183 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
184 used in BB that is outside of the REGION. */
187 sese_build_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
189 gimple_stmt_iterator bsi
;
195 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
196 for (bsi
= gsi_start_phis (e
->dest
); !gsi_end_p (bsi
); gsi_next (&bsi
))
197 sese_build_liveouts_use (region
, liveouts
, bb
,
198 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi
), e
));
200 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
202 gimple stmt
= gsi_stmt (bsi
);
204 if (is_gimple_debug (stmt
))
207 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
208 sese_build_liveouts_use (region
, liveouts
, bb
, USE_FROM_PTR (use_p
));
212 /* For a USE in BB, return true if BB is outside REGION and it's not
213 in the LIVEOUTS set. */
216 sese_bad_liveouts_use (sese region
, bitmap liveouts
, basic_block bb
,
222 if (TREE_CODE (use
) != SSA_NAME
)
225 ver
= SSA_NAME_VERSION (use
);
227 /* If it's in liveouts, the variable will get a new PHI node, and
228 the debug use will be properly adjusted. */
229 if (bitmap_bit_p (liveouts
, ver
))
232 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (use
));
235 || !bb_in_sese_p (def_bb
, region
)
236 || bb_in_sese_p (bb
, region
))
242 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
243 are not marked as liveouts. */
246 sese_reset_debug_liveouts_bb (sese region
, bitmap liveouts
, basic_block bb
)
248 gimple_stmt_iterator bsi
;
252 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
254 gimple stmt
= gsi_stmt (bsi
);
256 if (!is_gimple_debug (stmt
))
259 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
260 if (sese_bad_liveouts_use (region
, liveouts
, bb
,
261 USE_FROM_PTR (use_p
)))
263 gimple_debug_bind_reset_value (stmt
);
270 /* Build the LIVEOUTS of REGION: the set of variables defined inside
271 and used outside the REGION. */
274 sese_build_liveouts (sese region
, bitmap liveouts
)
278 FOR_EACH_BB_FN (bb
, cfun
)
279 sese_build_liveouts_bb (region
, liveouts
, bb
);
280 if (MAY_HAVE_DEBUG_STMTS
)
281 FOR_EACH_BB_FN (bb
, cfun
)
282 sese_reset_debug_liveouts_bb (region
, liveouts
, bb
);
285 /* Builds a new SESE region from edges ENTRY and EXIT. */
288 new_sese (edge entry
, edge exit
)
290 sese region
= XNEW (struct sese_s
);
292 SESE_ENTRY (region
) = entry
;
293 SESE_EXIT (region
) = exit
;
294 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
295 SESE_LOOP_NEST (region
).create (3);
296 SESE_ADD_PARAMS (region
) = true;
297 SESE_PARAMS (region
).create (3);
302 /* Deletes REGION. */
305 free_sese (sese region
)
307 if (SESE_LOOPS (region
))
308 SESE_LOOPS (region
) = BITMAP_ALLOC (NULL
);
310 SESE_PARAMS (region
).release ();
311 SESE_LOOP_NEST (region
).release ();
316 /* Add exit phis for USE on EXIT. */
319 sese_add_exit_phis_edge (basic_block exit
, tree use
, edge false_e
, edge true_e
)
321 gimple phi
= create_phi_node (NULL_TREE
, exit
);
322 create_new_def_for (use
, phi
, gimple_phi_result_ptr (phi
));
323 add_phi_arg (phi
, use
, false_e
, UNKNOWN_LOCATION
);
324 add_phi_arg (phi
, use
, true_e
, UNKNOWN_LOCATION
);
327 /* Insert in the block BB phi nodes for variables defined in REGION
328 and used outside the REGION. The code generation moves REGION in
329 the else clause of an "if (1)" and generates code in the then
330 clause that is at this point empty:
339 sese_insert_phis_for_liveouts (sese region
, basic_block bb
,
340 edge false_e
, edge true_e
)
344 bitmap liveouts
= BITMAP_ALLOC (NULL
);
346 update_ssa (TODO_update_ssa
);
348 sese_build_liveouts (region
, liveouts
);
349 EXECUTE_IF_SET_IN_BITMAP (liveouts
, 0, i
, bi
)
350 sese_add_exit_phis_edge (bb
, ssa_name (i
), false_e
, true_e
);
351 BITMAP_FREE (liveouts
);
353 update_ssa (TODO_update_ssa
);
356 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
359 get_true_edge_from_guard_bb (basic_block bb
)
364 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
365 if (e
->flags
& EDGE_TRUE_VALUE
)
372 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
375 get_false_edge_from_guard_bb (basic_block bb
)
380 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
381 if (!(e
->flags
& EDGE_TRUE_VALUE
))
388 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */
391 get_rename (rename_map_type
*rename_map
, tree old_name
)
393 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
394 tree
*expr
= rename_map
->get (old_name
);
401 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
404 set_rename (rename_map_type
*rename_map
, tree old_name
, tree expr
)
406 if (old_name
== expr
)
409 rename_map
->put (old_name
, expr
);
412 /* Renames the scalar uses of the statement COPY, using the
413 substitution map RENAME_MAP, inserting the gimplification code at
414 GSI_TGT, for the translation REGION, with the original copied
415 statement in LOOP, and using the induction variable renaming map
416 IV_MAP. Returns true when something has been renamed. GLOOG_ERROR
417 is set when the code generation cannot continue. */
420 rename_uses (gimple copy
, rename_map_type
*rename_map
,
421 gimple_stmt_iterator
*gsi_tgt
,
422 sese region
, loop_p loop
, vec
<tree
> iv_map
,
427 bool changed
= false;
429 if (is_gimple_debug (copy
))
431 if (gimple_debug_bind_p (copy
))
432 gimple_debug_bind_reset_value (copy
);
433 else if (gimple_debug_source_bind_p (copy
))
441 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
443 tree old_name
= USE_FROM_PTR (use_p
);
447 if (TREE_CODE (old_name
) != SSA_NAME
448 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
452 new_expr
= get_rename (rename_map
, old_name
);
455 tree type_old_name
= TREE_TYPE (old_name
);
456 tree type_new_expr
= TREE_TYPE (new_expr
);
458 if (type_old_name
!= type_new_expr
459 || TREE_CODE (new_expr
) != SSA_NAME
)
461 tree var
= create_tmp_var (type_old_name
, "var");
463 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
464 new_expr
= fold_convert (type_old_name
, new_expr
);
466 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
467 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
470 replace_exp (use_p
, new_expr
);
474 scev
= scalar_evolution_in_region (region
, loop
, old_name
);
476 /* At this point we should know the exact scev for each
477 scalar SSA_NAME used in the scop: all the other scalar
478 SSA_NAMEs should have been translated out of SSA using
479 arrays with one element. */
480 if (chrec_contains_undetermined (scev
))
483 new_expr
= build_zero_cst (TREE_TYPE (old_name
));
486 new_expr
= chrec_apply_map (scev
, iv_map
);
488 /* The apply should produce an expression tree containing
489 the uses of the new induction variables. We should be
490 able to use new_expr instead of the old_name in the newly
491 generated loop nest. */
492 if (chrec_contains_undetermined (new_expr
)
493 || tree_contains_chrecs (new_expr
, NULL
))
496 new_expr
= build_zero_cst (TREE_TYPE (old_name
));
499 /* Replace the old_name with the new_expr. */
500 new_expr
= force_gimple_operand (unshare_expr (new_expr
), &stmts
,
503 gsi_insert_seq_before (gsi_tgt
, stmts
, GSI_SAME_STMT
);
504 replace_exp (use_p
, new_expr
);
506 if (TREE_CODE (new_expr
) == INTEGER_CST
507 && is_gimple_assign (copy
))
509 tree rhs
= gimple_assign_rhs1 (copy
);
511 if (TREE_CODE (rhs
) == ADDR_EXPR
)
512 recompute_tree_invariant_for_addr_expr (rhs
);
515 set_rename (rename_map
, old_name
, new_expr
);
521 /* Duplicates the statements of basic block BB into basic block NEW_BB
522 and compute the new induction variables according to the IV_MAP.
523 GLOOG_ERROR is set when the code generation cannot continue. */
526 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
527 rename_map_type
*rename_map
,
528 vec
<tree
> iv_map
, sese region
,
531 gimple_stmt_iterator gsi
, gsi_tgt
;
532 loop_p loop
= bb
->loop_father
;
534 gsi_tgt
= gsi_start_bb (new_bb
);
535 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
539 gimple stmt
= gsi_stmt (gsi
);
543 /* Do not copy labels or conditions. */
544 if (gimple_code (stmt
) == GIMPLE_LABEL
545 || gimple_code (stmt
) == GIMPLE_COND
)
548 /* Do not copy induction variables. */
549 if (is_gimple_assign (stmt
)
550 && (lhs
= gimple_assign_lhs (stmt
))
551 && TREE_CODE (lhs
) == SSA_NAME
552 && is_gimple_reg (lhs
)
553 && scev_analyzable_p (lhs
, region
))
556 /* Create a new copy of STMT and duplicate STMT's virtual
558 copy
= gimple_copy (stmt
);
559 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
561 maybe_duplicate_eh_stmt (copy
, stmt
);
562 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
564 /* Create new names for all the definitions created by COPY and
565 add replacement mappings for each new name. */
566 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
568 tree old_name
= DEF_FROM_PTR (def_p
);
569 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
570 set_rename (rename_map
, old_name
, new_name
);
573 if (rename_uses (copy
, rename_map
, &gsi_tgt
, region
, loop
, iv_map
,
576 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
577 fold_stmt_inplace (&gsi_tgt
);
584 /* Copies BB and includes in the copied BB all the statements that can
585 be reached following the use-def chains from the memory accesses,
586 and returns the next edge following this new block. GLOOG_ERROR is
587 set when the code generation cannot continue. */
590 copy_bb_and_scalar_dependences (basic_block bb
, sese region
,
591 edge next_e
, vec
<tree
> iv_map
,
594 basic_block new_bb
= split_edge (next_e
);
595 rename_map_type
rename_map (10);
597 next_e
= single_succ_edge (new_bb
);
598 graphite_copy_stmts_from_block (bb
, new_bb
, &rename_map
, iv_map
, region
,
600 remove_phi_nodes (new_bb
);
605 /* Returns the outermost loop in SCOP that contains BB. */
608 outermost_loop_in_sese (sese region
, basic_block bb
)
612 nest
= bb
->loop_father
;
613 while (loop_outer (nest
)
614 && loop_in_sese_p (loop_outer (nest
), region
))
615 nest
= loop_outer (nest
);
620 /* Sets the false region of an IF_REGION to REGION. */
623 if_region_set_false_region (ifsese if_region
, sese region
)
625 basic_block condition
= if_region_get_condition_block (if_region
);
626 edge false_edge
= get_false_edge_from_guard_bb (condition
);
627 basic_block dummy
= false_edge
->dest
;
628 edge entry_region
= SESE_ENTRY (region
);
629 edge exit_region
= SESE_EXIT (region
);
630 basic_block before_region
= entry_region
->src
;
631 basic_block last_in_region
= exit_region
->src
;
632 hashval_t hash
= htab_hash_pointer (exit_region
);
634 = current_loops
->exits
->find_slot_with_hash (exit_region
, hash
, NO_INSERT
);
636 entry_region
->flags
= false_edge
->flags
;
637 false_edge
->flags
= exit_region
->flags
;
639 redirect_edge_pred (entry_region
, condition
);
640 redirect_edge_pred (exit_region
, before_region
);
641 redirect_edge_pred (false_edge
, last_in_region
);
642 redirect_edge_succ (false_edge
, single_succ (dummy
));
643 delete_basic_block (dummy
);
645 exit_region
->flags
= EDGE_FALLTHRU
;
646 recompute_all_dominators ();
648 SESE_EXIT (region
) = false_edge
;
650 free (if_region
->false_region
);
651 if_region
->false_region
= region
;
655 struct loop_exit
*loop_exit
= ggc_cleared_alloc
<struct loop_exit
> ();
657 memcpy (loop_exit
, *((struct loop_exit
**) slot
), sizeof (struct loop_exit
));
658 current_loops
->exits
->clear_slot (slot
);
660 hashval_t hash
= htab_hash_pointer (false_edge
);
661 slot
= current_loops
->exits
->find_slot_with_hash (false_edge
, hash
,
663 loop_exit
->e
= false_edge
;
665 false_edge
->src
->loop_father
->exits
->next
= loop_exit
;
669 /* Creates an IFSESE with CONDITION on edge ENTRY. */
672 create_if_region_on_edge (edge entry
, tree condition
)
676 sese sese_region
= XNEW (struct sese_s
);
677 sese true_region
= XNEW (struct sese_s
);
678 sese false_region
= XNEW (struct sese_s
);
679 ifsese if_region
= XNEW (struct ifsese_s
);
680 edge exit
= create_empty_if_region_on_edge (entry
, condition
);
682 if_region
->region
= sese_region
;
683 if_region
->region
->entry
= entry
;
684 if_region
->region
->exit
= exit
;
686 FOR_EACH_EDGE (e
, ei
, entry
->dest
->succs
)
688 if (e
->flags
& EDGE_TRUE_VALUE
)
690 true_region
->entry
= e
;
691 true_region
->exit
= single_succ_edge (e
->dest
);
692 if_region
->true_region
= true_region
;
694 else if (e
->flags
& EDGE_FALSE_VALUE
)
696 false_region
->entry
= e
;
697 false_region
->exit
= single_succ_edge (e
->dest
);
698 if_region
->false_region
= false_region
;
705 /* Moves REGION in a condition expression:
713 move_sese_in_condition (sese region
)
715 basic_block pred_block
= split_edge (SESE_ENTRY (region
));
718 SESE_ENTRY (region
) = single_succ_edge (pred_block
);
719 if_region
= create_if_region_on_edge (single_pred_edge (pred_block
), integer_one_node
);
720 if_region_set_false_region (if_region
, region
);
725 /* Replaces the condition of the IF_REGION with CONDITION:
733 set_ifsese_condition (ifsese if_region
, tree condition
)
735 sese region
= if_region
->region
;
736 edge entry
= region
->entry
;
737 basic_block bb
= entry
->dest
;
738 gimple last
= last_stmt (bb
);
739 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
742 gcc_assert (gimple_code (last
) == GIMPLE_COND
);
744 gsi_remove (&gsi
, true);
745 gsi
= gsi_last_bb (bb
);
746 condition
= force_gimple_operand_gsi (&gsi
, condition
, true, NULL
,
747 false, GSI_NEW_STMT
);
748 cond_stmt
= gimple_build_cond_from_tree (condition
, NULL_TREE
, NULL_TREE
);
749 gsi
= gsi_last_bb (bb
);
750 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
753 /* Returns the scalar evolution of T in REGION. Every variable that
754 is not defined in the REGION is considered a parameter. */
757 scalar_evolution_in_region (sese region
, loop_p loop
, tree t
)
760 struct loop
*def_loop
;
761 basic_block before
= block_before_sese (region
);
763 /* SCOP parameters. */
764 if (TREE_CODE (t
) == SSA_NAME
765 && !defined_in_sese_p (t
, region
))
768 if (TREE_CODE (t
) != SSA_NAME
769 || loop_in_sese_p (loop
, region
))
770 return instantiate_scev (before
, loop
,
771 analyze_scalar_evolution (loop
, t
));
773 def
= SSA_NAME_DEF_STMT (t
);
774 def_loop
= loop_containing_stmt (def
);
776 if (loop_in_sese_p (def_loop
, region
))
778 t
= analyze_scalar_evolution (def_loop
, t
);
779 def_loop
= superloop_at_depth (def_loop
, loop_depth (loop
) + 1);
780 t
= compute_overall_effect_of_inner_loop (def_loop
, t
);
784 return instantiate_scev (before
, loop
, t
);