1 /* Control flow functions for trees.
2 Copyright (C) 2001-2014 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
24 #include "hash-table.h"
27 #include "trans-mem.h"
28 #include "stor-layout.h"
29 #include "print-tree.h"
31 #include "basic-block.h"
34 #include "gimple-pretty-print.h"
35 #include "pointer-set.h"
36 #include "tree-ssa-alias.h"
37 #include "internal-fn.h"
38 #include "gimple-fold.h"
40 #include "gimple-expr.h"
43 #include "gimple-iterator.h"
44 #include "gimplify-me.h"
45 #include "gimple-walk.h"
46 #include "gimple-ssa.h"
49 #include "tree-phinodes.h"
50 #include "ssa-iterators.h"
51 #include "stringpool.h"
52 #include "tree-ssanames.h"
53 #include "tree-ssa-loop-manip.h"
54 #include "tree-ssa-loop-niter.h"
55 #include "tree-into-ssa.h"
59 #include "tree-dump.h"
60 #include "tree-pass.h"
61 #include "diagnostic-core.h"
64 #include "tree-ssa-propagate.h"
65 #include "value-prof.h"
66 #include "tree-inline.h"
68 #include "tree-ssa-live.h"
70 #include "tree-cfgcleanup.h"
72 /* This file contains functions for building the Control Flow Graph (CFG)
73 for a function tree. */
75 /* Local declarations. */
77 /* Initial capacity for the basic block array. */
78 static const int initial_cfg_capacity = 20;
80 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
81 which use a particular edge. The CASE_LABEL_EXPRs are chained together
82 via their CASE_CHAIN field, which we clear after we're done with the
83 hash table to prevent problems with duplication of GIMPLE_SWITCHes.
85 Access to this list of CASE_LABEL_EXPRs allows us to efficiently
86 update the case vector in response to edge redirections.
88 Right now this table is set up and torn down at key points in the
89 compilation process. It would be nice if we could make the table
90 more persistent. The key is getting notification of changes to
91 the CFG (particularly edge removal, creation and redirection). */
93 static struct pointer_map_t *edge_to_cases;
95 /* If we record edge_to_cases, this bitmap will hold indexes
96 of basic blocks that end in a GIMPLE_SWITCH which we touched
97 due to edge manipulations. */
99 static bitmap touched_switch_bbs;
101 /* CFG statistics. */
104 long num_merged_labels;
107 static struct cfg_stats_d cfg_stats;
109 /* Hash table to store last discriminator assigned for each locus. */
110 struct locus_discrim_map
116 /* Hashtable helpers. */
118 struct locus_discrim_hasher : typed_free_remove <locus_discrim_map>
120 typedef locus_discrim_map value_type;
121 typedef locus_discrim_map compare_type;
122 static inline hashval_t hash (const value_type *);
123 static inline bool equal (const value_type *, const compare_type *);
126 /* Trivial hash function for a location_t. ITEM is a pointer to
127 a hash table entry that maps a location_t to a discriminator. */
130 locus_discrim_hasher::hash (const value_type *item)
132 return LOCATION_LINE (item->locus);
135 /* Equality function for the locus-to-discriminator map. A and B
136 point to the two hash table entries to compare. */
139 locus_discrim_hasher::equal (const value_type *a, const compare_type *b)
141 return LOCATION_LINE (a->locus) == LOCATION_LINE (b->locus);
144 static hash_table <locus_discrim_hasher> discriminator_per_locus;
146 /* Basic blocks and flowgraphs. */
147 static void make_blocks (gimple_seq);
150 static void make_edges (void);
151 static void assign_discriminators (void);
152 static void make_cond_expr_edges (basic_block);
153 static void make_gimple_switch_edges (basic_block);
154 static bool make_goto_expr_edges (basic_block);
155 static void make_gimple_asm_edges (basic_block);
156 static edge gimple_redirect_edge_and_branch (edge, basic_block);
157 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block);
159 /* Various helpers. */
160 static inline bool stmt_starts_bb_p (gimple, gimple);
161 static int gimple_verify_flow_info (void);
162 static void gimple_make_forwarder_block (edge);
163 static gimple first_non_label_stmt (basic_block);
164 static bool verify_gimple_transaction (gimple);
166 /* Flowgraph optimization and cleanup. */
167 static void gimple_merge_blocks (basic_block, basic_block);
168 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
169 static void remove_bb (basic_block);
170 static edge find_taken_edge_computed_goto (basic_block, tree);
171 static edge find_taken_edge_cond_expr (basic_block, tree);
172 static edge find_taken_edge_switch_expr (basic_block, tree);
173 static tree find_case_label_for_value (gimple, tree);
176 init_empty_tree_cfg_for_function (struct function *fn)
178 /* Initialize the basic block array. */
180 profile_status_for_fn (fn) = PROFILE_ABSENT;
181 n_basic_blocks_for_fn (fn) = NUM_FIXED_BLOCKS;
182 last_basic_block_for_fn (fn) = NUM_FIXED_BLOCKS;
183 vec_alloc (basic_block_info_for_fn (fn), initial_cfg_capacity);
184 vec_safe_grow_cleared (basic_block_info_for_fn (fn),
185 initial_cfg_capacity);
187 /* Build a mapping of labels to their associated blocks. */
188 vec_alloc (label_to_block_map_for_fn (fn), initial_cfg_capacity);
189 vec_safe_grow_cleared (label_to_block_map_for_fn (fn),
190 initial_cfg_capacity);
192 SET_BASIC_BLOCK_FOR_FN (fn, ENTRY_BLOCK, ENTRY_BLOCK_PTR_FOR_FN (fn));
193 SET_BASIC_BLOCK_FOR_FN (fn, EXIT_BLOCK, EXIT_BLOCK_PTR_FOR_FN (fn));
195 ENTRY_BLOCK_PTR_FOR_FN (fn)->next_bb
196 = EXIT_BLOCK_PTR_FOR_FN (fn);
197 EXIT_BLOCK_PTR_FOR_FN (fn)->prev_bb
198 = ENTRY_BLOCK_PTR_FOR_FN (fn);
202 init_empty_tree_cfg (void)
204 init_empty_tree_cfg_for_function (cfun);
207 /*---------------------------------------------------------------------------
209 ---------------------------------------------------------------------------*/
211 /* Entry point to the CFG builder for trees. SEQ is the sequence of
212 statements to be added to the flowgraph. */
215 build_gimple_cfg (gimple_seq seq)
217 /* Register specific gimple functions. */
218 gimple_register_cfg_hooks ();
220 memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
222 init_empty_tree_cfg ();
226 /* Make sure there is always at least one block, even if it's empty. */
227 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
228 create_empty_bb (ENTRY_BLOCK_PTR_FOR_FN (cfun));
230 /* Adjust the size of the array. */
231 if (basic_block_info_for_fn (cfun)->length ()
232 < (size_t) n_basic_blocks_for_fn (cfun))
233 vec_safe_grow_cleared (basic_block_info_for_fn (cfun),
234 n_basic_blocks_for_fn (cfun));
236 /* To speed up statement iterator walks, we first purge dead labels. */
237 cleanup_dead_labels ();
239 /* Group case nodes to reduce the number of edges.
240 We do this after cleaning up dead labels because otherwise we miss
241 a lot of obvious case merging opportunities. */
242 group_case_labels ();
244 /* Create the edges of the flowgraph. */
245 discriminator_per_locus.create (13);
247 assign_discriminators ();
248 cleanup_dead_labels ();
249 discriminator_per_locus.dispose ();
253 /* Look for ANNOTATE calls with loop annotation kind; if found, remove
254 them and propagate the information to the loop. We assume that the
255 annotations come immediately before the condition of the loop. */
258 replace_loop_annotate ()
262 gimple_stmt_iterator gsi;
265 FOR_EACH_LOOP (loop, 0)
267 gsi = gsi_last_bb (loop->header);
268 stmt = gsi_stmt (gsi);
269 if (!(stmt && gimple_code (stmt) == GIMPLE_COND))
271 for (gsi_prev_nondebug (&gsi); !gsi_end_p (gsi); gsi_prev (&gsi))
273 stmt = gsi_stmt (gsi);
274 if (gimple_code (stmt) != GIMPLE_CALL)
276 if (!gimple_call_internal_p (stmt)
277 || gimple_call_internal_fn (stmt) != IFN_ANNOTATE)
279 switch ((annot_expr_kind) tree_to_shwi (gimple_call_arg (stmt, 1)))
281 case annot_expr_ivdep_kind:
282 loop->safelen = INT_MAX;
284 case annot_expr_no_vector_kind:
285 loop->dont_vectorize = true;
287 case annot_expr_vector_kind:
288 loop->force_vectorize = true;
289 cfun->has_force_vectorize_loops = true;
294 stmt = gimple_build_assign (gimple_call_lhs (stmt),
295 gimple_call_arg (stmt, 0));
296 gsi_replace (&gsi, stmt, true);
300 /* Remove IFN_ANNOTATE. Safeguard for the case loop->latch == NULL. */
301 FOR_EACH_BB_FN (bb, cfun)
303 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
305 stmt = gsi_stmt (gsi);
306 if (gimple_code (stmt) != GIMPLE_CALL)
308 if (!gimple_call_internal_p (stmt)
309 || gimple_call_internal_fn (stmt) != IFN_ANNOTATE)
311 switch ((annot_expr_kind) tree_to_shwi (gimple_call_arg (stmt, 1)))
313 case annot_expr_ivdep_kind:
314 case annot_expr_no_vector_kind:
315 case annot_expr_vector_kind:
320 warning_at (gimple_location (stmt), 0, "ignoring loop annotation");
321 stmt = gimple_build_assign (gimple_call_lhs (stmt),
322 gimple_call_arg (stmt, 0));
323 gsi_replace (&gsi, stmt, true);
330 execute_build_cfg (void)
332 gimple_seq body = gimple_body (current_function_decl);
334 build_gimple_cfg (body);
335 gimple_set_body (current_function_decl, NULL);
336 if (dump_file && (dump_flags & TDF_DETAILS))
338 fprintf (dump_file, "Scope blocks:\n");
339 dump_scope_blocks (dump_file, dump_flags);
342 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
343 replace_loop_annotate ();
349 const pass_data pass_data_build_cfg =
351 GIMPLE_PASS, /* type */
353 OPTGROUP_NONE, /* optinfo_flags */
354 true, /* has_execute */
355 TV_TREE_CFG, /* tv_id */
356 PROP_gimple_leh, /* properties_required */
357 ( PROP_cfg | PROP_loops ), /* properties_provided */
358 0, /* properties_destroyed */
359 0, /* todo_flags_start */
360 TODO_verify_stmts, /* todo_flags_finish */
363 class pass_build_cfg : public gimple_opt_pass
366 pass_build_cfg (gcc::context *ctxt)
367 : gimple_opt_pass (pass_data_build_cfg, ctxt)
370 /* opt_pass methods: */
371 virtual unsigned int execute (function *) { return execute_build_cfg (); }
373 }; // class pass_build_cfg
378 make_pass_build_cfg (gcc::context *ctxt)
380 return new pass_build_cfg (ctxt);
384 /* Return true if T is a computed goto. */
387 computed_goto_p (gimple t)
389 return (gimple_code (t) == GIMPLE_GOTO
390 && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
393 /* Returns true for edge E where e->src ends with a GIMPLE_COND and
394 the other edge points to a bb with just __builtin_unreachable ().
395 I.e. return true for C->M edge in:
403 __builtin_unreachable ();
407 assert_unreachable_fallthru_edge_p (edge e)
409 basic_block pred_bb = e->src;
410 gimple last = last_stmt (pred_bb);
411 if (last && gimple_code (last) == GIMPLE_COND)
413 basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest;
414 if (other_bb == e->dest)
415 other_bb = EDGE_SUCC (pred_bb, 1)->dest;
416 if (EDGE_COUNT (other_bb->succs) == 0)
418 gimple_stmt_iterator gsi = gsi_after_labels (other_bb);
423 stmt = gsi_stmt (gsi);
424 while (is_gimple_debug (stmt) || gimple_clobber_p (stmt))
429 stmt = gsi_stmt (gsi);
431 return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE);
438 /* Build a flowgraph for the sequence of stmts SEQ. */
441 make_blocks (gimple_seq seq)
443 gimple_stmt_iterator i = gsi_start (seq);
445 bool start_new_block = true;
446 bool first_stmt_of_seq = true;
447 basic_block bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
449 while (!gsi_end_p (i))
456 /* If the statement starts a new basic block or if we have determined
457 in a previous pass that we need to create a new block for STMT, do
459 if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
461 if (!first_stmt_of_seq)
462 gsi_split_seq_before (&i, &seq);
463 bb = create_basic_block (seq, NULL, bb);
464 start_new_block = false;
467 /* Now add STMT to BB and create the subgraphs for special statement
469 gimple_set_bb (stmt, bb);
471 /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
473 if (stmt_ends_bb_p (stmt))
475 /* If the stmt can make abnormal goto use a new temporary
476 for the assignment to the LHS. This makes sure the old value
477 of the LHS is available on the abnormal edge. Otherwise
478 we will end up with overlapping life-ranges for abnormal
480 if (gimple_has_lhs (stmt)
481 && stmt_can_make_abnormal_goto (stmt)
482 && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt))))
484 tree lhs = gimple_get_lhs (stmt);
485 tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
486 gimple s = gimple_build_assign (lhs, tmp);
487 gimple_set_location (s, gimple_location (stmt));
488 gimple_set_block (s, gimple_block (stmt));
489 gimple_set_lhs (stmt, tmp);
490 if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE
491 || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE)
492 DECL_GIMPLE_REG_P (tmp) = 1;
493 gsi_insert_after (&i, s, GSI_SAME_STMT);
495 start_new_block = true;
499 first_stmt_of_seq = false;
504 /* Create and return a new empty basic block after bb AFTER. */
507 create_bb (void *h, void *e, basic_block after)
513 /* Create and initialize a new basic block. Since alloc_block uses
514 GC allocation that clears memory to allocate a basic block, we do
515 not have to clear the newly allocated basic block here. */
518 bb->index = last_basic_block_for_fn (cfun);
520 set_bb_seq (bb, h ? (gimple_seq) h : NULL);
522 /* Add the new block to the linked list of blocks. */
523 link_block (bb, after);
525 /* Grow the basic block array if needed. */
526 if ((size_t) last_basic_block_for_fn (cfun)
527 == basic_block_info_for_fn (cfun)->length ())
530 (last_basic_block_for_fn (cfun)
531 + (last_basic_block_for_fn (cfun) + 3) / 4);
532 vec_safe_grow_cleared (basic_block_info_for_fn (cfun), new_size);
535 /* Add the newly created block to the array. */
536 SET_BASIC_BLOCK_FOR_FN (cfun, last_basic_block_for_fn (cfun), bb);
538 n_basic_blocks_for_fn (cfun)++;
539 last_basic_block_for_fn (cfun)++;
545 /*---------------------------------------------------------------------------
547 ---------------------------------------------------------------------------*/
549 /* Fold COND_EXPR_COND of each COND_EXPR. */
552 fold_cond_expr_cond (void)
556 FOR_EACH_BB_FN (bb, cfun)
558 gimple stmt = last_stmt (bb);
560 if (stmt && gimple_code (stmt) == GIMPLE_COND)
562 location_t loc = gimple_location (stmt);
566 fold_defer_overflow_warnings ();
567 cond = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node,
568 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
571 zerop = integer_zerop (cond);
572 onep = integer_onep (cond);
575 zerop = onep = false;
577 fold_undefer_overflow_warnings (zerop || onep,
579 WARN_STRICT_OVERFLOW_CONDITIONAL);
581 gimple_cond_make_false (stmt);
583 gimple_cond_make_true (stmt);
588 /* If basic block BB has an abnormal edge to a basic block
589 containing IFN_ABNORMAL_DISPATCHER internal call, return
590 that the dispatcher's basic block, otherwise return NULL. */
593 get_abnormal_succ_dispatcher (basic_block bb)
598 FOR_EACH_EDGE (e, ei, bb->succs)
599 if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) == EDGE_ABNORMAL)
601 gimple_stmt_iterator gsi
602 = gsi_start_nondebug_after_labels_bb (e->dest);
603 gimple g = gsi_stmt (gsi);
605 && is_gimple_call (g)
606 && gimple_call_internal_p (g)
607 && gimple_call_internal_fn (g) == IFN_ABNORMAL_DISPATCHER)
613 /* Helper function for make_edges. Create a basic block with
614 with ABNORMAL_DISPATCHER internal call in it if needed, and
615 create abnormal edges from BBS to it and from it to FOR_BB
616 if COMPUTED_GOTO is false, otherwise factor the computed gotos. */
619 handle_abnormal_edges (basic_block *dispatcher_bbs,
620 basic_block for_bb, int *bb_to_omp_idx,
621 auto_vec<basic_block> *bbs, bool computed_goto)
623 basic_block *dispatcher = dispatcher_bbs + (computed_goto ? 1 : 0);
624 unsigned int idx = 0;
630 dispatcher = dispatcher_bbs + 2 * bb_to_omp_idx[for_bb->index];
631 if (bb_to_omp_idx[for_bb->index] != 0)
635 /* If the dispatcher has been created already, then there are basic
636 blocks with abnormal edges to it, so just make a new edge to
638 if (*dispatcher == NULL)
640 /* Check if there are any basic blocks that need to have
641 abnormal edges to this dispatcher. If there are none, return
643 if (bb_to_omp_idx == NULL)
645 if (bbs->is_empty ())
650 FOR_EACH_VEC_ELT (*bbs, idx, bb)
651 if (bb_to_omp_idx[bb->index] == bb_to_omp_idx[for_bb->index])
657 /* Create the dispatcher bb. */
658 *dispatcher = create_basic_block (NULL, NULL, for_bb);
661 /* Factor computed gotos into a common computed goto site. Also
662 record the location of that site so that we can un-factor the
663 gotos after we have converted back to normal form. */
664 gimple_stmt_iterator gsi = gsi_start_bb (*dispatcher);
666 /* Create the destination of the factored goto. Each original
667 computed goto will put its desired destination into this
668 variable and jump to the label we create immediately below. */
669 tree var = create_tmp_var (ptr_type_node, "gotovar");
671 /* Build a label for the new block which will contain the
672 factored computed goto. */
673 tree factored_label_decl
674 = create_artificial_label (UNKNOWN_LOCATION);
675 gimple factored_computed_goto_label
676 = gimple_build_label (factored_label_decl);
677 gsi_insert_after (&gsi, factored_computed_goto_label, GSI_NEW_STMT);
679 /* Build our new computed goto. */
680 gimple factored_computed_goto = gimple_build_goto (var);
681 gsi_insert_after (&gsi, factored_computed_goto, GSI_NEW_STMT);
683 FOR_EACH_VEC_ELT (*bbs, idx, bb)
686 && bb_to_omp_idx[bb->index] != bb_to_omp_idx[for_bb->index])
689 gsi = gsi_last_bb (bb);
690 gimple last = gsi_stmt (gsi);
692 gcc_assert (computed_goto_p (last));
694 /* Copy the original computed goto's destination into VAR. */
696 = gimple_build_assign (var, gimple_goto_dest (last));
697 gsi_insert_before (&gsi, assignment, GSI_SAME_STMT);
699 edge e = make_edge (bb, *dispatcher, EDGE_FALLTHRU);
700 e->goto_locus = gimple_location (last);
701 gsi_remove (&gsi, true);
706 tree arg = inner ? boolean_true_node : boolean_false_node;
707 gimple g = gimple_build_call_internal (IFN_ABNORMAL_DISPATCHER,
709 gimple_stmt_iterator gsi = gsi_after_labels (*dispatcher);
710 gsi_insert_after (&gsi, g, GSI_NEW_STMT);
712 /* Create predecessor edges of the dispatcher. */
713 FOR_EACH_VEC_ELT (*bbs, idx, bb)
716 && bb_to_omp_idx[bb->index] != bb_to_omp_idx[for_bb->index])
718 make_edge (bb, *dispatcher, EDGE_ABNORMAL);
723 make_edge (*dispatcher, for_bb, EDGE_ABNORMAL);
726 /* Join all the blocks in the flowgraph. */
732 struct omp_region *cur_region = NULL;
733 auto_vec<basic_block> ab_edge_goto;
734 auto_vec<basic_block> ab_edge_call;
735 int *bb_to_omp_idx = NULL;
736 int cur_omp_region_idx = 0;
738 /* Create an edge from entry to the first block with executable
740 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun),
741 BASIC_BLOCK_FOR_FN (cfun, NUM_FIXED_BLOCKS),
744 /* Traverse the basic block array placing edges. */
745 FOR_EACH_BB_FN (bb, cfun)
747 gimple last = last_stmt (bb);
751 bb_to_omp_idx[bb->index] = cur_omp_region_idx;
755 enum gimple_code code = gimple_code (last);
759 if (make_goto_expr_edges (bb))
760 ab_edge_goto.safe_push (bb);
764 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
768 make_cond_expr_edges (bb);
772 make_gimple_switch_edges (bb);
776 make_eh_edges (last);
779 case GIMPLE_EH_DISPATCH:
780 fallthru = make_eh_dispatch_edges (last);
784 /* If this function receives a nonlocal goto, then we need to
785 make edges from this call site to all the nonlocal goto
787 if (stmt_can_make_abnormal_goto (last))
788 ab_edge_call.safe_push (bb);
790 /* If this statement has reachable exception handlers, then
791 create abnormal edges to them. */
792 make_eh_edges (last);
794 /* BUILTIN_RETURN is really a return statement. */
795 if (gimple_call_builtin_p (last, BUILT_IN_RETURN))
797 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
800 /* Some calls are known not to return. */
802 fallthru = !(gimple_call_flags (last) & ECF_NORETURN);
806 /* A GIMPLE_ASSIGN may throw internally and thus be considered
808 if (is_ctrl_altering_stmt (last))
809 make_eh_edges (last);
814 make_gimple_asm_edges (bb);
819 fallthru = make_gimple_omp_edges (bb, &cur_region,
820 &cur_omp_region_idx);
821 if (cur_region && bb_to_omp_idx == NULL)
822 bb_to_omp_idx = XCNEWVEC (int, n_basic_blocks_for_fn (cfun));
825 case GIMPLE_TRANSACTION:
827 tree abort_label = gimple_transaction_label (last);
829 make_edge (bb, label_to_block (abort_label), EDGE_TM_ABORT);
835 gcc_assert (!stmt_ends_bb_p (last));
843 make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
846 /* Computed gotos are hell to deal with, especially if there are
847 lots of them with a large number of destinations. So we factor
848 them to a common computed goto location before we build the
849 edge list. After we convert back to normal form, we will un-factor
850 the computed gotos since factoring introduces an unwanted jump.
851 For non-local gotos and abnormal edges from calls to calls that return
852 twice or forced labels, factor the abnormal edges too, by having all
853 abnormal edges from the calls go to a common artificial basic block
854 with ABNORMAL_DISPATCHER internal call and abnormal edges from that
855 basic block to all forced labels and calls returning twice.
856 We do this per-OpenMP structured block, because those regions
857 are guaranteed to be single entry single exit by the standard,
858 so it is not allowed to enter or exit such regions abnormally this way,
859 thus all computed gotos, non-local gotos and setjmp/longjmp calls
860 must not transfer control across SESE region boundaries. */
861 if (!ab_edge_goto.is_empty () || !ab_edge_call.is_empty ())
863 gimple_stmt_iterator gsi;
864 basic_block dispatcher_bb_array[2] = { NULL, NULL };
865 basic_block *dispatcher_bbs = dispatcher_bb_array;
866 int count = n_basic_blocks_for_fn (cfun);
869 dispatcher_bbs = XCNEWVEC (basic_block, 2 * count);
871 FOR_EACH_BB_FN (bb, cfun)
873 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
875 gimple label_stmt = gsi_stmt (gsi);
878 if (gimple_code (label_stmt) != GIMPLE_LABEL)
881 target = gimple_label_label (label_stmt);
883 /* Make an edge to every label block that has been marked as a
884 potential target for a computed goto or a non-local goto. */
885 if (FORCED_LABEL (target))
886 handle_abnormal_edges (dispatcher_bbs, bb, bb_to_omp_idx,
887 &ab_edge_goto, true);
888 if (DECL_NONLOCAL (target))
890 handle_abnormal_edges (dispatcher_bbs, bb, bb_to_omp_idx,
891 &ab_edge_call, false);
896 if (!gsi_end_p (gsi) && is_gimple_debug (gsi_stmt (gsi)))
897 gsi_next_nondebug (&gsi);
898 if (!gsi_end_p (gsi))
900 /* Make an edge to every setjmp-like call. */
901 gimple call_stmt = gsi_stmt (gsi);
902 if (is_gimple_call (call_stmt)
903 && ((gimple_call_flags (call_stmt) & ECF_RETURNS_TWICE)
904 || gimple_call_builtin_p (call_stmt,
905 BUILT_IN_SETJMP_RECEIVER)))
906 handle_abnormal_edges (dispatcher_bbs, bb, bb_to_omp_idx,
907 &ab_edge_call, false);
912 XDELETE (dispatcher_bbs);
915 XDELETE (bb_to_omp_idx);
919 /* Fold COND_EXPR_COND of each COND_EXPR. */
920 fold_cond_expr_cond ();
923 /* Find the next available discriminator value for LOCUS. The
924 discriminator distinguishes among several basic blocks that
925 share a common locus, allowing for more accurate sample-based
929 next_discriminator_for_locus (location_t locus)
931 struct locus_discrim_map item;
932 struct locus_discrim_map **slot;
935 item.discriminator = 0;
936 slot = discriminator_per_locus.find_slot_with_hash (
937 &item, LOCATION_LINE (locus), INSERT);
939 if (*slot == HTAB_EMPTY_ENTRY)
941 *slot = XNEW (struct locus_discrim_map);
943 (*slot)->locus = locus;
944 (*slot)->discriminator = 0;
946 (*slot)->discriminator++;
947 return (*slot)->discriminator;
950 /* Return TRUE if LOCUS1 and LOCUS2 refer to the same source line. */
953 same_line_p (location_t locus1, location_t locus2)
955 expanded_location from, to;
957 if (locus1 == locus2)
960 from = expand_location (locus1);
961 to = expand_location (locus2);
963 if (from.line != to.line)
965 if (from.file == to.file)
967 return (from.file != NULL
969 && filename_cmp (from.file, to.file) == 0);
972 /* Assign discriminators to each basic block. */
975 assign_discriminators (void)
979 FOR_EACH_BB_FN (bb, cfun)
983 gimple last = last_stmt (bb);
984 location_t locus = last ? gimple_location (last) : UNKNOWN_LOCATION;
986 if (locus == UNKNOWN_LOCATION)
989 FOR_EACH_EDGE (e, ei, bb->succs)
991 gimple first = first_non_label_stmt (e->dest);
992 gimple last = last_stmt (e->dest);
993 if ((first && same_line_p (locus, gimple_location (first)))
994 || (last && same_line_p (locus, gimple_location (last))))
996 if (e->dest->discriminator != 0 && bb->discriminator == 0)
997 bb->discriminator = next_discriminator_for_locus (locus);
999 e->dest->discriminator = next_discriminator_for_locus (locus);
1005 /* Create the edges for a GIMPLE_COND starting at block BB. */
1008 make_cond_expr_edges (basic_block bb)
1010 gimple entry = last_stmt (bb);
1011 gimple then_stmt, else_stmt;
1012 basic_block then_bb, else_bb;
1013 tree then_label, else_label;
1017 gcc_assert (gimple_code (entry) == GIMPLE_COND);
1019 /* Entry basic blocks for each component. */
1020 then_label = gimple_cond_true_label (entry);
1021 else_label = gimple_cond_false_label (entry);
1022 then_bb = label_to_block (then_label);
1023 else_bb = label_to_block (else_label);
1024 then_stmt = first_stmt (then_bb);
1025 else_stmt = first_stmt (else_bb);
1027 e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
1028 e->goto_locus = gimple_location (then_stmt);
1029 e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
1031 e->goto_locus = gimple_location (else_stmt);
1033 /* We do not need the labels anymore. */
1034 gimple_cond_set_true_label (entry, NULL_TREE);
1035 gimple_cond_set_false_label (entry, NULL_TREE);
1039 /* Called for each element in the hash table (P) as we delete the
1040 edge to cases hash table.
1042 Clear all the TREE_CHAINs to prevent problems with copying of
1043 SWITCH_EXPRs and structure sharing rules, then free the hash table
1047 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
1048 void *data ATTRIBUTE_UNUSED)
1052 for (t = (tree) *value; t; t = next)
1054 next = CASE_CHAIN (t);
1055 CASE_CHAIN (t) = NULL;
1062 /* Start recording information mapping edges to case labels. */
1065 start_recording_case_labels (void)
1067 gcc_assert (edge_to_cases == NULL);
1068 edge_to_cases = pointer_map_create ();
1069 touched_switch_bbs = BITMAP_ALLOC (NULL);
1072 /* Return nonzero if we are recording information for case labels. */
1075 recording_case_labels_p (void)
1077 return (edge_to_cases != NULL);
1080 /* Stop recording information mapping edges to case labels and
1081 remove any information we have recorded. */
1083 end_recording_case_labels (void)
1087 pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
1088 pointer_map_destroy (edge_to_cases);
1089 edge_to_cases = NULL;
1090 EXECUTE_IF_SET_IN_BITMAP (touched_switch_bbs, 0, i, bi)
1092 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1095 gimple stmt = last_stmt (bb);
1096 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1097 group_case_labels_stmt (stmt);
1100 BITMAP_FREE (touched_switch_bbs);
1103 /* If we are inside a {start,end}_recording_cases block, then return
1104 a chain of CASE_LABEL_EXPRs from T which reference E.
1106 Otherwise return NULL. */
1109 get_cases_for_edge (edge e, gimple t)
1114 /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
1115 chains available. Return NULL so the caller can detect this case. */
1116 if (!recording_case_labels_p ())
1119 slot = pointer_map_contains (edge_to_cases, e);
1121 return (tree) *slot;
1123 /* If we did not find E in the hash table, then this must be the first
1124 time we have been queried for information about E & T. Add all the
1125 elements from T to the hash table then perform the query again. */
1127 n = gimple_switch_num_labels (t);
1128 for (i = 0; i < n; i++)
1130 tree elt = gimple_switch_label (t, i);
1131 tree lab = CASE_LABEL (elt);
1132 basic_block label_bb = label_to_block (lab);
1133 edge this_edge = find_edge (e->src, label_bb);
1135 /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
1137 slot = pointer_map_insert (edge_to_cases, this_edge);
1138 CASE_CHAIN (elt) = (tree) *slot;
1142 return (tree) *pointer_map_contains (edge_to_cases, e);
1145 /* Create the edges for a GIMPLE_SWITCH starting at block BB. */
1148 make_gimple_switch_edges (basic_block bb)
1150 gimple entry = last_stmt (bb);
1153 n = gimple_switch_num_labels (entry);
1155 for (i = 0; i < n; ++i)
1157 tree lab = CASE_LABEL (gimple_switch_label (entry, i));
1158 basic_block label_bb = label_to_block (lab);
1159 make_edge (bb, label_bb, 0);
1164 /* Return the basic block holding label DEST. */
1167 label_to_block_fn (struct function *ifun, tree dest)
1169 int uid = LABEL_DECL_UID (dest);
1171 /* We would die hard when faced by an undefined label. Emit a label to
1172 the very first basic block. This will hopefully make even the dataflow
1173 and undefined variable warnings quite right. */
1174 if (seen_error () && uid < 0)
1176 gimple_stmt_iterator gsi =
1177 gsi_start_bb (BASIC_BLOCK_FOR_FN (cfun, NUM_FIXED_BLOCKS));
1180 stmt = gimple_build_label (dest);
1181 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1182 uid = LABEL_DECL_UID (dest);
1184 if (vec_safe_length (ifun->cfg->x_label_to_block_map) <= (unsigned int) uid)
1186 return (*ifun->cfg->x_label_to_block_map)[uid];
1189 /* Create edges for a goto statement at block BB. Returns true
1190 if abnormal edges should be created. */
1193 make_goto_expr_edges (basic_block bb)
1195 gimple_stmt_iterator last = gsi_last_bb (bb);
1196 gimple goto_t = gsi_stmt (last);
1198 /* A simple GOTO creates normal edges. */
1199 if (simple_goto_p (goto_t))
1201 tree dest = gimple_goto_dest (goto_t);
1202 basic_block label_bb = label_to_block (dest);
1203 edge e = make_edge (bb, label_bb, EDGE_FALLTHRU);
1204 e->goto_locus = gimple_location (goto_t);
1205 gsi_remove (&last, true);
1209 /* A computed GOTO creates abnormal edges. */
1213 /* Create edges for an asm statement with labels at block BB. */
1216 make_gimple_asm_edges (basic_block bb)
1218 gimple stmt = last_stmt (bb);
1219 int i, n = gimple_asm_nlabels (stmt);
1221 for (i = 0; i < n; ++i)
1223 tree label = TREE_VALUE (gimple_asm_label_op (stmt, i));
1224 basic_block label_bb = label_to_block (label);
1225 make_edge (bb, label_bb, 0);
1229 /*---------------------------------------------------------------------------
1231 ---------------------------------------------------------------------------*/
1233 /* Cleanup useless labels in basic blocks. This is something we wish
1234 to do early because it allows us to group case labels before creating
1235 the edges for the CFG, and it speeds up block statement iterators in
1236 all passes later on.
1237 We rerun this pass after CFG is created, to get rid of the labels that
1238 are no longer referenced. After then we do not run it any more, since
1239 (almost) no new labels should be created. */
1241 /* A map from basic block index to the leading label of that block. */
1242 static struct label_record
1247 /* True if the label is referenced from somewhere. */
1251 /* Given LABEL return the first label in the same basic block. */
1254 main_block_label (tree label)
1256 basic_block bb = label_to_block (label);
1257 tree main_label = label_for_bb[bb->index].label;
1259 /* label_to_block possibly inserted undefined label into the chain. */
1262 label_for_bb[bb->index].label = label;
1266 label_for_bb[bb->index].used = true;
1270 /* Clean up redundant labels within the exception tree. */
1273 cleanup_dead_labels_eh (void)
1280 if (cfun->eh == NULL)
1283 for (i = 1; vec_safe_iterate (cfun->eh->lp_array, i, &lp); ++i)
1284 if (lp && lp->post_landing_pad)
1286 lab = main_block_label (lp->post_landing_pad);
1287 if (lab != lp->post_landing_pad)
1289 EH_LANDING_PAD_NR (lp->post_landing_pad) = 0;
1290 EH_LANDING_PAD_NR (lab) = lp->index;
1294 FOR_ALL_EH_REGION (r)
1298 case ERT_MUST_NOT_THROW:
1304 for (c = r->u.eh_try.first_catch; c ; c = c->next_catch)
1308 c->label = main_block_label (lab);
1313 case ERT_ALLOWED_EXCEPTIONS:
1314 lab = r->u.allowed.label;
1316 r->u.allowed.label = main_block_label (lab);
1322 /* Cleanup redundant labels. This is a three-step process:
1323 1) Find the leading label for each block.
1324 2) Redirect all references to labels to the leading labels.
1325 3) Cleanup all useless labels. */
1328 cleanup_dead_labels (void)
1331 label_for_bb = XCNEWVEC (struct label_record, last_basic_block_for_fn (cfun));
1333 /* Find a suitable label for each block. We use the first user-defined
1334 label if there is one, or otherwise just the first label we see. */
1335 FOR_EACH_BB_FN (bb, cfun)
1337 gimple_stmt_iterator i;
1339 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
1342 gimple stmt = gsi_stmt (i);
1344 if (gimple_code (stmt) != GIMPLE_LABEL)
1347 label = gimple_label_label (stmt);
1349 /* If we have not yet seen a label for the current block,
1350 remember this one and see if there are more labels. */
1351 if (!label_for_bb[bb->index].label)
1353 label_for_bb[bb->index].label = label;
1357 /* If we did see a label for the current block already, but it
1358 is an artificially created label, replace it if the current
1359 label is a user defined label. */
1360 if (!DECL_ARTIFICIAL (label)
1361 && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
1363 label_for_bb[bb->index].label = label;
1369 /* Now redirect all jumps/branches to the selected label.
1370 First do so for each block ending in a control statement. */
1371 FOR_EACH_BB_FN (bb, cfun)
1373 gimple stmt = last_stmt (bb);
1374 tree label, new_label;
1379 switch (gimple_code (stmt))
1382 label = gimple_cond_true_label (stmt);
1385 new_label = main_block_label (label);
1386 if (new_label != label)
1387 gimple_cond_set_true_label (stmt, new_label);
1390 label = gimple_cond_false_label (stmt);
1393 new_label = main_block_label (label);
1394 if (new_label != label)
1395 gimple_cond_set_false_label (stmt, new_label);
1401 size_t i, n = gimple_switch_num_labels (stmt);
1403 /* Replace all destination labels. */
1404 for (i = 0; i < n; ++i)
1406 tree case_label = gimple_switch_label (stmt, i);
1407 label = CASE_LABEL (case_label);
1408 new_label = main_block_label (label);
1409 if (new_label != label)
1410 CASE_LABEL (case_label) = new_label;
1417 int i, n = gimple_asm_nlabels (stmt);
1419 for (i = 0; i < n; ++i)
1421 tree cons = gimple_asm_label_op (stmt, i);
1422 tree label = main_block_label (TREE_VALUE (cons));
1423 TREE_VALUE (cons) = label;
1428 /* We have to handle gotos until they're removed, and we don't
1429 remove them until after we've created the CFG edges. */
1431 if (!computed_goto_p (stmt))
1433 label = gimple_goto_dest (stmt);
1434 new_label = main_block_label (label);
1435 if (new_label != label)
1436 gimple_goto_set_dest (stmt, new_label);
1440 case GIMPLE_TRANSACTION:
1442 tree label = gimple_transaction_label (stmt);
1445 tree new_label = main_block_label (label);
1446 if (new_label != label)
1447 gimple_transaction_set_label (stmt, new_label);
1457 /* Do the same for the exception region tree labels. */
1458 cleanup_dead_labels_eh ();
1460 /* Finally, purge dead labels. All user-defined labels and labels that
1461 can be the target of non-local gotos and labels which have their
1462 address taken are preserved. */
1463 FOR_EACH_BB_FN (bb, cfun)
1465 gimple_stmt_iterator i;
1466 tree label_for_this_bb = label_for_bb[bb->index].label;
1468 if (!label_for_this_bb)
1471 /* If the main label of the block is unused, we may still remove it. */
1472 if (!label_for_bb[bb->index].used)
1473 label_for_this_bb = NULL;
1475 for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1478 gimple stmt = gsi_stmt (i);
1480 if (gimple_code (stmt) != GIMPLE_LABEL)
1483 label = gimple_label_label (stmt);
1485 if (label == label_for_this_bb
1486 || !DECL_ARTIFICIAL (label)
1487 || DECL_NONLOCAL (label)
1488 || FORCED_LABEL (label))
1491 gsi_remove (&i, true);
1495 free (label_for_bb);
1498 /* Scan the sorted vector of cases in STMT (a GIMPLE_SWITCH) and combine
1499 the ones jumping to the same label.
1500 Eg. three separate entries 1: 2: 3: become one entry 1..3: */
1503 group_case_labels_stmt (gimple stmt)
1505 int old_size = gimple_switch_num_labels (stmt);
1506 int i, j, new_size = old_size;
1507 basic_block default_bb = NULL;
1509 default_bb = label_to_block (CASE_LABEL (gimple_switch_default_label (stmt)));
1511 /* Look for possible opportunities to merge cases. */
1513 while (i < old_size)
1515 tree base_case, base_high;
1516 basic_block base_bb;
1518 base_case = gimple_switch_label (stmt, i);
1520 gcc_assert (base_case);
1521 base_bb = label_to_block (CASE_LABEL (base_case));
1523 /* Discard cases that have the same destination as the
1525 if (base_bb == default_bb)
1527 gimple_switch_set_label (stmt, i, NULL_TREE);
1533 base_high = CASE_HIGH (base_case)
1534 ? CASE_HIGH (base_case)
1535 : CASE_LOW (base_case);
1538 /* Try to merge case labels. Break out when we reach the end
1539 of the label vector or when we cannot merge the next case
1540 label with the current one. */
1541 while (i < old_size)
1543 tree merge_case = gimple_switch_label (stmt, i);
1544 basic_block merge_bb = label_to_block (CASE_LABEL (merge_case));
1545 double_int bhp1 = tree_to_double_int (base_high) + double_int_one;
1547 /* Merge the cases if they jump to the same place,
1548 and their ranges are consecutive. */
1549 if (merge_bb == base_bb
1550 && tree_to_double_int (CASE_LOW (merge_case)) == bhp1)
1552 base_high = CASE_HIGH (merge_case) ?
1553 CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1554 CASE_HIGH (base_case) = base_high;
1555 gimple_switch_set_label (stmt, i, NULL_TREE);
1564 /* Compress the case labels in the label vector, and adjust the
1565 length of the vector. */
1566 for (i = 0, j = 0; i < new_size; i++)
1568 while (! gimple_switch_label (stmt, j))
1570 gimple_switch_set_label (stmt, i,
1571 gimple_switch_label (stmt, j++));
1574 gcc_assert (new_size <= old_size);
1575 gimple_switch_set_num_labels (stmt, new_size);
1578 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
1579 and scan the sorted vector of cases. Combine the ones jumping to the
1583 group_case_labels (void)
1587 FOR_EACH_BB_FN (bb, cfun)
1589 gimple stmt = last_stmt (bb);
1590 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1591 group_case_labels_stmt (stmt);
1595 /* Checks whether we can merge block B into block A. */
1598 gimple_can_merge_blocks_p (basic_block a, basic_block b)
1601 gimple_stmt_iterator gsi;
1603 if (!single_succ_p (a))
1606 if (single_succ_edge (a)->flags & EDGE_COMPLEX)
1609 if (single_succ (a) != b)
1612 if (!single_pred_p (b))
1615 if (b == EXIT_BLOCK_PTR_FOR_FN (cfun))
1618 /* If A ends by a statement causing exceptions or something similar, we
1619 cannot merge the blocks. */
1620 stmt = last_stmt (a);
1621 if (stmt && stmt_ends_bb_p (stmt))
1624 /* Do not allow a block with only a non-local label to be merged. */
1626 && gimple_code (stmt) == GIMPLE_LABEL
1627 && DECL_NONLOCAL (gimple_label_label (stmt)))
1630 /* Examine the labels at the beginning of B. */
1631 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
1634 stmt = gsi_stmt (gsi);
1635 if (gimple_code (stmt) != GIMPLE_LABEL)
1637 lab = gimple_label_label (stmt);
1639 /* Do not remove user forced labels or for -O0 any user labels. */
1640 if (!DECL_ARTIFICIAL (lab) && (!optimize || FORCED_LABEL (lab)))
1644 /* Protect the loop latches. */
1645 if (current_loops && b->loop_father->latch == b)
1648 /* It must be possible to eliminate all phi nodes in B. If ssa form
1649 is not up-to-date and a name-mapping is registered, we cannot eliminate
1650 any phis. Symbols marked for renaming are never a problem though. */
1651 for (gsi = gsi_start_phis (b); !gsi_end_p (gsi); gsi_next (&gsi))
1653 gimple phi = gsi_stmt (gsi);
1654 /* Technically only new names matter. */
1655 if (name_registered_for_update_p (PHI_RESULT (phi)))
1659 /* When not optimizing, don't merge if we'd lose goto_locus. */
1661 && single_succ_edge (a)->goto_locus != UNKNOWN_LOCATION)
1663 location_t goto_locus = single_succ_edge (a)->goto_locus;
1664 gimple_stmt_iterator prev, next;
1665 prev = gsi_last_nondebug_bb (a);
1666 next = gsi_after_labels (b);
1667 if (!gsi_end_p (next) && is_gimple_debug (gsi_stmt (next)))
1668 gsi_next_nondebug (&next);
1669 if ((gsi_end_p (prev)
1670 || gimple_location (gsi_stmt (prev)) != goto_locus)
1671 && (gsi_end_p (next)
1672 || gimple_location (gsi_stmt (next)) != goto_locus))
1679 /* Replaces all uses of NAME by VAL. */
1682 replace_uses_by (tree name, tree val)
1684 imm_use_iterator imm_iter;
1689 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1691 /* Mark the block if we change the last stmt in it. */
1692 if (cfgcleanup_altered_bbs
1693 && stmt_ends_bb_p (stmt))
1694 bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1696 FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1698 replace_exp (use, val);
1700 if (gimple_code (stmt) == GIMPLE_PHI)
1702 e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use));
1703 if (e->flags & EDGE_ABNORMAL)
1705 /* This can only occur for virtual operands, since
1706 for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1707 would prevent replacement. */
1708 gcc_checking_assert (virtual_operand_p (name));
1709 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1714 if (gimple_code (stmt) != GIMPLE_PHI)
1716 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1717 gimple orig_stmt = stmt;
1720 /* FIXME. It shouldn't be required to keep TREE_CONSTANT
1721 on ADDR_EXPRs up-to-date on GIMPLE. Propagation will
1722 only change sth from non-invariant to invariant, and only
1723 when propagating constants. */
1724 if (is_gimple_min_invariant (val))
1725 for (i = 0; i < gimple_num_ops (stmt); i++)
1727 tree op = gimple_op (stmt, i);
1728 /* Operands may be empty here. For example, the labels
1729 of a GIMPLE_COND are nulled out following the creation
1730 of the corresponding CFG edges. */
1731 if (op && TREE_CODE (op) == ADDR_EXPR)
1732 recompute_tree_invariant_for_addr_expr (op);
1735 if (fold_stmt (&gsi))
1736 stmt = gsi_stmt (gsi);
1738 if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
1739 gimple_purge_dead_eh_edges (gimple_bb (stmt));
1745 gcc_checking_assert (has_zero_uses (name));
1747 /* Also update the trees stored in loop structures. */
1752 FOR_EACH_LOOP (loop, 0)
1754 substitute_in_loop_info (loop, name, val);
1759 /* Merge block B into block A. */
1762 gimple_merge_blocks (basic_block a, basic_block b)
1764 gimple_stmt_iterator last, gsi, psi;
1767 fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1769 /* Remove all single-valued PHI nodes from block B of the form
1770 V_i = PHI <V_j> by propagating V_j to all the uses of V_i. */
1771 gsi = gsi_last_bb (a);
1772 for (psi = gsi_start_phis (b); !gsi_end_p (psi); )
1774 gimple phi = gsi_stmt (psi);
1775 tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1777 bool may_replace_uses = (virtual_operand_p (def)
1778 || may_propagate_copy (def, use));
1780 /* In case we maintain loop closed ssa form, do not propagate arguments
1781 of loop exit phi nodes. */
1783 && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1784 && !virtual_operand_p (def)
1785 && TREE_CODE (use) == SSA_NAME
1786 && a->loop_father != b->loop_father)
1787 may_replace_uses = false;
1789 if (!may_replace_uses)
1791 gcc_assert (!virtual_operand_p (def));
1793 /* Note that just emitting the copies is fine -- there is no problem
1794 with ordering of phi nodes. This is because A is the single
1795 predecessor of B, therefore results of the phi nodes cannot
1796 appear as arguments of the phi nodes. */
1797 copy = gimple_build_assign (def, use);
1798 gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1799 remove_phi_node (&psi, false);
1803 /* If we deal with a PHI for virtual operands, we can simply
1804 propagate these without fussing with folding or updating
1806 if (virtual_operand_p (def))
1808 imm_use_iterator iter;
1809 use_operand_p use_p;
1812 FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1813 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1814 SET_USE (use_p, use);
1816 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
1817 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use) = 1;
1820 replace_uses_by (def, use);
1822 remove_phi_node (&psi, true);
1826 /* Ensure that B follows A. */
1827 move_block_after (b, a);
1829 gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1830 gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1832 /* Remove labels from B and set gimple_bb to A for other statements. */
1833 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1835 gimple stmt = gsi_stmt (gsi);
1836 if (gimple_code (stmt) == GIMPLE_LABEL)
1838 tree label = gimple_label_label (stmt);
1841 gsi_remove (&gsi, false);
1843 /* Now that we can thread computed gotos, we might have
1844 a situation where we have a forced label in block B
1845 However, the label at the start of block B might still be
1846 used in other ways (think about the runtime checking for
1847 Fortran assigned gotos). So we can not just delete the
1848 label. Instead we move the label to the start of block A. */
1849 if (FORCED_LABEL (label))
1851 gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1852 gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT);
1854 /* Other user labels keep around in a form of a debug stmt. */
1855 else if (!DECL_ARTIFICIAL (label) && MAY_HAVE_DEBUG_STMTS)
1857 gimple dbg = gimple_build_debug_bind (label,
1860 gimple_debug_bind_reset_value (dbg);
1861 gsi_insert_before (&gsi, dbg, GSI_SAME_STMT);
1864 lp_nr = EH_LANDING_PAD_NR (label);
1867 eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1868 lp->post_landing_pad = NULL;
1873 gimple_set_bb (stmt, a);
1878 /* Merge the sequences. */
1879 last = gsi_last_bb (a);
1880 gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1881 set_bb_seq (b, NULL);
1883 if (cfgcleanup_altered_bbs)
1884 bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1888 /* Return the one of two successors of BB that is not reachable by a
1889 complex edge, if there is one. Else, return BB. We use
1890 this in optimizations that use post-dominators for their heuristics,
1891 to catch the cases in C++ where function calls are involved. */
1894 single_noncomplex_succ (basic_block bb)
1897 if (EDGE_COUNT (bb->succs) != 2)
1900 e0 = EDGE_SUCC (bb, 0);
1901 e1 = EDGE_SUCC (bb, 1);
1902 if (e0->flags & EDGE_COMPLEX)
1904 if (e1->flags & EDGE_COMPLEX)
1910 /* T is CALL_EXPR. Set current_function_calls_* flags. */
1913 notice_special_calls (gimple call)
1915 int flags = gimple_call_flags (call);
1917 if (flags & ECF_MAY_BE_ALLOCA)
1918 cfun->calls_alloca = true;
1919 if (flags & ECF_RETURNS_TWICE)
1920 cfun->calls_setjmp = true;
1924 /* Clear flags set by notice_special_calls. Used by dead code removal
1925 to update the flags. */
1928 clear_special_calls (void)
1930 cfun->calls_alloca = false;
1931 cfun->calls_setjmp = false;
1934 /* Remove PHI nodes associated with basic block BB and all edges out of BB. */
1937 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1939 /* Since this block is no longer reachable, we can just delete all
1940 of its PHI nodes. */
1941 remove_phi_nodes (bb);
1943 /* Remove edges to BB's successors. */
1944 while (EDGE_COUNT (bb->succs) > 0)
1945 remove_edge (EDGE_SUCC (bb, 0));
1949 /* Remove statements of basic block BB. */
1952 remove_bb (basic_block bb)
1954 gimple_stmt_iterator i;
1958 fprintf (dump_file, "Removing basic block %d\n", bb->index);
1959 if (dump_flags & TDF_DETAILS)
1961 dump_bb (dump_file, bb, 0, TDF_BLOCKS);
1962 fprintf (dump_file, "\n");
1968 struct loop *loop = bb->loop_father;
1970 /* If a loop gets removed, clean up the information associated
1972 if (loop->latch == bb
1973 || loop->header == bb)
1974 free_numbers_of_iterations_estimates_loop (loop);
1977 /* Remove all the instructions in the block. */
1978 if (bb_seq (bb) != NULL)
1980 /* Walk backwards so as to get a chance to substitute all
1981 released DEFs into debug stmts. See
1982 eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
1984 for (i = gsi_last_bb (bb); !gsi_end_p (i);)
1986 gimple stmt = gsi_stmt (i);
1987 if (gimple_code (stmt) == GIMPLE_LABEL
1988 && (FORCED_LABEL (gimple_label_label (stmt))
1989 || DECL_NONLOCAL (gimple_label_label (stmt))))
1992 gimple_stmt_iterator new_gsi;
1994 /* A non-reachable non-local label may still be referenced.
1995 But it no longer needs to carry the extra semantics of
1997 if (DECL_NONLOCAL (gimple_label_label (stmt)))
1999 DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
2000 FORCED_LABEL (gimple_label_label (stmt)) = 1;
2003 new_bb = bb->prev_bb;
2004 new_gsi = gsi_start_bb (new_bb);
2005 gsi_remove (&i, false);
2006 gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
2010 /* Release SSA definitions if we are in SSA. Note that we
2011 may be called when not in SSA. For example,
2012 final_cleanup calls this function via
2013 cleanup_tree_cfg. */
2014 if (gimple_in_ssa_p (cfun))
2015 release_defs (stmt);
2017 gsi_remove (&i, true);
2021 i = gsi_last_bb (bb);
2027 remove_phi_nodes_and_edges_for_unreachable_block (bb);
2028 bb->il.gimple.seq = NULL;
2029 bb->il.gimple.phi_nodes = NULL;
2033 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2034 predicate VAL, return the edge that will be taken out of the block.
2035 If VAL does not match a unique edge, NULL is returned. */
2038 find_taken_edge (basic_block bb, tree val)
2042 stmt = last_stmt (bb);
2045 gcc_assert (is_ctrl_stmt (stmt));
2050 if (!is_gimple_min_invariant (val))
2053 if (gimple_code (stmt) == GIMPLE_COND)
2054 return find_taken_edge_cond_expr (bb, val);
2056 if (gimple_code (stmt) == GIMPLE_SWITCH)
2057 return find_taken_edge_switch_expr (bb, val);
2059 if (computed_goto_p (stmt))
2061 /* Only optimize if the argument is a label, if the argument is
2062 not a label then we can not construct a proper CFG.
2064 It may be the case that we only need to allow the LABEL_REF to
2065 appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
2066 appear inside a LABEL_EXPR just to be safe. */
2067 if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
2068 && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
2069 return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
2076 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2077 statement, determine which of the outgoing edges will be taken out of the
2078 block. Return NULL if either edge may be taken. */
2081 find_taken_edge_computed_goto (basic_block bb, tree val)
2086 dest = label_to_block (val);
2089 e = find_edge (bb, dest);
2090 gcc_assert (e != NULL);
2096 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2097 statement, determine which of the two edges will be taken out of the
2098 block. Return NULL if either edge may be taken. */
2101 find_taken_edge_cond_expr (basic_block bb, tree val)
2103 edge true_edge, false_edge;
2105 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2107 gcc_assert (TREE_CODE (val) == INTEGER_CST);
2108 return (integer_zerop (val) ? false_edge : true_edge);
2111 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2112 statement, determine which edge will be taken out of the block. Return
2113 NULL if any edge may be taken. */
2116 find_taken_edge_switch_expr (basic_block bb, tree val)
2118 basic_block dest_bb;
2123 switch_stmt = last_stmt (bb);
2124 taken_case = find_case_label_for_value (switch_stmt, val);
2125 dest_bb = label_to_block (CASE_LABEL (taken_case));
2127 e = find_edge (bb, dest_bb);
2133 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
2134 We can make optimal use here of the fact that the case labels are
2135 sorted: We can do a binary search for a case matching VAL. */
2138 find_case_label_for_value (gimple switch_stmt, tree val)
2140 size_t low, high, n = gimple_switch_num_labels (switch_stmt);
2141 tree default_case = gimple_switch_default_label (switch_stmt);
2143 for (low = 0, high = n; high - low > 1; )
2145 size_t i = (high + low) / 2;
2146 tree t = gimple_switch_label (switch_stmt, i);
2149 /* Cache the result of comparing CASE_LOW and val. */
2150 cmp = tree_int_cst_compare (CASE_LOW (t), val);
2157 if (CASE_HIGH (t) == NULL)
2159 /* A singe-valued case label. */
2165 /* A case range. We can only handle integer ranges. */
2166 if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2171 return default_case;
2175 /* Dump a basic block on stderr. */
2178 gimple_debug_bb (basic_block bb)
2180 dump_bb (stderr, bb, 0, TDF_VOPS|TDF_MEMSYMS|TDF_BLOCKS);
2184 /* Dump basic block with index N on stderr. */
2187 gimple_debug_bb_n (int n)
2189 gimple_debug_bb (BASIC_BLOCK_FOR_FN (cfun, n));
2190 return BASIC_BLOCK_FOR_FN (cfun, n);
2194 /* Dump the CFG on stderr.
2196 FLAGS are the same used by the tree dumping functions
2197 (see TDF_* in dumpfile.h). */
2200 gimple_debug_cfg (int flags)
2202 gimple_dump_cfg (stderr, flags);
2206 /* Dump the program showing basic block boundaries on the given FILE.
2208 FLAGS are the same used by the tree dumping functions (see TDF_* in
2212 gimple_dump_cfg (FILE *file, int flags)
2214 if (flags & TDF_DETAILS)
2216 dump_function_header (file, current_function_decl, flags);
2217 fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2218 n_basic_blocks_for_fn (cfun), n_edges_for_fn (cfun),
2219 last_basic_block_for_fn (cfun));
2221 brief_dump_cfg (file, flags | TDF_COMMENT);
2222 fprintf (file, "\n");
2225 if (flags & TDF_STATS)
2226 dump_cfg_stats (file);
2228 dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2232 /* Dump CFG statistics on FILE. */
2235 dump_cfg_stats (FILE *file)
2237 static long max_num_merged_labels = 0;
2238 unsigned long size, total = 0;
2241 const char * const fmt_str = "%-30s%-13s%12s\n";
2242 const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2243 const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2244 const char * const fmt_str_3 = "%-43s%11lu%c\n";
2245 const char *funcname = current_function_name ();
2247 fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2249 fprintf (file, "---------------------------------------------------------\n");
2250 fprintf (file, fmt_str, "", " Number of ", "Memory");
2251 fprintf (file, fmt_str, "", " instances ", "used ");
2252 fprintf (file, "---------------------------------------------------------\n");
2254 size = n_basic_blocks_for_fn (cfun) * sizeof (struct basic_block_def);
2256 fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks_for_fn (cfun),
2257 SCALE (size), LABEL (size));
2260 FOR_EACH_BB_FN (bb, cfun)
2261 num_edges += EDGE_COUNT (bb->succs);
2262 size = num_edges * sizeof (struct edge_def);
2264 fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2266 fprintf (file, "---------------------------------------------------------\n");
2267 fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2269 fprintf (file, "---------------------------------------------------------\n");
2270 fprintf (file, "\n");
2272 if (cfg_stats.num_merged_labels > max_num_merged_labels)
2273 max_num_merged_labels = cfg_stats.num_merged_labels;
2275 fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2276 cfg_stats.num_merged_labels, max_num_merged_labels);
2278 fprintf (file, "\n");
2282 /* Dump CFG statistics on stderr. Keep extern so that it's always
2283 linked in the final executable. */
2286 debug_cfg_stats (void)
2288 dump_cfg_stats (stderr);
2291 /*---------------------------------------------------------------------------
2292 Miscellaneous helpers
2293 ---------------------------------------------------------------------------*/
2295 /* Return true if T, a GIMPLE_CALL, can make an abnormal transfer of control
2296 flow. Transfers of control flow associated with EH are excluded. */
2299 call_can_make_abnormal_goto (gimple t)
2301 /* If the function has no non-local labels, then a call cannot make an
2302 abnormal transfer of control. */
2303 if (!cfun->has_nonlocal_label
2304 && !cfun->calls_setjmp)
2307 /* Likewise if the call has no side effects. */
2308 if (!gimple_has_side_effects (t))
2311 /* Likewise if the called function is leaf. */
2312 if (gimple_call_flags (t) & ECF_LEAF)
2319 /* Return true if T can make an abnormal transfer of control flow.
2320 Transfers of control flow associated with EH are excluded. */
2323 stmt_can_make_abnormal_goto (gimple t)
2325 if (computed_goto_p (t))
2327 if (is_gimple_call (t))
2328 return call_can_make_abnormal_goto (t);
2333 /* Return true if T represents a stmt that always transfers control. */
2336 is_ctrl_stmt (gimple t)
2338 switch (gimple_code (t))
2352 /* Return true if T is a statement that may alter the flow of control
2353 (e.g., a call to a non-returning function). */
2356 is_ctrl_altering_stmt (gimple t)
2360 switch (gimple_code (t))
2364 int flags = gimple_call_flags (t);
2366 /* A call alters control flow if it can make an abnormal goto. */
2367 if (call_can_make_abnormal_goto (t))
2370 /* A call also alters control flow if it does not return. */
2371 if (flags & ECF_NORETURN)
2374 /* TM ending statements have backedges out of the transaction.
2375 Return true so we split the basic block containing them.
2376 Note that the TM_BUILTIN test is merely an optimization. */
2377 if ((flags & ECF_TM_BUILTIN)
2378 && is_tm_ending_fndecl (gimple_call_fndecl (t)))
2381 /* BUILT_IN_RETURN call is same as return statement. */
2382 if (gimple_call_builtin_p (t, BUILT_IN_RETURN))
2387 case GIMPLE_EH_DISPATCH:
2388 /* EH_DISPATCH branches to the individual catch handlers at
2389 this level of a try or allowed-exceptions region. It can
2390 fallthru to the next statement as well. */
2394 if (gimple_asm_nlabels (t) > 0)
2399 /* OpenMP directives alter control flow. */
2402 case GIMPLE_TRANSACTION:
2403 /* A transaction start alters control flow. */
2410 /* If a statement can throw, it alters control flow. */
2411 return stmt_can_throw_internal (t);
2415 /* Return true if T is a simple local goto. */
2418 simple_goto_p (gimple t)
2420 return (gimple_code (t) == GIMPLE_GOTO
2421 && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2425 /* Return true if STMT should start a new basic block. PREV_STMT is
2426 the statement preceding STMT. It is used when STMT is a label or a
2427 case label. Labels should only start a new basic block if their
2428 previous statement wasn't a label. Otherwise, sequence of labels
2429 would generate unnecessary basic blocks that only contain a single
2433 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2438 /* Labels start a new basic block only if the preceding statement
2439 wasn't a label of the same type. This prevents the creation of
2440 consecutive blocks that have nothing but a single label. */
2441 if (gimple_code (stmt) == GIMPLE_LABEL)
2443 /* Nonlocal and computed GOTO targets always start a new block. */
2444 if (DECL_NONLOCAL (gimple_label_label (stmt))
2445 || FORCED_LABEL (gimple_label_label (stmt)))
2448 if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2450 if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2453 cfg_stats.num_merged_labels++;
2459 else if (gimple_code (stmt) == GIMPLE_CALL
2460 && gimple_call_flags (stmt) & ECF_RETURNS_TWICE)
2461 /* setjmp acts similar to a nonlocal GOTO target and thus should
2462 start a new block. */
2469 /* Return true if T should end a basic block. */
2472 stmt_ends_bb_p (gimple t)
2474 return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2477 /* Remove block annotations and other data structures. */
2480 delete_tree_cfg_annotations (void)
2482 vec_free (label_to_block_map_for_fn (cfun));
2486 /* Return the first statement in basic block BB. */
2489 first_stmt (basic_block bb)
2491 gimple_stmt_iterator i = gsi_start_bb (bb);
2494 while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2502 /* Return the first non-label statement in basic block BB. */
2505 first_non_label_stmt (basic_block bb)
2507 gimple_stmt_iterator i = gsi_start_bb (bb);
2508 while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2510 return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2513 /* Return the last statement in basic block BB. */
2516 last_stmt (basic_block bb)
2518 gimple_stmt_iterator i = gsi_last_bb (bb);
2521 while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2529 /* Return the last statement of an otherwise empty block. Return NULL
2530 if the block is totally empty, or if it contains more than one
2534 last_and_only_stmt (basic_block bb)
2536 gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
2542 last = gsi_stmt (i);
2543 gsi_prev_nondebug (&i);
2547 /* Empty statements should no longer appear in the instruction stream.
2548 Everything that might have appeared before should be deleted by
2549 remove_useless_stmts, and the optimizers should just gsi_remove
2550 instead of smashing with build_empty_stmt.
2552 Thus the only thing that should appear here in a block containing
2553 one executable statement is a label. */
2554 prev = gsi_stmt (i);
2555 if (gimple_code (prev) == GIMPLE_LABEL)
2561 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE. */
2564 reinstall_phi_args (edge new_edge, edge old_edge)
2566 edge_var_map_vector *v;
2569 gimple_stmt_iterator phis;
2571 v = redirect_edge_var_map_vector (old_edge);
2575 for (i = 0, phis = gsi_start_phis (new_edge->dest);
2576 v->iterate (i, &vm) && !gsi_end_p (phis);
2577 i++, gsi_next (&phis))
2579 gimple phi = gsi_stmt (phis);
2580 tree result = redirect_edge_var_map_result (vm);
2581 tree arg = redirect_edge_var_map_def (vm);
2583 gcc_assert (result == gimple_phi_result (phi));
2585 add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
2588 redirect_edge_var_map_clear (old_edge);
2591 /* Returns the basic block after which the new basic block created
2592 by splitting edge EDGE_IN should be placed. Tries to keep the new block
2593 near its "logical" location. This is of most help to humans looking
2594 at debugging dumps. */
2597 split_edge_bb_loc (edge edge_in)
2599 basic_block dest = edge_in->dest;
2600 basic_block dest_prev = dest->prev_bb;
2604 edge e = find_edge (dest_prev, dest);
2605 if (e && !(e->flags & EDGE_COMPLEX))
2606 return edge_in->src;
2611 /* Split a (typically critical) edge EDGE_IN. Return the new block.
2612 Abort on abnormal edges. */
2615 gimple_split_edge (edge edge_in)
2617 basic_block new_bb, after_bb, dest;
2620 /* Abnormal edges cannot be split. */
2621 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2623 dest = edge_in->dest;
2625 after_bb = split_edge_bb_loc (edge_in);
2627 new_bb = create_empty_bb (after_bb);
2628 new_bb->frequency = EDGE_FREQUENCY (edge_in);
2629 new_bb->count = edge_in->count;
2630 new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2631 new_edge->probability = REG_BR_PROB_BASE;
2632 new_edge->count = edge_in->count;
2634 e = redirect_edge_and_branch (edge_in, new_bb);
2635 gcc_assert (e == edge_in);
2636 reinstall_phi_args (new_edge, e);
2642 /* Verify properties of the address expression T with base object BASE. */
2645 verify_address (tree t, tree base)
2648 bool old_side_effects;
2650 bool new_side_effects;
2652 old_constant = TREE_CONSTANT (t);
2653 old_side_effects = TREE_SIDE_EFFECTS (t);
2655 recompute_tree_invariant_for_addr_expr (t);
2656 new_side_effects = TREE_SIDE_EFFECTS (t);
2657 new_constant = TREE_CONSTANT (t);
2659 if (old_constant != new_constant)
2661 error ("constant not recomputed when ADDR_EXPR changed");
2664 if (old_side_effects != new_side_effects)
2666 error ("side effects not recomputed when ADDR_EXPR changed");
2670 if (!(TREE_CODE (base) == VAR_DECL
2671 || TREE_CODE (base) == PARM_DECL
2672 || TREE_CODE (base) == RESULT_DECL))
2675 if (DECL_GIMPLE_REG_P (base))
2677 error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2684 /* Callback for walk_tree, check that all elements with address taken are
2685 properly noticed as such. The DATA is an int* that is 1 if TP was seen
2686 inside a PHI node. */
2689 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2696 /* Check operand N for being valid GIMPLE and give error MSG if not. */
2697 #define CHECK_OP(N, MSG) \
2698 do { if (!is_gimple_val (TREE_OPERAND (t, N))) \
2699 { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2701 switch (TREE_CODE (t))
2704 if (SSA_NAME_IN_FREE_LIST (t))
2706 error ("SSA name in freelist but still referenced");
2712 error ("INDIRECT_REF in gimple IL");
2716 x = TREE_OPERAND (t, 0);
2717 if (!POINTER_TYPE_P (TREE_TYPE (x))
2718 || !is_gimple_mem_ref_addr (x))
2720 error ("invalid first operand of MEM_REF");
2723 if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST
2724 || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1))))
2726 error ("invalid offset operand of MEM_REF");
2727 return TREE_OPERAND (t, 1);
2729 if (TREE_CODE (x) == ADDR_EXPR
2730 && (x = verify_address (x, TREE_OPERAND (x, 0))))
2736 x = fold (ASSERT_EXPR_COND (t));
2737 if (x == boolean_false_node)
2739 error ("ASSERT_EXPR with an always-false condition");
2745 error ("MODIFY_EXPR not expected while having tuples");
2752 gcc_assert (is_gimple_address (t));
2754 /* Skip any references (they will be checked when we recurse down the
2755 tree) and ensure that any variable used as a prefix is marked
2757 for (x = TREE_OPERAND (t, 0);
2758 handled_component_p (x);
2759 x = TREE_OPERAND (x, 0))
2762 if ((tem = verify_address (t, x)))
2765 if (!(TREE_CODE (x) == VAR_DECL
2766 || TREE_CODE (x) == PARM_DECL
2767 || TREE_CODE (x) == RESULT_DECL))
2770 if (!TREE_ADDRESSABLE (x))
2772 error ("address taken, but ADDRESSABLE bit not set");
2780 x = COND_EXPR_COND (t);
2781 if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2783 error ("non-integral used in condition");
2786 if (!is_gimple_condexpr (x))
2788 error ("invalid conditional operand");
2793 case NON_LVALUE_EXPR:
2794 case TRUTH_NOT_EXPR:
2798 case FIX_TRUNC_EXPR:
2803 CHECK_OP (0, "invalid operand to unary operator");
2809 if (!is_gimple_reg_type (TREE_TYPE (t)))
2811 error ("non-scalar BIT_FIELD_REF, IMAGPART_EXPR or REALPART_EXPR");
2815 if (TREE_CODE (t) == BIT_FIELD_REF)
2817 tree t0 = TREE_OPERAND (t, 0);
2818 tree t1 = TREE_OPERAND (t, 1);
2819 tree t2 = TREE_OPERAND (t, 2);
2820 if (!tree_fits_uhwi_p (t1)
2821 || !tree_fits_uhwi_p (t2))
2823 error ("invalid position or size operand to BIT_FIELD_REF");
2826 if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2827 && (TYPE_PRECISION (TREE_TYPE (t))
2828 != tree_to_uhwi (t1)))
2830 error ("integral result type precision does not match "
2831 "field size of BIT_FIELD_REF");
2834 else if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2835 && TYPE_MODE (TREE_TYPE (t)) != BLKmode
2836 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2837 != tree_to_uhwi (t1)))
2839 error ("mode precision of non-integral result does not "
2840 "match field size of BIT_FIELD_REF");
2843 if (!AGGREGATE_TYPE_P (TREE_TYPE (t0))
2844 && (tree_to_uhwi (t1) + tree_to_uhwi (t2)
2845 > tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t0)))))
2847 error ("position plus size exceeds size of referenced object in "
2852 t = TREE_OPERAND (t, 0);
2857 case ARRAY_RANGE_REF:
2858 case VIEW_CONVERT_EXPR:
2859 /* We have a nest of references. Verify that each of the operands
2860 that determine where to reference is either a constant or a variable,
2861 verify that the base is valid, and then show we've already checked
2863 while (handled_component_p (t))
2865 if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2866 CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2867 else if (TREE_CODE (t) == ARRAY_REF
2868 || TREE_CODE (t) == ARRAY_RANGE_REF)
2870 CHECK_OP (1, "invalid array index");
2871 if (TREE_OPERAND (t, 2))
2872 CHECK_OP (2, "invalid array lower bound");
2873 if (TREE_OPERAND (t, 3))
2874 CHECK_OP (3, "invalid array stride");
2876 else if (TREE_CODE (t) == BIT_FIELD_REF
2877 || TREE_CODE (t) == REALPART_EXPR
2878 || TREE_CODE (t) == IMAGPART_EXPR)
2880 error ("non-top-level BIT_FIELD_REF, IMAGPART_EXPR or "
2885 t = TREE_OPERAND (t, 0);
2888 if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2890 error ("invalid reference prefix");
2897 /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2898 POINTER_PLUS_EXPR. */
2899 if (POINTER_TYPE_P (TREE_TYPE (t)))
2901 error ("invalid operand to plus/minus, type is a pointer");
2904 CHECK_OP (0, "invalid operand to binary operator");
2905 CHECK_OP (1, "invalid operand to binary operator");
2908 case POINTER_PLUS_EXPR:
2909 /* Check to make sure the first operand is a pointer or reference type. */
2910 if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
2912 error ("invalid operand to pointer plus, first operand is not a pointer");
2915 /* Check to make sure the second operand is a ptrofftype. */
2916 if (!ptrofftype_p (TREE_TYPE (TREE_OPERAND (t, 1))))
2918 error ("invalid operand to pointer plus, second operand is not an "
2919 "integer type of appropriate width");
2929 case UNORDERED_EXPR:
2938 case TRUNC_DIV_EXPR:
2940 case FLOOR_DIV_EXPR:
2941 case ROUND_DIV_EXPR:
2942 case TRUNC_MOD_EXPR:
2944 case FLOOR_MOD_EXPR:
2945 case ROUND_MOD_EXPR:
2947 case EXACT_DIV_EXPR:
2957 CHECK_OP (0, "invalid operand to binary operator");
2958 CHECK_OP (1, "invalid operand to binary operator");
2962 if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2966 case CASE_LABEL_EXPR:
2969 error ("invalid CASE_CHAIN");
2983 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
2984 Returns true if there is an error, otherwise false. */
2987 verify_types_in_gimple_min_lval (tree expr)
2991 if (is_gimple_id (expr))
2994 if (TREE_CODE (expr) != TARGET_MEM_REF
2995 && TREE_CODE (expr) != MEM_REF)
2997 error ("invalid expression for min lvalue");
3001 /* TARGET_MEM_REFs are strange beasts. */
3002 if (TREE_CODE (expr) == TARGET_MEM_REF)
3005 op = TREE_OPERAND (expr, 0);
3006 if (!is_gimple_val (op))
3008 error ("invalid operand in indirect reference");
3009 debug_generic_stmt (op);
3012 /* Memory references now generally can involve a value conversion. */
3017 /* Verify if EXPR is a valid GIMPLE reference expression. If
3018 REQUIRE_LVALUE is true verifies it is an lvalue. Returns true
3019 if there is an error, otherwise false. */
3022 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
3024 while (handled_component_p (expr))
3026 tree op = TREE_OPERAND (expr, 0);
3028 if (TREE_CODE (expr) == ARRAY_REF
3029 || TREE_CODE (expr) == ARRAY_RANGE_REF)
3031 if (!is_gimple_val (TREE_OPERAND (expr, 1))
3032 || (TREE_OPERAND (expr, 2)
3033 && !is_gimple_val (TREE_OPERAND (expr, 2)))
3034 || (TREE_OPERAND (expr, 3)
3035 && !is_gimple_val (TREE_OPERAND (expr, 3))))
3037 error ("invalid operands to array reference");
3038 debug_generic_stmt (expr);
3043 /* Verify if the reference array element types are compatible. */
3044 if (TREE_CODE (expr) == ARRAY_REF
3045 && !useless_type_conversion_p (TREE_TYPE (expr),
3046 TREE_TYPE (TREE_TYPE (op))))
3048 error ("type mismatch in array reference");
3049 debug_generic_stmt (TREE_TYPE (expr));
3050 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3053 if (TREE_CODE (expr) == ARRAY_RANGE_REF
3054 && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
3055 TREE_TYPE (TREE_TYPE (op))))
3057 error ("type mismatch in array range reference");
3058 debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
3059 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3063 if ((TREE_CODE (expr) == REALPART_EXPR
3064 || TREE_CODE (expr) == IMAGPART_EXPR)
3065 && !useless_type_conversion_p (TREE_TYPE (expr),
3066 TREE_TYPE (TREE_TYPE (op))))
3068 error ("type mismatch in real/imagpart reference");
3069 debug_generic_stmt (TREE_TYPE (expr));
3070 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3074 if (TREE_CODE (expr) == COMPONENT_REF
3075 && !useless_type_conversion_p (TREE_TYPE (expr),
3076 TREE_TYPE (TREE_OPERAND (expr, 1))))
3078 error ("type mismatch in component reference");
3079 debug_generic_stmt (TREE_TYPE (expr));
3080 debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3084 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
3086 /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check
3087 that their operand is not an SSA name or an invariant when
3088 requiring an lvalue (this usually means there is a SRA or IPA-SRA
3089 bug). Otherwise there is nothing to verify, gross mismatches at
3090 most invoke undefined behavior. */
3092 && (TREE_CODE (op) == SSA_NAME
3093 || is_gimple_min_invariant (op)))
3095 error ("conversion of an SSA_NAME on the left hand side");
3096 debug_generic_stmt (expr);
3099 else if (TREE_CODE (op) == SSA_NAME
3100 && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op)))
3102 error ("conversion of register to a different size");
3103 debug_generic_stmt (expr);
3106 else if (!handled_component_p (op))
3113 if (TREE_CODE (expr) == MEM_REF)
3115 if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0)))
3117 error ("invalid address operand in MEM_REF");
3118 debug_generic_stmt (expr);
3121 if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST
3122 || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
3124 error ("invalid offset operand in MEM_REF");
3125 debug_generic_stmt (expr);
3129 else if (TREE_CODE (expr) == TARGET_MEM_REF)
3131 if (!TMR_BASE (expr)
3132 || !is_gimple_mem_ref_addr (TMR_BASE (expr)))
3134 error ("invalid address operand in TARGET_MEM_REF");
3137 if (!TMR_OFFSET (expr)
3138 || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST
3139 || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr))))
3141 error ("invalid offset operand in TARGET_MEM_REF");
3142 debug_generic_stmt (expr);
3147 return ((require_lvalue || !is_gimple_min_invariant (expr))
3148 && verify_types_in_gimple_min_lval (expr));
3151 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3152 list of pointer-to types that is trivially convertible to DEST. */
3155 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3159 if (!TYPE_POINTER_TO (src_obj))
3162 for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3163 if (useless_type_conversion_p (dest, src))
3169 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3170 from TYPE2 can be handled by FIXED_CONVERT_EXPR. */
3173 valid_fixed_convert_types_p (tree type1, tree type2)
3175 return (FIXED_POINT_TYPE_P (type1)
3176 && (INTEGRAL_TYPE_P (type2)
3177 || SCALAR_FLOAT_TYPE_P (type2)
3178 || FIXED_POINT_TYPE_P (type2)));
3181 /* Verify the contents of a GIMPLE_CALL STMT. Returns true when there
3182 is a problem, otherwise false. */
3185 verify_gimple_call (gimple stmt)
3187 tree fn = gimple_call_fn (stmt);
3188 tree fntype, fndecl;
3191 if (gimple_call_internal_p (stmt))
3195 error ("gimple call has two targets");
3196 debug_generic_stmt (fn);
3204 error ("gimple call has no target");
3209 if (fn && !is_gimple_call_addr (fn))
3211 error ("invalid function in gimple call");
3212 debug_generic_stmt (fn);
3217 && (!POINTER_TYPE_P (TREE_TYPE (fn))
3218 || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3219 && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE)))
3221 error ("non-function in gimple call");
3225 fndecl = gimple_call_fndecl (stmt);
3227 && TREE_CODE (fndecl) == FUNCTION_DECL
3228 && DECL_LOOPING_CONST_OR_PURE_P (fndecl)
3229 && !DECL_PURE_P (fndecl)
3230 && !TREE_READONLY (fndecl))
3232 error ("invalid pure const state for function");
3236 if (gimple_call_lhs (stmt)
3237 && (!is_gimple_lvalue (gimple_call_lhs (stmt))
3238 || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true)))
3240 error ("invalid LHS in gimple call");
3244 if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt))
3246 error ("LHS in noreturn call");
3250 fntype = gimple_call_fntype (stmt);
3252 && gimple_call_lhs (stmt)
3253 && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3255 /* ??? At least C++ misses conversions at assignments from
3256 void * call results.
3257 ??? Java is completely off. Especially with functions
3258 returning java.lang.Object.
3259 For now simply allow arbitrary pointer type conversions. */
3260 && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3261 && POINTER_TYPE_P (TREE_TYPE (fntype))))
3263 error ("invalid conversion in gimple call");
3264 debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3265 debug_generic_stmt (TREE_TYPE (fntype));
3269 if (gimple_call_chain (stmt)
3270 && !is_gimple_val (gimple_call_chain (stmt)))
3272 error ("invalid static chain in gimple call");
3273 debug_generic_stmt (gimple_call_chain (stmt));
3277 /* If there is a static chain argument, this should not be an indirect
3278 call, and the decl should have DECL_STATIC_CHAIN set. */
3279 if (gimple_call_chain (stmt))
3281 if (!gimple_call_fndecl (stmt))
3283 error ("static chain in indirect gimple call");
3286 fn = TREE_OPERAND (fn, 0);
3288 if (!DECL_STATIC_CHAIN (fn))
3290 error ("static chain with function that doesn%'t use one");
3295 /* ??? The C frontend passes unpromoted arguments in case it
3296 didn't see a function declaration before the call. So for now
3297 leave the call arguments mostly unverified. Once we gimplify
3298 unit-at-a-time we have a chance to fix this. */
3300 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3302 tree arg = gimple_call_arg (stmt, i);
3303 if ((is_gimple_reg_type (TREE_TYPE (arg))
3304 && !is_gimple_val (arg))
3305 || (!is_gimple_reg_type (TREE_TYPE (arg))
3306 && !is_gimple_lvalue (arg)))
3308 error ("invalid argument to gimple call");
3309 debug_generic_expr (arg);
3317 /* Verifies the gimple comparison with the result type TYPE and
3318 the operands OP0 and OP1. */
3321 verify_gimple_comparison (tree type, tree op0, tree op1)
3323 tree op0_type = TREE_TYPE (op0);
3324 tree op1_type = TREE_TYPE (op1);
3326 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3328 error ("invalid operands in gimple comparison");
3332 /* For comparisons we do not have the operations type as the
3333 effective type the comparison is carried out in. Instead
3334 we require that either the first operand is trivially
3335 convertible into the second, or the other way around.
3336 Because we special-case pointers to void we allow
3337 comparisons of pointers with the same mode as well. */
3338 if (!useless_type_conversion_p (op0_type, op1_type)
3339 && !useless_type_conversion_p (op1_type, op0_type)
3340 && (!POINTER_TYPE_P (op0_type)
3341 || !POINTER_TYPE_P (op1_type)
3342 || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3344 error ("mismatching comparison operand types");
3345 debug_generic_expr (op0_type);
3346 debug_generic_expr (op1_type);
3350 /* The resulting type of a comparison may be an effective boolean type. */
3351 if (INTEGRAL_TYPE_P (type)
3352 && (TREE_CODE (type) == BOOLEAN_TYPE
3353 || TYPE_PRECISION (type) == 1))
3355 if (TREE_CODE (op0_type) == VECTOR_TYPE
3356 || TREE_CODE (op1_type) == VECTOR_TYPE)
3358 error ("vector comparison returning a boolean");
3359 debug_generic_expr (op0_type);
3360 debug_generic_expr (op1_type);
3364 /* Or an integer vector type with the same size and element count
3365 as the comparison operand types. */
3366 else if (TREE_CODE (type) == VECTOR_TYPE
3367 && TREE_CODE (TREE_TYPE (type)) == INTEGER_TYPE)
3369 if (TREE_CODE (op0_type) != VECTOR_TYPE
3370 || TREE_CODE (op1_type) != VECTOR_TYPE)
3372 error ("non-vector operands in vector comparison");
3373 debug_generic_expr (op0_type);
3374 debug_generic_expr (op1_type);
3378 if (TYPE_VECTOR_SUBPARTS (type) != TYPE_VECTOR_SUBPARTS (op0_type)
3379 || (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (type)))
3380 != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0_type))))
3381 /* The result of a vector comparison is of signed
3383 || TYPE_UNSIGNED (TREE_TYPE (type)))
3385 error ("invalid vector comparison resulting type");
3386 debug_generic_expr (type);
3392 error ("bogus comparison result type");
3393 debug_generic_expr (type);
3400 /* Verify a gimple assignment statement STMT with an unary rhs.
3401 Returns true if anything is wrong. */
3404 verify_gimple_assign_unary (gimple stmt)
3406 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3407 tree lhs = gimple_assign_lhs (stmt);
3408 tree lhs_type = TREE_TYPE (lhs);
3409 tree rhs1 = gimple_assign_rhs1 (stmt);
3410 tree rhs1_type = TREE_TYPE (rhs1);
3412 if (!is_gimple_reg (lhs))
3414 error ("non-register as LHS of unary operation");
3418 if (!is_gimple_val (rhs1))
3420 error ("invalid operand in unary operation");
3424 /* First handle conversions. */
3429 /* Allow conversions from pointer type to integral type only if
3430 there is no sign or zero extension involved.
3431 For targets were the precision of ptrofftype doesn't match that
3432 of pointers we need to allow arbitrary conversions to ptrofftype. */
3433 if ((POINTER_TYPE_P (lhs_type)
3434 && INTEGRAL_TYPE_P (rhs1_type))
3435 || (POINTER_TYPE_P (rhs1_type)
3436 && INTEGRAL_TYPE_P (lhs_type)
3437 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3438 || ptrofftype_p (sizetype))))
3441 /* Allow conversion from integral to offset type and vice versa. */
3442 if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3443 && INTEGRAL_TYPE_P (rhs1_type))
3444 || (INTEGRAL_TYPE_P (lhs_type)
3445 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3448 /* Otherwise assert we are converting between types of the
3450 if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3452 error ("invalid types in nop conversion");
3453 debug_generic_expr (lhs_type);
3454 debug_generic_expr (rhs1_type);
3461 case ADDR_SPACE_CONVERT_EXPR:
3463 if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3464 || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3465 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3467 error ("invalid types in address space conversion");
3468 debug_generic_expr (lhs_type);
3469 debug_generic_expr (rhs1_type);
3476 case FIXED_CONVERT_EXPR:
3478 if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3479 && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3481 error ("invalid types in fixed-point conversion");
3482 debug_generic_expr (lhs_type);
3483 debug_generic_expr (rhs1_type);
3492 if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3493 && (!VECTOR_INTEGER_TYPE_P (rhs1_type)
3494 || !VECTOR_FLOAT_TYPE_P (lhs_type)))
3496 error ("invalid types in conversion to floating point");
3497 debug_generic_expr (lhs_type);
3498 debug_generic_expr (rhs1_type);
3505 case FIX_TRUNC_EXPR:
3507 if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3508 && (!VECTOR_INTEGER_TYPE_P (lhs_type)
3509 || !VECTOR_FLOAT_TYPE_P (rhs1_type)))
3511 error ("invalid types in conversion to integer");
3512 debug_generic_expr (lhs_type);
3513 debug_generic_expr (rhs1_type);
3520 case VEC_UNPACK_HI_EXPR:
3521 case VEC_UNPACK_LO_EXPR:
3522 case REDUC_MAX_EXPR:
3523 case REDUC_MIN_EXPR:
3524 case REDUC_PLUS_EXPR:
3525 case VEC_UNPACK_FLOAT_HI_EXPR:
3526 case VEC_UNPACK_FLOAT_LO_EXPR:
3534 case NON_LVALUE_EXPR:
3542 /* For the remaining codes assert there is no conversion involved. */
3543 if (!useless_type_conversion_p (lhs_type, rhs1_type))
3545 error ("non-trivial conversion in unary operation");
3546 debug_generic_expr (lhs_type);
3547 debug_generic_expr (rhs1_type);
3554 /* Verify a gimple assignment statement STMT with a binary rhs.
3555 Returns true if anything is wrong. */
3558 verify_gimple_assign_binary (gimple stmt)
3560 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3561 tree lhs = gimple_assign_lhs (stmt);
3562 tree lhs_type = TREE_TYPE (lhs);
3563 tree rhs1 = gimple_assign_rhs1 (stmt);
3564 tree rhs1_type = TREE_TYPE (rhs1);
3565 tree rhs2 = gimple_assign_rhs2 (stmt);
3566 tree rhs2_type = TREE_TYPE (rhs2);
3568 if (!is_gimple_reg (lhs))
3570 error ("non-register as LHS of binary operation");
3574 if (!is_gimple_val (rhs1)
3575 || !is_gimple_val (rhs2))
3577 error ("invalid operands in binary operation");
3581 /* First handle operations that involve different types. */
3586 if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3587 || !(INTEGRAL_TYPE_P (rhs1_type)
3588 || SCALAR_FLOAT_TYPE_P (rhs1_type))
3589 || !(INTEGRAL_TYPE_P (rhs2_type)
3590 || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3592 error ("type mismatch in complex expression");
3593 debug_generic_expr (lhs_type);
3594 debug_generic_expr (rhs1_type);
3595 debug_generic_expr (rhs2_type);
3607 /* Shifts and rotates are ok on integral types, fixed point
3608 types and integer vector types. */
3609 if ((!INTEGRAL_TYPE_P (rhs1_type)
3610 && !FIXED_POINT_TYPE_P (rhs1_type)
3611 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3612 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3613 || (!INTEGRAL_TYPE_P (rhs2_type)
3614 /* Vector shifts of vectors are also ok. */
3615 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3616 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3617 && TREE_CODE (rhs2_type) == VECTOR_TYPE
3618 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3619 || !useless_type_conversion_p (lhs_type, rhs1_type))
3621 error ("type mismatch in shift expression");
3622 debug_generic_expr (lhs_type);
3623 debug_generic_expr (rhs1_type);
3624 debug_generic_expr (rhs2_type);
3631 case VEC_LSHIFT_EXPR:
3632 case VEC_RSHIFT_EXPR:
3634 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3635 || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3636 || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3637 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3638 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3639 || (!INTEGRAL_TYPE_P (rhs2_type)
3640 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3641 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3642 || !useless_type_conversion_p (lhs_type, rhs1_type))
3644 error ("type mismatch in vector shift expression");
3645 debug_generic_expr (lhs_type);
3646 debug_generic_expr (rhs1_type);
3647 debug_generic_expr (rhs2_type);
3650 /* For shifting a vector of non-integral components we
3651 only allow shifting by a constant multiple of the element size. */
3652 if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3653 && (TREE_CODE (rhs2) != INTEGER_CST
3654 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3655 TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3657 error ("non-element sized vector shift of floating point vector");
3664 case WIDEN_LSHIFT_EXPR:
3666 if (!INTEGRAL_TYPE_P (lhs_type)
3667 || !INTEGRAL_TYPE_P (rhs1_type)
3668 || TREE_CODE (rhs2) != INTEGER_CST
3669 || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)))
3671 error ("type mismatch in widening vector shift expression");
3672 debug_generic_expr (lhs_type);
3673 debug_generic_expr (rhs1_type);
3674 debug_generic_expr (rhs2_type);
3681 case VEC_WIDEN_LSHIFT_HI_EXPR:
3682 case VEC_WIDEN_LSHIFT_LO_EXPR:
3684 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3685 || TREE_CODE (lhs_type) != VECTOR_TYPE
3686 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3687 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs_type))
3688 || TREE_CODE (rhs2) != INTEGER_CST
3689 || (2 * TYPE_PRECISION (TREE_TYPE (rhs1_type))
3690 > TYPE_PRECISION (TREE_TYPE (lhs_type))))
3692 error ("type mismatch in widening vector shift expression");
3693 debug_generic_expr (lhs_type);
3694 debug_generic_expr (rhs1_type);
3695 debug_generic_expr (rhs2_type);
3705 tree lhs_etype = lhs_type;
3706 tree rhs1_etype = rhs1_type;
3707 tree rhs2_etype = rhs2_type;
3708 if (TREE_CODE (lhs_type) == VECTOR_TYPE)
3710 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3711 || TREE_CODE (rhs2_type) != VECTOR_TYPE)
3713 error ("invalid non-vector operands to vector valued plus");
3716 lhs_etype = TREE_TYPE (lhs_type);
3717 rhs1_etype = TREE_TYPE (rhs1_type);
3718 rhs2_etype = TREE_TYPE (rhs2_type);
3720 if (POINTER_TYPE_P (lhs_etype)
3721 || POINTER_TYPE_P (rhs1_etype)
3722 || POINTER_TYPE_P (rhs2_etype))
3724 error ("invalid (pointer) operands to plus/minus");
3728 /* Continue with generic binary expression handling. */
3732 case POINTER_PLUS_EXPR:
3734 if (!POINTER_TYPE_P (rhs1_type)
3735 || !useless_type_conversion_p (lhs_type, rhs1_type)
3736 || !ptrofftype_p (rhs2_type))
3738 error ("type mismatch in pointer plus expression");
3739 debug_generic_stmt (lhs_type);
3740 debug_generic_stmt (rhs1_type);
3741 debug_generic_stmt (rhs2_type);
3748 case TRUTH_ANDIF_EXPR:
3749 case TRUTH_ORIF_EXPR:
3750 case TRUTH_AND_EXPR:
3752 case TRUTH_XOR_EXPR:
3762 case UNORDERED_EXPR:
3770 /* Comparisons are also binary, but the result type is not
3771 connected to the operand types. */
3772 return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3774 case WIDEN_MULT_EXPR:
3775 if (TREE_CODE (lhs_type) != INTEGER_TYPE)
3777 return ((2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type))
3778 || (TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type)));
3780 case WIDEN_SUM_EXPR:
3781 case VEC_WIDEN_MULT_HI_EXPR:
3782 case VEC_WIDEN_MULT_LO_EXPR:
3783 case VEC_WIDEN_MULT_EVEN_EXPR:
3784 case VEC_WIDEN_MULT_ODD_EXPR:
3785 case VEC_PACK_TRUNC_EXPR:
3786 case VEC_PACK_SAT_EXPR:
3787 case VEC_PACK_FIX_TRUNC_EXPR:
3792 case MULT_HIGHPART_EXPR:
3793 case TRUNC_DIV_EXPR:
3795 case FLOOR_DIV_EXPR:
3796 case ROUND_DIV_EXPR:
3797 case TRUNC_MOD_EXPR:
3799 case FLOOR_MOD_EXPR:
3800 case ROUND_MOD_EXPR:
3802 case EXACT_DIV_EXPR:
3808 /* Continue with generic binary expression handling. */
3815 if (!useless_type_conversion_p (lhs_type, rhs1_type)
3816 || !useless_type_conversion_p (lhs_type, rhs2_type))
3818 error ("type mismatch in binary expression");
3819 debug_generic_stmt (lhs_type);
3820 debug_generic_stmt (rhs1_type);
3821 debug_generic_stmt (rhs2_type);
3828 /* Verify a gimple assignment statement STMT with a ternary rhs.
3829 Returns true if anything is wrong. */
3832 verify_gimple_assign_ternary (gimple stmt)
3834 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3835 tree lhs = gimple_assign_lhs (stmt);
3836 tree lhs_type = TREE_TYPE (lhs);
3837 tree rhs1 = gimple_assign_rhs1 (stmt);
3838 tree rhs1_type = TREE_TYPE (rhs1);
3839 tree rhs2 = gimple_assign_rhs2 (stmt);
3840 tree rhs2_type = TREE_TYPE (rhs2);
3841 tree rhs3 = gimple_assign_rhs3 (stmt);
3842 tree rhs3_type = TREE_TYPE (rhs3);
3844 if (!is_gimple_reg (lhs))
3846 error ("non-register as LHS of ternary operation");
3850 if (((rhs_code == VEC_COND_EXPR || rhs_code == COND_EXPR)
3851 ? !is_gimple_condexpr (rhs1) : !is_gimple_val (rhs1))
3852 || !is_gimple_val (rhs2)
3853 || !is_gimple_val (rhs3))
3855 error ("invalid operands in ternary operation");
3859 /* First handle operations that involve different types. */
3862 case WIDEN_MULT_PLUS_EXPR:
3863 case WIDEN_MULT_MINUS_EXPR:
3864 if ((!INTEGRAL_TYPE_P (rhs1_type)
3865 && !FIXED_POINT_TYPE_P (rhs1_type))
3866 || !useless_type_conversion_p (rhs1_type, rhs2_type)
3867 || !useless_type_conversion_p (lhs_type, rhs3_type)
3868 || 2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)
3869 || TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type))
3871 error ("type mismatch in widening multiply-accumulate expression");
3872 debug_generic_expr (lhs_type);
3873 debug_generic_expr (rhs1_type);
3874 debug_generic_expr (rhs2_type);
3875 debug_generic_expr (rhs3_type);
3881 if (!useless_type_conversion_p (lhs_type, rhs1_type)
3882 || !useless_type_conversion_p (lhs_type, rhs2_type)
3883 || !useless_type_conversion_p (lhs_type, rhs3_type))
3885 error ("type mismatch in fused multiply-add expression");
3886 debug_generic_expr (lhs_type);
3887 debug_generic_expr (rhs1_type);
3888 debug_generic_expr (rhs2_type);
3889 debug_generic_expr (rhs3_type);
3896 if (!useless_type_conversion_p (lhs_type, rhs2_type)
3897 || !useless_type_conversion_p (lhs_type, rhs3_type))
3899 error ("type mismatch in conditional expression");
3900 debug_generic_expr (lhs_type);
3901 debug_generic_expr (rhs2_type);
3902 debug_generic_expr (rhs3_type);
3908 if (!useless_type_conversion_p (lhs_type, rhs1_type)
3909 || !useless_type_conversion_p (lhs_type, rhs2_type))
3911 error ("type mismatch in vector permute expression");
3912 debug_generic_expr (lhs_type);
3913 debug_generic_expr (rhs1_type);
3914 debug_generic_expr (rhs2_type);
3915 debug_generic_expr (rhs3_type);
3919 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3920 || TREE_CODE (rhs2_type) != VECTOR_TYPE
3921 || TREE_CODE (rhs3_type) != VECTOR_TYPE)
3923 error ("vector types expected in vector permute expression");
3924 debug_generic_expr (lhs_type);
3925 debug_generic_expr (rhs1_type);
3926 debug_generic_expr (rhs2_type);
3927 debug_generic_expr (rhs3_type);
3931 if (TYPE_VECTOR_SUBPARTS (rhs1_type) != TYPE_VECTOR_SUBPARTS (rhs2_type)
3932 || TYPE_VECTOR_SUBPARTS (rhs2_type)
3933 != TYPE_VECTOR_SUBPARTS (rhs3_type)
3934 || TYPE_VECTOR_SUBPARTS (rhs3_type)
3935 != TYPE_VECTOR_SUBPARTS (lhs_type))
3937 error ("vectors with different element number found "
3938 "in vector permute expression");
3939 debug_generic_expr (lhs_type);
3940 debug_generic_expr (rhs1_type);
3941 debug_generic_expr (rhs2_type);
3942 debug_generic_expr (rhs3_type);
3946 if (TREE_CODE (TREE_TYPE (rhs3_type)) != INTEGER_TYPE
3947 || GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs3_type)))
3948 != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1_type))))
3950 error ("invalid mask type in vector permute expression");
3951 debug_generic_expr (lhs_type);
3952 debug_generic_expr (rhs1_type);
3953 debug_generic_expr (rhs2_type);
3954 debug_generic_expr (rhs3_type);
3961 case REALIGN_LOAD_EXPR:
3971 /* Verify a gimple assignment statement STMT with a single rhs.
3972 Returns true if anything is wrong. */
3975 verify_gimple_assign_single (gimple stmt)
3977 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3978 tree lhs = gimple_assign_lhs (stmt);
3979 tree lhs_type = TREE_TYPE (lhs);
3980 tree rhs1 = gimple_assign_rhs1 (stmt);
3981 tree rhs1_type = TREE_TYPE (rhs1);
3984 if (!useless_type_conversion_p (lhs_type, rhs1_type))
3986 error ("non-trivial conversion at assignment");
3987 debug_generic_expr (lhs_type);
3988 debug_generic_expr (rhs1_type);
3992 if (gimple_clobber_p (stmt)
3993 && !(DECL_P (lhs) || TREE_CODE (lhs) == MEM_REF))
3995 error ("non-decl/MEM_REF LHS in clobber statement");
3996 debug_generic_expr (lhs);
4000 if (handled_component_p (lhs)
4001 || TREE_CODE (lhs) == MEM_REF
4002 || TREE_CODE (lhs) == TARGET_MEM_REF)
4003 res |= verify_types_in_gimple_reference (lhs, true);
4005 /* Special codes we cannot handle via their class. */
4010 tree op = TREE_OPERAND (rhs1, 0);
4011 if (!is_gimple_addressable (op))
4013 error ("invalid operand in unary expression");
4017 /* Technically there is no longer a need for matching types, but
4018 gimple hygiene asks for this check. In LTO we can end up
4019 combining incompatible units and thus end up with addresses
4020 of globals that change their type to a common one. */
4022 && !types_compatible_p (TREE_TYPE (op),
4023 TREE_TYPE (TREE_TYPE (rhs1)))
4024 && !one_pointer_to_useless_type_conversion_p (TREE_TYPE (rhs1),
4027 error ("type mismatch in address expression");
4028 debug_generic_stmt (TREE_TYPE (rhs1));
4029 debug_generic_stmt (TREE_TYPE (op));
4033 return verify_types_in_gimple_reference (op, true);
4038 error ("INDIRECT_REF in gimple IL");
4044 case ARRAY_RANGE_REF:
4045 case VIEW_CONVERT_EXPR:
4048 case TARGET_MEM_REF:
4050 if (!is_gimple_reg (lhs)
4051 && is_gimple_reg_type (TREE_TYPE (lhs)))
4053 error ("invalid rhs for gimple memory store");
4054 debug_generic_stmt (lhs);
4055 debug_generic_stmt (rhs1);
4058 return res || verify_types_in_gimple_reference (rhs1, false);
4070 /* tcc_declaration */
4075 if (!is_gimple_reg (lhs)
4076 && !is_gimple_reg (rhs1)
4077 && is_gimple_reg_type (TREE_TYPE (lhs)))
4079 error ("invalid rhs for gimple memory store");
4080 debug_generic_stmt (lhs);
4081 debug_generic_stmt (rhs1);
4087 if (TREE_CODE (rhs1_type) == VECTOR_TYPE)
4090 tree elt_i, elt_v, elt_t = NULL_TREE;
4092 if (CONSTRUCTOR_NELTS (rhs1) == 0)
4094 /* For vector CONSTRUCTORs we require that either it is empty
4095 CONSTRUCTOR, or it is a CONSTRUCTOR of smaller vector elements
4096 (then the element count must be correct to cover the whole
4097 outer vector and index must be NULL on all elements, or it is
4098 a CONSTRUCTOR of scalar elements, where we as an exception allow
4099 smaller number of elements (assuming zero filling) and
4100 consecutive indexes as compared to NULL indexes (such
4101 CONSTRUCTORs can appear in the IL from FEs). */
4102 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (rhs1), i, elt_i, elt_v)
4104 if (elt_t == NULL_TREE)
4106 elt_t = TREE_TYPE (elt_v);
4107 if (TREE_CODE (elt_t) == VECTOR_TYPE)
4109 tree elt_t = TREE_TYPE (elt_v);
4110 if (!useless_type_conversion_p (TREE_TYPE (rhs1_type),
4113 error ("incorrect type of vector CONSTRUCTOR"
4115 debug_generic_stmt (rhs1);
4118 else if (CONSTRUCTOR_NELTS (rhs1)
4119 * TYPE_VECTOR_SUBPARTS (elt_t)
4120 != TYPE_VECTOR_SUBPARTS (rhs1_type))
4122 error ("incorrect number of vector CONSTRUCTOR"
4124 debug_generic_stmt (rhs1);
4128 else if (!useless_type_conversion_p (TREE_TYPE (rhs1_type),
4131 error ("incorrect type of vector CONSTRUCTOR elements");
4132 debug_generic_stmt (rhs1);
4135 else if (CONSTRUCTOR_NELTS (rhs1)
4136 > TYPE_VECTOR_SUBPARTS (rhs1_type))
4138 error ("incorrect number of vector CONSTRUCTOR elements");
4139 debug_generic_stmt (rhs1);
4143 else if (!useless_type_conversion_p (elt_t, TREE_TYPE (elt_v)))
4145 error ("incorrect type of vector CONSTRUCTOR elements");
4146 debug_generic_stmt (rhs1);
4149 if (elt_i != NULL_TREE
4150 && (TREE_CODE (elt_t) == VECTOR_TYPE
4151 || TREE_CODE (elt_i) != INTEGER_CST
4152 || compare_tree_int (elt_i, i) != 0))
4154 error ("vector CONSTRUCTOR with non-NULL element index");
4155 debug_generic_stmt (rhs1);
4163 case WITH_SIZE_EXPR:
4173 /* Verify the contents of a GIMPLE_ASSIGN STMT. Returns true when there
4174 is a problem, otherwise false. */
4177 verify_gimple_assign (gimple stmt)
4179 switch (gimple_assign_rhs_class (stmt))
4181 case GIMPLE_SINGLE_RHS:
4182 return verify_gimple_assign_single (stmt);
4184 case GIMPLE_UNARY_RHS:
4185 return verify_gimple_assign_unary (stmt);
4187 case GIMPLE_BINARY_RHS:
4188 return verify_gimple_assign_binary (stmt);
4190 case GIMPLE_TERNARY_RHS:
4191 return verify_gimple_assign_ternary (stmt);
4198 /* Verify the contents of a GIMPLE_RETURN STMT. Returns true when there
4199 is a problem, otherwise false. */
4202 verify_gimple_return (gimple stmt)
4204 tree op = gimple_return_retval (stmt);
4205 tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
4207 /* We cannot test for present return values as we do not fix up missing
4208 return values from the original source. */
4212 if (!is_gimple_val (op)
4213 && TREE_CODE (op) != RESULT_DECL)
4215 error ("invalid operand in return statement");
4216 debug_generic_stmt (op);
4220 if ((TREE_CODE (op) == RESULT_DECL
4221 && DECL_BY_REFERENCE (op))
4222 || (TREE_CODE (op) == SSA_NAME
4223 && SSA_NAME_VAR (op)
4224 && TREE_CODE (SSA_NAME_VAR (op)) == RESULT_DECL
4225 && DECL_BY_REFERENCE (SSA_NAME_VAR (op))))
4226 op = TREE_TYPE (op);
4228 if (!useless_type_conversion_p (restype, TREE_TYPE (op)))
4230 error ("invalid conversion in return statement");
4231 debug_generic_stmt (restype);
4232 debug_generic_stmt (TREE_TYPE (op));
4240 /* Verify the contents of a GIMPLE_GOTO STMT. Returns true when there
4241 is a problem, otherwise false. */
4244 verify_gimple_goto (gimple stmt)
4246 tree dest = gimple_goto_dest (stmt);
4248 /* ??? We have two canonical forms of direct goto destinations, a
4249 bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL. */
4250 if (TREE_CODE (dest) != LABEL_DECL
4251 && (!is_gimple_val (dest)
4252 || !POINTER_TYPE_P (TREE_TYPE (dest))))
4254 error ("goto destination is neither a label nor a pointer");
4261 /* Verify the contents of a GIMPLE_SWITCH STMT. Returns true when there
4262 is a problem, otherwise false. */
4265 verify_gimple_switch (gimple stmt)
4268 tree elt, prev_upper_bound = NULL_TREE;
4269 tree index_type, elt_type = NULL_TREE;
4271 if (!is_gimple_val (gimple_switch_index (stmt)))
4273 error ("invalid operand to switch statement");
4274 debug_generic_stmt (gimple_switch_index (stmt));
4278 index_type = TREE_TYPE (gimple_switch_index (stmt));
4279 if (! INTEGRAL_TYPE_P (index_type))
4281 error ("non-integral type switch statement");
4282 debug_generic_expr (index_type);
4286 elt = gimple_switch_label (stmt, 0);
4287 if (CASE_LOW (elt) != NULL_TREE || CASE_HIGH (elt) != NULL_TREE)
4289 error ("invalid default case label in switch statement");
4290 debug_generic_expr (elt);
4294 n = gimple_switch_num_labels (stmt);
4295 for (i = 1; i < n; i++)
4297 elt = gimple_switch_label (stmt, i);
4299 if (! CASE_LOW (elt))
4301 error ("invalid case label in switch statement");
4302 debug_generic_expr (elt);
4306 && ! tree_int_cst_lt (CASE_LOW (elt), CASE_HIGH (elt)))
4308 error ("invalid case range in switch statement");
4309 debug_generic_expr (elt);
4315 if (TREE_TYPE (CASE_LOW (elt)) != elt_type
4316 || (CASE_HIGH (elt) && TREE_TYPE (CASE_HIGH (elt)) != elt_type))
4318 error ("type mismatch for case label in switch statement");
4319 debug_generic_expr (elt);
4325 elt_type = TREE_TYPE (CASE_LOW (elt));
4326 if (TYPE_PRECISION (index_type) < TYPE_PRECISION (elt_type))
4328 error ("type precision mismatch in switch statement");
4333 if (prev_upper_bound)
4335 if (! tree_int_cst_lt (prev_upper_bound, CASE_LOW (elt)))
4337 error ("case labels not sorted in switch statement");
4342 prev_upper_bound = CASE_HIGH (elt);
4343 if (! prev_upper_bound)
4344 prev_upper_bound = CASE_LOW (elt);
4350 /* Verify a gimple debug statement STMT.
4351 Returns true if anything is wrong. */
4354 verify_gimple_debug (gimple stmt ATTRIBUTE_UNUSED)
4356 /* There isn't much that could be wrong in a gimple debug stmt. A
4357 gimple debug bind stmt, for example, maps a tree, that's usually
4358 a VAR_DECL or a PARM_DECL, but that could also be some scalarized
4359 component or member of an aggregate type, to another tree, that
4360 can be an arbitrary expression. These stmts expand into debug
4361 insns, and are converted to debug notes by var-tracking.c. */
4365 /* Verify a gimple label statement STMT.
4366 Returns true if anything is wrong. */
4369 verify_gimple_label (gimple stmt)
4371 tree decl = gimple_label_label (stmt);
4375 if (TREE_CODE (decl) != LABEL_DECL)
4377 if (!DECL_NONLOCAL (decl) && !FORCED_LABEL (decl)
4378 && DECL_CONTEXT (decl) != current_function_decl)
4380 error ("label's context is not the current function decl");
4384 uid = LABEL_DECL_UID (decl);
4387 || (*label_to_block_map_for_fn (cfun))[uid] != gimple_bb (stmt)))
4389 error ("incorrect entry in label_to_block_map");
4393 uid = EH_LANDING_PAD_NR (decl);
4396 eh_landing_pad lp = get_eh_landing_pad_from_number (uid);
4397 if (decl != lp->post_landing_pad)
4399 error ("incorrect setting of landing pad number");
4407 /* Verify the GIMPLE statement STMT. Returns true if there is an
4408 error, otherwise false. */
4411 verify_gimple_stmt (gimple stmt)
4413 switch (gimple_code (stmt))
4416 return verify_gimple_assign (stmt);
4419 return verify_gimple_label (stmt);
4422 return verify_gimple_call (stmt);
4425 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
4427 error ("invalid comparison code in gimple cond");
4430 if (!(!gimple_cond_true_label (stmt)
4431 || TREE_CODE (gimple_cond_true_label (stmt)) == LABEL_DECL)
4432 || !(!gimple_cond_false_label (stmt)
4433 || TREE_CODE (gimple_cond_false_label (stmt)) == LABEL_DECL))
4435 error ("invalid labels in gimple cond");
4439 return verify_gimple_comparison (boolean_type_node,
4440 gimple_cond_lhs (stmt),
4441 gimple_cond_rhs (stmt));
4444 return verify_gimple_goto (stmt);
4447 return verify_gimple_switch (stmt);
4450 return verify_gimple_return (stmt);
4455 case GIMPLE_TRANSACTION:
4456 return verify_gimple_transaction (stmt);
4458 /* Tuples that do not have tree operands. */
4460 case GIMPLE_PREDICT:
4462 case GIMPLE_EH_DISPATCH:
4463 case GIMPLE_EH_MUST_NOT_THROW:
4467 /* OpenMP directives are validated by the FE and never operated
4468 on by the optimizers. Furthermore, GIMPLE_OMP_FOR may contain
4469 non-gimple expressions when the main index variable has had
4470 its address taken. This does not affect the loop itself
4471 because the header of an GIMPLE_OMP_FOR is merely used to determine
4472 how to setup the parallel iteration. */
4476 return verify_gimple_debug (stmt);
4483 /* Verify the contents of a GIMPLE_PHI. Returns true if there is a problem,
4484 and false otherwise. */
4487 verify_gimple_phi (gimple phi)
4491 tree phi_result = gimple_phi_result (phi);
4496 error ("invalid PHI result");
4500 virtual_p = virtual_operand_p (phi_result);
4501 if (TREE_CODE (phi_result) != SSA_NAME
4503 && SSA_NAME_VAR (phi_result) != gimple_vop (cfun)))
4505 error ("invalid PHI result");
4509 for (i = 0; i < gimple_phi_num_args (phi); i++)
4511 tree t = gimple_phi_arg_def (phi, i);
4515 error ("missing PHI def");
4519 /* Addressable variables do have SSA_NAMEs but they
4520 are not considered gimple values. */
4521 else if ((TREE_CODE (t) == SSA_NAME
4522 && virtual_p != virtual_operand_p (t))
4524 && (TREE_CODE (t) != SSA_NAME
4525 || SSA_NAME_VAR (t) != gimple_vop (cfun)))
4527 && !is_gimple_val (t)))
4529 error ("invalid PHI argument");
4530 debug_generic_expr (t);
4533 #ifdef ENABLE_TYPES_CHECKING
4534 if (!useless_type_conversion_p (TREE_TYPE (phi_result), TREE_TYPE (t)))
4536 error ("incompatible types in PHI argument %u", i);
4537 debug_generic_stmt (TREE_TYPE (phi_result));
4538 debug_generic_stmt (TREE_TYPE (t));
4547 /* Verify the GIMPLE statements inside the sequence STMTS. */
4550 verify_gimple_in_seq_2 (gimple_seq stmts)
4552 gimple_stmt_iterator ittr;
4555 for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
4557 gimple stmt = gsi_stmt (ittr);
4559 switch (gimple_code (stmt))
4562 err |= verify_gimple_in_seq_2 (gimple_bind_body (stmt));
4566 err |= verify_gimple_in_seq_2 (gimple_try_eval (stmt));
4567 err |= verify_gimple_in_seq_2 (gimple_try_cleanup (stmt));
4570 case GIMPLE_EH_FILTER:
4571 err |= verify_gimple_in_seq_2 (gimple_eh_filter_failure (stmt));
4574 case GIMPLE_EH_ELSE:
4575 err |= verify_gimple_in_seq_2 (gimple_eh_else_n_body (stmt));
4576 err |= verify_gimple_in_seq_2 (gimple_eh_else_e_body (stmt));
4580 err |= verify_gimple_in_seq_2 (gimple_catch_handler (stmt));
4583 case GIMPLE_TRANSACTION:
4584 err |= verify_gimple_transaction (stmt);
4589 bool err2 = verify_gimple_stmt (stmt);
4591 debug_gimple_stmt (stmt);
4600 /* Verify the contents of a GIMPLE_TRANSACTION. Returns true if there
4601 is a problem, otherwise false. */
4604 verify_gimple_transaction (gimple stmt)
4606 tree lab = gimple_transaction_label (stmt);
4607 if (lab != NULL && TREE_CODE (lab) != LABEL_DECL)
4609 return verify_gimple_in_seq_2 (gimple_transaction_body (stmt));
4613 /* Verify the GIMPLE statements inside the statement list STMTS. */
4616 verify_gimple_in_seq (gimple_seq stmts)
4618 timevar_push (TV_TREE_STMT_VERIFY);
4619 if (verify_gimple_in_seq_2 (stmts))
4620 internal_error ("verify_gimple failed");
4621 timevar_pop (TV_TREE_STMT_VERIFY);
4624 /* Return true when the T can be shared. */
4627 tree_node_can_be_shared (tree t)
4629 if (IS_TYPE_OR_DECL_P (t)
4630 || is_gimple_min_invariant (t)
4631 || TREE_CODE (t) == SSA_NAME
4632 || t == error_mark_node
4633 || TREE_CODE (t) == IDENTIFIER_NODE)
4636 if (TREE_CODE (t) == CASE_LABEL_EXPR)
4645 /* Called via walk_tree. Verify tree sharing. */
4648 verify_node_sharing_1 (tree *tp, int *walk_subtrees, void *data)
4650 struct pointer_set_t *visited = (struct pointer_set_t *) data;
4652 if (tree_node_can_be_shared (*tp))
4654 *walk_subtrees = false;
4658 if (pointer_set_insert (visited, *tp))
4664 /* Called via walk_gimple_stmt. Verify tree sharing. */
4667 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4669 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4670 return verify_node_sharing_1 (tp, walk_subtrees, wi->info);
4673 static bool eh_error_found;
4675 verify_eh_throw_stmt_node (void **slot, void *data)
4677 struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4678 struct pointer_set_t *visited = (struct pointer_set_t *) data;
4680 if (!pointer_set_contains (visited, node->stmt))
4682 error ("dead STMT in EH table");
4683 debug_gimple_stmt (node->stmt);
4684 eh_error_found = true;
4689 /* Verify if the location LOCs block is in BLOCKS. */
4692 verify_location (pointer_set_t *blocks, location_t loc)
4694 tree block = LOCATION_BLOCK (loc);
4695 if (block != NULL_TREE
4696 && !pointer_set_contains (blocks, block))
4698 error ("location references block not in block tree");
4701 if (block != NULL_TREE)
4702 return verify_location (blocks, BLOCK_SOURCE_LOCATION (block));
4706 /* Called via walk_tree. Verify that expressions have no blocks. */
4709 verify_expr_no_block (tree *tp, int *walk_subtrees, void *)
4713 *walk_subtrees = false;
4717 location_t loc = EXPR_LOCATION (*tp);
4718 if (LOCATION_BLOCK (loc) != NULL)
4724 /* Called via walk_tree. Verify locations of expressions. */
4727 verify_expr_location_1 (tree *tp, int *walk_subtrees, void *data)
4729 struct pointer_set_t *blocks = (struct pointer_set_t *) data;
4731 if (TREE_CODE (*tp) == VAR_DECL
4732 && DECL_HAS_DEBUG_EXPR_P (*tp))
4734 tree t = DECL_DEBUG_EXPR (*tp);
4735 tree addr = walk_tree (&t, verify_expr_no_block, NULL, NULL);
4739 if ((TREE_CODE (*tp) == VAR_DECL
4740 || TREE_CODE (*tp) == PARM_DECL
4741 || TREE_CODE (*tp) == RESULT_DECL)
4742 && DECL_HAS_VALUE_EXPR_P (*tp))
4744 tree t = DECL_VALUE_EXPR (*tp);
4745 tree addr = walk_tree (&t, verify_expr_no_block, NULL, NULL);
4752 *walk_subtrees = false;
4756 location_t loc = EXPR_LOCATION (*tp);
4757 if (verify_location (blocks, loc))
4763 /* Called via walk_gimple_op. Verify locations of expressions. */
4766 verify_expr_location (tree *tp, int *walk_subtrees, void *data)
4768 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4769 return verify_expr_location_1 (tp, walk_subtrees, wi->info);
4772 /* Insert all subblocks of BLOCK into BLOCKS and recurse. */
4775 collect_subblocks (pointer_set_t *blocks, tree block)
4778 for (t = BLOCK_SUBBLOCKS (block); t; t = BLOCK_CHAIN (t))
4780 pointer_set_insert (blocks, t);
4781 collect_subblocks (blocks, t);
4785 /* Verify the GIMPLE statements in the CFG of FN. */
4788 verify_gimple_in_cfg (struct function *fn)
4792 struct pointer_set_t *visited, *visited_stmts, *blocks;
4794 timevar_push (TV_TREE_STMT_VERIFY);
4795 visited = pointer_set_create ();
4796 visited_stmts = pointer_set_create ();
4798 /* Collect all BLOCKs referenced by the BLOCK tree of FN. */
4799 blocks = pointer_set_create ();
4800 if (DECL_INITIAL (fn->decl))
4802 pointer_set_insert (blocks, DECL_INITIAL (fn->decl));
4803 collect_subblocks (blocks, DECL_INITIAL (fn->decl));
4806 FOR_EACH_BB_FN (bb, fn)
4808 gimple_stmt_iterator gsi;
4810 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4812 gimple phi = gsi_stmt (gsi);
4816 pointer_set_insert (visited_stmts, phi);
4818 if (gimple_bb (phi) != bb)
4820 error ("gimple_bb (phi) is set to a wrong basic block");
4824 err2 |= verify_gimple_phi (phi);
4826 /* Only PHI arguments have locations. */
4827 if (gimple_location (phi) != UNKNOWN_LOCATION)
4829 error ("PHI node with location");
4833 for (i = 0; i < gimple_phi_num_args (phi); i++)
4835 tree arg = gimple_phi_arg_def (phi, i);
4836 tree addr = walk_tree (&arg, verify_node_sharing_1,
4840 error ("incorrect sharing of tree nodes");
4841 debug_generic_expr (addr);
4844 location_t loc = gimple_phi_arg_location (phi, i);
4845 if (virtual_operand_p (gimple_phi_result (phi))
4846 && loc != UNKNOWN_LOCATION)
4848 error ("virtual PHI with argument locations");
4851 addr = walk_tree (&arg, verify_expr_location_1, blocks, NULL);
4854 debug_generic_expr (addr);
4857 err2 |= verify_location (blocks, loc);
4861 debug_gimple_stmt (phi);
4865 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4867 gimple stmt = gsi_stmt (gsi);
4869 struct walk_stmt_info wi;
4873 pointer_set_insert (visited_stmts, stmt);
4875 if (gimple_bb (stmt) != bb)
4877 error ("gimple_bb (stmt) is set to a wrong basic block");
4881 err2 |= verify_gimple_stmt (stmt);
4882 err2 |= verify_location (blocks, gimple_location (stmt));
4884 memset (&wi, 0, sizeof (wi));
4885 wi.info = (void *) visited;
4886 addr = walk_gimple_op (stmt, verify_node_sharing, &wi);
4889 error ("incorrect sharing of tree nodes");
4890 debug_generic_expr (addr);
4894 memset (&wi, 0, sizeof (wi));
4895 wi.info = (void *) blocks;
4896 addr = walk_gimple_op (stmt, verify_expr_location, &wi);
4899 debug_generic_expr (addr);
4903 /* ??? Instead of not checking these stmts at all the walker
4904 should know its context via wi. */
4905 if (!is_gimple_debug (stmt)
4906 && !is_gimple_omp (stmt))
4908 memset (&wi, 0, sizeof (wi));
4909 addr = walk_gimple_op (stmt, verify_expr, &wi);
4912 debug_generic_expr (addr);
4913 inform (gimple_location (stmt), "in statement");
4918 /* If the statement is marked as part of an EH region, then it is
4919 expected that the statement could throw. Verify that when we
4920 have optimizations that simplify statements such that we prove
4921 that they cannot throw, that we update other data structures
4923 lp_nr = lookup_stmt_eh_lp (stmt);
4926 if (!stmt_could_throw_p (stmt))
4928 error ("statement marked for throw, but doesn%'t");
4932 && !gsi_one_before_end_p (gsi)
4933 && stmt_can_throw_internal (stmt))
4935 error ("statement marked for throw in middle of block");
4941 debug_gimple_stmt (stmt);
4946 eh_error_found = false;
4947 if (get_eh_throw_stmt_table (cfun))
4948 htab_traverse (get_eh_throw_stmt_table (cfun),
4949 verify_eh_throw_stmt_node,
4952 if (err || eh_error_found)
4953 internal_error ("verify_gimple failed");
4955 pointer_set_destroy (visited);
4956 pointer_set_destroy (visited_stmts);
4957 pointer_set_destroy (blocks);
4958 verify_histograms ();
4959 timevar_pop (TV_TREE_STMT_VERIFY);
4963 /* Verifies that the flow information is OK. */
4966 gimple_verify_flow_info (void)
4970 gimple_stmt_iterator gsi;
4975 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->il.gimple.seq
4976 || ENTRY_BLOCK_PTR_FOR_FN (cfun)->il.gimple.phi_nodes)
4978 error ("ENTRY_BLOCK has IL associated with it");
4982 if (EXIT_BLOCK_PTR_FOR_FN (cfun)->il.gimple.seq
4983 || EXIT_BLOCK_PTR_FOR_FN (cfun)->il.gimple.phi_nodes)
4985 error ("EXIT_BLOCK has IL associated with it");
4989 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4990 if (e->flags & EDGE_FALLTHRU)
4992 error ("fallthru to exit from bb %d", e->src->index);
4996 FOR_EACH_BB_FN (bb, cfun)
4998 bool found_ctrl_stmt = false;
5002 /* Skip labels on the start of basic block. */
5003 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5006 gimple prev_stmt = stmt;
5008 stmt = gsi_stmt (gsi);
5010 if (gimple_code (stmt) != GIMPLE_LABEL)
5013 label = gimple_label_label (stmt);
5014 if (prev_stmt && DECL_NONLOCAL (label))
5016 error ("nonlocal label ");
5017 print_generic_expr (stderr, label, 0);
5018 fprintf (stderr, " is not first in a sequence of labels in bb %d",
5023 if (prev_stmt && EH_LANDING_PAD_NR (label) != 0)
5025 error ("EH landing pad label ");
5026 print_generic_expr (stderr, label, 0);
5027 fprintf (stderr, " is not first in a sequence of labels in bb %d",
5032 if (label_to_block (label) != bb)
5035 print_generic_expr (stderr, label, 0);
5036 fprintf (stderr, " to block does not match in bb %d",
5041 if (decl_function_context (label) != current_function_decl)
5044 print_generic_expr (stderr, label, 0);
5045 fprintf (stderr, " has incorrect context in bb %d",
5051 /* Verify that body of basic block BB is free of control flow. */
5052 for (; !gsi_end_p (gsi); gsi_next (&gsi))
5054 gimple stmt = gsi_stmt (gsi);
5056 if (found_ctrl_stmt)
5058 error ("control flow in the middle of basic block %d",
5063 if (stmt_ends_bb_p (stmt))
5064 found_ctrl_stmt = true;
5066 if (gimple_code (stmt) == GIMPLE_LABEL)
5069 print_generic_expr (stderr, gimple_label_label (stmt), 0);
5070 fprintf (stderr, " in the middle of basic block %d", bb->index);
5075 gsi = gsi_last_bb (bb);
5076 if (gsi_end_p (gsi))
5079 stmt = gsi_stmt (gsi);
5081 if (gimple_code (stmt) == GIMPLE_LABEL)
5084 err |= verify_eh_edges (stmt);
5086 if (is_ctrl_stmt (stmt))
5088 FOR_EACH_EDGE (e, ei, bb->succs)
5089 if (e->flags & EDGE_FALLTHRU)
5091 error ("fallthru edge after a control statement in bb %d",
5097 if (gimple_code (stmt) != GIMPLE_COND)
5099 /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
5100 after anything else but if statement. */
5101 FOR_EACH_EDGE (e, ei, bb->succs)
5102 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
5104 error ("true/false edge after a non-GIMPLE_COND in bb %d",
5110 switch (gimple_code (stmt))
5117 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
5121 || !(true_edge->flags & EDGE_TRUE_VALUE)
5122 || !(false_edge->flags & EDGE_FALSE_VALUE)
5123 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
5124 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
5125 || EDGE_COUNT (bb->succs) >= 3)
5127 error ("wrong outgoing edge flags at end of bb %d",
5135 if (simple_goto_p (stmt))
5137 error ("explicit goto at end of bb %d", bb->index);
5142 /* FIXME. We should double check that the labels in the
5143 destination blocks have their address taken. */
5144 FOR_EACH_EDGE (e, ei, bb->succs)
5145 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
5146 | EDGE_FALSE_VALUE))
5147 || !(e->flags & EDGE_ABNORMAL))
5149 error ("wrong outgoing edge flags at end of bb %d",
5157 if (!gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
5159 /* ... fallthru ... */
5161 if (!single_succ_p (bb)
5162 || (single_succ_edge (bb)->flags
5163 & (EDGE_FALLTHRU | EDGE_ABNORMAL
5164 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
5166 error ("wrong outgoing edge flags at end of bb %d", bb->index);
5169 if (single_succ (bb) != EXIT_BLOCK_PTR_FOR_FN (cfun))
5171 error ("return edge does not point to exit in bb %d",
5183 n = gimple_switch_num_labels (stmt);
5185 /* Mark all the destination basic blocks. */
5186 for (i = 0; i < n; ++i)
5188 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
5189 basic_block label_bb = label_to_block (lab);
5190 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
5191 label_bb->aux = (void *)1;
5194 /* Verify that the case labels are sorted. */
5195 prev = gimple_switch_label (stmt, 0);
5196 for (i = 1; i < n; ++i)
5198 tree c = gimple_switch_label (stmt, i);
5201 error ("found default case not at the start of "
5207 && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
5209 error ("case labels not sorted: ");
5210 print_generic_expr (stderr, prev, 0);
5211 fprintf (stderr," is greater than ");
5212 print_generic_expr (stderr, c, 0);
5213 fprintf (stderr," but comes before it.\n");
5218 /* VRP will remove the default case if it can prove it will
5219 never be executed. So do not verify there always exists
5220 a default case here. */
5222 FOR_EACH_EDGE (e, ei, bb->succs)
5226 error ("extra outgoing edge %d->%d",
5227 bb->index, e->dest->index);
5231 e->dest->aux = (void *)2;
5232 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
5233 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
5235 error ("wrong outgoing edge flags at end of bb %d",
5241 /* Check that we have all of them. */
5242 for (i = 0; i < n; ++i)
5244 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
5245 basic_block label_bb = label_to_block (lab);
5247 if (label_bb->aux != (void *)2)
5249 error ("missing edge %i->%i", bb->index, label_bb->index);
5254 FOR_EACH_EDGE (e, ei, bb->succs)
5255 e->dest->aux = (void *)0;
5259 case GIMPLE_EH_DISPATCH:
5260 err |= verify_eh_dispatch_edge (stmt);
5268 if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
5269 verify_dominators (CDI_DOMINATORS);
5275 /* Updates phi nodes after creating a forwarder block joined
5276 by edge FALLTHRU. */
5279 gimple_make_forwarder_block (edge fallthru)
5283 basic_block dummy, bb;
5285 gimple_stmt_iterator gsi;
5287 dummy = fallthru->src;
5288 bb = fallthru->dest;
5290 if (single_pred_p (bb))
5293 /* If we redirected a branch we must create new PHI nodes at the
5295 for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
5297 gimple phi, new_phi;
5299 phi = gsi_stmt (gsi);
5300 var = gimple_phi_result (phi);
5301 new_phi = create_phi_node (var, bb);
5302 gimple_phi_set_result (phi, copy_ssa_name (var, phi));
5303 add_phi_arg (new_phi, gimple_phi_result (phi), fallthru,
5307 /* Add the arguments we have stored on edges. */
5308 FOR_EACH_EDGE (e, ei, bb->preds)
5313 flush_pending_stmts (e);
5318 /* Return a non-special label in the head of basic block BLOCK.
5319 Create one if it doesn't exist. */
5322 gimple_block_label (basic_block bb)
5324 gimple_stmt_iterator i, s = gsi_start_bb (bb);
5329 for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
5331 stmt = gsi_stmt (i);
5332 if (gimple_code (stmt) != GIMPLE_LABEL)
5334 label = gimple_label_label (stmt);
5335 if (!DECL_NONLOCAL (label))
5338 gsi_move_before (&i, &s);
5343 label = create_artificial_label (UNKNOWN_LOCATION);
5344 stmt = gimple_build_label (label);
5345 gsi_insert_before (&s, stmt, GSI_NEW_STMT);
5350 /* Attempt to perform edge redirection by replacing a possibly complex
5351 jump instruction by a goto or by removing the jump completely.
5352 This can apply only if all edges now point to the same block. The
5353 parameters and return values are equivalent to
5354 redirect_edge_and_branch. */
5357 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
5359 basic_block src = e->src;
5360 gimple_stmt_iterator i;
5363 /* We can replace or remove a complex jump only when we have exactly
5365 if (EDGE_COUNT (src->succs) != 2
5366 /* Verify that all targets will be TARGET. Specifically, the
5367 edge that is not E must also go to TARGET. */
5368 || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
5371 i = gsi_last_bb (src);
5375 stmt = gsi_stmt (i);
5377 if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
5379 gsi_remove (&i, true);
5380 e = ssa_redirect_edge (e, target);
5381 e->flags = EDGE_FALLTHRU;
5389 /* Redirect E to DEST. Return NULL on failure. Otherwise, return the
5390 edge representing the redirected branch. */
5393 gimple_redirect_edge_and_branch (edge e, basic_block dest)
5395 basic_block bb = e->src;
5396 gimple_stmt_iterator gsi;
5400 if (e->flags & EDGE_ABNORMAL)
5403 if (e->dest == dest)
5406 if (e->flags & EDGE_EH)
5407 return redirect_eh_edge (e, dest);
5409 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
5411 ret = gimple_try_redirect_by_replacing_jump (e, dest);
5416 gsi = gsi_last_bb (bb);
5417 stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
5419 switch (stmt ? gimple_code (stmt) : GIMPLE_ERROR_MARK)
5422 /* For COND_EXPR, we only need to redirect the edge. */
5426 /* No non-abnormal edges should lead from a non-simple goto, and
5427 simple ones should be represented implicitly. */
5432 tree label = gimple_block_label (dest);
5433 tree cases = get_cases_for_edge (e, stmt);
5435 /* If we have a list of cases associated with E, then use it
5436 as it's a lot faster than walking the entire case vector. */
5439 edge e2 = find_edge (e->src, dest);
5446 CASE_LABEL (cases) = label;
5447 cases = CASE_CHAIN (cases);
5450 /* If there was already an edge in the CFG, then we need
5451 to move all the cases associated with E to E2. */
5454 tree cases2 = get_cases_for_edge (e2, stmt);
5456 CASE_CHAIN (last) = CASE_CHAIN (cases2);
5457 CASE_CHAIN (cases2) = first;
5459 bitmap_set_bit (touched_switch_bbs, gimple_bb (stmt)->index);
5463 size_t i, n = gimple_switch_num_labels (stmt);
5465 for (i = 0; i < n; i++)
5467 tree elt = gimple_switch_label (stmt, i);
5468 if (label_to_block (CASE_LABEL (elt)) == e->dest)
5469 CASE_LABEL (elt) = label;
5477 int i, n = gimple_asm_nlabels (stmt);
5480 for (i = 0; i < n; ++i)
5482 tree cons = gimple_asm_label_op (stmt, i);
5483 if (label_to_block (TREE_VALUE (cons)) == e->dest)
5486 label = gimple_block_label (dest);
5487 TREE_VALUE (cons) = label;
5491 /* If we didn't find any label matching the former edge in the
5492 asm labels, we must be redirecting the fallthrough
5494 gcc_assert (label || (e->flags & EDGE_FALLTHRU));
5499 gsi_remove (&gsi, true);
5500 e->flags |= EDGE_FALLTHRU;
5503 case GIMPLE_OMP_RETURN:
5504 case GIMPLE_OMP_CONTINUE:
5505 case GIMPLE_OMP_SECTIONS_SWITCH:
5506 case GIMPLE_OMP_FOR:
5507 /* The edges from OMP constructs can be simply redirected. */
5510 case GIMPLE_EH_DISPATCH:
5511 if (!(e->flags & EDGE_FALLTHRU))
5512 redirect_eh_dispatch_edge (stmt, e, dest);
5515 case GIMPLE_TRANSACTION:
5516 /* The ABORT edge has a stored label associated with it, otherwise
5517 the edges are simply redirectable. */
5519 gimple_transaction_set_label (stmt, gimple_block_label (dest));
5523 /* Otherwise it must be a fallthru edge, and we don't need to
5524 do anything besides redirecting it. */
5525 gcc_assert (e->flags & EDGE_FALLTHRU);
5529 /* Update/insert PHI nodes as necessary. */
5531 /* Now update the edges in the CFG. */
5532 e = ssa_redirect_edge (e, dest);
5537 /* Returns true if it is possible to remove edge E by redirecting
5538 it to the destination of the other edge from E->src. */
5541 gimple_can_remove_branch_p (const_edge e)
5543 if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
5549 /* Simple wrapper, as we can always redirect fallthru edges. */
5552 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
5554 e = gimple_redirect_edge_and_branch (e, dest);
5561 /* Splits basic block BB after statement STMT (but at least after the
5562 labels). If STMT is NULL, BB is split just after the labels. */
5565 gimple_split_block (basic_block bb, void *stmt)
5567 gimple_stmt_iterator gsi;
5568 gimple_stmt_iterator gsi_tgt;
5575 new_bb = create_empty_bb (bb);
5577 /* Redirect the outgoing edges. */
5578 new_bb->succs = bb->succs;
5580 FOR_EACH_EDGE (e, ei, new_bb->succs)
5583 if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
5586 /* Move everything from GSI to the new basic block. */
5587 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5589 act = gsi_stmt (gsi);
5590 if (gimple_code (act) == GIMPLE_LABEL)
5603 if (gsi_end_p (gsi))
5606 /* Split the statement list - avoid re-creating new containers as this
5607 brings ugly quadratic memory consumption in the inliner.
5608 (We are still quadratic since we need to update stmt BB pointers,
5610 gsi_split_seq_before (&gsi, &list);
5611 set_bb_seq (new_bb, list);
5612 for (gsi_tgt = gsi_start (list);
5613 !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
5614 gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
5620 /* Moves basic block BB after block AFTER. */
5623 gimple_move_block_after (basic_block bb, basic_block after)
5625 if (bb->prev_bb == after)
5629 link_block (bb, after);
5635 /* Return TRUE if block BB has no executable statements, otherwise return
5639 gimple_empty_block_p (basic_block bb)
5641 /* BB must have no executable statements. */
5642 gimple_stmt_iterator gsi = gsi_after_labels (bb);
5645 if (gsi_end_p (gsi))
5647 if (is_gimple_debug (gsi_stmt (gsi)))
5648 gsi_next_nondebug (&gsi);
5649 return gsi_end_p (gsi);
5653 /* Split a basic block if it ends with a conditional branch and if the
5654 other part of the block is not empty. */
5657 gimple_split_block_before_cond_jump (basic_block bb)
5659 gimple last, split_point;
5660 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
5661 if (gsi_end_p (gsi))
5663 last = gsi_stmt (gsi);
5664 if (gimple_code (last) != GIMPLE_COND
5665 && gimple_code (last) != GIMPLE_SWITCH)
5667 gsi_prev_nondebug (&gsi);
5668 split_point = gsi_stmt (gsi);
5669 return split_block (bb, split_point)->dest;
5673 /* Return true if basic_block can be duplicated. */
5676 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5681 /* Create a duplicate of the basic block BB. NOTE: This does not
5682 preserve SSA form. */
5685 gimple_duplicate_bb (basic_block bb)
5688 gimple_stmt_iterator gsi, gsi_tgt;
5689 gimple_seq phis = phi_nodes (bb);
5690 gimple phi, stmt, copy;
5692 new_bb = create_empty_bb (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
5694 /* Copy the PHI nodes. We ignore PHI node arguments here because
5695 the incoming edges have not been setup yet. */
5696 for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
5698 phi = gsi_stmt (gsi);
5699 copy = create_phi_node (NULL_TREE, new_bb);
5700 create_new_def_for (gimple_phi_result (phi), copy,
5701 gimple_phi_result_ptr (copy));
5702 gimple_set_uid (copy, gimple_uid (phi));
5705 gsi_tgt = gsi_start_bb (new_bb);
5706 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5708 def_operand_p def_p;
5709 ssa_op_iter op_iter;
5712 stmt = gsi_stmt (gsi);
5713 if (gimple_code (stmt) == GIMPLE_LABEL)
5716 /* Don't duplicate label debug stmts. */
5717 if (gimple_debug_bind_p (stmt)
5718 && TREE_CODE (gimple_debug_bind_get_var (stmt))
5722 /* Create a new copy of STMT and duplicate STMT's virtual
5724 copy = gimple_copy (stmt);
5725 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
5727 maybe_duplicate_eh_stmt (copy, stmt);
5728 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5730 /* When copying around a stmt writing into a local non-user
5731 aggregate, make sure it won't share stack slot with other
5733 lhs = gimple_get_lhs (stmt);
5734 if (lhs && TREE_CODE (lhs) != SSA_NAME)
5736 tree base = get_base_address (lhs);
5738 && (TREE_CODE (base) == VAR_DECL
5739 || TREE_CODE (base) == RESULT_DECL)
5740 && DECL_IGNORED_P (base)
5741 && !TREE_STATIC (base)
5742 && !DECL_EXTERNAL (base)
5743 && (TREE_CODE (base) != VAR_DECL
5744 || !DECL_HAS_VALUE_EXPR_P (base)))
5745 DECL_NONSHAREABLE (base) = 1;
5748 /* Create new names for all the definitions created by COPY and
5749 add replacement mappings for each new name. */
5750 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5751 create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5757 /* Adds phi node arguments for edge E_COPY after basic block duplication. */
5760 add_phi_args_after_copy_edge (edge e_copy)
5762 basic_block bb, bb_copy = e_copy->src, dest;
5765 gimple phi, phi_copy;
5767 gimple_stmt_iterator psi, psi_copy;
5769 if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
5772 bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5774 if (e_copy->dest->flags & BB_DUPLICATED)
5775 dest = get_bb_original (e_copy->dest);
5777 dest = e_copy->dest;
5779 e = find_edge (bb, dest);
5782 /* During loop unrolling the target of the latch edge is copied.
5783 In this case we are not looking for edge to dest, but to
5784 duplicated block whose original was dest. */
5785 FOR_EACH_EDGE (e, ei, bb->succs)
5787 if ((e->dest->flags & BB_DUPLICATED)
5788 && get_bb_original (e->dest) == dest)
5792 gcc_assert (e != NULL);
5795 for (psi = gsi_start_phis (e->dest),
5796 psi_copy = gsi_start_phis (e_copy->dest);
5798 gsi_next (&psi), gsi_next (&psi_copy))
5800 phi = gsi_stmt (psi);
5801 phi_copy = gsi_stmt (psi_copy);
5802 def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5803 add_phi_arg (phi_copy, def, e_copy,
5804 gimple_phi_arg_location_from_edge (phi, e));
5809 /* Basic block BB_COPY was created by code duplication. Add phi node
5810 arguments for edges going out of BB_COPY. The blocks that were
5811 duplicated have BB_DUPLICATED set. */
5814 add_phi_args_after_copy_bb (basic_block bb_copy)
5819 FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5821 add_phi_args_after_copy_edge (e_copy);
5825 /* Blocks in REGION_COPY array of length N_REGION were created by
5826 duplication of basic blocks. Add phi node arguments for edges
5827 going from these blocks. If E_COPY is not NULL, also add
5828 phi node arguments for its destination.*/
5831 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5836 for (i = 0; i < n_region; i++)
5837 region_copy[i]->flags |= BB_DUPLICATED;
5839 for (i = 0; i < n_region; i++)
5840 add_phi_args_after_copy_bb (region_copy[i]);
5842 add_phi_args_after_copy_edge (e_copy);
5844 for (i = 0; i < n_region; i++)
5845 region_copy[i]->flags &= ~BB_DUPLICATED;
5848 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5849 important exit edge EXIT. By important we mean that no SSA name defined
5850 inside region is live over the other exit edges of the region. All entry
5851 edges to the region must go to ENTRY->dest. The edge ENTRY is redirected
5852 to the duplicate of the region. Dominance and loop information is
5853 updated if UPDATE_DOMINANCE is true, but not the SSA web. If
5854 UPDATE_DOMINANCE is false then we assume that the caller will update the
5855 dominance information after calling this function. The new basic
5856 blocks are stored to REGION_COPY in the same order as they had in REGION,
5857 provided that REGION_COPY is not NULL.
5858 The function returns false if it is unable to copy the region,
5862 gimple_duplicate_sese_region (edge entry, edge exit,
5863 basic_block *region, unsigned n_region,
5864 basic_block *region_copy,
5865 bool update_dominance)
5868 bool free_region_copy = false, copying_header = false;
5869 struct loop *loop = entry->dest->loop_father;
5871 vec<basic_block> doms;
5873 int total_freq = 0, entry_freq = 0;
5874 gcov_type total_count = 0, entry_count = 0;
5876 if (!can_copy_bbs_p (region, n_region))
5879 /* Some sanity checking. Note that we do not check for all possible
5880 missuses of the functions. I.e. if you ask to copy something weird,
5881 it will work, but the state of structures probably will not be
5883 for (i = 0; i < n_region; i++)
5885 /* We do not handle subloops, i.e. all the blocks must belong to the
5887 if (region[i]->loop_father != loop)
5890 if (region[i] != entry->dest
5891 && region[i] == loop->header)
5895 /* In case the function is used for loop header copying (which is the primary
5896 use), ensure that EXIT and its copy will be new latch and entry edges. */
5897 if (loop->header == entry->dest)
5899 copying_header = true;
5901 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5904 for (i = 0; i < n_region; i++)
5905 if (region[i] != exit->src
5906 && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5910 initialize_original_copy_tables ();
5913 set_loop_copy (loop, loop_outer (loop));
5915 set_loop_copy (loop, loop);
5919 region_copy = XNEWVEC (basic_block, n_region);
5920 free_region_copy = true;
5923 /* Record blocks outside the region that are dominated by something
5925 if (update_dominance)
5928 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5931 if (entry->dest->count)
5933 total_count = entry->dest->count;
5934 entry_count = entry->count;
5935 /* Fix up corner cases, to avoid division by zero or creation of negative
5937 if (entry_count > total_count)
5938 entry_count = total_count;
5942 total_freq = entry->dest->frequency;
5943 entry_freq = EDGE_FREQUENCY (entry);
5944 /* Fix up corner cases, to avoid division by zero or creation of negative
5946 if (total_freq == 0)
5948 else if (entry_freq > total_freq)
5949 entry_freq = total_freq;
5952 copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5953 split_edge_bb_loc (entry), update_dominance);
5956 scale_bbs_frequencies_gcov_type (region, n_region,
5957 total_count - entry_count,
5959 scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5964 scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5966 scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5971 loop->header = exit->dest;
5972 loop->latch = exit->src;
5975 /* Redirect the entry and add the phi node arguments. */
5976 redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5977 gcc_assert (redirected != NULL);
5978 flush_pending_stmts (entry);
5980 /* Concerning updating of dominators: We must recount dominators
5981 for entry block and its copy. Anything that is outside of the
5982 region, but was dominated by something inside needs recounting as
5984 if (update_dominance)
5986 set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5987 doms.safe_push (get_bb_original (entry->dest));
5988 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5992 /* Add the other PHI node arguments. */
5993 add_phi_args_after_copy (region_copy, n_region, NULL);
5995 if (free_region_copy)
5998 free_original_copy_tables ();
6002 /* Checks if BB is part of the region defined by N_REGION BBS. */
6004 bb_part_of_region_p (basic_block bb, basic_block* bbs, unsigned n_region)
6008 for (n = 0; n < n_region; n++)
6016 /* Duplicates REGION consisting of N_REGION blocks. The new blocks
6017 are stored to REGION_COPY in the same order in that they appear
6018 in REGION, if REGION_COPY is not NULL. ENTRY is the entry to
6019 the region, EXIT an exit from it. The condition guarding EXIT
6020 is moved to ENTRY. Returns true if duplication succeeds, false
6046 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
6047 basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
6048 basic_block *region_copy ATTRIBUTE_UNUSED)
6051 bool free_region_copy = false;
6052 struct loop *loop = exit->dest->loop_father;
6053 struct loop *orig_loop = entry->dest->loop_father;
6054 basic_block switch_bb, entry_bb, nentry_bb;
6055 vec<basic_block> doms;
6056 int total_freq = 0, exit_freq = 0;
6057 gcov_type total_count = 0, exit_count = 0;
6058 edge exits[2], nexits[2], e;
6059 gimple_stmt_iterator gsi;
6062 basic_block exit_bb;
6063 gimple_stmt_iterator psi;
6066 struct loop *target, *aloop, *cloop;
6068 gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
6070 exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
6072 if (!can_copy_bbs_p (region, n_region))
6075 initialize_original_copy_tables ();
6076 set_loop_copy (orig_loop, loop);
6079 for (aloop = orig_loop->inner; aloop; aloop = aloop->next)
6081 if (bb_part_of_region_p (aloop->header, region, n_region))
6083 cloop = duplicate_loop (aloop, target);
6084 duplicate_subloops (aloop, cloop);
6090 region_copy = XNEWVEC (basic_block, n_region);
6091 free_region_copy = true;
6094 gcc_assert (!need_ssa_update_p (cfun));
6096 /* Record blocks outside the region that are dominated by something
6098 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
6100 if (exit->src->count)
6102 total_count = exit->src->count;
6103 exit_count = exit->count;
6104 /* Fix up corner cases, to avoid division by zero or creation of negative
6106 if (exit_count > total_count)
6107 exit_count = total_count;
6111 total_freq = exit->src->frequency;
6112 exit_freq = EDGE_FREQUENCY (exit);
6113 /* Fix up corner cases, to avoid division by zero or creation of negative
6115 if (total_freq == 0)
6117 if (exit_freq > total_freq)
6118 exit_freq = total_freq;
6121 copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
6122 split_edge_bb_loc (exit), true);
6125 scale_bbs_frequencies_gcov_type (region, n_region,
6126 total_count - exit_count,
6128 scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
6133 scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
6135 scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
6138 /* Create the switch block, and put the exit condition to it. */
6139 entry_bb = entry->dest;
6140 nentry_bb = get_bb_copy (entry_bb);
6141 if (!last_stmt (entry->src)
6142 || !stmt_ends_bb_p (last_stmt (entry->src)))
6143 switch_bb = entry->src;
6145 switch_bb = split_edge (entry);
6146 set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
6148 gsi = gsi_last_bb (switch_bb);
6149 cond_stmt = last_stmt (exit->src);
6150 gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
6151 cond_stmt = gimple_copy (cond_stmt);
6153 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
6155 sorig = single_succ_edge (switch_bb);
6156 sorig->flags = exits[1]->flags;
6157 snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
6159 /* Register the new edge from SWITCH_BB in loop exit lists. */
6160 rescan_loop_exit (snew, true, false);
6162 /* Add the PHI node arguments. */
6163 add_phi_args_after_copy (region_copy, n_region, snew);
6165 /* Get rid of now superfluous conditions and associated edges (and phi node
6167 exit_bb = exit->dest;
6169 e = redirect_edge_and_branch (exits[0], exits[1]->dest);
6170 PENDING_STMT (e) = NULL;
6172 /* The latch of ORIG_LOOP was copied, and so was the backedge
6173 to the original header. We redirect this backedge to EXIT_BB. */
6174 for (i = 0; i < n_region; i++)
6175 if (get_bb_original (region_copy[i]) == orig_loop->latch)
6177 gcc_assert (single_succ_edge (region_copy[i]));
6178 e = redirect_edge_and_branch (single_succ_edge (region_copy[i]), exit_bb);
6179 PENDING_STMT (e) = NULL;
6180 for (psi = gsi_start_phis (exit_bb);
6184 phi = gsi_stmt (psi);
6185 def = PHI_ARG_DEF (phi, nexits[0]->dest_idx);
6186 add_phi_arg (phi, def, e, gimple_phi_arg_location_from_edge (phi, e));
6189 e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
6190 PENDING_STMT (e) = NULL;
6192 /* Anything that is outside of the region, but was dominated by something
6193 inside needs to update dominance info. */
6194 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
6196 /* Update the SSA web. */
6197 update_ssa (TODO_update_ssa);
6199 if (free_region_copy)
6202 free_original_copy_tables ();
6206 /* Add all the blocks dominated by ENTRY to the array BBS_P. Stop
6207 adding blocks when the dominator traversal reaches EXIT. This
6208 function silently assumes that ENTRY strictly dominates EXIT. */
6211 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
6212 vec<basic_block> *bbs_p)
6216 for (son = first_dom_son (CDI_DOMINATORS, entry);
6218 son = next_dom_son (CDI_DOMINATORS, son))
6220 bbs_p->safe_push (son);
6222 gather_blocks_in_sese_region (son, exit, bbs_p);
6226 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
6227 The duplicates are recorded in VARS_MAP. */
6230 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
6233 tree t = *tp, new_t;
6234 struct function *f = DECL_STRUCT_FUNCTION (to_context);
6237 if (DECL_CONTEXT (t) == to_context)
6240 loc = pointer_map_contains (vars_map, t);
6244 loc = pointer_map_insert (vars_map, t);
6248 new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
6249 add_local_decl (f, new_t);
6253 gcc_assert (TREE_CODE (t) == CONST_DECL);
6254 new_t = copy_node (t);
6256 DECL_CONTEXT (new_t) = to_context;
6261 new_t = (tree) *loc;
6267 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
6268 VARS_MAP maps old ssa names and var_decls to the new ones. */
6271 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
6277 gcc_assert (!virtual_operand_p (name));
6279 loc = pointer_map_contains (vars_map, name);
6283 tree decl = SSA_NAME_VAR (name);
6286 replace_by_duplicate_decl (&decl, vars_map, to_context);
6287 new_name = make_ssa_name_fn (DECL_STRUCT_FUNCTION (to_context),
6288 decl, SSA_NAME_DEF_STMT (name));
6289 if (SSA_NAME_IS_DEFAULT_DEF (name))
6290 set_ssa_default_def (DECL_STRUCT_FUNCTION (to_context),
6294 new_name = copy_ssa_name_fn (DECL_STRUCT_FUNCTION (to_context),
6295 name, SSA_NAME_DEF_STMT (name));
6297 loc = pointer_map_insert (vars_map, name);
6301 new_name = (tree) *loc;
6312 struct pointer_map_t *vars_map;
6313 htab_t new_label_map;
6314 struct pointer_map_t *eh_map;
6318 /* Helper for move_block_to_fn. Set TREE_BLOCK in every expression
6319 contained in *TP if it has been ORIG_BLOCK previously and change the
6320 DECL_CONTEXT of every local variable referenced in *TP. */
6323 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
6325 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
6326 struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
6331 tree block = TREE_BLOCK (t);
6332 if (block == p->orig_block
6333 || (p->orig_block == NULL_TREE
6334 && block != NULL_TREE))
6335 TREE_SET_BLOCK (t, p->new_block);
6336 #ifdef ENABLE_CHECKING
6337 else if (block != NULL_TREE)
6339 while (block && TREE_CODE (block) == BLOCK && block != p->orig_block)
6340 block = BLOCK_SUPERCONTEXT (block);
6341 gcc_assert (block == p->orig_block);
6345 else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
6347 if (TREE_CODE (t) == SSA_NAME)
6348 *tp = replace_ssa_name (t, p->vars_map, p->to_context);
6349 else if (TREE_CODE (t) == LABEL_DECL)
6351 if (p->new_label_map)
6353 struct tree_map in, *out;
6355 out = (struct tree_map *)
6356 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
6361 DECL_CONTEXT (t) = p->to_context;
6363 else if (p->remap_decls_p)
6365 /* Replace T with its duplicate. T should no longer appear in the
6366 parent function, so this looks wasteful; however, it may appear
6367 in referenced_vars, and more importantly, as virtual operands of
6368 statements, and in alias lists of other variables. It would be
6369 quite difficult to expunge it from all those places. ??? It might
6370 suffice to do this for addressable variables. */
6371 if ((TREE_CODE (t) == VAR_DECL
6372 && !is_global_var (t))
6373 || TREE_CODE (t) == CONST_DECL)
6374 replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
6378 else if (TYPE_P (t))
6384 /* Helper for move_stmt_r. Given an EH region number for the source
6385 function, map that to the duplicate EH regio number in the dest. */
6388 move_stmt_eh_region_nr (int old_nr, struct move_stmt_d *p)
6390 eh_region old_r, new_r;
6393 old_r = get_eh_region_from_number (old_nr);
6394 slot = pointer_map_contains (p->eh_map, old_r);
6395 new_r = (eh_region) *slot;
6397 return new_r->index;
6400 /* Similar, but operate on INTEGER_CSTs. */
6403 move_stmt_eh_region_tree_nr (tree old_t_nr, struct move_stmt_d *p)
6407 old_nr = tree_to_shwi (old_t_nr);
6408 new_nr = move_stmt_eh_region_nr (old_nr, p);
6410 return build_int_cst (integer_type_node, new_nr);
6413 /* Like move_stmt_op, but for gimple statements.
6415 Helper for move_block_to_fn. Set GIMPLE_BLOCK in every expression
6416 contained in the current statement in *GSI_P and change the
6417 DECL_CONTEXT of every local variable referenced in the current
6421 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
6422 struct walk_stmt_info *wi)
6424 struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
6425 gimple stmt = gsi_stmt (*gsi_p);
6426 tree block = gimple_block (stmt);
6428 if (block == p->orig_block
6429 || (p->orig_block == NULL_TREE
6430 && block != NULL_TREE))
6431 gimple_set_block (stmt, p->new_block);
6433 switch (gimple_code (stmt))
6436 /* Remap the region numbers for __builtin_eh_{pointer,filter}. */
6438 tree r, fndecl = gimple_call_fndecl (stmt);
6439 if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
6440 switch (DECL_FUNCTION_CODE (fndecl))
6442 case BUILT_IN_EH_COPY_VALUES:
6443 r = gimple_call_arg (stmt, 1);
6444 r = move_stmt_eh_region_tree_nr (r, p);
6445 gimple_call_set_arg (stmt, 1, r);
6448 case BUILT_IN_EH_POINTER:
6449 case BUILT_IN_EH_FILTER:
6450 r = gimple_call_arg (stmt, 0);
6451 r = move_stmt_eh_region_tree_nr (r, p);
6452 gimple_call_set_arg (stmt, 0, r);
6463 int r = gimple_resx_region (stmt);
6464 r = move_stmt_eh_region_nr (r, p);
6465 gimple_resx_set_region (stmt, r);
6469 case GIMPLE_EH_DISPATCH:
6471 int r = gimple_eh_dispatch_region (stmt);
6472 r = move_stmt_eh_region_nr (r, p);
6473 gimple_eh_dispatch_set_region (stmt, r);
6477 case GIMPLE_OMP_RETURN:
6478 case GIMPLE_OMP_CONTINUE:
6481 if (is_gimple_omp (stmt))
6483 /* Do not remap variables inside OMP directives. Variables
6484 referenced in clauses and directive header belong to the
6485 parent function and should not be moved into the child
6487 bool save_remap_decls_p = p->remap_decls_p;
6488 p->remap_decls_p = false;
6489 *handled_ops_p = true;
6491 walk_gimple_seq_mod (gimple_omp_body_ptr (stmt), move_stmt_r,
6494 p->remap_decls_p = save_remap_decls_p;
6502 /* Move basic block BB from function CFUN to function DEST_FN. The
6503 block is moved out of the original linked list and placed after
6504 block AFTER in the new list. Also, the block is removed from the
6505 original array of blocks and placed in DEST_FN's array of blocks.
6506 If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
6507 updated to reflect the moved edges.
6509 The local variables are remapped to new instances, VARS_MAP is used
6510 to record the mapping. */
6513 move_block_to_fn (struct function *dest_cfun, basic_block bb,
6514 basic_block after, bool update_edge_count_p,
6515 struct move_stmt_d *d)
6517 struct control_flow_graph *cfg;
6520 gimple_stmt_iterator si;
6521 unsigned old_len, new_len;
6523 /* Remove BB from dominance structures. */
6524 delete_from_dominance_info (CDI_DOMINATORS, bb);
6526 /* Move BB from its current loop to the copy in the new function. */
6529 struct loop *new_loop = (struct loop *)bb->loop_father->aux;
6531 bb->loop_father = new_loop;
6534 /* Link BB to the new linked list. */
6535 move_block_after (bb, after);
6537 /* Update the edge count in the corresponding flowgraphs. */
6538 if (update_edge_count_p)
6539 FOR_EACH_EDGE (e, ei, bb->succs)
6541 cfun->cfg->x_n_edges--;
6542 dest_cfun->cfg->x_n_edges++;
6545 /* Remove BB from the original basic block array. */
6546 (*cfun->cfg->x_basic_block_info)[bb->index] = NULL;
6547 cfun->cfg->x_n_basic_blocks--;
6549 /* Grow DEST_CFUN's basic block array if needed. */
6550 cfg = dest_cfun->cfg;
6551 cfg->x_n_basic_blocks++;
6552 if (bb->index >= cfg->x_last_basic_block)
6553 cfg->x_last_basic_block = bb->index + 1;
6555 old_len = vec_safe_length (cfg->x_basic_block_info);
6556 if ((unsigned) cfg->x_last_basic_block >= old_len)
6558 new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
6559 vec_safe_grow_cleared (cfg->x_basic_block_info, new_len);
6562 (*cfg->x_basic_block_info)[bb->index] = bb;
6564 /* Remap the variables in phi nodes. */
6565 for (si = gsi_start_phis (bb); !gsi_end_p (si); )
6567 gimple phi = gsi_stmt (si);
6569 tree op = PHI_RESULT (phi);
6573 if (virtual_operand_p (op))
6575 /* Remove the phi nodes for virtual operands (alias analysis will be
6576 run for the new function, anyway). */
6577 remove_phi_node (&si, true);
6581 SET_PHI_RESULT (phi,
6582 replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6583 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
6585 op = USE_FROM_PTR (use);
6586 if (TREE_CODE (op) == SSA_NAME)
6587 SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6590 for (i = 0; i < EDGE_COUNT (bb->preds); i++)
6592 location_t locus = gimple_phi_arg_location (phi, i);
6593 tree block = LOCATION_BLOCK (locus);
6595 if (locus == UNKNOWN_LOCATION)
6597 if (d->orig_block == NULL_TREE || block == d->orig_block)
6599 if (d->new_block == NULL_TREE)
6600 locus = LOCATION_LOCUS (locus);
6602 locus = COMBINE_LOCATION_DATA (line_table, locus, d->new_block);
6603 gimple_phi_arg_set_location (phi, i, locus);
6610 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6612 gimple stmt = gsi_stmt (si);
6613 struct walk_stmt_info wi;
6615 memset (&wi, 0, sizeof (wi));
6617 walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
6619 if (gimple_code (stmt) == GIMPLE_LABEL)
6621 tree label = gimple_label_label (stmt);
6622 int uid = LABEL_DECL_UID (label);
6624 gcc_assert (uid > -1);
6626 old_len = vec_safe_length (cfg->x_label_to_block_map);
6627 if (old_len <= (unsigned) uid)
6629 new_len = 3 * uid / 2 + 1;
6630 vec_safe_grow_cleared (cfg->x_label_to_block_map, new_len);
6633 (*cfg->x_label_to_block_map)[uid] = bb;
6634 (*cfun->cfg->x_label_to_block_map)[uid] = NULL;
6636 gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
6638 if (uid >= dest_cfun->cfg->last_label_uid)
6639 dest_cfun->cfg->last_label_uid = uid + 1;
6642 maybe_duplicate_eh_stmt_fn (dest_cfun, stmt, cfun, stmt, d->eh_map, 0);
6643 remove_stmt_from_eh_lp_fn (cfun, stmt);
6645 gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
6646 gimple_remove_stmt_histograms (cfun, stmt);
6648 /* We cannot leave any operands allocated from the operand caches of
6649 the current function. */
6650 free_stmt_operands (cfun, stmt);
6651 push_cfun (dest_cfun);
6656 FOR_EACH_EDGE (e, ei, bb->succs)
6657 if (e->goto_locus != UNKNOWN_LOCATION)
6659 tree block = LOCATION_BLOCK (e->goto_locus);
6660 if (d->orig_block == NULL_TREE
6661 || block == d->orig_block)
6662 e->goto_locus = d->new_block ?
6663 COMBINE_LOCATION_DATA (line_table, e->goto_locus, d->new_block) :
6664 LOCATION_LOCUS (e->goto_locus);
6668 /* Examine the statements in BB (which is in SRC_CFUN); find and return
6669 the outermost EH region. Use REGION as the incoming base EH region. */
6672 find_outermost_region_in_block (struct function *src_cfun,
6673 basic_block bb, eh_region region)
6675 gimple_stmt_iterator si;
6677 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6679 gimple stmt = gsi_stmt (si);
6680 eh_region stmt_region;
6683 lp_nr = lookup_stmt_eh_lp_fn (src_cfun, stmt);
6684 stmt_region = get_eh_region_from_lp_number_fn (src_cfun, lp_nr);
6688 region = stmt_region;
6689 else if (stmt_region != region)
6691 region = eh_region_outermost (src_cfun, stmt_region, region);
6692 gcc_assert (region != NULL);
6701 new_label_mapper (tree decl, void *data)
6703 htab_t hash = (htab_t) data;
6707 gcc_assert (TREE_CODE (decl) == LABEL_DECL);
6709 m = XNEW (struct tree_map);
6710 m->hash = DECL_UID (decl);
6711 m->base.from = decl;
6712 m->to = create_artificial_label (UNKNOWN_LOCATION);
6713 LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
6714 if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
6715 cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
6717 slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
6718 gcc_assert (*slot == NULL);
6725 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
6729 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map,
6734 for (tp = &BLOCK_VARS (block); *tp; tp = &DECL_CHAIN (*tp))
6737 if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL)
6739 replace_by_duplicate_decl (&t, vars_map, to_context);
6742 if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
6744 SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
6745 DECL_HAS_VALUE_EXPR_P (t) = 1;
6747 DECL_CHAIN (t) = DECL_CHAIN (*tp);
6752 for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
6753 replace_block_vars_by_duplicates (block, vars_map, to_context);
6756 /* Fixup the loop arrays and numbers after moving LOOP and its subloops
6760 fixup_loop_arrays_after_move (struct function *fn1, struct function *fn2,
6763 /* Discard it from the old loop array. */
6764 (*get_loops (fn1))[loop->num] = NULL;
6766 /* Place it in the new loop array, assigning it a new number. */
6767 loop->num = number_of_loops (fn2);
6768 vec_safe_push (loops_for_fn (fn2)->larray, loop);
6770 /* Recurse to children. */
6771 for (loop = loop->inner; loop; loop = loop->next)
6772 fixup_loop_arrays_after_move (fn1, fn2, loop);
6775 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
6776 EXIT_BB to function DEST_CFUN. The whole region is replaced by a
6777 single basic block in the original CFG and the new basic block is
6778 returned. DEST_CFUN must not have a CFG yet.
6780 Note that the region need not be a pure SESE region. Blocks inside
6781 the region may contain calls to abort/exit. The only restriction
6782 is that ENTRY_BB should be the only entry point and it must
6785 Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
6786 functions outermost BLOCK, move all subblocks of ORIG_BLOCK
6787 to the new function.
6789 All local variables referenced in the region are assumed to be in
6790 the corresponding BLOCK_VARS and unexpanded variable lists
6791 associated with DEST_CFUN. */
6794 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
6795 basic_block exit_bb, tree orig_block)
6797 vec<basic_block> bbs, dom_bbs;
6798 basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
6799 basic_block after, bb, *entry_pred, *exit_succ, abb;
6800 struct function *saved_cfun = cfun;
6801 int *entry_flag, *exit_flag;
6802 unsigned *entry_prob, *exit_prob;
6803 unsigned i, num_entry_edges, num_exit_edges, num_nodes;
6806 htab_t new_label_map;
6807 struct pointer_map_t *vars_map, *eh_map;
6808 struct loop *loop = entry_bb->loop_father;
6809 struct loop *loop0 = get_loop (saved_cfun, 0);
6810 struct move_stmt_d d;
6812 /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
6814 gcc_assert (entry_bb != exit_bb
6816 || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
6818 /* Collect all the blocks in the region. Manually add ENTRY_BB
6819 because it won't be added by dfs_enumerate_from. */
6821 bbs.safe_push (entry_bb);
6822 gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
6824 /* The blocks that used to be dominated by something in BBS will now be
6825 dominated by the new block. */
6826 dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
6830 /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG. We need to remember
6831 the predecessor edges to ENTRY_BB and the successor edges to
6832 EXIT_BB so that we can re-attach them to the new basic block that
6833 will replace the region. */
6834 num_entry_edges = EDGE_COUNT (entry_bb->preds);
6835 entry_pred = XNEWVEC (basic_block, num_entry_edges);
6836 entry_flag = XNEWVEC (int, num_entry_edges);
6837 entry_prob = XNEWVEC (unsigned, num_entry_edges);
6839 for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
6841 entry_prob[i] = e->probability;
6842 entry_flag[i] = e->flags;
6843 entry_pred[i++] = e->src;
6849 num_exit_edges = EDGE_COUNT (exit_bb->succs);
6850 exit_succ = XNEWVEC (basic_block, num_exit_edges);
6851 exit_flag = XNEWVEC (int, num_exit_edges);
6852 exit_prob = XNEWVEC (unsigned, num_exit_edges);
6854 for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6856 exit_prob[i] = e->probability;
6857 exit_flag[i] = e->flags;
6858 exit_succ[i++] = e->dest;
6870 /* Switch context to the child function to initialize DEST_FN's CFG. */
6871 gcc_assert (dest_cfun->cfg == NULL);
6872 push_cfun (dest_cfun);
6874 init_empty_tree_cfg ();
6876 /* Initialize EH information for the new function. */
6878 new_label_map = NULL;
6881 eh_region region = NULL;
6883 FOR_EACH_VEC_ELT (bbs, i, bb)
6884 region = find_outermost_region_in_block (saved_cfun, bb, region);
6886 init_eh_for_function ();
6889 new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6890 eh_map = duplicate_eh_regions (saved_cfun, region, 0,
6891 new_label_mapper, new_label_map);
6895 /* Initialize an empty loop tree. */
6896 struct loops *loops = ggc_alloc_cleared_loops ();
6897 init_loops_structure (dest_cfun, loops, 1);
6898 loops->state = LOOPS_MAY_HAVE_MULTIPLE_LATCHES;
6899 set_loops_for_fn (dest_cfun, loops);
6901 /* Move the outlined loop tree part. */
6902 num_nodes = bbs.length ();
6903 FOR_EACH_VEC_ELT (bbs, i, bb)
6905 if (bb->loop_father->header == bb)
6907 struct loop *this_loop = bb->loop_father;
6908 struct loop *outer = loop_outer (this_loop);
6910 /* If the SESE region contains some bbs ending with
6911 a noreturn call, those are considered to belong
6912 to the outermost loop in saved_cfun, rather than
6913 the entry_bb's loop_father. */
6917 num_nodes -= this_loop->num_nodes;
6918 flow_loop_tree_node_remove (bb->loop_father);
6919 flow_loop_tree_node_add (get_loop (dest_cfun, 0), this_loop);
6920 fixup_loop_arrays_after_move (saved_cfun, cfun, this_loop);
6923 else if (bb->loop_father == loop0 && loop0 != loop)
6926 /* Remove loop exits from the outlined region. */
6927 if (loops_for_fn (saved_cfun)->exits)
6928 FOR_EACH_EDGE (e, ei, bb->succs)
6930 void **slot = htab_find_slot_with_hash
6931 (loops_for_fn (saved_cfun)->exits, e,
6932 htab_hash_pointer (e), NO_INSERT);
6934 htab_clear_slot (loops_for_fn (saved_cfun)->exits, slot);
6939 /* Adjust the number of blocks in the tree root of the outlined part. */
6940 get_loop (dest_cfun, 0)->num_nodes = bbs.length () + 2;
6942 /* Setup a mapping to be used by move_block_to_fn. */
6943 loop->aux = current_loops->tree_root;
6944 loop0->aux = current_loops->tree_root;
6948 /* Move blocks from BBS into DEST_CFUN. */
6949 gcc_assert (bbs.length () >= 2);
6950 after = dest_cfun->cfg->x_entry_block_ptr;
6951 vars_map = pointer_map_create ();
6953 memset (&d, 0, sizeof (d));
6954 d.orig_block = orig_block;
6955 d.new_block = DECL_INITIAL (dest_cfun->decl);
6956 d.from_context = cfun->decl;
6957 d.to_context = dest_cfun->decl;
6958 d.vars_map = vars_map;
6959 d.new_label_map = new_label_map;
6961 d.remap_decls_p = true;
6963 FOR_EACH_VEC_ELT (bbs, i, bb)
6965 /* No need to update edge counts on the last block. It has
6966 already been updated earlier when we detached the region from
6967 the original CFG. */
6968 move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d);
6974 /* Loop sizes are no longer correct, fix them up. */
6975 loop->num_nodes -= num_nodes;
6976 for (struct loop *outer = loop_outer (loop);
6977 outer; outer = loop_outer (outer))
6978 outer->num_nodes -= num_nodes;
6979 loop0->num_nodes -= bbs.length () - num_nodes;
6981 if (saved_cfun->has_simduid_loops || saved_cfun->has_force_vectorize_loops)
6984 for (i = 0; vec_safe_iterate (loops->larray, i, &aloop); i++)
6989 replace_by_duplicate_decl (&aloop->simduid, d.vars_map,
6991 dest_cfun->has_simduid_loops = true;
6993 if (aloop->force_vectorize)
6994 dest_cfun->has_force_vectorize_loops = true;
6998 /* Rewire BLOCK_SUBBLOCKS of orig_block. */
7002 gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
7004 BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
7005 = BLOCK_SUBBLOCKS (orig_block);
7006 for (block = BLOCK_SUBBLOCKS (orig_block);
7007 block; block = BLOCK_CHAIN (block))
7008 BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
7009 BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
7012 replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
7013 vars_map, dest_cfun->decl);
7016 htab_delete (new_label_map);
7018 pointer_map_destroy (eh_map);
7019 pointer_map_destroy (vars_map);
7021 /* Rewire the entry and exit blocks. The successor to the entry
7022 block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
7023 the child function. Similarly, the predecessor of DEST_FN's
7024 EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR. We
7025 need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
7026 various CFG manipulation function get to the right CFG.
7028 FIXME, this is silly. The CFG ought to become a parameter to
7030 push_cfun (dest_cfun);
7031 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), entry_bb, EDGE_FALLTHRU);
7033 make_edge (exit_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
7036 /* Back in the original function, the SESE region has disappeared,
7037 create a new basic block in its place. */
7038 bb = create_empty_bb (entry_pred[0]);
7040 add_bb_to_loop (bb, loop);
7041 for (i = 0; i < num_entry_edges; i++)
7043 e = make_edge (entry_pred[i], bb, entry_flag[i]);
7044 e->probability = entry_prob[i];
7047 for (i = 0; i < num_exit_edges; i++)
7049 e = make_edge (bb, exit_succ[i], exit_flag[i]);
7050 e->probability = exit_prob[i];
7053 set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
7054 FOR_EACH_VEC_ELT (dom_bbs, i, abb)
7055 set_immediate_dominator (CDI_DOMINATORS, abb, bb);
7073 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in dumpfile.h)
7077 dump_function_to_file (tree fndecl, FILE *file, int flags)
7079 tree arg, var, old_current_fndecl = current_function_decl;
7080 struct function *dsf;
7081 bool ignore_topmost_bind = false, any_var = false;
7084 bool tmclone = (TREE_CODE (fndecl) == FUNCTION_DECL
7085 && decl_is_tm_clone (fndecl));
7086 struct function *fun = DECL_STRUCT_FUNCTION (fndecl);
7088 current_function_decl = fndecl;
7090 /* Print the return type of the function: */
7091 print_generic_expr (file, TREE_TYPE (TREE_TYPE (fun->decl)),
7092 dump_flags | TDF_SLIM);
7093 fprintf (file, "\n");
7095 fprintf (file, "%s %s(", function_name (fun), tmclone ? "[tm-clone] " : "");
7097 arg = DECL_ARGUMENTS (fndecl);
7100 print_generic_expr (file, TREE_TYPE (arg), dump_flags);
7101 fprintf (file, " ");
7102 print_generic_expr (file, arg, dump_flags);
7103 if (flags & TDF_VERBOSE)
7104 print_node (file, "", arg, 4);
7105 if (DECL_CHAIN (arg))
7106 fprintf (file, ", ");
7107 arg = DECL_CHAIN (arg);
7109 fprintf (file, ")\n");
7111 if (flags & TDF_VERBOSE)
7112 print_node (file, "", fndecl, 2);
7114 dsf = DECL_STRUCT_FUNCTION (fndecl);
7115 if (dsf && (flags & TDF_EH))
7116 dump_eh_tree (file, dsf);
7118 if (flags & TDF_RAW && !gimple_has_body_p (fndecl))
7120 dump_node (fndecl, TDF_SLIM | flags, file);
7121 current_function_decl = old_current_fndecl;
7125 /* When GIMPLE is lowered, the variables are no longer available in
7126 BIND_EXPRs, so display them separately. */
7127 if (fun && fun->decl == fndecl && (fun->curr_properties & PROP_gimple_lcf))
7130 ignore_topmost_bind = true;
7132 fprintf (file, "{\n");
7133 if (!vec_safe_is_empty (fun->local_decls))
7134 FOR_EACH_LOCAL_DECL (fun, ix, var)
7136 print_generic_decl (file, var, flags);
7137 if (flags & TDF_VERBOSE)
7138 print_node (file, "", var, 4);
7139 fprintf (file, "\n");
7143 if (gimple_in_ssa_p (cfun))
7144 for (ix = 1; ix < num_ssa_names; ++ix)
7146 tree name = ssa_name (ix);
7147 if (name && !SSA_NAME_VAR (name))
7149 fprintf (file, " ");
7150 print_generic_expr (file, TREE_TYPE (name), flags);
7151 fprintf (file, " ");
7152 print_generic_expr (file, name, flags);
7153 fprintf (file, ";\n");
7160 if (fun && fun->decl == fndecl
7162 && basic_block_info_for_fn (fun))
7164 /* If the CFG has been built, emit a CFG-based dump. */
7165 if (!ignore_topmost_bind)
7166 fprintf (file, "{\n");
7168 if (any_var && n_basic_blocks_for_fn (fun))
7169 fprintf (file, "\n");
7171 FOR_EACH_BB_FN (bb, fun)
7172 dump_bb (file, bb, 2, flags | TDF_COMMENT);
7174 fprintf (file, "}\n");
7176 else if (DECL_SAVED_TREE (fndecl) == NULL)
7178 /* The function is now in GIMPLE form but the CFG has not been
7179 built yet. Emit the single sequence of GIMPLE statements
7180 that make up its body. */
7181 gimple_seq body = gimple_body (fndecl);
7183 if (gimple_seq_first_stmt (body)
7184 && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
7185 && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
7186 print_gimple_seq (file, body, 0, flags);
7189 if (!ignore_topmost_bind)
7190 fprintf (file, "{\n");
7193 fprintf (file, "\n");
7195 print_gimple_seq (file, body, 2, flags);
7196 fprintf (file, "}\n");
7203 /* Make a tree based dump. */
7204 chain = DECL_SAVED_TREE (fndecl);
7205 if (chain && TREE_CODE (chain) == BIND_EXPR)
7207 if (ignore_topmost_bind)
7209 chain = BIND_EXPR_BODY (chain);
7217 if (!ignore_topmost_bind)
7218 fprintf (file, "{\n");
7223 fprintf (file, "\n");
7225 print_generic_stmt_indented (file, chain, flags, indent);
7226 if (ignore_topmost_bind)
7227 fprintf (file, "}\n");
7230 if (flags & TDF_ENUMERATE_LOCALS)
7231 dump_enumerated_decls (file, flags);
7232 fprintf (file, "\n\n");
7234 current_function_decl = old_current_fndecl;
7237 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h) */
7240 debug_function (tree fn, int flags)
7242 dump_function_to_file (fn, stderr, flags);
7246 /* Print on FILE the indexes for the predecessors of basic_block BB. */
7249 print_pred_bbs (FILE *file, basic_block bb)
7254 FOR_EACH_EDGE (e, ei, bb->preds)
7255 fprintf (file, "bb_%d ", e->src->index);
7259 /* Print on FILE the indexes for the successors of basic_block BB. */
7262 print_succ_bbs (FILE *file, basic_block bb)
7267 FOR_EACH_EDGE (e, ei, bb->succs)
7268 fprintf (file, "bb_%d ", e->dest->index);
7271 /* Print to FILE the basic block BB following the VERBOSITY level. */
7274 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
7276 char *s_indent = (char *) alloca ((size_t) indent + 1);
7277 memset ((void *) s_indent, ' ', (size_t) indent);
7278 s_indent[indent] = '\0';
7280 /* Print basic_block's header. */
7283 fprintf (file, "%s bb_%d (preds = {", s_indent, bb->index);
7284 print_pred_bbs (file, bb);
7285 fprintf (file, "}, succs = {");
7286 print_succ_bbs (file, bb);
7287 fprintf (file, "})\n");
7290 /* Print basic_block's body. */
7293 fprintf (file, "%s {\n", s_indent);
7294 dump_bb (file, bb, indent + 4, TDF_VOPS|TDF_MEMSYMS);
7295 fprintf (file, "%s }\n", s_indent);
7299 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
7301 /* Pretty print LOOP on FILE, indented INDENT spaces. Following
7302 VERBOSITY level this outputs the contents of the loop, or just its
7306 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
7314 s_indent = (char *) alloca ((size_t) indent + 1);
7315 memset ((void *) s_indent, ' ', (size_t) indent);
7316 s_indent[indent] = '\0';
7318 /* Print loop's header. */
7319 fprintf (file, "%sloop_%d (", s_indent, loop->num);
7321 fprintf (file, "header = %d", loop->header->index);
7324 fprintf (file, "deleted)\n");
7328 fprintf (file, ", latch = %d", loop->latch->index);
7330 fprintf (file, ", multiple latches");
7331 fprintf (file, ", niter = ");
7332 print_generic_expr (file, loop->nb_iterations, 0);
7334 if (loop->any_upper_bound)
7336 fprintf (file, ", upper_bound = ");
7337 dump_double_int (file, loop->nb_iterations_upper_bound, true);
7340 if (loop->any_estimate)
7342 fprintf (file, ", estimate = ");
7343 dump_double_int (file, loop->nb_iterations_estimate, true);
7345 fprintf (file, ")\n");
7347 /* Print loop's body. */
7350 fprintf (file, "%s{\n", s_indent);
7351 FOR_EACH_BB_FN (bb, cfun)
7352 if (bb->loop_father == loop)
7353 print_loops_bb (file, bb, indent, verbosity);
7355 print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
7356 fprintf (file, "%s}\n", s_indent);
7360 /* Print the LOOP and its sibling loops on FILE, indented INDENT
7361 spaces. Following VERBOSITY level this outputs the contents of the
7362 loop, or just its structure. */
7365 print_loop_and_siblings (FILE *file, struct loop *loop, int indent,
7371 print_loop (file, loop, indent, verbosity);
7372 print_loop_and_siblings (file, loop->next, indent, verbosity);
7375 /* Follow a CFG edge from the entry point of the program, and on entry
7376 of a loop, pretty print the loop structure on FILE. */
7379 print_loops (FILE *file, int verbosity)
7383 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
7384 if (bb && bb->loop_father)
7385 print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
7391 debug (struct loop &ref)
7393 print_loop (stderr, &ref, 0, /*verbosity*/0);
7397 debug (struct loop *ptr)
7402 fprintf (stderr, "<nil>\n");
7405 /* Dump a loop verbosely. */
7408 debug_verbose (struct loop &ref)
7410 print_loop (stderr, &ref, 0, /*verbosity*/3);
7414 debug_verbose (struct loop *ptr)
7419 fprintf (stderr, "<nil>\n");
7423 /* Debugging loops structure at tree level, at some VERBOSITY level. */
7426 debug_loops (int verbosity)
7428 print_loops (stderr, verbosity);
7431 /* Print on stderr the code of LOOP, at some VERBOSITY level. */
7434 debug_loop (struct loop *loop, int verbosity)
7436 print_loop (stderr, loop, 0, verbosity);
7439 /* Print on stderr the code of loop number NUM, at some VERBOSITY
7443 debug_loop_num (unsigned num, int verbosity)
7445 debug_loop (get_loop (cfun, num), verbosity);
7448 /* Return true if BB ends with a call, possibly followed by some
7449 instructions that must stay with the call. Return false,
7453 gimple_block_ends_with_call_p (basic_block bb)
7455 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
7456 return !gsi_end_p (gsi) && is_gimple_call (gsi_stmt (gsi));
7460 /* Return true if BB ends with a conditional branch. Return false,
7464 gimple_block_ends_with_condjump_p (const_basic_block bb)
7466 gimple stmt = last_stmt (CONST_CAST_BB (bb));
7467 return (stmt && gimple_code (stmt) == GIMPLE_COND);
7471 /* Return true if we need to add fake edge to exit at statement T.
7472 Helper function for gimple_flow_call_edges_add. */
7475 need_fake_edge_p (gimple t)
7477 tree fndecl = NULL_TREE;
7480 /* NORETURN and LONGJMP calls already have an edge to exit.
7481 CONST and PURE calls do not need one.
7482 We don't currently check for CONST and PURE here, although
7483 it would be a good idea, because those attributes are
7484 figured out from the RTL in mark_constant_function, and
7485 the counter incrementation code from -fprofile-arcs
7486 leads to different results from -fbranch-probabilities. */
7487 if (is_gimple_call (t))
7489 fndecl = gimple_call_fndecl (t);
7490 call_flags = gimple_call_flags (t);
7493 if (is_gimple_call (t)
7495 && DECL_BUILT_IN (fndecl)
7496 && (call_flags & ECF_NOTHROW)
7497 && !(call_flags & ECF_RETURNS_TWICE)
7498 /* fork() doesn't really return twice, but the effect of
7499 wrapping it in __gcov_fork() which calls __gcov_flush()
7500 and clears the counters before forking has the same
7501 effect as returning twice. Force a fake edge. */
7502 && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
7503 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK))
7506 if (is_gimple_call (t))
7512 if (!(call_flags & ECF_NORETURN))
7516 FOR_EACH_EDGE (e, ei, bb->succs)
7517 if ((e->flags & EDGE_FAKE) == 0)
7521 if (gimple_code (t) == GIMPLE_ASM
7522 && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
7529 /* Add fake edges to the function exit for any non constant and non
7530 noreturn calls (or noreturn calls with EH/abnormal edges),
7531 volatile inline assembly in the bitmap of blocks specified by BLOCKS
7532 or to the whole CFG if BLOCKS is zero. Return the number of blocks
7535 The goal is to expose cases in which entering a basic block does
7536 not imply that all subsequent instructions must be executed. */
7539 gimple_flow_call_edges_add (sbitmap blocks)
7542 int blocks_split = 0;
7543 int last_bb = last_basic_block_for_fn (cfun);
7544 bool check_last_block = false;
7546 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
7550 check_last_block = true;
7552 check_last_block = bitmap_bit_p (blocks,
7553 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
7555 /* In the last basic block, before epilogue generation, there will be
7556 a fallthru edge to EXIT. Special care is required if the last insn
7557 of the last basic block is a call because make_edge folds duplicate
7558 edges, which would result in the fallthru edge also being marked
7559 fake, which would result in the fallthru edge being removed by
7560 remove_fake_edges, which would result in an invalid CFG.
7562 Moreover, we can't elide the outgoing fake edge, since the block
7563 profiler needs to take this into account in order to solve the minimal
7564 spanning tree in the case that the call doesn't return.
7566 Handle this by adding a dummy instruction in a new last basic block. */
7567 if (check_last_block)
7569 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
7570 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
7573 if (!gsi_end_p (gsi))
7576 if (t && need_fake_edge_p (t))
7580 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
7583 gsi_insert_on_edge (e, gimple_build_nop ());
7584 gsi_commit_edge_inserts ();
7589 /* Now add fake edges to the function exit for any non constant
7590 calls since there is no way that we can determine if they will
7592 for (i = 0; i < last_bb; i++)
7594 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
7595 gimple_stmt_iterator gsi;
7596 gimple stmt, last_stmt;
7601 if (blocks && !bitmap_bit_p (blocks, i))
7604 gsi = gsi_last_nondebug_bb (bb);
7605 if (!gsi_end_p (gsi))
7607 last_stmt = gsi_stmt (gsi);
7610 stmt = gsi_stmt (gsi);
7611 if (need_fake_edge_p (stmt))
7615 /* The handling above of the final block before the
7616 epilogue should be enough to verify that there is
7617 no edge to the exit block in CFG already.
7618 Calling make_edge in such case would cause us to
7619 mark that edge as fake and remove it later. */
7620 #ifdef ENABLE_CHECKING
7621 if (stmt == last_stmt)
7623 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
7624 gcc_assert (e == NULL);
7628 /* Note that the following may create a new basic block
7629 and renumber the existing basic blocks. */
7630 if (stmt != last_stmt)
7632 e = split_block (bb, stmt);
7636 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
7640 while (!gsi_end_p (gsi));
7645 verify_flow_info ();
7647 return blocks_split;
7650 /* Removes edge E and all the blocks dominated by it, and updates dominance
7651 information. The IL in E->src needs to be updated separately.
7652 If dominance info is not available, only the edge E is removed.*/
7655 remove_edge_and_dominated_blocks (edge e)
7657 vec<basic_block> bbs_to_remove = vNULL;
7658 vec<basic_block> bbs_to_fix_dom = vNULL;
7662 bool none_removed = false;
7664 basic_block bb, dbb;
7667 if (!dom_info_available_p (CDI_DOMINATORS))
7673 /* No updating is needed for edges to exit. */
7674 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
7676 if (cfgcleanup_altered_bbs)
7677 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7682 /* First, we find the basic blocks to remove. If E->dest has a predecessor
7683 that is not dominated by E->dest, then this set is empty. Otherwise,
7684 all the basic blocks dominated by E->dest are removed.
7686 Also, to DF_IDOM we store the immediate dominators of the blocks in
7687 the dominance frontier of E (i.e., of the successors of the
7688 removed blocks, if there are any, and of E->dest otherwise). */
7689 FOR_EACH_EDGE (f, ei, e->dest->preds)
7694 if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
7696 none_removed = true;
7701 df = BITMAP_ALLOC (NULL);
7702 df_idom = BITMAP_ALLOC (NULL);
7705 bitmap_set_bit (df_idom,
7706 get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
7709 bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest);
7710 FOR_EACH_VEC_ELT (bbs_to_remove, i, bb)
7712 FOR_EACH_EDGE (f, ei, bb->succs)
7714 if (f->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
7715 bitmap_set_bit (df, f->dest->index);
7718 FOR_EACH_VEC_ELT (bbs_to_remove, i, bb)
7719 bitmap_clear_bit (df, bb->index);
7721 EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
7723 bb = BASIC_BLOCK_FOR_FN (cfun, i);
7724 bitmap_set_bit (df_idom,
7725 get_immediate_dominator (CDI_DOMINATORS, bb)->index);
7729 if (cfgcleanup_altered_bbs)
7731 /* Record the set of the altered basic blocks. */
7732 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7733 bitmap_ior_into (cfgcleanup_altered_bbs, df);
7736 /* Remove E and the cancelled blocks. */
7741 /* Walk backwards so as to get a chance to substitute all
7742 released DEFs into debug stmts. See
7743 eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
7745 for (i = bbs_to_remove.length (); i-- > 0; )
7746 delete_basic_block (bbs_to_remove[i]);
7749 /* Update the dominance information. The immediate dominator may change only
7750 for blocks whose immediate dominator belongs to DF_IDOM:
7752 Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
7753 removal. Let Z the arbitrary block such that idom(Z) = Y and
7754 Z dominates X after the removal. Before removal, there exists a path P
7755 from Y to X that avoids Z. Let F be the last edge on P that is
7756 removed, and let W = F->dest. Before removal, idom(W) = Y (since Y
7757 dominates W, and because of P, Z does not dominate W), and W belongs to
7758 the dominance frontier of E. Therefore, Y belongs to DF_IDOM. */
7759 EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
7761 bb = BASIC_BLOCK_FOR_FN (cfun, i);
7762 for (dbb = first_dom_son (CDI_DOMINATORS, bb);
7764 dbb = next_dom_son (CDI_DOMINATORS, dbb))
7765 bbs_to_fix_dom.safe_push (dbb);
7768 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
7771 BITMAP_FREE (df_idom);
7772 bbs_to_remove.release ();
7773 bbs_to_fix_dom.release ();
7776 /* Purge dead EH edges from basic block BB. */
7779 gimple_purge_dead_eh_edges (basic_block bb)
7781 bool changed = false;
7784 gimple stmt = last_stmt (bb);
7786 if (stmt && stmt_can_throw_internal (stmt))
7789 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7791 if (e->flags & EDGE_EH)
7793 remove_edge_and_dominated_blocks (e);
7803 /* Purge dead EH edges from basic block listed in BLOCKS. */
7806 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
7808 bool changed = false;
7812 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7814 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
7816 /* Earlier gimple_purge_dead_eh_edges could have removed
7817 this basic block already. */
7818 gcc_assert (bb || changed);
7820 changed |= gimple_purge_dead_eh_edges (bb);
7826 /* Purge dead abnormal call edges from basic block BB. */
7829 gimple_purge_dead_abnormal_call_edges (basic_block bb)
7831 bool changed = false;
7834 gimple stmt = last_stmt (bb);
7836 if (!cfun->has_nonlocal_label
7837 && !cfun->calls_setjmp)
7840 if (stmt && stmt_can_make_abnormal_goto (stmt))
7843 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7845 if (e->flags & EDGE_ABNORMAL)
7847 if (e->flags & EDGE_FALLTHRU)
7848 e->flags &= ~EDGE_ABNORMAL;
7850 remove_edge_and_dominated_blocks (e);
7860 /* Purge dead abnormal call edges from basic block listed in BLOCKS. */
7863 gimple_purge_all_dead_abnormal_call_edges (const_bitmap blocks)
7865 bool changed = false;
7869 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7871 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
7873 /* Earlier gimple_purge_dead_abnormal_call_edges could have removed
7874 this basic block already. */
7875 gcc_assert (bb || changed);
7877 changed |= gimple_purge_dead_abnormal_call_edges (bb);
7883 /* This function is called whenever a new edge is created or
7887 gimple_execute_on_growing_pred (edge e)
7889 basic_block bb = e->dest;
7891 if (!gimple_seq_empty_p (phi_nodes (bb)))
7892 reserve_phi_args_for_new_edge (bb);
7895 /* This function is called immediately before edge E is removed from
7896 the edge vector E->dest->preds. */
7899 gimple_execute_on_shrinking_pred (edge e)
7901 if (!gimple_seq_empty_p (phi_nodes (e->dest)))
7902 remove_phi_args (e);
7905 /*---------------------------------------------------------------------------
7906 Helper functions for Loop versioning
7907 ---------------------------------------------------------------------------*/
7909 /* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy
7910 of 'first'. Both of them are dominated by 'new_head' basic block. When
7911 'new_head' was created by 'second's incoming edge it received phi arguments
7912 on the edge by split_edge(). Later, additional edge 'e' was created to
7913 connect 'new_head' and 'first'. Now this routine adds phi args on this
7914 additional edge 'e' that new_head to second edge received as part of edge
7918 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
7919 basic_block new_head, edge e)
7922 gimple_stmt_iterator psi1, psi2;
7924 edge e2 = find_edge (new_head, second);
7926 /* Because NEW_HEAD has been created by splitting SECOND's incoming
7927 edge, we should always have an edge from NEW_HEAD to SECOND. */
7928 gcc_assert (e2 != NULL);
7930 /* Browse all 'second' basic block phi nodes and add phi args to
7931 edge 'e' for 'first' head. PHI args are always in correct order. */
7933 for (psi2 = gsi_start_phis (second),
7934 psi1 = gsi_start_phis (first);
7935 !gsi_end_p (psi2) && !gsi_end_p (psi1);
7936 gsi_next (&psi2), gsi_next (&psi1))
7938 phi1 = gsi_stmt (psi1);
7939 phi2 = gsi_stmt (psi2);
7940 def = PHI_ARG_DEF (phi2, e2->dest_idx);
7941 add_phi_arg (phi1, def, e, gimple_phi_arg_location_from_edge (phi2, e2));
7946 /* Adds a if else statement to COND_BB with condition COND_EXPR.
7947 SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
7948 the destination of the ELSE part. */
7951 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
7952 basic_block second_head ATTRIBUTE_UNUSED,
7953 basic_block cond_bb, void *cond_e)
7955 gimple_stmt_iterator gsi;
7956 gimple new_cond_expr;
7957 tree cond_expr = (tree) cond_e;
7960 /* Build new conditional expr */
7961 new_cond_expr = gimple_build_cond_from_tree (cond_expr,
7962 NULL_TREE, NULL_TREE);
7964 /* Add new cond in cond_bb. */
7965 gsi = gsi_last_bb (cond_bb);
7966 gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
7968 /* Adjust edges appropriately to connect new head with first head
7969 as well as second head. */
7970 e0 = single_succ_edge (cond_bb);
7971 e0->flags &= ~EDGE_FALLTHRU;
7972 e0->flags |= EDGE_FALSE_VALUE;
7976 /* Do book-keeping of basic block BB for the profile consistency checker.
7977 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
7978 then do post-pass accounting. Store the counting in RECORD. */
7980 gimple_account_profile_record (basic_block bb, int after_pass,
7981 struct profile_record *record)
7983 gimple_stmt_iterator i;
7984 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
7986 record->size[after_pass]
7987 += estimate_num_insns (gsi_stmt (i), &eni_size_weights);
7988 if (profile_status_for_fn (cfun) == PROFILE_READ)
7989 record->time[after_pass]
7990 += estimate_num_insns (gsi_stmt (i),
7991 &eni_time_weights) * bb->count;
7992 else if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
7993 record->time[after_pass]
7994 += estimate_num_insns (gsi_stmt (i),
7995 &eni_time_weights) * bb->frequency;
7999 struct cfg_hooks gimple_cfg_hooks = {
8001 gimple_verify_flow_info,
8002 gimple_dump_bb, /* dump_bb */
8003 gimple_dump_bb_for_graph, /* dump_bb_for_graph */
8004 create_bb, /* create_basic_block */
8005 gimple_redirect_edge_and_branch, /* redirect_edge_and_branch */
8006 gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force */
8007 gimple_can_remove_branch_p, /* can_remove_branch_p */
8008 remove_bb, /* delete_basic_block */
8009 gimple_split_block, /* split_block */
8010 gimple_move_block_after, /* move_block_after */
8011 gimple_can_merge_blocks_p, /* can_merge_blocks_p */
8012 gimple_merge_blocks, /* merge_blocks */
8013 gimple_predict_edge, /* predict_edge */
8014 gimple_predicted_by_p, /* predicted_by_p */
8015 gimple_can_duplicate_bb_p, /* can_duplicate_block_p */
8016 gimple_duplicate_bb, /* duplicate_block */
8017 gimple_split_edge, /* split_edge */
8018 gimple_make_forwarder_block, /* make_forward_block */
8019 NULL, /* tidy_fallthru_edge */
8020 NULL, /* force_nonfallthru */
8021 gimple_block_ends_with_call_p,/* block_ends_with_call_p */
8022 gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
8023 gimple_flow_call_edges_add, /* flow_call_edges_add */
8024 gimple_execute_on_growing_pred, /* execute_on_growing_pred */
8025 gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
8026 gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
8027 gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
8028 gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
8029 extract_true_false_edges_from_block, /* extract_cond_bb_edges */
8030 flush_pending_stmts, /* flush_pending_stmts */
8031 gimple_empty_block_p, /* block_empty_p */
8032 gimple_split_block_before_cond_jump, /* split_block_before_cond_jump */
8033 gimple_account_profile_record,
8037 /* Split all critical edges. */
8040 split_critical_edges (void)
8046 /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
8047 expensive. So we want to enable recording of edge to CASE_LABEL_EXPR
8048 mappings around the calls to split_edge. */
8049 start_recording_case_labels ();
8050 FOR_ALL_BB_FN (bb, cfun)
8052 FOR_EACH_EDGE (e, ei, bb->succs)
8054 if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
8056 /* PRE inserts statements to edges and expects that
8057 since split_critical_edges was done beforehand, committing edge
8058 insertions will not split more edges. In addition to critical
8059 edges we must split edges that have multiple successors and
8060 end by control flow statements, such as RESX.
8061 Go ahead and split them too. This matches the logic in
8062 gimple_find_edge_insert_loc. */
8063 else if ((!single_pred_p (e->dest)
8064 || !gimple_seq_empty_p (phi_nodes (e->dest))
8065 || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
8066 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
8067 && !(e->flags & EDGE_ABNORMAL))
8069 gimple_stmt_iterator gsi;
8071 gsi = gsi_last_bb (e->src);
8072 if (!gsi_end_p (gsi)
8073 && stmt_ends_bb_p (gsi_stmt (gsi))
8074 && (gimple_code (gsi_stmt (gsi)) != GIMPLE_RETURN
8075 && !gimple_call_builtin_p (gsi_stmt (gsi),
8081 end_recording_case_labels ();
8087 const pass_data pass_data_split_crit_edges =
8089 GIMPLE_PASS, /* type */
8090 "crited", /* name */
8091 OPTGROUP_NONE, /* optinfo_flags */
8092 true, /* has_execute */
8093 TV_TREE_SPLIT_EDGES, /* tv_id */
8094 PROP_cfg, /* properties_required */
8095 PROP_no_crit_edges, /* properties_provided */
8096 0, /* properties_destroyed */
8097 0, /* todo_flags_start */
8098 TODO_verify_flow, /* todo_flags_finish */
8101 class pass_split_crit_edges : public gimple_opt_pass
8104 pass_split_crit_edges (gcc::context *ctxt)
8105 : gimple_opt_pass (pass_data_split_crit_edges, ctxt)
8108 /* opt_pass methods: */
8109 virtual unsigned int execute (function *) { return split_critical_edges (); }
8111 opt_pass * clone () { return new pass_split_crit_edges (m_ctxt); }
8112 }; // class pass_split_crit_edges
8117 make_pass_split_crit_edges (gcc::context *ctxt)
8119 return new pass_split_crit_edges (ctxt);
8123 /* Build a ternary operation and gimplify it. Emit code before GSI.
8124 Return the gimple_val holding the result. */
8127 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
8128 tree type, tree a, tree b, tree c)
8131 location_t loc = gimple_location (gsi_stmt (*gsi));
8133 ret = fold_build3_loc (loc, code, type, a, b, c);
8136 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
8140 /* Build a binary operation and gimplify it. Emit code before GSI.
8141 Return the gimple_val holding the result. */
8144 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
8145 tree type, tree a, tree b)
8149 ret = fold_build2_loc (gimple_location (gsi_stmt (*gsi)), code, type, a, b);
8152 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
8156 /* Build a unary operation and gimplify it. Emit code before GSI.
8157 Return the gimple_val holding the result. */
8160 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
8165 ret = fold_build1_loc (gimple_location (gsi_stmt (*gsi)), code, type, a);
8168 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
8174 /* Given a basic block B which ends with a conditional and has
8175 precisely two successors, determine which of the edges is taken if
8176 the conditional is true and which is taken if the conditional is
8177 false. Set TRUE_EDGE and FALSE_EDGE appropriately. */
8180 extract_true_false_edges_from_block (basic_block b,
8184 edge e = EDGE_SUCC (b, 0);
8186 if (e->flags & EDGE_TRUE_VALUE)
8189 *false_edge = EDGE_SUCC (b, 1);
8194 *true_edge = EDGE_SUCC (b, 1);
8198 /* Emit return warnings. */
8202 const pass_data pass_data_warn_function_return =
8204 GIMPLE_PASS, /* type */
8205 "*warn_function_return", /* name */
8206 OPTGROUP_NONE, /* optinfo_flags */
8207 true, /* has_execute */
8208 TV_NONE, /* tv_id */
8209 PROP_cfg, /* properties_required */
8210 0, /* properties_provided */
8211 0, /* properties_destroyed */
8212 0, /* todo_flags_start */
8213 0, /* todo_flags_finish */
8216 class pass_warn_function_return : public gimple_opt_pass
8219 pass_warn_function_return (gcc::context *ctxt)
8220 : gimple_opt_pass (pass_data_warn_function_return, ctxt)
8223 /* opt_pass methods: */
8224 virtual unsigned int execute (function *);
8226 }; // class pass_warn_function_return
8229 pass_warn_function_return::execute (function *fun)
8231 source_location location;
8236 if (!targetm.warn_func_return (fun->decl))
8239 /* If we have a path to EXIT, then we do return. */
8240 if (TREE_THIS_VOLATILE (fun->decl)
8241 && EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (fun)->preds) > 0)
8243 location = UNKNOWN_LOCATION;
8244 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (fun)->preds)
8246 last = last_stmt (e->src);
8247 if ((gimple_code (last) == GIMPLE_RETURN
8248 || gimple_call_builtin_p (last, BUILT_IN_RETURN))
8249 && (location = gimple_location (last)) != UNKNOWN_LOCATION)
8252 if (location == UNKNOWN_LOCATION)
8253 location = cfun->function_end_locus;
8254 warning_at (location, 0, "%<noreturn%> function does return");
8257 /* If we see "return;" in some basic block, then we do reach the end
8258 without returning a value. */
8259 else if (warn_return_type
8260 && !TREE_NO_WARNING (fun->decl)
8261 && EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (fun)->preds) > 0
8262 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fun->decl))))
8264 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (fun)->preds)
8266 gimple last = last_stmt (e->src);
8267 if (gimple_code (last) == GIMPLE_RETURN
8268 && gimple_return_retval (last) == NULL
8269 && !gimple_no_warning_p (last))
8271 location = gimple_location (last);
8272 if (location == UNKNOWN_LOCATION)
8273 location = fun->function_end_locus;
8274 warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
8275 TREE_NO_WARNING (fun->decl) = 1;
8286 make_pass_warn_function_return (gcc::context *ctxt)
8288 return new pass_warn_function_return (ctxt);
8291 /* Walk a gimplified function and warn for functions whose return value is
8292 ignored and attribute((warn_unused_result)) is set. This is done before
8293 inlining, so we don't have to worry about that. */
8296 do_warn_unused_result (gimple_seq seq)
8299 gimple_stmt_iterator i;
8301 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
8303 gimple g = gsi_stmt (i);
8305 switch (gimple_code (g))
8308 do_warn_unused_result (gimple_bind_body (g));
8311 do_warn_unused_result (gimple_try_eval (g));
8312 do_warn_unused_result (gimple_try_cleanup (g));
8315 do_warn_unused_result (gimple_catch_handler (g));
8317 case GIMPLE_EH_FILTER:
8318 do_warn_unused_result (gimple_eh_filter_failure (g));
8322 if (gimple_call_lhs (g))
8324 if (gimple_call_internal_p (g))
8327 /* This is a naked call, as opposed to a GIMPLE_CALL with an
8328 LHS. All calls whose value is ignored should be
8329 represented like this. Look for the attribute. */
8330 fdecl = gimple_call_fndecl (g);
8331 ftype = gimple_call_fntype (g);
8333 if (lookup_attribute ("warn_unused_result", TYPE_ATTRIBUTES (ftype)))
8335 location_t loc = gimple_location (g);
8338 warning_at (loc, OPT_Wunused_result,
8339 "ignoring return value of %qD, "
8340 "declared with attribute warn_unused_result",
8343 warning_at (loc, OPT_Wunused_result,
8344 "ignoring return value of function "
8345 "declared with attribute warn_unused_result");
8350 /* Not a container, not a call, or a call whose value is used. */
8358 const pass_data pass_data_warn_unused_result =
8360 GIMPLE_PASS, /* type */
8361 "*warn_unused_result", /* name */
8362 OPTGROUP_NONE, /* optinfo_flags */
8363 true, /* has_execute */
8364 TV_NONE, /* tv_id */
8365 PROP_gimple_any, /* properties_required */
8366 0, /* properties_provided */
8367 0, /* properties_destroyed */
8368 0, /* todo_flags_start */
8369 0, /* todo_flags_finish */
8372 class pass_warn_unused_result : public gimple_opt_pass
8375 pass_warn_unused_result (gcc::context *ctxt)
8376 : gimple_opt_pass (pass_data_warn_unused_result, ctxt)
8379 /* opt_pass methods: */
8380 virtual bool gate (function *) { return flag_warn_unused_result; }
8381 virtual unsigned int execute (function *)
8383 do_warn_unused_result (gimple_body (current_function_decl));
8387 }; // class pass_warn_unused_result
8392 make_pass_warn_unused_result (gcc::context *ctxt)
8394 return new pass_warn_unused_result (ctxt);
8397 /* IPA passes, compilation of earlier functions or inlining
8398 might have changed some properties, such as marked functions nothrow,
8399 pure, const or noreturn.
8400 Remove redundant edges and basic blocks, and create new ones if necessary.
8402 This pass can't be executed as stand alone pass from pass manager, because
8403 in between inlining and this fixup the verify_flow_info would fail. */
8406 execute_fixup_cfg (void)
8409 gimple_stmt_iterator gsi;
8410 int todo = gimple_in_ssa_p (cfun) ? TODO_verify_ssa : 0;
8411 gcov_type count_scale;
8416 = GCOV_COMPUTE_SCALE (cgraph_get_node (current_function_decl)->count,
8417 ENTRY_BLOCK_PTR_FOR_FN (cfun)->count);
8419 ENTRY_BLOCK_PTR_FOR_FN (cfun)->count =
8420 cgraph_get_node (current_function_decl)->count;
8421 EXIT_BLOCK_PTR_FOR_FN (cfun)->count =
8422 apply_scale (EXIT_BLOCK_PTR_FOR_FN (cfun)->count,
8425 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
8426 e->count = apply_scale (e->count, count_scale);
8428 FOR_EACH_BB_FN (bb, cfun)
8430 bb->count = apply_scale (bb->count, count_scale);
8431 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
8433 gimple stmt = gsi_stmt (gsi);
8434 tree decl = is_gimple_call (stmt)
8435 ? gimple_call_fndecl (stmt)
8439 int flags = gimple_call_flags (stmt);
8440 if (flags & (ECF_CONST | ECF_PURE | ECF_LOOPING_CONST_OR_PURE))
8442 if (gimple_purge_dead_abnormal_call_edges (bb))
8443 todo |= TODO_cleanup_cfg;
8445 if (gimple_in_ssa_p (cfun))
8447 todo |= TODO_update_ssa | TODO_cleanup_cfg;
8452 if (flags & ECF_NORETURN
8453 && fixup_noreturn_call (stmt))
8454 todo |= TODO_cleanup_cfg;
8457 if (maybe_clean_eh_stmt (stmt)
8458 && gimple_purge_dead_eh_edges (bb))
8459 todo |= TODO_cleanup_cfg;
8462 FOR_EACH_EDGE (e, ei, bb->succs)
8463 e->count = apply_scale (e->count, count_scale);
8465 /* If we have a basic block with no successors that does not
8466 end with a control statement or a noreturn call end it with
8467 a call to __builtin_unreachable. This situation can occur
8468 when inlining a noreturn call that does in fact return. */
8469 if (EDGE_COUNT (bb->succs) == 0)
8471 gimple stmt = last_stmt (bb);
8473 || (!is_ctrl_stmt (stmt)
8474 && (!is_gimple_call (stmt)
8475 || (gimple_call_flags (stmt) & ECF_NORETURN) == 0)))
8477 stmt = gimple_build_call
8478 (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
8479 gimple_stmt_iterator gsi = gsi_last_bb (bb);
8480 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
8484 if (count_scale != REG_BR_PROB_BASE)
8485 compute_function_frequency ();
8487 /* We just processed all calls. */
8488 if (cfun->gimple_df)
8489 vec_free (MODIFIED_NORETURN_CALLS (cfun));
8491 /* Dump a textual representation of the flowgraph. */
8493 gimple_dump_cfg (dump_file, dump_flags);
8496 && (todo & TODO_cleanup_cfg))
8497 loops_state_set (LOOPS_NEED_FIXUP);
8504 const pass_data pass_data_fixup_cfg =
8506 GIMPLE_PASS, /* type */
8507 "*free_cfg_annotations", /* name */
8508 OPTGROUP_NONE, /* optinfo_flags */
8509 true, /* has_execute */
8510 TV_NONE, /* tv_id */
8511 PROP_cfg, /* properties_required */
8512 0, /* properties_provided */
8513 0, /* properties_destroyed */
8514 0, /* todo_flags_start */
8515 0, /* todo_flags_finish */
8518 class pass_fixup_cfg : public gimple_opt_pass
8521 pass_fixup_cfg (gcc::context *ctxt)
8522 : gimple_opt_pass (pass_data_fixup_cfg, ctxt)
8525 /* opt_pass methods: */
8526 opt_pass * clone () { return new pass_fixup_cfg (m_ctxt); }
8527 virtual unsigned int execute (function *) { return execute_fixup_cfg (); }
8529 }; // class pass_fixup_cfg
8534 make_pass_fixup_cfg (gcc::context *ctxt)
8536 return new pass_fixup_cfg (ctxt);
8539 /* Garbage collection support for edge_def. */
8541 extern void gt_ggc_mx (tree&);
8542 extern void gt_ggc_mx (gimple&);
8543 extern void gt_ggc_mx (rtx&);
8544 extern void gt_ggc_mx (basic_block&);
8547 gt_ggc_mx (edge_def *e)
8549 tree block = LOCATION_BLOCK (e->goto_locus);
8551 gt_ggc_mx (e->dest);
8552 if (current_ir_type () == IR_GIMPLE)
8553 gt_ggc_mx (e->insns.g);
8555 gt_ggc_mx (e->insns.r);
8559 /* PCH support for edge_def. */
8561 extern void gt_pch_nx (tree&);
8562 extern void gt_pch_nx (gimple&);
8563 extern void gt_pch_nx (rtx&);
8564 extern void gt_pch_nx (basic_block&);
8567 gt_pch_nx (edge_def *e)
8569 tree block = LOCATION_BLOCK (e->goto_locus);
8571 gt_pch_nx (e->dest);
8572 if (current_ir_type () == IR_GIMPLE)
8573 gt_pch_nx (e->insns.g);
8575 gt_pch_nx (e->insns.r);
8580 gt_pch_nx (edge_def *e, gt_pointer_operator op, void *cookie)
8582 tree block = LOCATION_BLOCK (e->goto_locus);
8583 op (&(e->src), cookie);
8584 op (&(e->dest), cookie);
8585 if (current_ir_type () == IR_GIMPLE)
8586 op (&(e->insns.g), cookie);
8588 op (&(e->insns.r), cookie);
8589 op (&(block), cookie);