1 /* Control flow functions for trees.
2 Copyright (C) 2001-2013 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"
28 #include "basic-block.h"
32 #include "gimple-pretty-print.h"
34 #include "gimple-iterator.h"
35 #include "gimple-walk.h"
36 #include "gimple-ssa.h"
39 #include "tree-phinodes.h"
40 #include "ssa-iterators.h"
41 #include "tree-ssanames.h"
42 #include "tree-ssa-loop-manip.h"
43 #include "tree-ssa-loop-niter.h"
44 #include "tree-into-ssa.h"
47 #include "tree-dump.h"
48 #include "tree-pass.h"
49 #include "diagnostic-core.h"
52 #include "tree-ssa-propagate.h"
53 #include "value-prof.h"
54 #include "pointer-set.h"
55 #include "tree-inline.h"
57 #include "tree-ssa-live.h"
59 #include "tree-cfgcleanup.h"
61 /* This file contains functions for building the Control Flow Graph (CFG)
62 for a function tree. */
64 /* Local declarations. */
66 /* Initial capacity for the basic block array. */
67 static const int initial_cfg_capacity = 20;
69 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
70 which use a particular edge. The CASE_LABEL_EXPRs are chained together
71 via their CASE_CHAIN field, which we clear after we're done with the
72 hash table to prevent problems with duplication of GIMPLE_SWITCHes.
74 Access to this list of CASE_LABEL_EXPRs allows us to efficiently
75 update the case vector in response to edge redirections.
77 Right now this table is set up and torn down at key points in the
78 compilation process. It would be nice if we could make the table
79 more persistent. The key is getting notification of changes to
80 the CFG (particularly edge removal, creation and redirection). */
82 static struct pointer_map_t *edge_to_cases;
84 /* If we record edge_to_cases, this bitmap will hold indexes
85 of basic blocks that end in a GIMPLE_SWITCH which we touched
86 due to edge manipulations. */
88 static bitmap touched_switch_bbs;
93 long num_merged_labels;
96 static struct cfg_stats_d cfg_stats;
98 /* Nonzero if we found a computed goto while building basic blocks. */
99 static bool found_computed_goto;
101 /* Hash table to store last discriminator assigned for each locus. */
102 struct locus_discrim_map
108 /* Hashtable helpers. */
110 struct locus_discrim_hasher : typed_free_remove <locus_discrim_map>
112 typedef locus_discrim_map value_type;
113 typedef locus_discrim_map compare_type;
114 static inline hashval_t hash (const value_type *);
115 static inline bool equal (const value_type *, const compare_type *);
118 /* Trivial hash function for a location_t. ITEM is a pointer to
119 a hash table entry that maps a location_t to a discriminator. */
122 locus_discrim_hasher::hash (const value_type *item)
124 return LOCATION_LINE (item->locus);
127 /* Equality function for the locus-to-discriminator map. A and B
128 point to the two hash table entries to compare. */
131 locus_discrim_hasher::equal (const value_type *a, const compare_type *b)
133 return LOCATION_LINE (a->locus) == LOCATION_LINE (b->locus);
136 static hash_table <locus_discrim_hasher> discriminator_per_locus;
138 /* Basic blocks and flowgraphs. */
139 static void make_blocks (gimple_seq);
140 static void factor_computed_gotos (void);
143 static void make_edges (void);
144 static void assign_discriminators (void);
145 static void make_cond_expr_edges (basic_block);
146 static void make_gimple_switch_edges (basic_block);
147 static void make_goto_expr_edges (basic_block);
148 static void make_gimple_asm_edges (basic_block);
149 static edge gimple_redirect_edge_and_branch (edge, basic_block);
150 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block);
151 static unsigned int split_critical_edges (void);
153 /* Various helpers. */
154 static inline bool stmt_starts_bb_p (gimple, gimple);
155 static int gimple_verify_flow_info (void);
156 static void gimple_make_forwarder_block (edge);
157 static gimple first_non_label_stmt (basic_block);
158 static bool verify_gimple_transaction (gimple);
160 /* Flowgraph optimization and cleanup. */
161 static void gimple_merge_blocks (basic_block, basic_block);
162 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
163 static void remove_bb (basic_block);
164 static edge find_taken_edge_computed_goto (basic_block, tree);
165 static edge find_taken_edge_cond_expr (basic_block, tree);
166 static edge find_taken_edge_switch_expr (basic_block, tree);
167 static tree find_case_label_for_value (gimple, tree);
170 init_empty_tree_cfg_for_function (struct function *fn)
172 /* Initialize the basic block array. */
174 profile_status_for_function (fn) = PROFILE_ABSENT;
175 n_basic_blocks_for_function (fn) = NUM_FIXED_BLOCKS;
176 last_basic_block_for_function (fn) = NUM_FIXED_BLOCKS;
177 vec_alloc (basic_block_info_for_function (fn), initial_cfg_capacity);
178 vec_safe_grow_cleared (basic_block_info_for_function (fn),
179 initial_cfg_capacity);
181 /* Build a mapping of labels to their associated blocks. */
182 vec_alloc (label_to_block_map_for_function (fn), initial_cfg_capacity);
183 vec_safe_grow_cleared (label_to_block_map_for_function (fn),
184 initial_cfg_capacity);
186 SET_BASIC_BLOCK_FOR_FUNCTION (fn, ENTRY_BLOCK,
187 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn));
188 SET_BASIC_BLOCK_FOR_FUNCTION (fn, EXIT_BLOCK,
189 EXIT_BLOCK_PTR_FOR_FUNCTION (fn));
191 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn)->next_bb
192 = EXIT_BLOCK_PTR_FOR_FUNCTION (fn);
193 EXIT_BLOCK_PTR_FOR_FUNCTION (fn)->prev_bb
194 = ENTRY_BLOCK_PTR_FOR_FUNCTION (fn);
198 init_empty_tree_cfg (void)
200 init_empty_tree_cfg_for_function (cfun);
203 /*---------------------------------------------------------------------------
205 ---------------------------------------------------------------------------*/
207 /* Entry point to the CFG builder for trees. SEQ is the sequence of
208 statements to be added to the flowgraph. */
211 build_gimple_cfg (gimple_seq seq)
213 /* Register specific gimple functions. */
214 gimple_register_cfg_hooks ();
216 memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
218 init_empty_tree_cfg ();
220 found_computed_goto = 0;
223 /* Computed gotos are hell to deal with, especially if there are
224 lots of them with a large number of destinations. So we factor
225 them to a common computed goto location before we build the
226 edge list. After we convert back to normal form, we will un-factor
227 the computed gotos since factoring introduces an unwanted jump. */
228 if (found_computed_goto)
229 factor_computed_gotos ();
231 /* Make sure there is always at least one block, even if it's empty. */
232 if (n_basic_blocks == NUM_FIXED_BLOCKS)
233 create_empty_bb (ENTRY_BLOCK_PTR);
235 /* Adjust the size of the array. */
236 if (basic_block_info->length () < (size_t) n_basic_blocks)
237 vec_safe_grow_cleared (basic_block_info, n_basic_blocks);
239 /* To speed up statement iterator walks, we first purge dead labels. */
240 cleanup_dead_labels ();
242 /* Group case nodes to reduce the number of edges.
243 We do this after cleaning up dead labels because otherwise we miss
244 a lot of obvious case merging opportunities. */
245 group_case_labels ();
247 /* Create the edges of the flowgraph. */
248 discriminator_per_locus.create (13);
250 assign_discriminators ();
251 cleanup_dead_labels ();
252 discriminator_per_locus.dispose ();
256 /* Search for ANNOTATE call with annot_expr_ivdep_kind; if found, remove
257 it and set loop->safelen to INT_MAX. We assume that the annotation
258 comes immediately before the condition. */
261 replace_loop_annotate ()
266 gimple_stmt_iterator gsi;
269 FOR_EACH_LOOP (li, loop, 0)
271 gsi = gsi_last_bb (loop->header);
272 stmt = gsi_stmt (gsi);
273 if (stmt && gimple_code (stmt) == GIMPLE_COND)
275 gsi_prev_nondebug (&gsi);
278 stmt = gsi_stmt (gsi);
279 if (gimple_code (stmt) != GIMPLE_CALL)
281 if (!gimple_call_internal_p (stmt)
282 || gimple_call_internal_fn (stmt) != IFN_ANNOTATE)
284 if ((annot_expr_kind) tree_low_cst (gimple_call_arg (stmt, 1), 0)
285 != annot_expr_ivdep_kind)
287 stmt = gimple_build_assign (gimple_call_lhs (stmt),
288 gimple_call_arg (stmt, 0));
289 gsi_replace (&gsi, stmt, true);
290 loop->safelen = INT_MAX;
294 /* Remove IFN_ANNOTATE. Safeguard for the case loop->latch == NULL. */
297 gsi = gsi_last_bb (bb);
298 stmt = gsi_stmt (gsi);
299 if (stmt && gimple_code (stmt) == GIMPLE_COND)
300 gsi_prev_nondebug (&gsi);
303 stmt = gsi_stmt (gsi);
304 if (gimple_code (stmt) != GIMPLE_CALL)
306 if (!gimple_call_internal_p (stmt)
307 || gimple_call_internal_fn (stmt) != IFN_ANNOTATE)
309 if ((annot_expr_kind) tree_low_cst (gimple_call_arg (stmt, 1), 0)
310 != annot_expr_ivdep_kind)
312 warning_at (gimple_location (stmt), 0, "ignoring %<GCC ivdep%> "
314 stmt = gimple_build_assign (gimple_call_lhs (stmt),
315 gimple_call_arg (stmt, 0));
316 gsi_replace (&gsi, stmt, true);
322 execute_build_cfg (void)
324 gimple_seq body = gimple_body (current_function_decl);
326 build_gimple_cfg (body);
327 gimple_set_body (current_function_decl, NULL);
328 if (dump_file && (dump_flags & TDF_DETAILS))
330 fprintf (dump_file, "Scope blocks:\n");
331 dump_scope_blocks (dump_file, dump_flags);
334 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
335 replace_loop_annotate ();
341 const pass_data pass_data_build_cfg =
343 GIMPLE_PASS, /* type */
345 OPTGROUP_NONE, /* optinfo_flags */
346 false, /* has_gate */
347 true, /* has_execute */
348 TV_TREE_CFG, /* tv_id */
349 PROP_gimple_leh, /* properties_required */
350 ( PROP_cfg | PROP_loops ), /* properties_provided */
351 0, /* properties_destroyed */
352 0, /* todo_flags_start */
353 TODO_verify_stmts, /* todo_flags_finish */
356 class pass_build_cfg : public gimple_opt_pass
359 pass_build_cfg (gcc::context *ctxt)
360 : gimple_opt_pass (pass_data_build_cfg, ctxt)
363 /* opt_pass methods: */
364 unsigned int execute () { return execute_build_cfg (); }
366 }; // class pass_build_cfg
371 make_pass_build_cfg (gcc::context *ctxt)
373 return new pass_build_cfg (ctxt);
377 /* Return true if T is a computed goto. */
380 computed_goto_p (gimple t)
382 return (gimple_code (t) == GIMPLE_GOTO
383 && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
386 /* Returns true for edge E where e->src ends with a GIMPLE_COND and
387 the other edge points to a bb with just __builtin_unreachable ().
388 I.e. return true for C->M edge in:
396 __builtin_unreachable ();
400 assert_unreachable_fallthru_edge_p (edge e)
402 basic_block pred_bb = e->src;
403 gimple last = last_stmt (pred_bb);
404 if (last && gimple_code (last) == GIMPLE_COND)
406 basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest;
407 if (other_bb == e->dest)
408 other_bb = EDGE_SUCC (pred_bb, 1)->dest;
409 if (EDGE_COUNT (other_bb->succs) == 0)
411 gimple_stmt_iterator gsi = gsi_after_labels (other_bb);
416 stmt = gsi_stmt (gsi);
417 if (is_gimple_debug (stmt))
419 gsi_next_nondebug (&gsi);
422 stmt = gsi_stmt (gsi);
424 return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE);
431 /* Search the CFG for any computed gotos. If found, factor them to a
432 common computed goto site. Also record the location of that site so
433 that we can un-factor the gotos after we have converted back to
437 factor_computed_gotos (void)
440 tree factored_label_decl = NULL;
442 gimple factored_computed_goto_label = NULL;
443 gimple factored_computed_goto = NULL;
445 /* We know there are one or more computed gotos in this function.
446 Examine the last statement in each basic block to see if the block
447 ends with a computed goto. */
451 gimple_stmt_iterator gsi = gsi_last_bb (bb);
457 last = gsi_stmt (gsi);
459 /* Ignore the computed goto we create when we factor the original
461 if (last == factored_computed_goto)
464 /* If the last statement is a computed goto, factor it. */
465 if (computed_goto_p (last))
469 /* The first time we find a computed goto we need to create
470 the factored goto block and the variable each original
471 computed goto will use for their goto destination. */
472 if (!factored_computed_goto)
474 basic_block new_bb = create_empty_bb (bb);
475 gimple_stmt_iterator new_gsi = gsi_start_bb (new_bb);
477 /* Create the destination of the factored goto. Each original
478 computed goto will put its desired destination into this
479 variable and jump to the label we create immediately
481 var = create_tmp_var (ptr_type_node, "gotovar");
483 /* Build a label for the new block which will contain the
484 factored computed goto. */
485 factored_label_decl = create_artificial_label (UNKNOWN_LOCATION);
486 factored_computed_goto_label
487 = gimple_build_label (factored_label_decl);
488 gsi_insert_after (&new_gsi, factored_computed_goto_label,
491 /* Build our new computed goto. */
492 factored_computed_goto = gimple_build_goto (var);
493 gsi_insert_after (&new_gsi, factored_computed_goto, GSI_NEW_STMT);
496 /* Copy the original computed goto's destination into VAR. */
497 assignment = gimple_build_assign (var, gimple_goto_dest (last));
498 gsi_insert_before (&gsi, assignment, GSI_SAME_STMT);
500 /* And re-vector the computed goto to the new destination. */
501 gimple_goto_set_dest (last, factored_label_decl);
507 /* Build a flowgraph for the sequence of stmts SEQ. */
510 make_blocks (gimple_seq seq)
512 gimple_stmt_iterator i = gsi_start (seq);
514 bool start_new_block = true;
515 bool first_stmt_of_seq = true;
516 basic_block bb = ENTRY_BLOCK_PTR;
518 while (!gsi_end_p (i))
525 /* If the statement starts a new basic block or if we have determined
526 in a previous pass that we need to create a new block for STMT, do
528 if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
530 if (!first_stmt_of_seq)
531 gsi_split_seq_before (&i, &seq);
532 bb = create_basic_block (seq, NULL, bb);
533 start_new_block = false;
536 /* Now add STMT to BB and create the subgraphs for special statement
538 gimple_set_bb (stmt, bb);
540 if (computed_goto_p (stmt))
541 found_computed_goto = true;
543 /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
545 if (stmt_ends_bb_p (stmt))
547 /* If the stmt can make abnormal goto use a new temporary
548 for the assignment to the LHS. This makes sure the old value
549 of the LHS is available on the abnormal edge. Otherwise
550 we will end up with overlapping life-ranges for abnormal
552 if (gimple_has_lhs (stmt)
553 && stmt_can_make_abnormal_goto (stmt)
554 && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt))))
556 tree lhs = gimple_get_lhs (stmt);
557 tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
558 gimple s = gimple_build_assign (lhs, tmp);
559 gimple_set_location (s, gimple_location (stmt));
560 gimple_set_block (s, gimple_block (stmt));
561 gimple_set_lhs (stmt, tmp);
562 if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE
563 || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE)
564 DECL_GIMPLE_REG_P (tmp) = 1;
565 gsi_insert_after (&i, s, GSI_SAME_STMT);
567 start_new_block = true;
571 first_stmt_of_seq = false;
576 /* Create and return a new empty basic block after bb AFTER. */
579 create_bb (void *h, void *e, basic_block after)
585 /* Create and initialize a new basic block. Since alloc_block uses
586 GC allocation that clears memory to allocate a basic block, we do
587 not have to clear the newly allocated basic block here. */
590 bb->index = last_basic_block;
592 set_bb_seq (bb, h ? (gimple_seq) h : NULL);
594 /* Add the new block to the linked list of blocks. */
595 link_block (bb, after);
597 /* Grow the basic block array if needed. */
598 if ((size_t) last_basic_block == basic_block_info->length ())
600 size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
601 vec_safe_grow_cleared (basic_block_info, new_size);
604 /* Add the newly created block to the array. */
605 SET_BASIC_BLOCK (last_basic_block, bb);
614 /*---------------------------------------------------------------------------
616 ---------------------------------------------------------------------------*/
618 /* Fold COND_EXPR_COND of each COND_EXPR. */
621 fold_cond_expr_cond (void)
627 gimple stmt = last_stmt (bb);
629 if (stmt && gimple_code (stmt) == GIMPLE_COND)
631 location_t loc = gimple_location (stmt);
635 fold_defer_overflow_warnings ();
636 cond = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node,
637 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
640 zerop = integer_zerop (cond);
641 onep = integer_onep (cond);
644 zerop = onep = false;
646 fold_undefer_overflow_warnings (zerop || onep,
648 WARN_STRICT_OVERFLOW_CONDITIONAL);
650 gimple_cond_make_false (stmt);
652 gimple_cond_make_true (stmt);
657 /* Join all the blocks in the flowgraph. */
663 struct omp_region *cur_region = NULL;
665 /* Create an edge from entry to the first block with executable
667 make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
669 /* Traverse the basic block array placing edges. */
672 gimple last = last_stmt (bb);
677 enum gimple_code code = gimple_code (last);
681 make_goto_expr_edges (bb);
685 make_edge (bb, EXIT_BLOCK_PTR, 0);
689 make_cond_expr_edges (bb);
693 make_gimple_switch_edges (bb);
697 make_eh_edges (last);
700 case GIMPLE_EH_DISPATCH:
701 fallthru = make_eh_dispatch_edges (last);
705 /* If this function receives a nonlocal goto, then we need to
706 make edges from this call site to all the nonlocal goto
708 if (stmt_can_make_abnormal_goto (last))
709 make_abnormal_goto_edges (bb, true);
711 /* If this statement has reachable exception handlers, then
712 create abnormal edges to them. */
713 make_eh_edges (last);
715 /* BUILTIN_RETURN is really a return statement. */
716 if (gimple_call_builtin_p (last, BUILT_IN_RETURN))
717 make_edge (bb, EXIT_BLOCK_PTR, 0), fallthru = false;
718 /* Some calls are known not to return. */
720 fallthru = !(gimple_call_flags (last) & ECF_NORETURN);
724 /* A GIMPLE_ASSIGN may throw internally and thus be considered
726 if (is_ctrl_altering_stmt (last))
727 make_eh_edges (last);
732 make_gimple_asm_edges (bb);
737 fallthru = make_gimple_omp_edges (bb, &cur_region);
740 case GIMPLE_TRANSACTION:
742 tree abort_label = gimple_transaction_label (last);
744 make_edge (bb, label_to_block (abort_label), EDGE_TM_ABORT);
750 gcc_assert (!stmt_ends_bb_p (last));
758 make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
763 /* Fold COND_EXPR_COND of each COND_EXPR. */
764 fold_cond_expr_cond ();
767 /* Find the next available discriminator value for LOCUS. The
768 discriminator distinguishes among several basic blocks that
769 share a common locus, allowing for more accurate sample-based
773 next_discriminator_for_locus (location_t locus)
775 struct locus_discrim_map item;
776 struct locus_discrim_map **slot;
779 item.discriminator = 0;
780 slot = discriminator_per_locus.find_slot_with_hash (
781 &item, LOCATION_LINE (locus), INSERT);
783 if (*slot == HTAB_EMPTY_ENTRY)
785 *slot = XNEW (struct locus_discrim_map);
787 (*slot)->locus = locus;
788 (*slot)->discriminator = 0;
790 (*slot)->discriminator++;
791 return (*slot)->discriminator;
794 /* Return TRUE if LOCUS1 and LOCUS2 refer to the same source line. */
797 same_line_p (location_t locus1, location_t locus2)
799 expanded_location from, to;
801 if (locus1 == locus2)
804 from = expand_location (locus1);
805 to = expand_location (locus2);
807 if (from.line != to.line)
809 if (from.file == to.file)
811 return (from.file != NULL
813 && filename_cmp (from.file, to.file) == 0);
816 /* Assign discriminators to each basic block. */
819 assign_discriminators (void)
827 gimple last = last_stmt (bb);
828 location_t locus = last ? gimple_location (last) : UNKNOWN_LOCATION;
830 if (locus == UNKNOWN_LOCATION)
833 FOR_EACH_EDGE (e, ei, bb->succs)
835 gimple first = first_non_label_stmt (e->dest);
836 gimple last = last_stmt (e->dest);
837 if ((first && same_line_p (locus, gimple_location (first)))
838 || (last && same_line_p (locus, gimple_location (last))))
840 if (e->dest->discriminator != 0 && bb->discriminator == 0)
841 bb->discriminator = next_discriminator_for_locus (locus);
843 e->dest->discriminator = next_discriminator_for_locus (locus);
849 /* Create the edges for a GIMPLE_COND starting at block BB. */
852 make_cond_expr_edges (basic_block bb)
854 gimple entry = last_stmt (bb);
855 gimple then_stmt, else_stmt;
856 basic_block then_bb, else_bb;
857 tree then_label, else_label;
861 gcc_assert (gimple_code (entry) == GIMPLE_COND);
863 /* Entry basic blocks for each component. */
864 then_label = gimple_cond_true_label (entry);
865 else_label = gimple_cond_false_label (entry);
866 then_bb = label_to_block (then_label);
867 else_bb = label_to_block (else_label);
868 then_stmt = first_stmt (then_bb);
869 else_stmt = first_stmt (else_bb);
871 e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
872 e->goto_locus = gimple_location (then_stmt);
873 e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
875 e->goto_locus = gimple_location (else_stmt);
877 /* We do not need the labels anymore. */
878 gimple_cond_set_true_label (entry, NULL_TREE);
879 gimple_cond_set_false_label (entry, NULL_TREE);
883 /* Called for each element in the hash table (P) as we delete the
884 edge to cases hash table.
886 Clear all the TREE_CHAINs to prevent problems with copying of
887 SWITCH_EXPRs and structure sharing rules, then free the hash table
891 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
892 void *data ATTRIBUTE_UNUSED)
896 for (t = (tree) *value; t; t = next)
898 next = CASE_CHAIN (t);
899 CASE_CHAIN (t) = NULL;
906 /* Start recording information mapping edges to case labels. */
909 start_recording_case_labels (void)
911 gcc_assert (edge_to_cases == NULL);
912 edge_to_cases = pointer_map_create ();
913 touched_switch_bbs = BITMAP_ALLOC (NULL);
916 /* Return nonzero if we are recording information for case labels. */
919 recording_case_labels_p (void)
921 return (edge_to_cases != NULL);
924 /* Stop recording information mapping edges to case labels and
925 remove any information we have recorded. */
927 end_recording_case_labels (void)
931 pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
932 pointer_map_destroy (edge_to_cases);
933 edge_to_cases = NULL;
934 EXECUTE_IF_SET_IN_BITMAP (touched_switch_bbs, 0, i, bi)
936 basic_block bb = BASIC_BLOCK (i);
939 gimple stmt = last_stmt (bb);
940 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
941 group_case_labels_stmt (stmt);
944 BITMAP_FREE (touched_switch_bbs);
947 /* If we are inside a {start,end}_recording_cases block, then return
948 a chain of CASE_LABEL_EXPRs from T which reference E.
950 Otherwise return NULL. */
953 get_cases_for_edge (edge e, gimple t)
958 /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
959 chains available. Return NULL so the caller can detect this case. */
960 if (!recording_case_labels_p ())
963 slot = pointer_map_contains (edge_to_cases, e);
967 /* If we did not find E in the hash table, then this must be the first
968 time we have been queried for information about E & T. Add all the
969 elements from T to the hash table then perform the query again. */
971 n = gimple_switch_num_labels (t);
972 for (i = 0; i < n; i++)
974 tree elt = gimple_switch_label (t, i);
975 tree lab = CASE_LABEL (elt);
976 basic_block label_bb = label_to_block (lab);
977 edge this_edge = find_edge (e->src, label_bb);
979 /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
981 slot = pointer_map_insert (edge_to_cases, this_edge);
982 CASE_CHAIN (elt) = (tree) *slot;
986 return (tree) *pointer_map_contains (edge_to_cases, e);
989 /* Create the edges for a GIMPLE_SWITCH starting at block BB. */
992 make_gimple_switch_edges (basic_block bb)
994 gimple entry = last_stmt (bb);
997 n = gimple_switch_num_labels (entry);
999 for (i = 0; i < n; ++i)
1001 tree lab = CASE_LABEL (gimple_switch_label (entry, i));
1002 basic_block label_bb = label_to_block (lab);
1003 make_edge (bb, label_bb, 0);
1008 /* Return the basic block holding label DEST. */
1011 label_to_block_fn (struct function *ifun, tree dest)
1013 int uid = LABEL_DECL_UID (dest);
1015 /* We would die hard when faced by an undefined label. Emit a label to
1016 the very first basic block. This will hopefully make even the dataflow
1017 and undefined variable warnings quite right. */
1018 if (seen_error () && uid < 0)
1020 gimple_stmt_iterator gsi = gsi_start_bb (BASIC_BLOCK (NUM_FIXED_BLOCKS));
1023 stmt = gimple_build_label (dest);
1024 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1025 uid = LABEL_DECL_UID (dest);
1027 if (vec_safe_length (ifun->cfg->x_label_to_block_map) <= (unsigned int) uid)
1029 return (*ifun->cfg->x_label_to_block_map)[uid];
1032 /* Create edges for an abnormal goto statement at block BB. If FOR_CALL
1033 is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR. */
1036 make_abnormal_goto_edges (basic_block bb, bool for_call)
1038 basic_block target_bb;
1039 gimple_stmt_iterator gsi;
1041 FOR_EACH_BB (target_bb)
1043 for (gsi = gsi_start_bb (target_bb); !gsi_end_p (gsi); gsi_next (&gsi))
1045 gimple label_stmt = gsi_stmt (gsi);
1048 if (gimple_code (label_stmt) != GIMPLE_LABEL)
1051 target = gimple_label_label (label_stmt);
1053 /* Make an edge to every label block that has been marked as a
1054 potential target for a computed goto or a non-local goto. */
1055 if ((FORCED_LABEL (target) && !for_call)
1056 || (DECL_NONLOCAL (target) && for_call))
1058 make_edge (bb, target_bb, EDGE_ABNORMAL);
1062 if (!gsi_end_p (gsi)
1063 && is_gimple_debug (gsi_stmt (gsi)))
1064 gsi_next_nondebug (&gsi);
1065 if (!gsi_end_p (gsi))
1067 /* Make an edge to every setjmp-like call. */
1068 gimple call_stmt = gsi_stmt (gsi);
1069 if (is_gimple_call (call_stmt)
1070 && (gimple_call_flags (call_stmt) & ECF_RETURNS_TWICE))
1071 make_edge (bb, target_bb, EDGE_ABNORMAL);
1076 /* Create edges for a goto statement at block BB. */
1079 make_goto_expr_edges (basic_block bb)
1081 gimple_stmt_iterator last = gsi_last_bb (bb);
1082 gimple goto_t = gsi_stmt (last);
1084 /* A simple GOTO creates normal edges. */
1085 if (simple_goto_p (goto_t))
1087 tree dest = gimple_goto_dest (goto_t);
1088 basic_block label_bb = label_to_block (dest);
1089 edge e = make_edge (bb, label_bb, EDGE_FALLTHRU);
1090 e->goto_locus = gimple_location (goto_t);
1091 gsi_remove (&last, true);
1095 /* A computed GOTO creates abnormal edges. */
1096 make_abnormal_goto_edges (bb, false);
1099 /* Create edges for an asm statement with labels at block BB. */
1102 make_gimple_asm_edges (basic_block bb)
1104 gimple stmt = last_stmt (bb);
1105 int i, n = gimple_asm_nlabels (stmt);
1107 for (i = 0; i < n; ++i)
1109 tree label = TREE_VALUE (gimple_asm_label_op (stmt, i));
1110 basic_block label_bb = label_to_block (label);
1111 make_edge (bb, label_bb, 0);
1115 /*---------------------------------------------------------------------------
1117 ---------------------------------------------------------------------------*/
1119 /* Cleanup useless labels in basic blocks. This is something we wish
1120 to do early because it allows us to group case labels before creating
1121 the edges for the CFG, and it speeds up block statement iterators in
1122 all passes later on.
1123 We rerun this pass after CFG is created, to get rid of the labels that
1124 are no longer referenced. After then we do not run it any more, since
1125 (almost) no new labels should be created. */
1127 /* A map from basic block index to the leading label of that block. */
1128 static struct label_record
1133 /* True if the label is referenced from somewhere. */
1137 /* Given LABEL return the first label in the same basic block. */
1140 main_block_label (tree label)
1142 basic_block bb = label_to_block (label);
1143 tree main_label = label_for_bb[bb->index].label;
1145 /* label_to_block possibly inserted undefined label into the chain. */
1148 label_for_bb[bb->index].label = label;
1152 label_for_bb[bb->index].used = true;
1156 /* Clean up redundant labels within the exception tree. */
1159 cleanup_dead_labels_eh (void)
1166 if (cfun->eh == NULL)
1169 for (i = 1; vec_safe_iterate (cfun->eh->lp_array, i, &lp); ++i)
1170 if (lp && lp->post_landing_pad)
1172 lab = main_block_label (lp->post_landing_pad);
1173 if (lab != lp->post_landing_pad)
1175 EH_LANDING_PAD_NR (lp->post_landing_pad) = 0;
1176 EH_LANDING_PAD_NR (lab) = lp->index;
1180 FOR_ALL_EH_REGION (r)
1184 case ERT_MUST_NOT_THROW:
1190 for (c = r->u.eh_try.first_catch; c ; c = c->next_catch)
1194 c->label = main_block_label (lab);
1199 case ERT_ALLOWED_EXCEPTIONS:
1200 lab = r->u.allowed.label;
1202 r->u.allowed.label = main_block_label (lab);
1208 /* Cleanup redundant labels. This is a three-step process:
1209 1) Find the leading label for each block.
1210 2) Redirect all references to labels to the leading labels.
1211 3) Cleanup all useless labels. */
1214 cleanup_dead_labels (void)
1217 label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
1219 /* Find a suitable label for each block. We use the first user-defined
1220 label if there is one, or otherwise just the first label we see. */
1223 gimple_stmt_iterator i;
1225 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
1228 gimple stmt = gsi_stmt (i);
1230 if (gimple_code (stmt) != GIMPLE_LABEL)
1233 label = gimple_label_label (stmt);
1235 /* If we have not yet seen a label for the current block,
1236 remember this one and see if there are more labels. */
1237 if (!label_for_bb[bb->index].label)
1239 label_for_bb[bb->index].label = label;
1243 /* If we did see a label for the current block already, but it
1244 is an artificially created label, replace it if the current
1245 label is a user defined label. */
1246 if (!DECL_ARTIFICIAL (label)
1247 && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
1249 label_for_bb[bb->index].label = label;
1255 /* Now redirect all jumps/branches to the selected label.
1256 First do so for each block ending in a control statement. */
1259 gimple stmt = last_stmt (bb);
1260 tree label, new_label;
1265 switch (gimple_code (stmt))
1268 label = gimple_cond_true_label (stmt);
1271 new_label = main_block_label (label);
1272 if (new_label != label)
1273 gimple_cond_set_true_label (stmt, new_label);
1276 label = gimple_cond_false_label (stmt);
1279 new_label = main_block_label (label);
1280 if (new_label != label)
1281 gimple_cond_set_false_label (stmt, new_label);
1287 size_t i, n = gimple_switch_num_labels (stmt);
1289 /* Replace all destination labels. */
1290 for (i = 0; i < n; ++i)
1292 tree case_label = gimple_switch_label (stmt, i);
1293 label = CASE_LABEL (case_label);
1294 new_label = main_block_label (label);
1295 if (new_label != label)
1296 CASE_LABEL (case_label) = new_label;
1303 int i, n = gimple_asm_nlabels (stmt);
1305 for (i = 0; i < n; ++i)
1307 tree cons = gimple_asm_label_op (stmt, i);
1308 tree label = main_block_label (TREE_VALUE (cons));
1309 TREE_VALUE (cons) = label;
1314 /* We have to handle gotos until they're removed, and we don't
1315 remove them until after we've created the CFG edges. */
1317 if (!computed_goto_p (stmt))
1319 label = gimple_goto_dest (stmt);
1320 new_label = main_block_label (label);
1321 if (new_label != label)
1322 gimple_goto_set_dest (stmt, new_label);
1326 case GIMPLE_TRANSACTION:
1328 tree label = gimple_transaction_label (stmt);
1331 tree new_label = main_block_label (label);
1332 if (new_label != label)
1333 gimple_transaction_set_label (stmt, new_label);
1343 /* Do the same for the exception region tree labels. */
1344 cleanup_dead_labels_eh ();
1346 /* Finally, purge dead labels. All user-defined labels and labels that
1347 can be the target of non-local gotos and labels which have their
1348 address taken are preserved. */
1351 gimple_stmt_iterator i;
1352 tree label_for_this_bb = label_for_bb[bb->index].label;
1354 if (!label_for_this_bb)
1357 /* If the main label of the block is unused, we may still remove it. */
1358 if (!label_for_bb[bb->index].used)
1359 label_for_this_bb = NULL;
1361 for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1364 gimple stmt = gsi_stmt (i);
1366 if (gimple_code (stmt) != GIMPLE_LABEL)
1369 label = gimple_label_label (stmt);
1371 if (label == label_for_this_bb
1372 || !DECL_ARTIFICIAL (label)
1373 || DECL_NONLOCAL (label)
1374 || FORCED_LABEL (label))
1377 gsi_remove (&i, true);
1381 free (label_for_bb);
1384 /* Scan the sorted vector of cases in STMT (a GIMPLE_SWITCH) and combine
1385 the ones jumping to the same label.
1386 Eg. three separate entries 1: 2: 3: become one entry 1..3: */
1389 group_case_labels_stmt (gimple stmt)
1391 int old_size = gimple_switch_num_labels (stmt);
1392 int i, j, new_size = old_size;
1393 basic_block default_bb = NULL;
1395 default_bb = label_to_block (CASE_LABEL (gimple_switch_default_label (stmt)));
1397 /* Look for possible opportunities to merge cases. */
1399 while (i < old_size)
1401 tree base_case, base_high;
1402 basic_block base_bb;
1404 base_case = gimple_switch_label (stmt, i);
1406 gcc_assert (base_case);
1407 base_bb = label_to_block (CASE_LABEL (base_case));
1409 /* Discard cases that have the same destination as the
1411 if (base_bb == default_bb)
1413 gimple_switch_set_label (stmt, i, NULL_TREE);
1419 base_high = CASE_HIGH (base_case)
1420 ? CASE_HIGH (base_case)
1421 : CASE_LOW (base_case);
1424 /* Try to merge case labels. Break out when we reach the end
1425 of the label vector or when we cannot merge the next case
1426 label with the current one. */
1427 while (i < old_size)
1429 tree merge_case = gimple_switch_label (stmt, i);
1430 basic_block merge_bb = label_to_block (CASE_LABEL (merge_case));
1431 double_int bhp1 = tree_to_double_int (base_high) + double_int_one;
1433 /* Merge the cases if they jump to the same place,
1434 and their ranges are consecutive. */
1435 if (merge_bb == base_bb
1436 && tree_to_double_int (CASE_LOW (merge_case)) == bhp1)
1438 base_high = CASE_HIGH (merge_case) ?
1439 CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1440 CASE_HIGH (base_case) = base_high;
1441 gimple_switch_set_label (stmt, i, NULL_TREE);
1450 /* Compress the case labels in the label vector, and adjust the
1451 length of the vector. */
1452 for (i = 0, j = 0; i < new_size; i++)
1454 while (! gimple_switch_label (stmt, j))
1456 gimple_switch_set_label (stmt, i,
1457 gimple_switch_label (stmt, j++));
1460 gcc_assert (new_size <= old_size);
1461 gimple_switch_set_num_labels (stmt, new_size);
1464 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
1465 and scan the sorted vector of cases. Combine the ones jumping to the
1469 group_case_labels (void)
1475 gimple stmt = last_stmt (bb);
1476 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1477 group_case_labels_stmt (stmt);
1481 /* Checks whether we can merge block B into block A. */
1484 gimple_can_merge_blocks_p (basic_block a, basic_block b)
1487 gimple_stmt_iterator gsi;
1489 if (!single_succ_p (a))
1492 if (single_succ_edge (a)->flags & EDGE_COMPLEX)
1495 if (single_succ (a) != b)
1498 if (!single_pred_p (b))
1501 if (b == EXIT_BLOCK_PTR)
1504 /* If A ends by a statement causing exceptions or something similar, we
1505 cannot merge the blocks. */
1506 stmt = last_stmt (a);
1507 if (stmt && stmt_ends_bb_p (stmt))
1510 /* Do not allow a block with only a non-local label to be merged. */
1512 && gimple_code (stmt) == GIMPLE_LABEL
1513 && DECL_NONLOCAL (gimple_label_label (stmt)))
1516 /* Examine the labels at the beginning of B. */
1517 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
1520 stmt = gsi_stmt (gsi);
1521 if (gimple_code (stmt) != GIMPLE_LABEL)
1523 lab = gimple_label_label (stmt);
1525 /* Do not remove user forced labels or for -O0 any user labels. */
1526 if (!DECL_ARTIFICIAL (lab) && (!optimize || FORCED_LABEL (lab)))
1530 /* Protect the loop latches. */
1531 if (current_loops && b->loop_father->latch == b)
1534 /* It must be possible to eliminate all phi nodes in B. If ssa form
1535 is not up-to-date and a name-mapping is registered, we cannot eliminate
1536 any phis. Symbols marked for renaming are never a problem though. */
1537 for (gsi = gsi_start_phis (b); !gsi_end_p (gsi); gsi_next (&gsi))
1539 gimple phi = gsi_stmt (gsi);
1540 /* Technically only new names matter. */
1541 if (name_registered_for_update_p (PHI_RESULT (phi)))
1545 /* When not optimizing, don't merge if we'd lose goto_locus. */
1547 && single_succ_edge (a)->goto_locus != UNKNOWN_LOCATION)
1549 location_t goto_locus = single_succ_edge (a)->goto_locus;
1550 gimple_stmt_iterator prev, next;
1551 prev = gsi_last_nondebug_bb (a);
1552 next = gsi_after_labels (b);
1553 if (!gsi_end_p (next) && is_gimple_debug (gsi_stmt (next)))
1554 gsi_next_nondebug (&next);
1555 if ((gsi_end_p (prev)
1556 || gimple_location (gsi_stmt (prev)) != goto_locus)
1557 && (gsi_end_p (next)
1558 || gimple_location (gsi_stmt (next)) != goto_locus))
1565 /* Replaces all uses of NAME by VAL. */
1568 replace_uses_by (tree name, tree val)
1570 imm_use_iterator imm_iter;
1575 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1577 FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1579 replace_exp (use, val);
1581 if (gimple_code (stmt) == GIMPLE_PHI)
1583 e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use));
1584 if (e->flags & EDGE_ABNORMAL)
1586 /* This can only occur for virtual operands, since
1587 for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1588 would prevent replacement. */
1589 gcc_checking_assert (virtual_operand_p (name));
1590 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1595 if (gimple_code (stmt) != GIMPLE_PHI)
1597 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1598 gimple orig_stmt = stmt;
1601 /* Mark the block if we changed the last stmt in it. */
1602 if (cfgcleanup_altered_bbs
1603 && stmt_ends_bb_p (stmt))
1604 bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1606 /* FIXME. It shouldn't be required to keep TREE_CONSTANT
1607 on ADDR_EXPRs up-to-date on GIMPLE. Propagation will
1608 only change sth from non-invariant to invariant, and only
1609 when propagating constants. */
1610 if (is_gimple_min_invariant (val))
1611 for (i = 0; i < gimple_num_ops (stmt); i++)
1613 tree op = gimple_op (stmt, i);
1614 /* Operands may be empty here. For example, the labels
1615 of a GIMPLE_COND are nulled out following the creation
1616 of the corresponding CFG edges. */
1617 if (op && TREE_CODE (op) == ADDR_EXPR)
1618 recompute_tree_invariant_for_addr_expr (op);
1621 if (fold_stmt (&gsi))
1622 stmt = gsi_stmt (gsi);
1624 if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
1625 gimple_purge_dead_eh_edges (gimple_bb (stmt));
1631 gcc_checking_assert (has_zero_uses (name));
1633 /* Also update the trees stored in loop structures. */
1639 FOR_EACH_LOOP (li, loop, 0)
1641 substitute_in_loop_info (loop, name, val);
1646 /* Merge block B into block A. */
1649 gimple_merge_blocks (basic_block a, basic_block b)
1651 gimple_stmt_iterator last, gsi, psi;
1654 fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1656 /* Remove all single-valued PHI nodes from block B of the form
1657 V_i = PHI <V_j> by propagating V_j to all the uses of V_i. */
1658 gsi = gsi_last_bb (a);
1659 for (psi = gsi_start_phis (b); !gsi_end_p (psi); )
1661 gimple phi = gsi_stmt (psi);
1662 tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1664 bool may_replace_uses = (virtual_operand_p (def)
1665 || may_propagate_copy (def, use));
1667 /* In case we maintain loop closed ssa form, do not propagate arguments
1668 of loop exit phi nodes. */
1670 && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1671 && !virtual_operand_p (def)
1672 && TREE_CODE (use) == SSA_NAME
1673 && a->loop_father != b->loop_father)
1674 may_replace_uses = false;
1676 if (!may_replace_uses)
1678 gcc_assert (!virtual_operand_p (def));
1680 /* Note that just emitting the copies is fine -- there is no problem
1681 with ordering of phi nodes. This is because A is the single
1682 predecessor of B, therefore results of the phi nodes cannot
1683 appear as arguments of the phi nodes. */
1684 copy = gimple_build_assign (def, use);
1685 gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1686 remove_phi_node (&psi, false);
1690 /* If we deal with a PHI for virtual operands, we can simply
1691 propagate these without fussing with folding or updating
1693 if (virtual_operand_p (def))
1695 imm_use_iterator iter;
1696 use_operand_p use_p;
1699 FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1700 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1701 SET_USE (use_p, use);
1703 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
1704 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use) = 1;
1707 replace_uses_by (def, use);
1709 remove_phi_node (&psi, true);
1713 /* Ensure that B follows A. */
1714 move_block_after (b, a);
1716 gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1717 gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1719 /* Remove labels from B and set gimple_bb to A for other statements. */
1720 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1722 gimple stmt = gsi_stmt (gsi);
1723 if (gimple_code (stmt) == GIMPLE_LABEL)
1725 tree label = gimple_label_label (stmt);
1728 gsi_remove (&gsi, false);
1730 /* Now that we can thread computed gotos, we might have
1731 a situation where we have a forced label in block B
1732 However, the label at the start of block B might still be
1733 used in other ways (think about the runtime checking for
1734 Fortran assigned gotos). So we can not just delete the
1735 label. Instead we move the label to the start of block A. */
1736 if (FORCED_LABEL (label))
1738 gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1739 gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT);
1741 /* Other user labels keep around in a form of a debug stmt. */
1742 else if (!DECL_ARTIFICIAL (label) && MAY_HAVE_DEBUG_STMTS)
1744 gimple dbg = gimple_build_debug_bind (label,
1747 gimple_debug_bind_reset_value (dbg);
1748 gsi_insert_before (&gsi, dbg, GSI_SAME_STMT);
1751 lp_nr = EH_LANDING_PAD_NR (label);
1754 eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1755 lp->post_landing_pad = NULL;
1760 gimple_set_bb (stmt, a);
1765 /* Merge the sequences. */
1766 last = gsi_last_bb (a);
1767 gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1768 set_bb_seq (b, NULL);
1770 if (cfgcleanup_altered_bbs)
1771 bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1775 /* Return the one of two successors of BB that is not reachable by a
1776 complex edge, if there is one. Else, return BB. We use
1777 this in optimizations that use post-dominators for their heuristics,
1778 to catch the cases in C++ where function calls are involved. */
1781 single_noncomplex_succ (basic_block bb)
1784 if (EDGE_COUNT (bb->succs) != 2)
1787 e0 = EDGE_SUCC (bb, 0);
1788 e1 = EDGE_SUCC (bb, 1);
1789 if (e0->flags & EDGE_COMPLEX)
1791 if (e1->flags & EDGE_COMPLEX)
1797 /* T is CALL_EXPR. Set current_function_calls_* flags. */
1800 notice_special_calls (gimple call)
1802 int flags = gimple_call_flags (call);
1804 if (flags & ECF_MAY_BE_ALLOCA)
1805 cfun->calls_alloca = true;
1806 if (flags & ECF_RETURNS_TWICE)
1807 cfun->calls_setjmp = true;
1811 /* Clear flags set by notice_special_calls. Used by dead code removal
1812 to update the flags. */
1815 clear_special_calls (void)
1817 cfun->calls_alloca = false;
1818 cfun->calls_setjmp = false;
1821 /* Remove PHI nodes associated with basic block BB and all edges out of BB. */
1824 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1826 /* Since this block is no longer reachable, we can just delete all
1827 of its PHI nodes. */
1828 remove_phi_nodes (bb);
1830 /* Remove edges to BB's successors. */
1831 while (EDGE_COUNT (bb->succs) > 0)
1832 remove_edge (EDGE_SUCC (bb, 0));
1836 /* Remove statements of basic block BB. */
1839 remove_bb (basic_block bb)
1841 gimple_stmt_iterator i;
1845 fprintf (dump_file, "Removing basic block %d\n", bb->index);
1846 if (dump_flags & TDF_DETAILS)
1848 dump_bb (dump_file, bb, 0, dump_flags);
1849 fprintf (dump_file, "\n");
1855 struct loop *loop = bb->loop_father;
1857 /* If a loop gets removed, clean up the information associated
1859 if (loop->latch == bb
1860 || loop->header == bb)
1861 free_numbers_of_iterations_estimates_loop (loop);
1864 /* Remove all the instructions in the block. */
1865 if (bb_seq (bb) != NULL)
1867 /* Walk backwards so as to get a chance to substitute all
1868 released DEFs into debug stmts. See
1869 eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
1871 for (i = gsi_last_bb (bb); !gsi_end_p (i);)
1873 gimple stmt = gsi_stmt (i);
1874 if (gimple_code (stmt) == GIMPLE_LABEL
1875 && (FORCED_LABEL (gimple_label_label (stmt))
1876 || DECL_NONLOCAL (gimple_label_label (stmt))))
1879 gimple_stmt_iterator new_gsi;
1881 /* A non-reachable non-local label may still be referenced.
1882 But it no longer needs to carry the extra semantics of
1884 if (DECL_NONLOCAL (gimple_label_label (stmt)))
1886 DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
1887 FORCED_LABEL (gimple_label_label (stmt)) = 1;
1890 new_bb = bb->prev_bb;
1891 new_gsi = gsi_start_bb (new_bb);
1892 gsi_remove (&i, false);
1893 gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
1897 /* Release SSA definitions if we are in SSA. Note that we
1898 may be called when not in SSA. For example,
1899 final_cleanup calls this function via
1900 cleanup_tree_cfg. */
1901 if (gimple_in_ssa_p (cfun))
1902 release_defs (stmt);
1904 gsi_remove (&i, true);
1908 i = gsi_last_bb (bb);
1914 remove_phi_nodes_and_edges_for_unreachable_block (bb);
1915 bb->il.gimple.seq = NULL;
1916 bb->il.gimple.phi_nodes = NULL;
1920 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
1921 predicate VAL, return the edge that will be taken out of the block.
1922 If VAL does not match a unique edge, NULL is returned. */
1925 find_taken_edge (basic_block bb, tree val)
1929 stmt = last_stmt (bb);
1932 gcc_assert (is_ctrl_stmt (stmt));
1937 if (!is_gimple_min_invariant (val))
1940 if (gimple_code (stmt) == GIMPLE_COND)
1941 return find_taken_edge_cond_expr (bb, val);
1943 if (gimple_code (stmt) == GIMPLE_SWITCH)
1944 return find_taken_edge_switch_expr (bb, val);
1946 if (computed_goto_p (stmt))
1948 /* Only optimize if the argument is a label, if the argument is
1949 not a label then we can not construct a proper CFG.
1951 It may be the case that we only need to allow the LABEL_REF to
1952 appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
1953 appear inside a LABEL_EXPR just to be safe. */
1954 if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
1955 && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
1956 return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
1963 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
1964 statement, determine which of the outgoing edges will be taken out of the
1965 block. Return NULL if either edge may be taken. */
1968 find_taken_edge_computed_goto (basic_block bb, tree val)
1973 dest = label_to_block (val);
1976 e = find_edge (bb, dest);
1977 gcc_assert (e != NULL);
1983 /* Given a constant value VAL and the entry block BB to a COND_EXPR
1984 statement, determine which of the two edges will be taken out of the
1985 block. Return NULL if either edge may be taken. */
1988 find_taken_edge_cond_expr (basic_block bb, tree val)
1990 edge true_edge, false_edge;
1992 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1994 gcc_assert (TREE_CODE (val) == INTEGER_CST);
1995 return (integer_zerop (val) ? false_edge : true_edge);
1998 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
1999 statement, determine which edge will be taken out of the block. Return
2000 NULL if any edge may be taken. */
2003 find_taken_edge_switch_expr (basic_block bb, tree val)
2005 basic_block dest_bb;
2010 switch_stmt = last_stmt (bb);
2011 taken_case = find_case_label_for_value (switch_stmt, val);
2012 dest_bb = label_to_block (CASE_LABEL (taken_case));
2014 e = find_edge (bb, dest_bb);
2020 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
2021 We can make optimal use here of the fact that the case labels are
2022 sorted: We can do a binary search for a case matching VAL. */
2025 find_case_label_for_value (gimple switch_stmt, tree val)
2027 size_t low, high, n = gimple_switch_num_labels (switch_stmt);
2028 tree default_case = gimple_switch_default_label (switch_stmt);
2030 for (low = 0, high = n; high - low > 1; )
2032 size_t i = (high + low) / 2;
2033 tree t = gimple_switch_label (switch_stmt, i);
2036 /* Cache the result of comparing CASE_LOW and val. */
2037 cmp = tree_int_cst_compare (CASE_LOW (t), val);
2044 if (CASE_HIGH (t) == NULL)
2046 /* A singe-valued case label. */
2052 /* A case range. We can only handle integer ranges. */
2053 if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2058 return default_case;
2062 /* Dump a basic block on stderr. */
2065 gimple_debug_bb (basic_block bb)
2067 dump_bb (stderr, bb, 0, TDF_VOPS|TDF_MEMSYMS|TDF_BLOCKS);
2071 /* Dump basic block with index N on stderr. */
2074 gimple_debug_bb_n (int n)
2076 gimple_debug_bb (BASIC_BLOCK (n));
2077 return BASIC_BLOCK (n);
2081 /* Dump the CFG on stderr.
2083 FLAGS are the same used by the tree dumping functions
2084 (see TDF_* in dumpfile.h). */
2087 gimple_debug_cfg (int flags)
2089 gimple_dump_cfg (stderr, flags);
2093 /* Dump the program showing basic block boundaries on the given FILE.
2095 FLAGS are the same used by the tree dumping functions (see TDF_* in
2099 gimple_dump_cfg (FILE *file, int flags)
2101 if (flags & TDF_DETAILS)
2103 dump_function_header (file, current_function_decl, flags);
2104 fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2105 n_basic_blocks, n_edges, last_basic_block);
2107 brief_dump_cfg (file, flags | TDF_COMMENT);
2108 fprintf (file, "\n");
2111 if (flags & TDF_STATS)
2112 dump_cfg_stats (file);
2114 dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2118 /* Dump CFG statistics on FILE. */
2121 dump_cfg_stats (FILE *file)
2123 static long max_num_merged_labels = 0;
2124 unsigned long size, total = 0;
2127 const char * const fmt_str = "%-30s%-13s%12s\n";
2128 const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2129 const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2130 const char * const fmt_str_3 = "%-43s%11lu%c\n";
2131 const char *funcname = current_function_name ();
2133 fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2135 fprintf (file, "---------------------------------------------------------\n");
2136 fprintf (file, fmt_str, "", " Number of ", "Memory");
2137 fprintf (file, fmt_str, "", " instances ", "used ");
2138 fprintf (file, "---------------------------------------------------------\n");
2140 size = n_basic_blocks * sizeof (struct basic_block_def);
2142 fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2143 SCALE (size), LABEL (size));
2147 num_edges += EDGE_COUNT (bb->succs);
2148 size = num_edges * sizeof (struct edge_def);
2150 fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2152 fprintf (file, "---------------------------------------------------------\n");
2153 fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2155 fprintf (file, "---------------------------------------------------------\n");
2156 fprintf (file, "\n");
2158 if (cfg_stats.num_merged_labels > max_num_merged_labels)
2159 max_num_merged_labels = cfg_stats.num_merged_labels;
2161 fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2162 cfg_stats.num_merged_labels, max_num_merged_labels);
2164 fprintf (file, "\n");
2168 /* Dump CFG statistics on stderr. Keep extern so that it's always
2169 linked in the final executable. */
2172 debug_cfg_stats (void)
2174 dump_cfg_stats (stderr);
2177 /*---------------------------------------------------------------------------
2178 Miscellaneous helpers
2179 ---------------------------------------------------------------------------*/
2181 /* Return true if T, a GIMPLE_CALL, can make an abnormal transfer of control
2182 flow. Transfers of control flow associated with EH are excluded. */
2185 call_can_make_abnormal_goto (gimple t)
2187 /* If the function has no non-local labels, then a call cannot make an
2188 abnormal transfer of control. */
2189 if (!cfun->has_nonlocal_label
2190 && !cfun->calls_setjmp)
2193 /* Likewise if the call has no side effects. */
2194 if (!gimple_has_side_effects (t))
2197 /* Likewise if the called function is leaf. */
2198 if (gimple_call_flags (t) & ECF_LEAF)
2205 /* Return true if T can make an abnormal transfer of control flow.
2206 Transfers of control flow associated with EH are excluded. */
2209 stmt_can_make_abnormal_goto (gimple t)
2211 if (computed_goto_p (t))
2213 if (is_gimple_call (t))
2214 return call_can_make_abnormal_goto (t);
2219 /* Return true if T represents a stmt that always transfers control. */
2222 is_ctrl_stmt (gimple t)
2224 switch (gimple_code (t))
2238 /* Return true if T is a statement that may alter the flow of control
2239 (e.g., a call to a non-returning function). */
2242 is_ctrl_altering_stmt (gimple t)
2246 switch (gimple_code (t))
2250 int flags = gimple_call_flags (t);
2252 /* A call alters control flow if it can make an abnormal goto. */
2253 if (call_can_make_abnormal_goto (t))
2256 /* A call also alters control flow if it does not return. */
2257 if (flags & ECF_NORETURN)
2260 /* TM ending statements have backedges out of the transaction.
2261 Return true so we split the basic block containing them.
2262 Note that the TM_BUILTIN test is merely an optimization. */
2263 if ((flags & ECF_TM_BUILTIN)
2264 && is_tm_ending_fndecl (gimple_call_fndecl (t)))
2267 /* BUILT_IN_RETURN call is same as return statement. */
2268 if (gimple_call_builtin_p (t, BUILT_IN_RETURN))
2273 case GIMPLE_EH_DISPATCH:
2274 /* EH_DISPATCH branches to the individual catch handlers at
2275 this level of a try or allowed-exceptions region. It can
2276 fallthru to the next statement as well. */
2280 if (gimple_asm_nlabels (t) > 0)
2285 /* OpenMP directives alter control flow. */
2288 case GIMPLE_TRANSACTION:
2289 /* A transaction start alters control flow. */
2296 /* If a statement can throw, it alters control flow. */
2297 return stmt_can_throw_internal (t);
2301 /* Return true if T is a simple local goto. */
2304 simple_goto_p (gimple t)
2306 return (gimple_code (t) == GIMPLE_GOTO
2307 && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2311 /* Return true if STMT should start a new basic block. PREV_STMT is
2312 the statement preceding STMT. It is used when STMT is a label or a
2313 case label. Labels should only start a new basic block if their
2314 previous statement wasn't a label. Otherwise, sequence of labels
2315 would generate unnecessary basic blocks that only contain a single
2319 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2324 /* Labels start a new basic block only if the preceding statement
2325 wasn't a label of the same type. This prevents the creation of
2326 consecutive blocks that have nothing but a single label. */
2327 if (gimple_code (stmt) == GIMPLE_LABEL)
2329 /* Nonlocal and computed GOTO targets always start a new block. */
2330 if (DECL_NONLOCAL (gimple_label_label (stmt))
2331 || FORCED_LABEL (gimple_label_label (stmt)))
2334 if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2336 if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2339 cfg_stats.num_merged_labels++;
2345 else if (gimple_code (stmt) == GIMPLE_CALL
2346 && gimple_call_flags (stmt) & ECF_RETURNS_TWICE)
2347 /* setjmp acts similar to a nonlocal GOTO target and thus should
2348 start a new block. */
2355 /* Return true if T should end a basic block. */
2358 stmt_ends_bb_p (gimple t)
2360 return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2363 /* Remove block annotations and other data structures. */
2366 delete_tree_cfg_annotations (void)
2368 vec_free (label_to_block_map);
2372 /* Return the first statement in basic block BB. */
2375 first_stmt (basic_block bb)
2377 gimple_stmt_iterator i = gsi_start_bb (bb);
2380 while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2388 /* Return the first non-label statement in basic block BB. */
2391 first_non_label_stmt (basic_block bb)
2393 gimple_stmt_iterator i = gsi_start_bb (bb);
2394 while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2396 return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2399 /* Return the last statement in basic block BB. */
2402 last_stmt (basic_block bb)
2404 gimple_stmt_iterator i = gsi_last_bb (bb);
2407 while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2415 /* Return the last statement of an otherwise empty block. Return NULL
2416 if the block is totally empty, or if it contains more than one
2420 last_and_only_stmt (basic_block bb)
2422 gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
2428 last = gsi_stmt (i);
2429 gsi_prev_nondebug (&i);
2433 /* Empty statements should no longer appear in the instruction stream.
2434 Everything that might have appeared before should be deleted by
2435 remove_useless_stmts, and the optimizers should just gsi_remove
2436 instead of smashing with build_empty_stmt.
2438 Thus the only thing that should appear here in a block containing
2439 one executable statement is a label. */
2440 prev = gsi_stmt (i);
2441 if (gimple_code (prev) == GIMPLE_LABEL)
2447 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE. */
2450 reinstall_phi_args (edge new_edge, edge old_edge)
2452 edge_var_map_vector *v;
2455 gimple_stmt_iterator phis;
2457 v = redirect_edge_var_map_vector (old_edge);
2461 for (i = 0, phis = gsi_start_phis (new_edge->dest);
2462 v->iterate (i, &vm) && !gsi_end_p (phis);
2463 i++, gsi_next (&phis))
2465 gimple phi = gsi_stmt (phis);
2466 tree result = redirect_edge_var_map_result (vm);
2467 tree arg = redirect_edge_var_map_def (vm);
2469 gcc_assert (result == gimple_phi_result (phi));
2471 add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
2474 redirect_edge_var_map_clear (old_edge);
2477 /* Returns the basic block after which the new basic block created
2478 by splitting edge EDGE_IN should be placed. Tries to keep the new block
2479 near its "logical" location. This is of most help to humans looking
2480 at debugging dumps. */
2483 split_edge_bb_loc (edge edge_in)
2485 basic_block dest = edge_in->dest;
2486 basic_block dest_prev = dest->prev_bb;
2490 edge e = find_edge (dest_prev, dest);
2491 if (e && !(e->flags & EDGE_COMPLEX))
2492 return edge_in->src;
2497 /* Split a (typically critical) edge EDGE_IN. Return the new block.
2498 Abort on abnormal edges. */
2501 gimple_split_edge (edge edge_in)
2503 basic_block new_bb, after_bb, dest;
2506 /* Abnormal edges cannot be split. */
2507 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2509 dest = edge_in->dest;
2511 after_bb = split_edge_bb_loc (edge_in);
2513 new_bb = create_empty_bb (after_bb);
2514 new_bb->frequency = EDGE_FREQUENCY (edge_in);
2515 new_bb->count = edge_in->count;
2516 new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2517 new_edge->probability = REG_BR_PROB_BASE;
2518 new_edge->count = edge_in->count;
2520 e = redirect_edge_and_branch (edge_in, new_bb);
2521 gcc_assert (e == edge_in);
2522 reinstall_phi_args (new_edge, e);
2528 /* Verify properties of the address expression T with base object BASE. */
2531 verify_address (tree t, tree base)
2534 bool old_side_effects;
2536 bool new_side_effects;
2538 old_constant = TREE_CONSTANT (t);
2539 old_side_effects = TREE_SIDE_EFFECTS (t);
2541 recompute_tree_invariant_for_addr_expr (t);
2542 new_side_effects = TREE_SIDE_EFFECTS (t);
2543 new_constant = TREE_CONSTANT (t);
2545 if (old_constant != new_constant)
2547 error ("constant not recomputed when ADDR_EXPR changed");
2550 if (old_side_effects != new_side_effects)
2552 error ("side effects not recomputed when ADDR_EXPR changed");
2556 if (!(TREE_CODE (base) == VAR_DECL
2557 || TREE_CODE (base) == PARM_DECL
2558 || TREE_CODE (base) == RESULT_DECL))
2561 if (DECL_GIMPLE_REG_P (base))
2563 error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2570 /* Callback for walk_tree, check that all elements with address taken are
2571 properly noticed as such. The DATA is an int* that is 1 if TP was seen
2572 inside a PHI node. */
2575 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2582 /* Check operand N for being valid GIMPLE and give error MSG if not. */
2583 #define CHECK_OP(N, MSG) \
2584 do { if (!is_gimple_val (TREE_OPERAND (t, N))) \
2585 { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2587 switch (TREE_CODE (t))
2590 if (SSA_NAME_IN_FREE_LIST (t))
2592 error ("SSA name in freelist but still referenced");
2598 error ("INDIRECT_REF in gimple IL");
2602 x = TREE_OPERAND (t, 0);
2603 if (!POINTER_TYPE_P (TREE_TYPE (x))
2604 || !is_gimple_mem_ref_addr (x))
2606 error ("invalid first operand of MEM_REF");
2609 if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST
2610 || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1))))
2612 error ("invalid offset operand of MEM_REF");
2613 return TREE_OPERAND (t, 1);
2615 if (TREE_CODE (x) == ADDR_EXPR
2616 && (x = verify_address (x, TREE_OPERAND (x, 0))))
2622 x = fold (ASSERT_EXPR_COND (t));
2623 if (x == boolean_false_node)
2625 error ("ASSERT_EXPR with an always-false condition");
2631 error ("MODIFY_EXPR not expected while having tuples");
2638 gcc_assert (is_gimple_address (t));
2640 /* Skip any references (they will be checked when we recurse down the
2641 tree) and ensure that any variable used as a prefix is marked
2643 for (x = TREE_OPERAND (t, 0);
2644 handled_component_p (x);
2645 x = TREE_OPERAND (x, 0))
2648 if ((tem = verify_address (t, x)))
2651 if (!(TREE_CODE (x) == VAR_DECL
2652 || TREE_CODE (x) == PARM_DECL
2653 || TREE_CODE (x) == RESULT_DECL))
2656 if (!TREE_ADDRESSABLE (x))
2658 error ("address taken, but ADDRESSABLE bit not set");
2666 x = COND_EXPR_COND (t);
2667 if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2669 error ("non-integral used in condition");
2672 if (!is_gimple_condexpr (x))
2674 error ("invalid conditional operand");
2679 case NON_LVALUE_EXPR:
2680 case TRUTH_NOT_EXPR:
2684 case FIX_TRUNC_EXPR:
2689 CHECK_OP (0, "invalid operand to unary operator");
2695 if (!is_gimple_reg_type (TREE_TYPE (t)))
2697 error ("non-scalar BIT_FIELD_REF, IMAGPART_EXPR or REALPART_EXPR");
2701 if (TREE_CODE (t) == BIT_FIELD_REF)
2703 if (!host_integerp (TREE_OPERAND (t, 1), 1)
2704 || !host_integerp (TREE_OPERAND (t, 2), 1))
2706 error ("invalid position or size operand to BIT_FIELD_REF");
2709 if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2710 && (TYPE_PRECISION (TREE_TYPE (t))
2711 != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2713 error ("integral result type precision does not match "
2714 "field size of BIT_FIELD_REF");
2717 else if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2718 && TYPE_MODE (TREE_TYPE (t)) != BLKmode
2719 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2720 != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2722 error ("mode precision of non-integral result does not "
2723 "match field size of BIT_FIELD_REF");
2727 t = TREE_OPERAND (t, 0);
2732 case ARRAY_RANGE_REF:
2733 case VIEW_CONVERT_EXPR:
2734 /* We have a nest of references. Verify that each of the operands
2735 that determine where to reference is either a constant or a variable,
2736 verify that the base is valid, and then show we've already checked
2738 while (handled_component_p (t))
2740 if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2741 CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2742 else if (TREE_CODE (t) == ARRAY_REF
2743 || TREE_CODE (t) == ARRAY_RANGE_REF)
2745 CHECK_OP (1, "invalid array index");
2746 if (TREE_OPERAND (t, 2))
2747 CHECK_OP (2, "invalid array lower bound");
2748 if (TREE_OPERAND (t, 3))
2749 CHECK_OP (3, "invalid array stride");
2751 else if (TREE_CODE (t) == BIT_FIELD_REF
2752 || TREE_CODE (t) == REALPART_EXPR
2753 || TREE_CODE (t) == IMAGPART_EXPR)
2755 error ("non-top-level BIT_FIELD_REF, IMAGPART_EXPR or "
2760 t = TREE_OPERAND (t, 0);
2763 if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2765 error ("invalid reference prefix");
2772 /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2773 POINTER_PLUS_EXPR. */
2774 if (POINTER_TYPE_P (TREE_TYPE (t)))
2776 error ("invalid operand to plus/minus, type is a pointer");
2779 CHECK_OP (0, "invalid operand to binary operator");
2780 CHECK_OP (1, "invalid operand to binary operator");
2783 case POINTER_PLUS_EXPR:
2784 /* Check to make sure the first operand is a pointer or reference type. */
2785 if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
2787 error ("invalid operand to pointer plus, first operand is not a pointer");
2790 /* Check to make sure the second operand is a ptrofftype. */
2791 if (!ptrofftype_p (TREE_TYPE (TREE_OPERAND (t, 1))))
2793 error ("invalid operand to pointer plus, second operand is not an "
2794 "integer type of appropriate width");
2804 case UNORDERED_EXPR:
2813 case TRUNC_DIV_EXPR:
2815 case FLOOR_DIV_EXPR:
2816 case ROUND_DIV_EXPR:
2817 case TRUNC_MOD_EXPR:
2819 case FLOOR_MOD_EXPR:
2820 case ROUND_MOD_EXPR:
2822 case EXACT_DIV_EXPR:
2832 CHECK_OP (0, "invalid operand to binary operator");
2833 CHECK_OP (1, "invalid operand to binary operator");
2837 if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2841 case CASE_LABEL_EXPR:
2844 error ("invalid CASE_CHAIN");
2858 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
2859 Returns true if there is an error, otherwise false. */
2862 verify_types_in_gimple_min_lval (tree expr)
2866 if (is_gimple_id (expr))
2869 if (TREE_CODE (expr) != TARGET_MEM_REF
2870 && TREE_CODE (expr) != MEM_REF)
2872 error ("invalid expression for min lvalue");
2876 /* TARGET_MEM_REFs are strange beasts. */
2877 if (TREE_CODE (expr) == TARGET_MEM_REF)
2880 op = TREE_OPERAND (expr, 0);
2881 if (!is_gimple_val (op))
2883 error ("invalid operand in indirect reference");
2884 debug_generic_stmt (op);
2887 /* Memory references now generally can involve a value conversion. */
2892 /* Verify if EXPR is a valid GIMPLE reference expression. If
2893 REQUIRE_LVALUE is true verifies it is an lvalue. Returns true
2894 if there is an error, otherwise false. */
2897 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
2899 while (handled_component_p (expr))
2901 tree op = TREE_OPERAND (expr, 0);
2903 if (TREE_CODE (expr) == ARRAY_REF
2904 || TREE_CODE (expr) == ARRAY_RANGE_REF)
2906 if (!is_gimple_val (TREE_OPERAND (expr, 1))
2907 || (TREE_OPERAND (expr, 2)
2908 && !is_gimple_val (TREE_OPERAND (expr, 2)))
2909 || (TREE_OPERAND (expr, 3)
2910 && !is_gimple_val (TREE_OPERAND (expr, 3))))
2912 error ("invalid operands to array reference");
2913 debug_generic_stmt (expr);
2918 /* Verify if the reference array element types are compatible. */
2919 if (TREE_CODE (expr) == ARRAY_REF
2920 && !useless_type_conversion_p (TREE_TYPE (expr),
2921 TREE_TYPE (TREE_TYPE (op))))
2923 error ("type mismatch in array reference");
2924 debug_generic_stmt (TREE_TYPE (expr));
2925 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2928 if (TREE_CODE (expr) == ARRAY_RANGE_REF
2929 && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
2930 TREE_TYPE (TREE_TYPE (op))))
2932 error ("type mismatch in array range reference");
2933 debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
2934 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2938 if ((TREE_CODE (expr) == REALPART_EXPR
2939 || TREE_CODE (expr) == IMAGPART_EXPR)
2940 && !useless_type_conversion_p (TREE_TYPE (expr),
2941 TREE_TYPE (TREE_TYPE (op))))
2943 error ("type mismatch in real/imagpart reference");
2944 debug_generic_stmt (TREE_TYPE (expr));
2945 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2949 if (TREE_CODE (expr) == COMPONENT_REF
2950 && !useless_type_conversion_p (TREE_TYPE (expr),
2951 TREE_TYPE (TREE_OPERAND (expr, 1))))
2953 error ("type mismatch in component reference");
2954 debug_generic_stmt (TREE_TYPE (expr));
2955 debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
2959 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2961 /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check
2962 that their operand is not an SSA name or an invariant when
2963 requiring an lvalue (this usually means there is a SRA or IPA-SRA
2964 bug). Otherwise there is nothing to verify, gross mismatches at
2965 most invoke undefined behavior. */
2967 && (TREE_CODE (op) == SSA_NAME
2968 || is_gimple_min_invariant (op)))
2970 error ("conversion of an SSA_NAME on the left hand side");
2971 debug_generic_stmt (expr);
2974 else if (TREE_CODE (op) == SSA_NAME
2975 && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op)))
2977 error ("conversion of register to a different size");
2978 debug_generic_stmt (expr);
2981 else if (!handled_component_p (op))
2988 if (TREE_CODE (expr) == MEM_REF)
2990 if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0)))
2992 error ("invalid address operand in MEM_REF");
2993 debug_generic_stmt (expr);
2996 if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST
2997 || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
2999 error ("invalid offset operand in MEM_REF");
3000 debug_generic_stmt (expr);
3004 else if (TREE_CODE (expr) == TARGET_MEM_REF)
3006 if (!TMR_BASE (expr)
3007 || !is_gimple_mem_ref_addr (TMR_BASE (expr)))
3009 error ("invalid address operand in TARGET_MEM_REF");
3012 if (!TMR_OFFSET (expr)
3013 || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST
3014 || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr))))
3016 error ("invalid offset operand in TARGET_MEM_REF");
3017 debug_generic_stmt (expr);
3022 return ((require_lvalue || !is_gimple_min_invariant (expr))
3023 && verify_types_in_gimple_min_lval (expr));
3026 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3027 list of pointer-to types that is trivially convertible to DEST. */
3030 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3034 if (!TYPE_POINTER_TO (src_obj))
3037 for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3038 if (useless_type_conversion_p (dest, src))
3044 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3045 from TYPE2 can be handled by FIXED_CONVERT_EXPR. */
3048 valid_fixed_convert_types_p (tree type1, tree type2)
3050 return (FIXED_POINT_TYPE_P (type1)
3051 && (INTEGRAL_TYPE_P (type2)
3052 || SCALAR_FLOAT_TYPE_P (type2)
3053 || FIXED_POINT_TYPE_P (type2)));
3056 /* Verify the contents of a GIMPLE_CALL STMT. Returns true when there
3057 is a problem, otherwise false. */
3060 verify_gimple_call (gimple stmt)
3062 tree fn = gimple_call_fn (stmt);
3063 tree fntype, fndecl;
3066 if (gimple_call_internal_p (stmt))
3070 error ("gimple call has two targets");
3071 debug_generic_stmt (fn);
3079 error ("gimple call has no target");
3084 if (fn && !is_gimple_call_addr (fn))
3086 error ("invalid function in gimple call");
3087 debug_generic_stmt (fn);
3092 && (!POINTER_TYPE_P (TREE_TYPE (fn))
3093 || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3094 && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE)))
3096 error ("non-function in gimple call");
3100 fndecl = gimple_call_fndecl (stmt);
3102 && TREE_CODE (fndecl) == FUNCTION_DECL
3103 && DECL_LOOPING_CONST_OR_PURE_P (fndecl)
3104 && !DECL_PURE_P (fndecl)
3105 && !TREE_READONLY (fndecl))
3107 error ("invalid pure const state for function");
3111 if (gimple_call_lhs (stmt)
3112 && (!is_gimple_lvalue (gimple_call_lhs (stmt))
3113 || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true)))
3115 error ("invalid LHS in gimple call");
3119 if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt))
3121 error ("LHS in noreturn call");
3125 fntype = gimple_call_fntype (stmt);
3127 && gimple_call_lhs (stmt)
3128 && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3130 /* ??? At least C++ misses conversions at assignments from
3131 void * call results.
3132 ??? Java is completely off. Especially with functions
3133 returning java.lang.Object.
3134 For now simply allow arbitrary pointer type conversions. */
3135 && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3136 && POINTER_TYPE_P (TREE_TYPE (fntype))))
3138 error ("invalid conversion in gimple call");
3139 debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3140 debug_generic_stmt (TREE_TYPE (fntype));
3144 if (gimple_call_chain (stmt)
3145 && !is_gimple_val (gimple_call_chain (stmt)))
3147 error ("invalid static chain in gimple call");
3148 debug_generic_stmt (gimple_call_chain (stmt));
3152 /* If there is a static chain argument, this should not be an indirect
3153 call, and the decl should have DECL_STATIC_CHAIN set. */
3154 if (gimple_call_chain (stmt))
3156 if (!gimple_call_fndecl (stmt))
3158 error ("static chain in indirect gimple call");
3161 fn = TREE_OPERAND (fn, 0);
3163 if (!DECL_STATIC_CHAIN (fn))
3165 error ("static chain with function that doesn%'t use one");
3170 /* ??? The C frontend passes unpromoted arguments in case it
3171 didn't see a function declaration before the call. So for now
3172 leave the call arguments mostly unverified. Once we gimplify
3173 unit-at-a-time we have a chance to fix this. */
3175 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3177 tree arg = gimple_call_arg (stmt, i);
3178 if ((is_gimple_reg_type (TREE_TYPE (arg))
3179 && !is_gimple_val (arg))
3180 || (!is_gimple_reg_type (TREE_TYPE (arg))
3181 && !is_gimple_lvalue (arg)))
3183 error ("invalid argument to gimple call");
3184 debug_generic_expr (arg);
3192 /* Verifies the gimple comparison with the result type TYPE and
3193 the operands OP0 and OP1. */
3196 verify_gimple_comparison (tree type, tree op0, tree op1)
3198 tree op0_type = TREE_TYPE (op0);
3199 tree op1_type = TREE_TYPE (op1);
3201 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3203 error ("invalid operands in gimple comparison");
3207 /* For comparisons we do not have the operations type as the
3208 effective type the comparison is carried out in. Instead
3209 we require that either the first operand is trivially
3210 convertible into the second, or the other way around.
3211 Because we special-case pointers to void we allow
3212 comparisons of pointers with the same mode as well. */
3213 if (!useless_type_conversion_p (op0_type, op1_type)
3214 && !useless_type_conversion_p (op1_type, op0_type)
3215 && (!POINTER_TYPE_P (op0_type)
3216 || !POINTER_TYPE_P (op1_type)
3217 || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3219 error ("mismatching comparison operand types");
3220 debug_generic_expr (op0_type);
3221 debug_generic_expr (op1_type);
3225 /* The resulting type of a comparison may be an effective boolean type. */
3226 if (INTEGRAL_TYPE_P (type)
3227 && (TREE_CODE (type) == BOOLEAN_TYPE
3228 || TYPE_PRECISION (type) == 1))
3230 if (TREE_CODE (op0_type) == VECTOR_TYPE
3231 || TREE_CODE (op1_type) == VECTOR_TYPE)
3233 error ("vector comparison returning a boolean");
3234 debug_generic_expr (op0_type);
3235 debug_generic_expr (op1_type);
3239 /* Or an integer vector type with the same size and element count
3240 as the comparison operand types. */
3241 else if (TREE_CODE (type) == VECTOR_TYPE
3242 && TREE_CODE (TREE_TYPE (type)) == INTEGER_TYPE)
3244 if (TREE_CODE (op0_type) != VECTOR_TYPE
3245 || TREE_CODE (op1_type) != VECTOR_TYPE)
3247 error ("non-vector operands in vector comparison");
3248 debug_generic_expr (op0_type);
3249 debug_generic_expr (op1_type);
3253 if (TYPE_VECTOR_SUBPARTS (type) != TYPE_VECTOR_SUBPARTS (op0_type)
3254 || (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (type)))
3255 != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0_type))))
3256 /* The result of a vector comparison is of signed
3258 || TYPE_UNSIGNED (TREE_TYPE (type)))
3260 error ("invalid vector comparison resulting type");
3261 debug_generic_expr (type);
3267 error ("bogus comparison result type");
3268 debug_generic_expr (type);
3275 /* Verify a gimple assignment statement STMT with an unary rhs.
3276 Returns true if anything is wrong. */
3279 verify_gimple_assign_unary (gimple stmt)
3281 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3282 tree lhs = gimple_assign_lhs (stmt);
3283 tree lhs_type = TREE_TYPE (lhs);
3284 tree rhs1 = gimple_assign_rhs1 (stmt);
3285 tree rhs1_type = TREE_TYPE (rhs1);
3287 if (!is_gimple_reg (lhs))
3289 error ("non-register as LHS of unary operation");
3293 if (!is_gimple_val (rhs1))
3295 error ("invalid operand in unary operation");
3299 /* First handle conversions. */
3304 /* Allow conversions from pointer type to integral type only if
3305 there is no sign or zero extension involved.
3306 For targets were the precision of ptrofftype doesn't match that
3307 of pointers we need to allow arbitrary conversions to ptrofftype. */
3308 if ((POINTER_TYPE_P (lhs_type)
3309 && INTEGRAL_TYPE_P (rhs1_type))
3310 || (POINTER_TYPE_P (rhs1_type)
3311 && INTEGRAL_TYPE_P (lhs_type)
3312 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3313 || ptrofftype_p (sizetype))))
3316 /* Allow conversion from integral to offset type and vice versa. */
3317 if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3318 && INTEGRAL_TYPE_P (rhs1_type))
3319 || (INTEGRAL_TYPE_P (lhs_type)
3320 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3323 /* Otherwise assert we are converting between types of the
3325 if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3327 error ("invalid types in nop conversion");
3328 debug_generic_expr (lhs_type);
3329 debug_generic_expr (rhs1_type);
3336 case ADDR_SPACE_CONVERT_EXPR:
3338 if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3339 || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3340 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3342 error ("invalid types in address space conversion");
3343 debug_generic_expr (lhs_type);
3344 debug_generic_expr (rhs1_type);
3351 case FIXED_CONVERT_EXPR:
3353 if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3354 && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3356 error ("invalid types in fixed-point conversion");
3357 debug_generic_expr (lhs_type);
3358 debug_generic_expr (rhs1_type);
3367 if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3368 && (!VECTOR_INTEGER_TYPE_P (rhs1_type)
3369 || !VECTOR_FLOAT_TYPE_P (lhs_type)))
3371 error ("invalid types in conversion to floating point");
3372 debug_generic_expr (lhs_type);
3373 debug_generic_expr (rhs1_type);
3380 case FIX_TRUNC_EXPR:
3382 if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3383 && (!VECTOR_INTEGER_TYPE_P (lhs_type)
3384 || !VECTOR_FLOAT_TYPE_P (rhs1_type)))
3386 error ("invalid types in conversion to integer");
3387 debug_generic_expr (lhs_type);
3388 debug_generic_expr (rhs1_type);
3395 case VEC_UNPACK_HI_EXPR:
3396 case VEC_UNPACK_LO_EXPR:
3397 case REDUC_MAX_EXPR:
3398 case REDUC_MIN_EXPR:
3399 case REDUC_PLUS_EXPR:
3400 case VEC_UNPACK_FLOAT_HI_EXPR:
3401 case VEC_UNPACK_FLOAT_LO_EXPR:
3409 case NON_LVALUE_EXPR:
3417 /* For the remaining codes assert there is no conversion involved. */
3418 if (!useless_type_conversion_p (lhs_type, rhs1_type))
3420 error ("non-trivial conversion in unary operation");
3421 debug_generic_expr (lhs_type);
3422 debug_generic_expr (rhs1_type);
3429 /* Verify a gimple assignment statement STMT with a binary rhs.
3430 Returns true if anything is wrong. */
3433 verify_gimple_assign_binary (gimple stmt)
3435 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3436 tree lhs = gimple_assign_lhs (stmt);
3437 tree lhs_type = TREE_TYPE (lhs);
3438 tree rhs1 = gimple_assign_rhs1 (stmt);
3439 tree rhs1_type = TREE_TYPE (rhs1);
3440 tree rhs2 = gimple_assign_rhs2 (stmt);
3441 tree rhs2_type = TREE_TYPE (rhs2);
3443 if (!is_gimple_reg (lhs))
3445 error ("non-register as LHS of binary operation");
3449 if (!is_gimple_val (rhs1)
3450 || !is_gimple_val (rhs2))
3452 error ("invalid operands in binary operation");
3456 /* First handle operations that involve different types. */
3461 if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3462 || !(INTEGRAL_TYPE_P (rhs1_type)
3463 || SCALAR_FLOAT_TYPE_P (rhs1_type))
3464 || !(INTEGRAL_TYPE_P (rhs2_type)
3465 || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3467 error ("type mismatch in complex expression");
3468 debug_generic_expr (lhs_type);
3469 debug_generic_expr (rhs1_type);
3470 debug_generic_expr (rhs2_type);
3482 /* Shifts and rotates are ok on integral types, fixed point
3483 types and integer vector types. */
3484 if ((!INTEGRAL_TYPE_P (rhs1_type)
3485 && !FIXED_POINT_TYPE_P (rhs1_type)
3486 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3487 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3488 || (!INTEGRAL_TYPE_P (rhs2_type)
3489 /* Vector shifts of vectors are also ok. */
3490 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3491 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3492 && TREE_CODE (rhs2_type) == VECTOR_TYPE
3493 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3494 || !useless_type_conversion_p (lhs_type, rhs1_type))
3496 error ("type mismatch in shift expression");
3497 debug_generic_expr (lhs_type);
3498 debug_generic_expr (rhs1_type);
3499 debug_generic_expr (rhs2_type);
3506 case VEC_LSHIFT_EXPR:
3507 case VEC_RSHIFT_EXPR:
3509 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3510 || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3511 || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3512 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3513 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3514 || (!INTEGRAL_TYPE_P (rhs2_type)
3515 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3516 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3517 || !useless_type_conversion_p (lhs_type, rhs1_type))
3519 error ("type mismatch in vector shift expression");
3520 debug_generic_expr (lhs_type);
3521 debug_generic_expr (rhs1_type);
3522 debug_generic_expr (rhs2_type);
3525 /* For shifting a vector of non-integral components we
3526 only allow shifting by a constant multiple of the element size. */
3527 if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3528 && (TREE_CODE (rhs2) != INTEGER_CST
3529 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3530 TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3532 error ("non-element sized vector shift of floating point vector");
3539 case WIDEN_LSHIFT_EXPR:
3541 if (!INTEGRAL_TYPE_P (lhs_type)
3542 || !INTEGRAL_TYPE_P (rhs1_type)
3543 || TREE_CODE (rhs2) != INTEGER_CST
3544 || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)))
3546 error ("type mismatch in widening vector shift expression");
3547 debug_generic_expr (lhs_type);
3548 debug_generic_expr (rhs1_type);
3549 debug_generic_expr (rhs2_type);
3556 case VEC_WIDEN_LSHIFT_HI_EXPR:
3557 case VEC_WIDEN_LSHIFT_LO_EXPR:
3559 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3560 || TREE_CODE (lhs_type) != VECTOR_TYPE
3561 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3562 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs_type))
3563 || TREE_CODE (rhs2) != INTEGER_CST
3564 || (2 * TYPE_PRECISION (TREE_TYPE (rhs1_type))
3565 > TYPE_PRECISION (TREE_TYPE (lhs_type))))
3567 error ("type mismatch in widening vector shift expression");
3568 debug_generic_expr (lhs_type);
3569 debug_generic_expr (rhs1_type);
3570 debug_generic_expr (rhs2_type);
3580 tree lhs_etype = lhs_type;
3581 tree rhs1_etype = rhs1_type;
3582 tree rhs2_etype = rhs2_type;
3583 if (TREE_CODE (lhs_type) == VECTOR_TYPE)
3585 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3586 || TREE_CODE (rhs2_type) != VECTOR_TYPE)
3588 error ("invalid non-vector operands to vector valued plus");
3591 lhs_etype = TREE_TYPE (lhs_type);
3592 rhs1_etype = TREE_TYPE (rhs1_type);
3593 rhs2_etype = TREE_TYPE (rhs2_type);
3595 if (POINTER_TYPE_P (lhs_etype)
3596 || POINTER_TYPE_P (rhs1_etype)
3597 || POINTER_TYPE_P (rhs2_etype))
3599 error ("invalid (pointer) operands to plus/minus");
3603 /* Continue with generic binary expression handling. */
3607 case POINTER_PLUS_EXPR:
3609 if (!POINTER_TYPE_P (rhs1_type)
3610 || !useless_type_conversion_p (lhs_type, rhs1_type)
3611 || !ptrofftype_p (rhs2_type))
3613 error ("type mismatch in pointer plus expression");
3614 debug_generic_stmt (lhs_type);
3615 debug_generic_stmt (rhs1_type);
3616 debug_generic_stmt (rhs2_type);
3623 case TRUTH_ANDIF_EXPR:
3624 case TRUTH_ORIF_EXPR:
3625 case TRUTH_AND_EXPR:
3627 case TRUTH_XOR_EXPR:
3637 case UNORDERED_EXPR:
3645 /* Comparisons are also binary, but the result type is not
3646 connected to the operand types. */
3647 return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3649 case WIDEN_MULT_EXPR:
3650 if (TREE_CODE (lhs_type) != INTEGER_TYPE)
3652 return ((2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type))
3653 || (TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type)));
3655 case WIDEN_SUM_EXPR:
3656 case VEC_WIDEN_MULT_HI_EXPR:
3657 case VEC_WIDEN_MULT_LO_EXPR:
3658 case VEC_WIDEN_MULT_EVEN_EXPR:
3659 case VEC_WIDEN_MULT_ODD_EXPR:
3660 case VEC_PACK_TRUNC_EXPR:
3661 case VEC_PACK_SAT_EXPR:
3662 case VEC_PACK_FIX_TRUNC_EXPR:
3667 case MULT_HIGHPART_EXPR:
3668 case TRUNC_DIV_EXPR:
3670 case FLOOR_DIV_EXPR:
3671 case ROUND_DIV_EXPR:
3672 case TRUNC_MOD_EXPR:
3674 case FLOOR_MOD_EXPR:
3675 case ROUND_MOD_EXPR:
3677 case EXACT_DIV_EXPR:
3683 /* Continue with generic binary expression handling. */
3690 if (!useless_type_conversion_p (lhs_type, rhs1_type)
3691 || !useless_type_conversion_p (lhs_type, rhs2_type))
3693 error ("type mismatch in binary expression");
3694 debug_generic_stmt (lhs_type);
3695 debug_generic_stmt (rhs1_type);
3696 debug_generic_stmt (rhs2_type);
3703 /* Verify a gimple assignment statement STMT with a ternary rhs.
3704 Returns true if anything is wrong. */
3707 verify_gimple_assign_ternary (gimple stmt)
3709 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3710 tree lhs = gimple_assign_lhs (stmt);
3711 tree lhs_type = TREE_TYPE (lhs);
3712 tree rhs1 = gimple_assign_rhs1 (stmt);
3713 tree rhs1_type = TREE_TYPE (rhs1);
3714 tree rhs2 = gimple_assign_rhs2 (stmt);
3715 tree rhs2_type = TREE_TYPE (rhs2);
3716 tree rhs3 = gimple_assign_rhs3 (stmt);
3717 tree rhs3_type = TREE_TYPE (rhs3);
3719 if (!is_gimple_reg (lhs))
3721 error ("non-register as LHS of ternary operation");
3725 if (((rhs_code == VEC_COND_EXPR || rhs_code == COND_EXPR)
3726 ? !is_gimple_condexpr (rhs1) : !is_gimple_val (rhs1))
3727 || !is_gimple_val (rhs2)
3728 || !is_gimple_val (rhs3))
3730 error ("invalid operands in ternary operation");
3734 /* First handle operations that involve different types. */
3737 case WIDEN_MULT_PLUS_EXPR:
3738 case WIDEN_MULT_MINUS_EXPR:
3739 if ((!INTEGRAL_TYPE_P (rhs1_type)
3740 && !FIXED_POINT_TYPE_P (rhs1_type))
3741 || !useless_type_conversion_p (rhs1_type, rhs2_type)
3742 || !useless_type_conversion_p (lhs_type, rhs3_type)
3743 || 2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)
3744 || TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type))
3746 error ("type mismatch in widening multiply-accumulate expression");
3747 debug_generic_expr (lhs_type);
3748 debug_generic_expr (rhs1_type);
3749 debug_generic_expr (rhs2_type);
3750 debug_generic_expr (rhs3_type);
3756 if (!useless_type_conversion_p (lhs_type, rhs1_type)
3757 || !useless_type_conversion_p (lhs_type, rhs2_type)
3758 || !useless_type_conversion_p (lhs_type, rhs3_type))
3760 error ("type mismatch in fused multiply-add expression");
3761 debug_generic_expr (lhs_type);
3762 debug_generic_expr (rhs1_type);
3763 debug_generic_expr (rhs2_type);
3764 debug_generic_expr (rhs3_type);
3771 if (!useless_type_conversion_p (lhs_type, rhs2_type)
3772 || !useless_type_conversion_p (lhs_type, rhs3_type))
3774 error ("type mismatch in conditional expression");
3775 debug_generic_expr (lhs_type);
3776 debug_generic_expr (rhs2_type);
3777 debug_generic_expr (rhs3_type);
3783 if (!useless_type_conversion_p (lhs_type, rhs1_type)
3784 || !useless_type_conversion_p (lhs_type, rhs2_type))
3786 error ("type mismatch in vector permute expression");
3787 debug_generic_expr (lhs_type);
3788 debug_generic_expr (rhs1_type);
3789 debug_generic_expr (rhs2_type);
3790 debug_generic_expr (rhs3_type);
3794 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3795 || TREE_CODE (rhs2_type) != VECTOR_TYPE
3796 || TREE_CODE (rhs3_type) != VECTOR_TYPE)
3798 error ("vector types expected in vector permute expression");
3799 debug_generic_expr (lhs_type);
3800 debug_generic_expr (rhs1_type);
3801 debug_generic_expr (rhs2_type);
3802 debug_generic_expr (rhs3_type);
3806 if (TYPE_VECTOR_SUBPARTS (rhs1_type) != TYPE_VECTOR_SUBPARTS (rhs2_type)
3807 || TYPE_VECTOR_SUBPARTS (rhs2_type)
3808 != TYPE_VECTOR_SUBPARTS (rhs3_type)
3809 || TYPE_VECTOR_SUBPARTS (rhs3_type)
3810 != TYPE_VECTOR_SUBPARTS (lhs_type))
3812 error ("vectors with different element number found "
3813 "in vector permute expression");
3814 debug_generic_expr (lhs_type);
3815 debug_generic_expr (rhs1_type);
3816 debug_generic_expr (rhs2_type);
3817 debug_generic_expr (rhs3_type);
3821 if (TREE_CODE (TREE_TYPE (rhs3_type)) != INTEGER_TYPE
3822 || GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs3_type)))
3823 != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1_type))))
3825 error ("invalid mask type in vector permute expression");
3826 debug_generic_expr (lhs_type);
3827 debug_generic_expr (rhs1_type);
3828 debug_generic_expr (rhs2_type);
3829 debug_generic_expr (rhs3_type);
3836 case REALIGN_LOAD_EXPR:
3846 /* Verify a gimple assignment statement STMT with a single rhs.
3847 Returns true if anything is wrong. */
3850 verify_gimple_assign_single (gimple stmt)
3852 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3853 tree lhs = gimple_assign_lhs (stmt);
3854 tree lhs_type = TREE_TYPE (lhs);
3855 tree rhs1 = gimple_assign_rhs1 (stmt);
3856 tree rhs1_type = TREE_TYPE (rhs1);
3859 if (!useless_type_conversion_p (lhs_type, rhs1_type))
3861 error ("non-trivial conversion at assignment");
3862 debug_generic_expr (lhs_type);
3863 debug_generic_expr (rhs1_type);
3867 if (gimple_clobber_p (stmt)
3868 && !(DECL_P (lhs) || TREE_CODE (lhs) == MEM_REF))
3870 error ("non-decl/MEM_REF LHS in clobber statement");
3871 debug_generic_expr (lhs);
3875 if (handled_component_p (lhs))
3876 res |= verify_types_in_gimple_reference (lhs, true);
3878 /* Special codes we cannot handle via their class. */
3883 tree op = TREE_OPERAND (rhs1, 0);
3884 if (!is_gimple_addressable (op))
3886 error ("invalid operand in unary expression");
3890 /* Technically there is no longer a need for matching types, but
3891 gimple hygiene asks for this check. In LTO we can end up
3892 combining incompatible units and thus end up with addresses
3893 of globals that change their type to a common one. */
3895 && !types_compatible_p (TREE_TYPE (op),
3896 TREE_TYPE (TREE_TYPE (rhs1)))
3897 && !one_pointer_to_useless_type_conversion_p (TREE_TYPE (rhs1),
3900 error ("type mismatch in address expression");
3901 debug_generic_stmt (TREE_TYPE (rhs1));
3902 debug_generic_stmt (TREE_TYPE (op));
3906 return verify_types_in_gimple_reference (op, true);
3911 error ("INDIRECT_REF in gimple IL");
3917 case ARRAY_RANGE_REF:
3918 case VIEW_CONVERT_EXPR:
3921 case TARGET_MEM_REF:
3923 if (!is_gimple_reg (lhs)
3924 && is_gimple_reg_type (TREE_TYPE (lhs)))
3926 error ("invalid rhs for gimple memory store");
3927 debug_generic_stmt (lhs);
3928 debug_generic_stmt (rhs1);
3931 return res || verify_types_in_gimple_reference (rhs1, false);
3943 /* tcc_declaration */
3948 if (!is_gimple_reg (lhs)
3949 && !is_gimple_reg (rhs1)
3950 && is_gimple_reg_type (TREE_TYPE (lhs)))
3952 error ("invalid rhs for gimple memory store");
3953 debug_generic_stmt (lhs);
3954 debug_generic_stmt (rhs1);
3960 if (TREE_CODE (rhs1_type) == VECTOR_TYPE)
3963 tree elt_i, elt_v, elt_t = NULL_TREE;
3965 if (CONSTRUCTOR_NELTS (rhs1) == 0)
3967 /* For vector CONSTRUCTORs we require that either it is empty
3968 CONSTRUCTOR, or it is a CONSTRUCTOR of smaller vector elements
3969 (then the element count must be correct to cover the whole
3970 outer vector and index must be NULL on all elements, or it is
3971 a CONSTRUCTOR of scalar elements, where we as an exception allow
3972 smaller number of elements (assuming zero filling) and
3973 consecutive indexes as compared to NULL indexes (such
3974 CONSTRUCTORs can appear in the IL from FEs). */
3975 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (rhs1), i, elt_i, elt_v)
3977 if (elt_t == NULL_TREE)
3979 elt_t = TREE_TYPE (elt_v);
3980 if (TREE_CODE (elt_t) == VECTOR_TYPE)
3982 tree elt_t = TREE_TYPE (elt_v);
3983 if (!useless_type_conversion_p (TREE_TYPE (rhs1_type),
3986 error ("incorrect type of vector CONSTRUCTOR"
3988 debug_generic_stmt (rhs1);
3991 else if (CONSTRUCTOR_NELTS (rhs1)
3992 * TYPE_VECTOR_SUBPARTS (elt_t)
3993 != TYPE_VECTOR_SUBPARTS (rhs1_type))
3995 error ("incorrect number of vector CONSTRUCTOR"
3997 debug_generic_stmt (rhs1);
4001 else if (!useless_type_conversion_p (TREE_TYPE (rhs1_type),
4004 error ("incorrect type of vector CONSTRUCTOR elements");
4005 debug_generic_stmt (rhs1);
4008 else if (CONSTRUCTOR_NELTS (rhs1)
4009 > TYPE_VECTOR_SUBPARTS (rhs1_type))
4011 error ("incorrect number of vector CONSTRUCTOR elements");
4012 debug_generic_stmt (rhs1);
4016 else if (!useless_type_conversion_p (elt_t, TREE_TYPE (elt_v)))
4018 error ("incorrect type of vector CONSTRUCTOR elements");
4019 debug_generic_stmt (rhs1);
4022 if (elt_i != NULL_TREE
4023 && (TREE_CODE (elt_t) == VECTOR_TYPE
4024 || TREE_CODE (elt_i) != INTEGER_CST
4025 || compare_tree_int (elt_i, i) != 0))
4027 error ("vector CONSTRUCTOR with non-NULL element index");
4028 debug_generic_stmt (rhs1);
4036 case WITH_SIZE_EXPR:
4046 /* Verify the contents of a GIMPLE_ASSIGN STMT. Returns true when there
4047 is a problem, otherwise false. */
4050 verify_gimple_assign (gimple stmt)
4052 switch (gimple_assign_rhs_class (stmt))
4054 case GIMPLE_SINGLE_RHS:
4055 return verify_gimple_assign_single (stmt);
4057 case GIMPLE_UNARY_RHS:
4058 return verify_gimple_assign_unary (stmt);
4060 case GIMPLE_BINARY_RHS:
4061 return verify_gimple_assign_binary (stmt);
4063 case GIMPLE_TERNARY_RHS:
4064 return verify_gimple_assign_ternary (stmt);
4071 /* Verify the contents of a GIMPLE_RETURN STMT. Returns true when there
4072 is a problem, otherwise false. */
4075 verify_gimple_return (gimple stmt)
4077 tree op = gimple_return_retval (stmt);
4078 tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
4080 /* We cannot test for present return values as we do not fix up missing
4081 return values from the original source. */
4085 if (!is_gimple_val (op)
4086 && TREE_CODE (op) != RESULT_DECL)
4088 error ("invalid operand in return statement");
4089 debug_generic_stmt (op);
4093 if ((TREE_CODE (op) == RESULT_DECL
4094 && DECL_BY_REFERENCE (op))
4095 || (TREE_CODE (op) == SSA_NAME
4096 && SSA_NAME_VAR (op)
4097 && TREE_CODE (SSA_NAME_VAR (op)) == RESULT_DECL
4098 && DECL_BY_REFERENCE (SSA_NAME_VAR (op))))
4099 op = TREE_TYPE (op);
4101 if (!useless_type_conversion_p (restype, TREE_TYPE (op)))
4103 error ("invalid conversion in return statement");
4104 debug_generic_stmt (restype);
4105 debug_generic_stmt (TREE_TYPE (op));
4113 /* Verify the contents of a GIMPLE_GOTO STMT. Returns true when there
4114 is a problem, otherwise false. */
4117 verify_gimple_goto (gimple stmt)
4119 tree dest = gimple_goto_dest (stmt);
4121 /* ??? We have two canonical forms of direct goto destinations, a
4122 bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL. */
4123 if (TREE_CODE (dest) != LABEL_DECL
4124 && (!is_gimple_val (dest)
4125 || !POINTER_TYPE_P (TREE_TYPE (dest))))
4127 error ("goto destination is neither a label nor a pointer");
4134 /* Verify the contents of a GIMPLE_SWITCH STMT. Returns true when there
4135 is a problem, otherwise false. */
4138 verify_gimple_switch (gimple stmt)
4141 tree elt, prev_upper_bound = NULL_TREE;
4142 tree index_type, elt_type = NULL_TREE;
4144 if (!is_gimple_val (gimple_switch_index (stmt)))
4146 error ("invalid operand to switch statement");
4147 debug_generic_stmt (gimple_switch_index (stmt));
4151 index_type = TREE_TYPE (gimple_switch_index (stmt));
4152 if (! INTEGRAL_TYPE_P (index_type))
4154 error ("non-integral type switch statement");
4155 debug_generic_expr (index_type);
4159 elt = gimple_switch_label (stmt, 0);
4160 if (CASE_LOW (elt) != NULL_TREE || CASE_HIGH (elt) != NULL_TREE)
4162 error ("invalid default case label in switch statement");
4163 debug_generic_expr (elt);
4167 n = gimple_switch_num_labels (stmt);
4168 for (i = 1; i < n; i++)
4170 elt = gimple_switch_label (stmt, i);
4172 if (! CASE_LOW (elt))
4174 error ("invalid case label in switch statement");
4175 debug_generic_expr (elt);
4179 && ! tree_int_cst_lt (CASE_LOW (elt), CASE_HIGH (elt)))
4181 error ("invalid case range in switch statement");
4182 debug_generic_expr (elt);
4188 if (TREE_TYPE (CASE_LOW (elt)) != elt_type
4189 || (CASE_HIGH (elt) && TREE_TYPE (CASE_HIGH (elt)) != elt_type))
4191 error ("type mismatch for case label in switch statement");
4192 debug_generic_expr (elt);
4198 elt_type = TREE_TYPE (CASE_LOW (elt));
4199 if (TYPE_PRECISION (index_type) < TYPE_PRECISION (elt_type))
4201 error ("type precision mismatch in switch statement");
4206 if (prev_upper_bound)
4208 if (! tree_int_cst_lt (prev_upper_bound, CASE_LOW (elt)))
4210 error ("case labels not sorted in switch statement");
4215 prev_upper_bound = CASE_HIGH (elt);
4216 if (! prev_upper_bound)
4217 prev_upper_bound = CASE_LOW (elt);
4223 /* Verify a gimple debug statement STMT.
4224 Returns true if anything is wrong. */
4227 verify_gimple_debug (gimple stmt ATTRIBUTE_UNUSED)
4229 /* There isn't much that could be wrong in a gimple debug stmt. A
4230 gimple debug bind stmt, for example, maps a tree, that's usually
4231 a VAR_DECL or a PARM_DECL, but that could also be some scalarized
4232 component or member of an aggregate type, to another tree, that
4233 can be an arbitrary expression. These stmts expand into debug
4234 insns, and are converted to debug notes by var-tracking.c. */
4238 /* Verify a gimple label statement STMT.
4239 Returns true if anything is wrong. */
4242 verify_gimple_label (gimple stmt)
4244 tree decl = gimple_label_label (stmt);
4248 if (TREE_CODE (decl) != LABEL_DECL)
4250 if (!DECL_NONLOCAL (decl) && !FORCED_LABEL (decl)
4251 && DECL_CONTEXT (decl) != current_function_decl)
4253 error ("label's context is not the current function decl");
4257 uid = LABEL_DECL_UID (decl);
4259 && (uid == -1 || (*label_to_block_map)[uid] != gimple_bb (stmt)))
4261 error ("incorrect entry in label_to_block_map");
4265 uid = EH_LANDING_PAD_NR (decl);
4268 eh_landing_pad lp = get_eh_landing_pad_from_number (uid);
4269 if (decl != lp->post_landing_pad)
4271 error ("incorrect setting of landing pad number");
4279 /* Verify the GIMPLE statement STMT. Returns true if there is an
4280 error, otherwise false. */
4283 verify_gimple_stmt (gimple stmt)
4285 switch (gimple_code (stmt))
4288 return verify_gimple_assign (stmt);
4291 return verify_gimple_label (stmt);
4294 return verify_gimple_call (stmt);
4297 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
4299 error ("invalid comparison code in gimple cond");
4302 if (!(!gimple_cond_true_label (stmt)
4303 || TREE_CODE (gimple_cond_true_label (stmt)) == LABEL_DECL)
4304 || !(!gimple_cond_false_label (stmt)
4305 || TREE_CODE (gimple_cond_false_label (stmt)) == LABEL_DECL))
4307 error ("invalid labels in gimple cond");
4311 return verify_gimple_comparison (boolean_type_node,
4312 gimple_cond_lhs (stmt),
4313 gimple_cond_rhs (stmt));
4316 return verify_gimple_goto (stmt);
4319 return verify_gimple_switch (stmt);
4322 return verify_gimple_return (stmt);
4327 case GIMPLE_TRANSACTION:
4328 return verify_gimple_transaction (stmt);
4330 /* Tuples that do not have tree operands. */
4332 case GIMPLE_PREDICT:
4334 case GIMPLE_EH_DISPATCH:
4335 case GIMPLE_EH_MUST_NOT_THROW:
4339 /* OpenMP directives are validated by the FE and never operated
4340 on by the optimizers. Furthermore, GIMPLE_OMP_FOR may contain
4341 non-gimple expressions when the main index variable has had
4342 its address taken. This does not affect the loop itself
4343 because the header of an GIMPLE_OMP_FOR is merely used to determine
4344 how to setup the parallel iteration. */
4348 return verify_gimple_debug (stmt);
4355 /* Verify the contents of a GIMPLE_PHI. Returns true if there is a problem,
4356 and false otherwise. */
4359 verify_gimple_phi (gimple phi)
4363 tree phi_result = gimple_phi_result (phi);
4368 error ("invalid PHI result");
4372 virtual_p = virtual_operand_p (phi_result);
4373 if (TREE_CODE (phi_result) != SSA_NAME
4375 && SSA_NAME_VAR (phi_result) != gimple_vop (cfun)))
4377 error ("invalid PHI result");
4381 for (i = 0; i < gimple_phi_num_args (phi); i++)
4383 tree t = gimple_phi_arg_def (phi, i);
4387 error ("missing PHI def");
4391 /* Addressable variables do have SSA_NAMEs but they
4392 are not considered gimple values. */
4393 else if ((TREE_CODE (t) == SSA_NAME
4394 && virtual_p != virtual_operand_p (t))
4396 && (TREE_CODE (t) != SSA_NAME
4397 || SSA_NAME_VAR (t) != gimple_vop (cfun)))
4399 && !is_gimple_val (t)))
4401 error ("invalid PHI argument");
4402 debug_generic_expr (t);
4405 #ifdef ENABLE_TYPES_CHECKING
4406 if (!useless_type_conversion_p (TREE_TYPE (phi_result), TREE_TYPE (t)))
4408 error ("incompatible types in PHI argument %u", i);
4409 debug_generic_stmt (TREE_TYPE (phi_result));
4410 debug_generic_stmt (TREE_TYPE (t));
4419 /* Verify the GIMPLE statements inside the sequence STMTS. */
4422 verify_gimple_in_seq_2 (gimple_seq stmts)
4424 gimple_stmt_iterator ittr;
4427 for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
4429 gimple stmt = gsi_stmt (ittr);
4431 switch (gimple_code (stmt))
4434 err |= verify_gimple_in_seq_2 (gimple_bind_body (stmt));
4438 err |= verify_gimple_in_seq_2 (gimple_try_eval (stmt));
4439 err |= verify_gimple_in_seq_2 (gimple_try_cleanup (stmt));
4442 case GIMPLE_EH_FILTER:
4443 err |= verify_gimple_in_seq_2 (gimple_eh_filter_failure (stmt));
4446 case GIMPLE_EH_ELSE:
4447 err |= verify_gimple_in_seq_2 (gimple_eh_else_n_body (stmt));
4448 err |= verify_gimple_in_seq_2 (gimple_eh_else_e_body (stmt));
4452 err |= verify_gimple_in_seq_2 (gimple_catch_handler (stmt));
4455 case GIMPLE_TRANSACTION:
4456 err |= verify_gimple_transaction (stmt);
4461 bool err2 = verify_gimple_stmt (stmt);
4463 debug_gimple_stmt (stmt);
4472 /* Verify the contents of a GIMPLE_TRANSACTION. Returns true if there
4473 is a problem, otherwise false. */
4476 verify_gimple_transaction (gimple stmt)
4478 tree lab = gimple_transaction_label (stmt);
4479 if (lab != NULL && TREE_CODE (lab) != LABEL_DECL)
4481 return verify_gimple_in_seq_2 (gimple_transaction_body (stmt));
4485 /* Verify the GIMPLE statements inside the statement list STMTS. */
4488 verify_gimple_in_seq (gimple_seq stmts)
4490 timevar_push (TV_TREE_STMT_VERIFY);
4491 if (verify_gimple_in_seq_2 (stmts))
4492 internal_error ("verify_gimple failed");
4493 timevar_pop (TV_TREE_STMT_VERIFY);
4496 /* Return true when the T can be shared. */
4499 tree_node_can_be_shared (tree t)
4501 if (IS_TYPE_OR_DECL_P (t)
4502 || is_gimple_min_invariant (t)
4503 || TREE_CODE (t) == SSA_NAME
4504 || t == error_mark_node
4505 || TREE_CODE (t) == IDENTIFIER_NODE)
4508 if (TREE_CODE (t) == CASE_LABEL_EXPR)
4517 /* Called via walk_tree. Verify tree sharing. */
4520 verify_node_sharing_1 (tree *tp, int *walk_subtrees, void *data)
4522 struct pointer_set_t *visited = (struct pointer_set_t *) data;
4524 if (tree_node_can_be_shared (*tp))
4526 *walk_subtrees = false;
4530 if (pointer_set_insert (visited, *tp))
4536 /* Called via walk_gimple_stmt. Verify tree sharing. */
4539 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4541 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4542 return verify_node_sharing_1 (tp, walk_subtrees, wi->info);
4545 static bool eh_error_found;
4547 verify_eh_throw_stmt_node (void **slot, void *data)
4549 struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4550 struct pointer_set_t *visited = (struct pointer_set_t *) data;
4552 if (!pointer_set_contains (visited, node->stmt))
4554 error ("dead STMT in EH table");
4555 debug_gimple_stmt (node->stmt);
4556 eh_error_found = true;
4561 /* Verify if the location LOCs block is in BLOCKS. */
4564 verify_location (pointer_set_t *blocks, location_t loc)
4566 tree block = LOCATION_BLOCK (loc);
4567 if (block != NULL_TREE
4568 && !pointer_set_contains (blocks, block))
4570 error ("location references block not in block tree");
4573 if (block != NULL_TREE)
4574 return verify_location (blocks, BLOCK_SOURCE_LOCATION (block));
4578 /* Called via walk_tree. Verify that expressions have no blocks. */
4581 verify_expr_no_block (tree *tp, int *walk_subtrees, void *)
4585 *walk_subtrees = false;
4589 location_t loc = EXPR_LOCATION (*tp);
4590 if (LOCATION_BLOCK (loc) != NULL)
4596 /* Called via walk_tree. Verify locations of expressions. */
4599 verify_expr_location_1 (tree *tp, int *walk_subtrees, void *data)
4601 struct pointer_set_t *blocks = (struct pointer_set_t *) data;
4603 if (TREE_CODE (*tp) == VAR_DECL
4604 && DECL_HAS_DEBUG_EXPR_P (*tp))
4606 tree t = DECL_DEBUG_EXPR (*tp);
4607 tree addr = walk_tree (&t, verify_expr_no_block, NULL, NULL);
4611 if ((TREE_CODE (*tp) == VAR_DECL
4612 || TREE_CODE (*tp) == PARM_DECL
4613 || TREE_CODE (*tp) == RESULT_DECL)
4614 && DECL_HAS_VALUE_EXPR_P (*tp))
4616 tree t = DECL_VALUE_EXPR (*tp);
4617 tree addr = walk_tree (&t, verify_expr_no_block, NULL, NULL);
4624 *walk_subtrees = false;
4628 location_t loc = EXPR_LOCATION (*tp);
4629 if (verify_location (blocks, loc))
4635 /* Called via walk_gimple_op. Verify locations of expressions. */
4638 verify_expr_location (tree *tp, int *walk_subtrees, void *data)
4640 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4641 return verify_expr_location_1 (tp, walk_subtrees, wi->info);
4644 /* Insert all subblocks of BLOCK into BLOCKS and recurse. */
4647 collect_subblocks (pointer_set_t *blocks, tree block)
4650 for (t = BLOCK_SUBBLOCKS (block); t; t = BLOCK_CHAIN (t))
4652 pointer_set_insert (blocks, t);
4653 collect_subblocks (blocks, t);
4657 /* Verify the GIMPLE statements in the CFG of FN. */
4660 verify_gimple_in_cfg (struct function *fn)
4664 struct pointer_set_t *visited, *visited_stmts, *blocks;
4666 timevar_push (TV_TREE_STMT_VERIFY);
4667 visited = pointer_set_create ();
4668 visited_stmts = pointer_set_create ();
4670 /* Collect all BLOCKs referenced by the BLOCK tree of FN. */
4671 blocks = pointer_set_create ();
4672 if (DECL_INITIAL (fn->decl))
4674 pointer_set_insert (blocks, DECL_INITIAL (fn->decl));
4675 collect_subblocks (blocks, DECL_INITIAL (fn->decl));
4678 FOR_EACH_BB_FN (bb, fn)
4680 gimple_stmt_iterator gsi;
4682 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4684 gimple phi = gsi_stmt (gsi);
4688 pointer_set_insert (visited_stmts, phi);
4690 if (gimple_bb (phi) != bb)
4692 error ("gimple_bb (phi) is set to a wrong basic block");
4696 err2 |= verify_gimple_phi (phi);
4698 /* Only PHI arguments have locations. */
4699 if (gimple_location (phi) != UNKNOWN_LOCATION)
4701 error ("PHI node with location");
4705 for (i = 0; i < gimple_phi_num_args (phi); i++)
4707 tree arg = gimple_phi_arg_def (phi, i);
4708 tree addr = walk_tree (&arg, verify_node_sharing_1,
4712 error ("incorrect sharing of tree nodes");
4713 debug_generic_expr (addr);
4716 location_t loc = gimple_phi_arg_location (phi, i);
4717 if (virtual_operand_p (gimple_phi_result (phi))
4718 && loc != UNKNOWN_LOCATION)
4720 error ("virtual PHI with argument locations");
4723 addr = walk_tree (&arg, verify_expr_location_1, blocks, NULL);
4726 debug_generic_expr (addr);
4729 err2 |= verify_location (blocks, loc);
4733 debug_gimple_stmt (phi);
4737 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4739 gimple stmt = gsi_stmt (gsi);
4741 struct walk_stmt_info wi;
4745 pointer_set_insert (visited_stmts, stmt);
4747 if (gimple_bb (stmt) != bb)
4749 error ("gimple_bb (stmt) is set to a wrong basic block");
4753 err2 |= verify_gimple_stmt (stmt);
4754 err2 |= verify_location (blocks, gimple_location (stmt));
4756 memset (&wi, 0, sizeof (wi));
4757 wi.info = (void *) visited;
4758 addr = walk_gimple_op (stmt, verify_node_sharing, &wi);
4761 error ("incorrect sharing of tree nodes");
4762 debug_generic_expr (addr);
4766 memset (&wi, 0, sizeof (wi));
4767 wi.info = (void *) blocks;
4768 addr = walk_gimple_op (stmt, verify_expr_location, &wi);
4771 debug_generic_expr (addr);
4775 /* ??? Instead of not checking these stmts at all the walker
4776 should know its context via wi. */
4777 if (!is_gimple_debug (stmt)
4778 && !is_gimple_omp (stmt))
4780 memset (&wi, 0, sizeof (wi));
4781 addr = walk_gimple_op (stmt, verify_expr, &wi);
4784 debug_generic_expr (addr);
4785 inform (gimple_location (stmt), "in statement");
4790 /* If the statement is marked as part of an EH region, then it is
4791 expected that the statement could throw. Verify that when we
4792 have optimizations that simplify statements such that we prove
4793 that they cannot throw, that we update other data structures
4795 lp_nr = lookup_stmt_eh_lp (stmt);
4798 if (!stmt_could_throw_p (stmt))
4800 error ("statement marked for throw, but doesn%'t");
4804 && !gsi_one_before_end_p (gsi)
4805 && stmt_can_throw_internal (stmt))
4807 error ("statement marked for throw in middle of block");
4813 debug_gimple_stmt (stmt);
4818 eh_error_found = false;
4819 if (get_eh_throw_stmt_table (cfun))
4820 htab_traverse (get_eh_throw_stmt_table (cfun),
4821 verify_eh_throw_stmt_node,
4824 if (err || eh_error_found)
4825 internal_error ("verify_gimple failed");
4827 pointer_set_destroy (visited);
4828 pointer_set_destroy (visited_stmts);
4829 pointer_set_destroy (blocks);
4830 verify_histograms ();
4831 timevar_pop (TV_TREE_STMT_VERIFY);
4835 /* Verifies that the flow information is OK. */
4838 gimple_verify_flow_info (void)
4842 gimple_stmt_iterator gsi;
4847 if (ENTRY_BLOCK_PTR->il.gimple.seq || ENTRY_BLOCK_PTR->il.gimple.phi_nodes)
4849 error ("ENTRY_BLOCK has IL associated with it");
4853 if (EXIT_BLOCK_PTR->il.gimple.seq || EXIT_BLOCK_PTR->il.gimple.phi_nodes)
4855 error ("EXIT_BLOCK has IL associated with it");
4859 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4860 if (e->flags & EDGE_FALLTHRU)
4862 error ("fallthru to exit from bb %d", e->src->index);
4868 bool found_ctrl_stmt = false;
4872 /* Skip labels on the start of basic block. */
4873 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4876 gimple prev_stmt = stmt;
4878 stmt = gsi_stmt (gsi);
4880 if (gimple_code (stmt) != GIMPLE_LABEL)
4883 label = gimple_label_label (stmt);
4884 if (prev_stmt && DECL_NONLOCAL (label))
4886 error ("nonlocal label ");
4887 print_generic_expr (stderr, label, 0);
4888 fprintf (stderr, " is not first in a sequence of labels in bb %d",
4893 if (prev_stmt && EH_LANDING_PAD_NR (label) != 0)
4895 error ("EH landing pad label ");
4896 print_generic_expr (stderr, label, 0);
4897 fprintf (stderr, " is not first in a sequence of labels in bb %d",
4902 if (label_to_block (label) != bb)
4905 print_generic_expr (stderr, label, 0);
4906 fprintf (stderr, " to block does not match in bb %d",
4911 if (decl_function_context (label) != current_function_decl)
4914 print_generic_expr (stderr, label, 0);
4915 fprintf (stderr, " has incorrect context in bb %d",
4921 /* Verify that body of basic block BB is free of control flow. */
4922 for (; !gsi_end_p (gsi); gsi_next (&gsi))
4924 gimple stmt = gsi_stmt (gsi);
4926 if (found_ctrl_stmt)
4928 error ("control flow in the middle of basic block %d",
4933 if (stmt_ends_bb_p (stmt))
4934 found_ctrl_stmt = true;
4936 if (gimple_code (stmt) == GIMPLE_LABEL)
4939 print_generic_expr (stderr, gimple_label_label (stmt), 0);
4940 fprintf (stderr, " in the middle of basic block %d", bb->index);
4945 gsi = gsi_last_bb (bb);
4946 if (gsi_end_p (gsi))
4949 stmt = gsi_stmt (gsi);
4951 if (gimple_code (stmt) == GIMPLE_LABEL)
4954 err |= verify_eh_edges (stmt);
4956 if (is_ctrl_stmt (stmt))
4958 FOR_EACH_EDGE (e, ei, bb->succs)
4959 if (e->flags & EDGE_FALLTHRU)
4961 error ("fallthru edge after a control statement in bb %d",
4967 if (gimple_code (stmt) != GIMPLE_COND)
4969 /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4970 after anything else but if statement. */
4971 FOR_EACH_EDGE (e, ei, bb->succs)
4972 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4974 error ("true/false edge after a non-GIMPLE_COND in bb %d",
4980 switch (gimple_code (stmt))
4987 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4991 || !(true_edge->flags & EDGE_TRUE_VALUE)
4992 || !(false_edge->flags & EDGE_FALSE_VALUE)
4993 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4994 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4995 || EDGE_COUNT (bb->succs) >= 3)
4997 error ("wrong outgoing edge flags at end of bb %d",
5005 if (simple_goto_p (stmt))
5007 error ("explicit goto at end of bb %d", bb->index);
5012 /* FIXME. We should double check that the labels in the
5013 destination blocks have their address taken. */
5014 FOR_EACH_EDGE (e, ei, bb->succs)
5015 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
5016 | EDGE_FALSE_VALUE))
5017 || !(e->flags & EDGE_ABNORMAL))
5019 error ("wrong outgoing edge flags at end of bb %d",
5027 if (!gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
5029 /* ... fallthru ... */
5031 if (!single_succ_p (bb)
5032 || (single_succ_edge (bb)->flags
5033 & (EDGE_FALLTHRU | EDGE_ABNORMAL
5034 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
5036 error ("wrong outgoing edge flags at end of bb %d", bb->index);
5039 if (single_succ (bb) != EXIT_BLOCK_PTR)
5041 error ("return edge does not point to exit in bb %d",
5053 n = gimple_switch_num_labels (stmt);
5055 /* Mark all the destination basic blocks. */
5056 for (i = 0; i < n; ++i)
5058 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
5059 basic_block label_bb = label_to_block (lab);
5060 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
5061 label_bb->aux = (void *)1;
5064 /* Verify that the case labels are sorted. */
5065 prev = gimple_switch_label (stmt, 0);
5066 for (i = 1; i < n; ++i)
5068 tree c = gimple_switch_label (stmt, i);
5071 error ("found default case not at the start of "
5077 && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
5079 error ("case labels not sorted: ");
5080 print_generic_expr (stderr, prev, 0);
5081 fprintf (stderr," is greater than ");
5082 print_generic_expr (stderr, c, 0);
5083 fprintf (stderr," but comes before it.\n");
5088 /* VRP will remove the default case if it can prove it will
5089 never be executed. So do not verify there always exists
5090 a default case here. */
5092 FOR_EACH_EDGE (e, ei, bb->succs)
5096 error ("extra outgoing edge %d->%d",
5097 bb->index, e->dest->index);
5101 e->dest->aux = (void *)2;
5102 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
5103 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
5105 error ("wrong outgoing edge flags at end of bb %d",
5111 /* Check that we have all of them. */
5112 for (i = 0; i < n; ++i)
5114 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
5115 basic_block label_bb = label_to_block (lab);
5117 if (label_bb->aux != (void *)2)
5119 error ("missing edge %i->%i", bb->index, label_bb->index);
5124 FOR_EACH_EDGE (e, ei, bb->succs)
5125 e->dest->aux = (void *)0;
5129 case GIMPLE_EH_DISPATCH:
5130 err |= verify_eh_dispatch_edge (stmt);
5138 if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
5139 verify_dominators (CDI_DOMINATORS);
5145 /* Updates phi nodes after creating a forwarder block joined
5146 by edge FALLTHRU. */
5149 gimple_make_forwarder_block (edge fallthru)
5153 basic_block dummy, bb;
5155 gimple_stmt_iterator gsi;
5157 dummy = fallthru->src;
5158 bb = fallthru->dest;
5160 if (single_pred_p (bb))
5163 /* If we redirected a branch we must create new PHI nodes at the
5165 for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
5167 gimple phi, new_phi;
5169 phi = gsi_stmt (gsi);
5170 var = gimple_phi_result (phi);
5171 new_phi = create_phi_node (var, bb);
5172 gimple_phi_set_result (phi, copy_ssa_name (var, phi));
5173 add_phi_arg (new_phi, gimple_phi_result (phi), fallthru,
5177 /* Add the arguments we have stored on edges. */
5178 FOR_EACH_EDGE (e, ei, bb->preds)
5183 flush_pending_stmts (e);
5188 /* Return a non-special label in the head of basic block BLOCK.
5189 Create one if it doesn't exist. */
5192 gimple_block_label (basic_block bb)
5194 gimple_stmt_iterator i, s = gsi_start_bb (bb);
5199 for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
5201 stmt = gsi_stmt (i);
5202 if (gimple_code (stmt) != GIMPLE_LABEL)
5204 label = gimple_label_label (stmt);
5205 if (!DECL_NONLOCAL (label))
5208 gsi_move_before (&i, &s);
5213 label = create_artificial_label (UNKNOWN_LOCATION);
5214 stmt = gimple_build_label (label);
5215 gsi_insert_before (&s, stmt, GSI_NEW_STMT);
5220 /* Attempt to perform edge redirection by replacing a possibly complex
5221 jump instruction by a goto or by removing the jump completely.
5222 This can apply only if all edges now point to the same block. The
5223 parameters and return values are equivalent to
5224 redirect_edge_and_branch. */
5227 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
5229 basic_block src = e->src;
5230 gimple_stmt_iterator i;
5233 /* We can replace or remove a complex jump only when we have exactly
5235 if (EDGE_COUNT (src->succs) != 2
5236 /* Verify that all targets will be TARGET. Specifically, the
5237 edge that is not E must also go to TARGET. */
5238 || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
5241 i = gsi_last_bb (src);
5245 stmt = gsi_stmt (i);
5247 if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
5249 gsi_remove (&i, true);
5250 e = ssa_redirect_edge (e, target);
5251 e->flags = EDGE_FALLTHRU;
5259 /* Redirect E to DEST. Return NULL on failure. Otherwise, return the
5260 edge representing the redirected branch. */
5263 gimple_redirect_edge_and_branch (edge e, basic_block dest)
5265 basic_block bb = e->src;
5266 gimple_stmt_iterator gsi;
5270 if (e->flags & EDGE_ABNORMAL)
5273 if (e->dest == dest)
5276 if (e->flags & EDGE_EH)
5277 return redirect_eh_edge (e, dest);
5279 if (e->src != ENTRY_BLOCK_PTR)
5281 ret = gimple_try_redirect_by_replacing_jump (e, dest);
5286 gsi = gsi_last_bb (bb);
5287 stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
5289 switch (stmt ? gimple_code (stmt) : GIMPLE_ERROR_MARK)
5292 /* For COND_EXPR, we only need to redirect the edge. */
5296 /* No non-abnormal edges should lead from a non-simple goto, and
5297 simple ones should be represented implicitly. */
5302 tree label = gimple_block_label (dest);
5303 tree cases = get_cases_for_edge (e, stmt);
5305 /* If we have a list of cases associated with E, then use it
5306 as it's a lot faster than walking the entire case vector. */
5309 edge e2 = find_edge (e->src, dest);
5316 CASE_LABEL (cases) = label;
5317 cases = CASE_CHAIN (cases);
5320 /* If there was already an edge in the CFG, then we need
5321 to move all the cases associated with E to E2. */
5324 tree cases2 = get_cases_for_edge (e2, stmt);
5326 CASE_CHAIN (last) = CASE_CHAIN (cases2);
5327 CASE_CHAIN (cases2) = first;
5329 bitmap_set_bit (touched_switch_bbs, gimple_bb (stmt)->index);
5333 size_t i, n = gimple_switch_num_labels (stmt);
5335 for (i = 0; i < n; i++)
5337 tree elt = gimple_switch_label (stmt, i);
5338 if (label_to_block (CASE_LABEL (elt)) == e->dest)
5339 CASE_LABEL (elt) = label;
5347 int i, n = gimple_asm_nlabels (stmt);
5350 for (i = 0; i < n; ++i)
5352 tree cons = gimple_asm_label_op (stmt, i);
5353 if (label_to_block (TREE_VALUE (cons)) == e->dest)
5356 label = gimple_block_label (dest);
5357 TREE_VALUE (cons) = label;
5361 /* If we didn't find any label matching the former edge in the
5362 asm labels, we must be redirecting the fallthrough
5364 gcc_assert (label || (e->flags & EDGE_FALLTHRU));
5369 gsi_remove (&gsi, true);
5370 e->flags |= EDGE_FALLTHRU;
5373 case GIMPLE_OMP_RETURN:
5374 case GIMPLE_OMP_CONTINUE:
5375 case GIMPLE_OMP_SECTIONS_SWITCH:
5376 case GIMPLE_OMP_FOR:
5377 /* The edges from OMP constructs can be simply redirected. */
5380 case GIMPLE_EH_DISPATCH:
5381 if (!(e->flags & EDGE_FALLTHRU))
5382 redirect_eh_dispatch_edge (stmt, e, dest);
5385 case GIMPLE_TRANSACTION:
5386 /* The ABORT edge has a stored label associated with it, otherwise
5387 the edges are simply redirectable. */
5389 gimple_transaction_set_label (stmt, gimple_block_label (dest));
5393 /* Otherwise it must be a fallthru edge, and we don't need to
5394 do anything besides redirecting it. */
5395 gcc_assert (e->flags & EDGE_FALLTHRU);
5399 /* Update/insert PHI nodes as necessary. */
5401 /* Now update the edges in the CFG. */
5402 e = ssa_redirect_edge (e, dest);
5407 /* Returns true if it is possible to remove edge E by redirecting
5408 it to the destination of the other edge from E->src. */
5411 gimple_can_remove_branch_p (const_edge e)
5413 if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
5419 /* Simple wrapper, as we can always redirect fallthru edges. */
5422 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
5424 e = gimple_redirect_edge_and_branch (e, dest);
5431 /* Splits basic block BB after statement STMT (but at least after the
5432 labels). If STMT is NULL, BB is split just after the labels. */
5435 gimple_split_block (basic_block bb, void *stmt)
5437 gimple_stmt_iterator gsi;
5438 gimple_stmt_iterator gsi_tgt;
5445 new_bb = create_empty_bb (bb);
5447 /* Redirect the outgoing edges. */
5448 new_bb->succs = bb->succs;
5450 FOR_EACH_EDGE (e, ei, new_bb->succs)
5453 if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
5456 /* Move everything from GSI to the new basic block. */
5457 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5459 act = gsi_stmt (gsi);
5460 if (gimple_code (act) == GIMPLE_LABEL)
5473 if (gsi_end_p (gsi))
5476 /* Split the statement list - avoid re-creating new containers as this
5477 brings ugly quadratic memory consumption in the inliner.
5478 (We are still quadratic since we need to update stmt BB pointers,
5480 gsi_split_seq_before (&gsi, &list);
5481 set_bb_seq (new_bb, list);
5482 for (gsi_tgt = gsi_start (list);
5483 !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
5484 gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
5490 /* Moves basic block BB after block AFTER. */
5493 gimple_move_block_after (basic_block bb, basic_block after)
5495 if (bb->prev_bb == after)
5499 link_block (bb, after);
5505 /* Return TRUE if block BB has no executable statements, otherwise return
5509 gimple_empty_block_p (basic_block bb)
5511 /* BB must have no executable statements. */
5512 gimple_stmt_iterator gsi = gsi_after_labels (bb);
5515 if (gsi_end_p (gsi))
5517 if (is_gimple_debug (gsi_stmt (gsi)))
5518 gsi_next_nondebug (&gsi);
5519 return gsi_end_p (gsi);
5523 /* Split a basic block if it ends with a conditional branch and if the
5524 other part of the block is not empty. */
5527 gimple_split_block_before_cond_jump (basic_block bb)
5529 gimple last, split_point;
5530 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
5531 if (gsi_end_p (gsi))
5533 last = gsi_stmt (gsi);
5534 if (gimple_code (last) != GIMPLE_COND
5535 && gimple_code (last) != GIMPLE_SWITCH)
5537 gsi_prev_nondebug (&gsi);
5538 split_point = gsi_stmt (gsi);
5539 return split_block (bb, split_point)->dest;
5543 /* Return true if basic_block can be duplicated. */
5546 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5551 /* Create a duplicate of the basic block BB. NOTE: This does not
5552 preserve SSA form. */
5555 gimple_duplicate_bb (basic_block bb)
5558 gimple_stmt_iterator gsi, gsi_tgt;
5559 gimple_seq phis = phi_nodes (bb);
5560 gimple phi, stmt, copy;
5562 new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
5564 /* Copy the PHI nodes. We ignore PHI node arguments here because
5565 the incoming edges have not been setup yet. */
5566 for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
5568 phi = gsi_stmt (gsi);
5569 copy = create_phi_node (NULL_TREE, new_bb);
5570 create_new_def_for (gimple_phi_result (phi), copy,
5571 gimple_phi_result_ptr (copy));
5572 gimple_set_uid (copy, gimple_uid (phi));
5575 gsi_tgt = gsi_start_bb (new_bb);
5576 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5578 def_operand_p def_p;
5579 ssa_op_iter op_iter;
5582 stmt = gsi_stmt (gsi);
5583 if (gimple_code (stmt) == GIMPLE_LABEL)
5586 /* Don't duplicate label debug stmts. */
5587 if (gimple_debug_bind_p (stmt)
5588 && TREE_CODE (gimple_debug_bind_get_var (stmt))
5592 /* Create a new copy of STMT and duplicate STMT's virtual
5594 copy = gimple_copy (stmt);
5595 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
5597 maybe_duplicate_eh_stmt (copy, stmt);
5598 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5600 /* When copying around a stmt writing into a local non-user
5601 aggregate, make sure it won't share stack slot with other
5603 lhs = gimple_get_lhs (stmt);
5604 if (lhs && TREE_CODE (lhs) != SSA_NAME)
5606 tree base = get_base_address (lhs);
5608 && (TREE_CODE (base) == VAR_DECL
5609 || TREE_CODE (base) == RESULT_DECL)
5610 && DECL_IGNORED_P (base)
5611 && !TREE_STATIC (base)
5612 && !DECL_EXTERNAL (base)
5613 && (TREE_CODE (base) != VAR_DECL
5614 || !DECL_HAS_VALUE_EXPR_P (base)))
5615 DECL_NONSHAREABLE (base) = 1;
5618 /* Create new names for all the definitions created by COPY and
5619 add replacement mappings for each new name. */
5620 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5621 create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5627 /* Adds phi node arguments for edge E_COPY after basic block duplication. */
5630 add_phi_args_after_copy_edge (edge e_copy)
5632 basic_block bb, bb_copy = e_copy->src, dest;
5635 gimple phi, phi_copy;
5637 gimple_stmt_iterator psi, psi_copy;
5639 if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
5642 bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5644 if (e_copy->dest->flags & BB_DUPLICATED)
5645 dest = get_bb_original (e_copy->dest);
5647 dest = e_copy->dest;
5649 e = find_edge (bb, dest);
5652 /* During loop unrolling the target of the latch edge is copied.
5653 In this case we are not looking for edge to dest, but to
5654 duplicated block whose original was dest. */
5655 FOR_EACH_EDGE (e, ei, bb->succs)
5657 if ((e->dest->flags & BB_DUPLICATED)
5658 && get_bb_original (e->dest) == dest)
5662 gcc_assert (e != NULL);
5665 for (psi = gsi_start_phis (e->dest),
5666 psi_copy = gsi_start_phis (e_copy->dest);
5668 gsi_next (&psi), gsi_next (&psi_copy))
5670 phi = gsi_stmt (psi);
5671 phi_copy = gsi_stmt (psi_copy);
5672 def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5673 add_phi_arg (phi_copy, def, e_copy,
5674 gimple_phi_arg_location_from_edge (phi, e));
5679 /* Basic block BB_COPY was created by code duplication. Add phi node
5680 arguments for edges going out of BB_COPY. The blocks that were
5681 duplicated have BB_DUPLICATED set. */
5684 add_phi_args_after_copy_bb (basic_block bb_copy)
5689 FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5691 add_phi_args_after_copy_edge (e_copy);
5695 /* Blocks in REGION_COPY array of length N_REGION were created by
5696 duplication of basic blocks. Add phi node arguments for edges
5697 going from these blocks. If E_COPY is not NULL, also add
5698 phi node arguments for its destination.*/
5701 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5706 for (i = 0; i < n_region; i++)
5707 region_copy[i]->flags |= BB_DUPLICATED;
5709 for (i = 0; i < n_region; i++)
5710 add_phi_args_after_copy_bb (region_copy[i]);
5712 add_phi_args_after_copy_edge (e_copy);
5714 for (i = 0; i < n_region; i++)
5715 region_copy[i]->flags &= ~BB_DUPLICATED;
5718 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5719 important exit edge EXIT. By important we mean that no SSA name defined
5720 inside region is live over the other exit edges of the region. All entry
5721 edges to the region must go to ENTRY->dest. The edge ENTRY is redirected
5722 to the duplicate of the region. Dominance and loop information is
5723 updated if UPDATE_DOMINANCE is true, but not the SSA web. If
5724 UPDATE_DOMINANCE is false then we assume that the caller will update the
5725 dominance information after calling this function. The new basic
5726 blocks are stored to REGION_COPY in the same order as they had in REGION,
5727 provided that REGION_COPY is not NULL.
5728 The function returns false if it is unable to copy the region,
5732 gimple_duplicate_sese_region (edge entry, edge exit,
5733 basic_block *region, unsigned n_region,
5734 basic_block *region_copy,
5735 bool update_dominance)
5738 bool free_region_copy = false, copying_header = false;
5739 struct loop *loop = entry->dest->loop_father;
5741 vec<basic_block> doms;
5743 int total_freq = 0, entry_freq = 0;
5744 gcov_type total_count = 0, entry_count = 0;
5746 if (!can_copy_bbs_p (region, n_region))
5749 /* Some sanity checking. Note that we do not check for all possible
5750 missuses of the functions. I.e. if you ask to copy something weird,
5751 it will work, but the state of structures probably will not be
5753 for (i = 0; i < n_region; i++)
5755 /* We do not handle subloops, i.e. all the blocks must belong to the
5757 if (region[i]->loop_father != loop)
5760 if (region[i] != entry->dest
5761 && region[i] == loop->header)
5765 set_loop_copy (loop, loop);
5767 /* In case the function is used for loop header copying (which is the primary
5768 use), ensure that EXIT and its copy will be new latch and entry edges. */
5769 if (loop->header == entry->dest)
5771 copying_header = true;
5772 set_loop_copy (loop, loop_outer (loop));
5774 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5777 for (i = 0; i < n_region; i++)
5778 if (region[i] != exit->src
5779 && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5785 region_copy = XNEWVEC (basic_block, n_region);
5786 free_region_copy = true;
5789 initialize_original_copy_tables ();
5791 /* Record blocks outside the region that are dominated by something
5793 if (update_dominance)
5796 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5799 if (entry->dest->count)
5801 total_count = entry->dest->count;
5802 entry_count = entry->count;
5803 /* Fix up corner cases, to avoid division by zero or creation of negative
5805 if (entry_count > total_count)
5806 entry_count = total_count;
5810 total_freq = entry->dest->frequency;
5811 entry_freq = EDGE_FREQUENCY (entry);
5812 /* Fix up corner cases, to avoid division by zero or creation of negative
5814 if (total_freq == 0)
5816 else if (entry_freq > total_freq)
5817 entry_freq = total_freq;
5820 copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5821 split_edge_bb_loc (entry), update_dominance);
5824 scale_bbs_frequencies_gcov_type (region, n_region,
5825 total_count - entry_count,
5827 scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5832 scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5834 scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5839 loop->header = exit->dest;
5840 loop->latch = exit->src;
5843 /* Redirect the entry and add the phi node arguments. */
5844 redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5845 gcc_assert (redirected != NULL);
5846 flush_pending_stmts (entry);
5848 /* Concerning updating of dominators: We must recount dominators
5849 for entry block and its copy. Anything that is outside of the
5850 region, but was dominated by something inside needs recounting as
5852 if (update_dominance)
5854 set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5855 doms.safe_push (get_bb_original (entry->dest));
5856 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5860 /* Add the other PHI node arguments. */
5861 add_phi_args_after_copy (region_copy, n_region, NULL);
5863 if (free_region_copy)
5866 free_original_copy_tables ();
5870 /* Checks if BB is part of the region defined by N_REGION BBS. */
5872 bb_part_of_region_p (basic_block bb, basic_block* bbs, unsigned n_region)
5876 for (n = 0; n < n_region; n++)
5884 /* Duplicates REGION consisting of N_REGION blocks. The new blocks
5885 are stored to REGION_COPY in the same order in that they appear
5886 in REGION, if REGION_COPY is not NULL. ENTRY is the entry to
5887 the region, EXIT an exit from it. The condition guarding EXIT
5888 is moved to ENTRY. Returns true if duplication succeeds, false
5914 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
5915 basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
5916 basic_block *region_copy ATTRIBUTE_UNUSED)
5919 bool free_region_copy = false;
5920 struct loop *loop = exit->dest->loop_father;
5921 struct loop *orig_loop = entry->dest->loop_father;
5922 basic_block switch_bb, entry_bb, nentry_bb;
5923 vec<basic_block> doms;
5924 int total_freq = 0, exit_freq = 0;
5925 gcov_type total_count = 0, exit_count = 0;
5926 edge exits[2], nexits[2], e;
5927 gimple_stmt_iterator gsi;
5930 basic_block exit_bb;
5931 gimple_stmt_iterator psi;
5934 struct loop *target, *aloop, *cloop;
5936 gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5938 exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5940 if (!can_copy_bbs_p (region, n_region))
5943 initialize_original_copy_tables ();
5944 set_loop_copy (orig_loop, loop);
5947 for (aloop = orig_loop->inner; aloop; aloop = aloop->next)
5949 if (bb_part_of_region_p (aloop->header, region, n_region))
5951 cloop = duplicate_loop (aloop, target);
5952 duplicate_subloops (aloop, cloop);
5958 region_copy = XNEWVEC (basic_block, n_region);
5959 free_region_copy = true;
5962 gcc_assert (!need_ssa_update_p (cfun));
5964 /* Record blocks outside the region that are dominated by something
5966 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5968 if (exit->src->count)
5970 total_count = exit->src->count;
5971 exit_count = exit->count;
5972 /* Fix up corner cases, to avoid division by zero or creation of negative
5974 if (exit_count > total_count)
5975 exit_count = total_count;
5979 total_freq = exit->src->frequency;
5980 exit_freq = EDGE_FREQUENCY (exit);
5981 /* Fix up corner cases, to avoid division by zero or creation of negative
5983 if (total_freq == 0)
5985 if (exit_freq > total_freq)
5986 exit_freq = total_freq;
5989 copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5990 split_edge_bb_loc (exit), true);
5993 scale_bbs_frequencies_gcov_type (region, n_region,
5994 total_count - exit_count,
5996 scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
6001 scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
6003 scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
6006 /* Create the switch block, and put the exit condition to it. */
6007 entry_bb = entry->dest;
6008 nentry_bb = get_bb_copy (entry_bb);
6009 if (!last_stmt (entry->src)
6010 || !stmt_ends_bb_p (last_stmt (entry->src)))
6011 switch_bb = entry->src;
6013 switch_bb = split_edge (entry);
6014 set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
6016 gsi = gsi_last_bb (switch_bb);
6017 cond_stmt = last_stmt (exit->src);
6018 gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
6019 cond_stmt = gimple_copy (cond_stmt);
6021 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
6023 sorig = single_succ_edge (switch_bb);
6024 sorig->flags = exits[1]->flags;
6025 snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
6027 /* Register the new edge from SWITCH_BB in loop exit lists. */
6028 rescan_loop_exit (snew, true, false);
6030 /* Add the PHI node arguments. */
6031 add_phi_args_after_copy (region_copy, n_region, snew);
6033 /* Get rid of now superfluous conditions and associated edges (and phi node
6035 exit_bb = exit->dest;
6037 e = redirect_edge_and_branch (exits[0], exits[1]->dest);
6038 PENDING_STMT (e) = NULL;
6040 /* The latch of ORIG_LOOP was copied, and so was the backedge
6041 to the original header. We redirect this backedge to EXIT_BB. */
6042 for (i = 0; i < n_region; i++)
6043 if (get_bb_original (region_copy[i]) == orig_loop->latch)
6045 gcc_assert (single_succ_edge (region_copy[i]));
6046 e = redirect_edge_and_branch (single_succ_edge (region_copy[i]), exit_bb);
6047 PENDING_STMT (e) = NULL;
6048 for (psi = gsi_start_phis (exit_bb);
6052 phi = gsi_stmt (psi);
6053 def = PHI_ARG_DEF (phi, nexits[0]->dest_idx);
6054 add_phi_arg (phi, def, e, gimple_phi_arg_location_from_edge (phi, e));
6057 e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
6058 PENDING_STMT (e) = NULL;
6060 /* Anything that is outside of the region, but was dominated by something
6061 inside needs to update dominance info. */
6062 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
6064 /* Update the SSA web. */
6065 update_ssa (TODO_update_ssa);
6067 if (free_region_copy)
6070 free_original_copy_tables ();
6074 /* Add all the blocks dominated by ENTRY to the array BBS_P. Stop
6075 adding blocks when the dominator traversal reaches EXIT. This
6076 function silently assumes that ENTRY strictly dominates EXIT. */
6079 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
6080 vec<basic_block> *bbs_p)
6084 for (son = first_dom_son (CDI_DOMINATORS, entry);
6086 son = next_dom_son (CDI_DOMINATORS, son))
6088 bbs_p->safe_push (son);
6090 gather_blocks_in_sese_region (son, exit, bbs_p);
6094 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
6095 The duplicates are recorded in VARS_MAP. */
6098 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
6101 tree t = *tp, new_t;
6102 struct function *f = DECL_STRUCT_FUNCTION (to_context);
6105 if (DECL_CONTEXT (t) == to_context)
6108 loc = pointer_map_contains (vars_map, t);
6112 loc = pointer_map_insert (vars_map, t);
6116 new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
6117 add_local_decl (f, new_t);
6121 gcc_assert (TREE_CODE (t) == CONST_DECL);
6122 new_t = copy_node (t);
6124 DECL_CONTEXT (new_t) = to_context;
6129 new_t = (tree) *loc;
6135 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
6136 VARS_MAP maps old ssa names and var_decls to the new ones. */
6139 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
6145 gcc_assert (!virtual_operand_p (name));
6147 loc = pointer_map_contains (vars_map, name);
6151 tree decl = SSA_NAME_VAR (name);
6154 replace_by_duplicate_decl (&decl, vars_map, to_context);
6155 new_name = make_ssa_name_fn (DECL_STRUCT_FUNCTION (to_context),
6156 decl, SSA_NAME_DEF_STMT (name));
6157 if (SSA_NAME_IS_DEFAULT_DEF (name))
6158 set_ssa_default_def (DECL_STRUCT_FUNCTION (to_context),
6162 new_name = copy_ssa_name_fn (DECL_STRUCT_FUNCTION (to_context),
6163 name, SSA_NAME_DEF_STMT (name));
6165 loc = pointer_map_insert (vars_map, name);
6169 new_name = (tree) *loc;
6180 struct pointer_map_t *vars_map;
6181 htab_t new_label_map;
6182 struct pointer_map_t *eh_map;
6186 /* Helper for move_block_to_fn. Set TREE_BLOCK in every expression
6187 contained in *TP if it has been ORIG_BLOCK previously and change the
6188 DECL_CONTEXT of every local variable referenced in *TP. */
6191 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
6193 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
6194 struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
6199 tree block = TREE_BLOCK (t);
6200 if (block == p->orig_block
6201 || (p->orig_block == NULL_TREE
6202 && block != NULL_TREE))
6203 TREE_SET_BLOCK (t, p->new_block);
6204 #ifdef ENABLE_CHECKING
6205 else if (block != NULL_TREE)
6207 while (block && TREE_CODE (block) == BLOCK && block != p->orig_block)
6208 block = BLOCK_SUPERCONTEXT (block);
6209 gcc_assert (block == p->orig_block);
6213 else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
6215 if (TREE_CODE (t) == SSA_NAME)
6216 *tp = replace_ssa_name (t, p->vars_map, p->to_context);
6217 else if (TREE_CODE (t) == LABEL_DECL)
6219 if (p->new_label_map)
6221 struct tree_map in, *out;
6223 out = (struct tree_map *)
6224 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
6229 DECL_CONTEXT (t) = p->to_context;
6231 else if (p->remap_decls_p)
6233 /* Replace T with its duplicate. T should no longer appear in the
6234 parent function, so this looks wasteful; however, it may appear
6235 in referenced_vars, and more importantly, as virtual operands of
6236 statements, and in alias lists of other variables. It would be
6237 quite difficult to expunge it from all those places. ??? It might
6238 suffice to do this for addressable variables. */
6239 if ((TREE_CODE (t) == VAR_DECL
6240 && !is_global_var (t))
6241 || TREE_CODE (t) == CONST_DECL)
6242 replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
6246 else if (TYPE_P (t))
6252 /* Helper for move_stmt_r. Given an EH region number for the source
6253 function, map that to the duplicate EH regio number in the dest. */
6256 move_stmt_eh_region_nr (int old_nr, struct move_stmt_d *p)
6258 eh_region old_r, new_r;
6261 old_r = get_eh_region_from_number (old_nr);
6262 slot = pointer_map_contains (p->eh_map, old_r);
6263 new_r = (eh_region) *slot;
6265 return new_r->index;
6268 /* Similar, but operate on INTEGER_CSTs. */
6271 move_stmt_eh_region_tree_nr (tree old_t_nr, struct move_stmt_d *p)
6275 old_nr = tree_low_cst (old_t_nr, 0);
6276 new_nr = move_stmt_eh_region_nr (old_nr, p);
6278 return build_int_cst (integer_type_node, new_nr);
6281 /* Like move_stmt_op, but for gimple statements.
6283 Helper for move_block_to_fn. Set GIMPLE_BLOCK in every expression
6284 contained in the current statement in *GSI_P and change the
6285 DECL_CONTEXT of every local variable referenced in the current
6289 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
6290 struct walk_stmt_info *wi)
6292 struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
6293 gimple stmt = gsi_stmt (*gsi_p);
6294 tree block = gimple_block (stmt);
6296 if (block == p->orig_block
6297 || (p->orig_block == NULL_TREE
6298 && block != NULL_TREE))
6299 gimple_set_block (stmt, p->new_block);
6301 switch (gimple_code (stmt))
6304 /* Remap the region numbers for __builtin_eh_{pointer,filter}. */
6306 tree r, fndecl = gimple_call_fndecl (stmt);
6307 if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
6308 switch (DECL_FUNCTION_CODE (fndecl))
6310 case BUILT_IN_EH_COPY_VALUES:
6311 r = gimple_call_arg (stmt, 1);
6312 r = move_stmt_eh_region_tree_nr (r, p);
6313 gimple_call_set_arg (stmt, 1, r);
6316 case BUILT_IN_EH_POINTER:
6317 case BUILT_IN_EH_FILTER:
6318 r = gimple_call_arg (stmt, 0);
6319 r = move_stmt_eh_region_tree_nr (r, p);
6320 gimple_call_set_arg (stmt, 0, r);
6331 int r = gimple_resx_region (stmt);
6332 r = move_stmt_eh_region_nr (r, p);
6333 gimple_resx_set_region (stmt, r);
6337 case GIMPLE_EH_DISPATCH:
6339 int r = gimple_eh_dispatch_region (stmt);
6340 r = move_stmt_eh_region_nr (r, p);
6341 gimple_eh_dispatch_set_region (stmt, r);
6345 case GIMPLE_OMP_RETURN:
6346 case GIMPLE_OMP_CONTINUE:
6349 if (is_gimple_omp (stmt))
6351 /* Do not remap variables inside OMP directives. Variables
6352 referenced in clauses and directive header belong to the
6353 parent function and should not be moved into the child
6355 bool save_remap_decls_p = p->remap_decls_p;
6356 p->remap_decls_p = false;
6357 *handled_ops_p = true;
6359 walk_gimple_seq_mod (gimple_omp_body_ptr (stmt), move_stmt_r,
6362 p->remap_decls_p = save_remap_decls_p;
6370 /* Move basic block BB from function CFUN to function DEST_FN. The
6371 block is moved out of the original linked list and placed after
6372 block AFTER in the new list. Also, the block is removed from the
6373 original array of blocks and placed in DEST_FN's array of blocks.
6374 If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
6375 updated to reflect the moved edges.
6377 The local variables are remapped to new instances, VARS_MAP is used
6378 to record the mapping. */
6381 move_block_to_fn (struct function *dest_cfun, basic_block bb,
6382 basic_block after, bool update_edge_count_p,
6383 struct move_stmt_d *d)
6385 struct control_flow_graph *cfg;
6388 gimple_stmt_iterator si;
6389 unsigned old_len, new_len;
6391 /* Remove BB from dominance structures. */
6392 delete_from_dominance_info (CDI_DOMINATORS, bb);
6394 /* Move BB from its current loop to the copy in the new function. */
6397 struct loop *new_loop = (struct loop *)bb->loop_father->aux;
6399 bb->loop_father = new_loop;
6402 /* Link BB to the new linked list. */
6403 move_block_after (bb, after);
6405 /* Update the edge count in the corresponding flowgraphs. */
6406 if (update_edge_count_p)
6407 FOR_EACH_EDGE (e, ei, bb->succs)
6409 cfun->cfg->x_n_edges--;
6410 dest_cfun->cfg->x_n_edges++;
6413 /* Remove BB from the original basic block array. */
6414 (*cfun->cfg->x_basic_block_info)[bb->index] = NULL;
6415 cfun->cfg->x_n_basic_blocks--;
6417 /* Grow DEST_CFUN's basic block array if needed. */
6418 cfg = dest_cfun->cfg;
6419 cfg->x_n_basic_blocks++;
6420 if (bb->index >= cfg->x_last_basic_block)
6421 cfg->x_last_basic_block = bb->index + 1;
6423 old_len = vec_safe_length (cfg->x_basic_block_info);
6424 if ((unsigned) cfg->x_last_basic_block >= old_len)
6426 new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
6427 vec_safe_grow_cleared (cfg->x_basic_block_info, new_len);
6430 (*cfg->x_basic_block_info)[bb->index] = bb;
6432 /* Remap the variables in phi nodes. */
6433 for (si = gsi_start_phis (bb); !gsi_end_p (si); )
6435 gimple phi = gsi_stmt (si);
6437 tree op = PHI_RESULT (phi);
6441 if (virtual_operand_p (op))
6443 /* Remove the phi nodes for virtual operands (alias analysis will be
6444 run for the new function, anyway). */
6445 remove_phi_node (&si, true);
6449 SET_PHI_RESULT (phi,
6450 replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6451 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
6453 op = USE_FROM_PTR (use);
6454 if (TREE_CODE (op) == SSA_NAME)
6455 SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6458 for (i = 0; i < EDGE_COUNT (bb->preds); i++)
6460 location_t locus = gimple_phi_arg_location (phi, i);
6461 tree block = LOCATION_BLOCK (locus);
6463 if (locus == UNKNOWN_LOCATION)
6465 if (d->orig_block == NULL_TREE || block == d->orig_block)
6467 if (d->new_block == NULL_TREE)
6468 locus = LOCATION_LOCUS (locus);
6470 locus = COMBINE_LOCATION_DATA (line_table, locus, d->new_block);
6471 gimple_phi_arg_set_location (phi, i, locus);
6478 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6480 gimple stmt = gsi_stmt (si);
6481 struct walk_stmt_info wi;
6483 memset (&wi, 0, sizeof (wi));
6485 walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
6487 if (gimple_code (stmt) == GIMPLE_LABEL)
6489 tree label = gimple_label_label (stmt);
6490 int uid = LABEL_DECL_UID (label);
6492 gcc_assert (uid > -1);
6494 old_len = vec_safe_length (cfg->x_label_to_block_map);
6495 if (old_len <= (unsigned) uid)
6497 new_len = 3 * uid / 2 + 1;
6498 vec_safe_grow_cleared (cfg->x_label_to_block_map, new_len);
6501 (*cfg->x_label_to_block_map)[uid] = bb;
6502 (*cfun->cfg->x_label_to_block_map)[uid] = NULL;
6504 gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
6506 if (uid >= dest_cfun->cfg->last_label_uid)
6507 dest_cfun->cfg->last_label_uid = uid + 1;
6510 maybe_duplicate_eh_stmt_fn (dest_cfun, stmt, cfun, stmt, d->eh_map, 0);
6511 remove_stmt_from_eh_lp_fn (cfun, stmt);
6513 gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
6514 gimple_remove_stmt_histograms (cfun, stmt);
6516 /* We cannot leave any operands allocated from the operand caches of
6517 the current function. */
6518 free_stmt_operands (stmt);
6519 push_cfun (dest_cfun);
6524 FOR_EACH_EDGE (e, ei, bb->succs)
6525 if (e->goto_locus != UNKNOWN_LOCATION)
6527 tree block = LOCATION_BLOCK (e->goto_locus);
6528 if (d->orig_block == NULL_TREE
6529 || block == d->orig_block)
6530 e->goto_locus = d->new_block ?
6531 COMBINE_LOCATION_DATA (line_table, e->goto_locus, d->new_block) :
6532 LOCATION_LOCUS (e->goto_locus);
6536 /* Examine the statements in BB (which is in SRC_CFUN); find and return
6537 the outermost EH region. Use REGION as the incoming base EH region. */
6540 find_outermost_region_in_block (struct function *src_cfun,
6541 basic_block bb, eh_region region)
6543 gimple_stmt_iterator si;
6545 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6547 gimple stmt = gsi_stmt (si);
6548 eh_region stmt_region;
6551 lp_nr = lookup_stmt_eh_lp_fn (src_cfun, stmt);
6552 stmt_region = get_eh_region_from_lp_number_fn (src_cfun, lp_nr);
6556 region = stmt_region;
6557 else if (stmt_region != region)
6559 region = eh_region_outermost (src_cfun, stmt_region, region);
6560 gcc_assert (region != NULL);
6569 new_label_mapper (tree decl, void *data)
6571 htab_t hash = (htab_t) data;
6575 gcc_assert (TREE_CODE (decl) == LABEL_DECL);
6577 m = XNEW (struct tree_map);
6578 m->hash = DECL_UID (decl);
6579 m->base.from = decl;
6580 m->to = create_artificial_label (UNKNOWN_LOCATION);
6581 LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
6582 if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
6583 cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
6585 slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
6586 gcc_assert (*slot == NULL);
6593 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
6597 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map,
6602 for (tp = &BLOCK_VARS (block); *tp; tp = &DECL_CHAIN (*tp))
6605 if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL)
6607 replace_by_duplicate_decl (&t, vars_map, to_context);
6610 if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
6612 SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
6613 DECL_HAS_VALUE_EXPR_P (t) = 1;
6615 DECL_CHAIN (t) = DECL_CHAIN (*tp);
6620 for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
6621 replace_block_vars_by_duplicates (block, vars_map, to_context);
6624 /* Fixup the loop arrays and numbers after moving LOOP and its subloops
6628 fixup_loop_arrays_after_move (struct function *fn1, struct function *fn2,
6631 /* Discard it from the old loop array. */
6632 (*get_loops (fn1))[loop->num] = NULL;
6634 /* Place it in the new loop array, assigning it a new number. */
6635 loop->num = number_of_loops (fn2);
6636 vec_safe_push (loops_for_fn (fn2)->larray, loop);
6638 /* Recurse to children. */
6639 for (loop = loop->inner; loop; loop = loop->next)
6640 fixup_loop_arrays_after_move (fn1, fn2, loop);
6643 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
6644 EXIT_BB to function DEST_CFUN. The whole region is replaced by a
6645 single basic block in the original CFG and the new basic block is
6646 returned. DEST_CFUN must not have a CFG yet.
6648 Note that the region need not be a pure SESE region. Blocks inside
6649 the region may contain calls to abort/exit. The only restriction
6650 is that ENTRY_BB should be the only entry point and it must
6653 Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
6654 functions outermost BLOCK, move all subblocks of ORIG_BLOCK
6655 to the new function.
6657 All local variables referenced in the region are assumed to be in
6658 the corresponding BLOCK_VARS and unexpanded variable lists
6659 associated with DEST_CFUN. */
6662 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
6663 basic_block exit_bb, tree orig_block)
6665 vec<basic_block> bbs, dom_bbs;
6666 basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
6667 basic_block after, bb, *entry_pred, *exit_succ, abb;
6668 struct function *saved_cfun = cfun;
6669 int *entry_flag, *exit_flag;
6670 unsigned *entry_prob, *exit_prob;
6671 unsigned i, num_entry_edges, num_exit_edges, num_nodes;
6674 htab_t new_label_map;
6675 struct pointer_map_t *vars_map, *eh_map;
6676 struct loop *loop = entry_bb->loop_father;
6677 struct loop *loop0 = get_loop (saved_cfun, 0);
6678 struct move_stmt_d d;
6680 /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
6682 gcc_assert (entry_bb != exit_bb
6684 || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
6686 /* Collect all the blocks in the region. Manually add ENTRY_BB
6687 because it won't be added by dfs_enumerate_from. */
6689 bbs.safe_push (entry_bb);
6690 gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
6692 /* The blocks that used to be dominated by something in BBS will now be
6693 dominated by the new block. */
6694 dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
6698 /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG. We need to remember
6699 the predecessor edges to ENTRY_BB and the successor edges to
6700 EXIT_BB so that we can re-attach them to the new basic block that
6701 will replace the region. */
6702 num_entry_edges = EDGE_COUNT (entry_bb->preds);
6703 entry_pred = XNEWVEC (basic_block, num_entry_edges);
6704 entry_flag = XNEWVEC (int, num_entry_edges);
6705 entry_prob = XNEWVEC (unsigned, num_entry_edges);
6707 for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
6709 entry_prob[i] = e->probability;
6710 entry_flag[i] = e->flags;
6711 entry_pred[i++] = e->src;
6717 num_exit_edges = EDGE_COUNT (exit_bb->succs);
6718 exit_succ = XNEWVEC (basic_block, num_exit_edges);
6719 exit_flag = XNEWVEC (int, num_exit_edges);
6720 exit_prob = XNEWVEC (unsigned, num_exit_edges);
6722 for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6724 exit_prob[i] = e->probability;
6725 exit_flag[i] = e->flags;
6726 exit_succ[i++] = e->dest;
6738 /* Switch context to the child function to initialize DEST_FN's CFG. */
6739 gcc_assert (dest_cfun->cfg == NULL);
6740 push_cfun (dest_cfun);
6742 init_empty_tree_cfg ();
6744 /* Initialize EH information for the new function. */
6746 new_label_map = NULL;
6749 eh_region region = NULL;
6751 FOR_EACH_VEC_ELT (bbs, i, bb)
6752 region = find_outermost_region_in_block (saved_cfun, bb, region);
6754 init_eh_for_function ();
6757 new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6758 eh_map = duplicate_eh_regions (saved_cfun, region, 0,
6759 new_label_mapper, new_label_map);
6763 /* Initialize an empty loop tree. */
6764 struct loops *loops = ggc_alloc_cleared_loops ();
6765 init_loops_structure (dest_cfun, loops, 1);
6766 loops->state = LOOPS_MAY_HAVE_MULTIPLE_LATCHES;
6767 set_loops_for_fn (dest_cfun, loops);
6769 /* Move the outlined loop tree part. */
6770 num_nodes = bbs.length ();
6771 FOR_EACH_VEC_ELT (bbs, i, bb)
6773 if (bb->loop_father->header == bb)
6775 struct loop *this_loop = bb->loop_father;
6776 struct loop *outer = loop_outer (this_loop);
6778 /* If the SESE region contains some bbs ending with
6779 a noreturn call, those are considered to belong
6780 to the outermost loop in saved_cfun, rather than
6781 the entry_bb's loop_father. */
6785 num_nodes -= this_loop->num_nodes;
6786 flow_loop_tree_node_remove (bb->loop_father);
6787 flow_loop_tree_node_add (get_loop (dest_cfun, 0), this_loop);
6788 fixup_loop_arrays_after_move (saved_cfun, cfun, this_loop);
6791 else if (bb->loop_father == loop0 && loop0 != loop)
6794 /* Remove loop exits from the outlined region. */
6795 if (loops_for_fn (saved_cfun)->exits)
6796 FOR_EACH_EDGE (e, ei, bb->succs)
6798 void **slot = htab_find_slot_with_hash
6799 (loops_for_fn (saved_cfun)->exits, e,
6800 htab_hash_pointer (e), NO_INSERT);
6802 htab_clear_slot (loops_for_fn (saved_cfun)->exits, slot);
6807 /* Adjust the number of blocks in the tree root of the outlined part. */
6808 get_loop (dest_cfun, 0)->num_nodes = bbs.length () + 2;
6810 /* Setup a mapping to be used by move_block_to_fn. */
6811 loop->aux = current_loops->tree_root;
6812 loop0->aux = current_loops->tree_root;
6816 /* Move blocks from BBS into DEST_CFUN. */
6817 gcc_assert (bbs.length () >= 2);
6818 after = dest_cfun->cfg->x_entry_block_ptr;
6819 vars_map = pointer_map_create ();
6821 memset (&d, 0, sizeof (d));
6822 d.orig_block = orig_block;
6823 d.new_block = DECL_INITIAL (dest_cfun->decl);
6824 d.from_context = cfun->decl;
6825 d.to_context = dest_cfun->decl;
6826 d.vars_map = vars_map;
6827 d.new_label_map = new_label_map;
6829 d.remap_decls_p = true;
6831 FOR_EACH_VEC_ELT (bbs, i, bb)
6833 /* No need to update edge counts on the last block. It has
6834 already been updated earlier when we detached the region from
6835 the original CFG. */
6836 move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d);
6842 /* Loop sizes are no longer correct, fix them up. */
6843 loop->num_nodes -= num_nodes;
6844 for (struct loop *outer = loop_outer (loop);
6845 outer; outer = loop_outer (outer))
6846 outer->num_nodes -= num_nodes;
6847 loop0->num_nodes -= bbs.length () - num_nodes;
6849 if (saved_cfun->has_simduid_loops || saved_cfun->has_force_vect_loops)
6852 for (i = 0; vec_safe_iterate (loops->larray, i, &aloop); i++)
6857 replace_by_duplicate_decl (&aloop->simduid, d.vars_map,
6859 dest_cfun->has_simduid_loops = true;
6861 if (aloop->force_vect)
6862 dest_cfun->has_force_vect_loops = true;
6866 /* Rewire BLOCK_SUBBLOCKS of orig_block. */
6870 gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6872 BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6873 = BLOCK_SUBBLOCKS (orig_block);
6874 for (block = BLOCK_SUBBLOCKS (orig_block);
6875 block; block = BLOCK_CHAIN (block))
6876 BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
6877 BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
6880 replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
6881 vars_map, dest_cfun->decl);
6884 htab_delete (new_label_map);
6886 pointer_map_destroy (eh_map);
6887 pointer_map_destroy (vars_map);
6889 /* Rewire the entry and exit blocks. The successor to the entry
6890 block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6891 the child function. Similarly, the predecessor of DEST_FN's
6892 EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR. We
6893 need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6894 various CFG manipulation function get to the right CFG.
6896 FIXME, this is silly. The CFG ought to become a parameter to
6898 push_cfun (dest_cfun);
6899 make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6901 make_edge (exit_bb, EXIT_BLOCK_PTR, 0);
6904 /* Back in the original function, the SESE region has disappeared,
6905 create a new basic block in its place. */
6906 bb = create_empty_bb (entry_pred[0]);
6908 add_bb_to_loop (bb, loop);
6909 for (i = 0; i < num_entry_edges; i++)
6911 e = make_edge (entry_pred[i], bb, entry_flag[i]);
6912 e->probability = entry_prob[i];
6915 for (i = 0; i < num_exit_edges; i++)
6917 e = make_edge (bb, exit_succ[i], exit_flag[i]);
6918 e->probability = exit_prob[i];
6921 set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6922 FOR_EACH_VEC_ELT (dom_bbs, i, abb)
6923 set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6941 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in dumpfile.h)
6945 dump_function_to_file (tree fndecl, FILE *file, int flags)
6947 tree arg, var, old_current_fndecl = current_function_decl;
6948 struct function *dsf;
6949 bool ignore_topmost_bind = false, any_var = false;
6952 bool tmclone = (TREE_CODE (fndecl) == FUNCTION_DECL
6953 && decl_is_tm_clone (fndecl));
6954 struct function *fun = DECL_STRUCT_FUNCTION (fndecl);
6956 current_function_decl = fndecl;
6957 fprintf (file, "%s %s(", function_name (fun), tmclone ? "[tm-clone] " : "");
6959 arg = DECL_ARGUMENTS (fndecl);
6962 print_generic_expr (file, TREE_TYPE (arg), dump_flags);
6963 fprintf (file, " ");
6964 print_generic_expr (file, arg, dump_flags);
6965 if (flags & TDF_VERBOSE)
6966 print_node (file, "", arg, 4);
6967 if (DECL_CHAIN (arg))
6968 fprintf (file, ", ");
6969 arg = DECL_CHAIN (arg);
6971 fprintf (file, ")\n");
6973 if (flags & TDF_VERBOSE)
6974 print_node (file, "", fndecl, 2);
6976 dsf = DECL_STRUCT_FUNCTION (fndecl);
6977 if (dsf && (flags & TDF_EH))
6978 dump_eh_tree (file, dsf);
6980 if (flags & TDF_RAW && !gimple_has_body_p (fndecl))
6982 dump_node (fndecl, TDF_SLIM | flags, file);
6983 current_function_decl = old_current_fndecl;
6987 /* When GIMPLE is lowered, the variables are no longer available in
6988 BIND_EXPRs, so display them separately. */
6989 if (fun && fun->decl == fndecl && (fun->curr_properties & PROP_gimple_lcf))
6992 ignore_topmost_bind = true;
6994 fprintf (file, "{\n");
6995 if (!vec_safe_is_empty (fun->local_decls))
6996 FOR_EACH_LOCAL_DECL (fun, ix, var)
6998 print_generic_decl (file, var, flags);
6999 if (flags & TDF_VERBOSE)
7000 print_node (file, "", var, 4);
7001 fprintf (file, "\n");
7005 if (gimple_in_ssa_p (cfun))
7006 for (ix = 1; ix < num_ssa_names; ++ix)
7008 tree name = ssa_name (ix);
7009 if (name && !SSA_NAME_VAR (name))
7011 fprintf (file, " ");
7012 print_generic_expr (file, TREE_TYPE (name), flags);
7013 fprintf (file, " ");
7014 print_generic_expr (file, name, flags);
7015 fprintf (file, ";\n");
7022 if (fun && fun->decl == fndecl
7024 && basic_block_info_for_function (fun))
7026 /* If the CFG has been built, emit a CFG-based dump. */
7027 if (!ignore_topmost_bind)
7028 fprintf (file, "{\n");
7030 if (any_var && n_basic_blocks_for_function (fun))
7031 fprintf (file, "\n");
7033 FOR_EACH_BB_FN (bb, fun)
7034 dump_bb (file, bb, 2, flags | TDF_COMMENT);
7036 fprintf (file, "}\n");
7038 else if (DECL_SAVED_TREE (fndecl) == NULL)
7040 /* The function is now in GIMPLE form but the CFG has not been
7041 built yet. Emit the single sequence of GIMPLE statements
7042 that make up its body. */
7043 gimple_seq body = gimple_body (fndecl);
7045 if (gimple_seq_first_stmt (body)
7046 && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
7047 && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
7048 print_gimple_seq (file, body, 0, flags);
7051 if (!ignore_topmost_bind)
7052 fprintf (file, "{\n");
7055 fprintf (file, "\n");
7057 print_gimple_seq (file, body, 2, flags);
7058 fprintf (file, "}\n");
7065 /* Make a tree based dump. */
7066 chain = DECL_SAVED_TREE (fndecl);
7067 if (chain && TREE_CODE (chain) == BIND_EXPR)
7069 if (ignore_topmost_bind)
7071 chain = BIND_EXPR_BODY (chain);
7079 if (!ignore_topmost_bind)
7080 fprintf (file, "{\n");
7085 fprintf (file, "\n");
7087 print_generic_stmt_indented (file, chain, flags, indent);
7088 if (ignore_topmost_bind)
7089 fprintf (file, "}\n");
7092 if (flags & TDF_ENUMERATE_LOCALS)
7093 dump_enumerated_decls (file, flags);
7094 fprintf (file, "\n\n");
7096 current_function_decl = old_current_fndecl;
7099 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h) */
7102 debug_function (tree fn, int flags)
7104 dump_function_to_file (fn, stderr, flags);
7108 /* Print on FILE the indexes for the predecessors of basic_block BB. */
7111 print_pred_bbs (FILE *file, basic_block bb)
7116 FOR_EACH_EDGE (e, ei, bb->preds)
7117 fprintf (file, "bb_%d ", e->src->index);
7121 /* Print on FILE the indexes for the successors of basic_block BB. */
7124 print_succ_bbs (FILE *file, basic_block bb)
7129 FOR_EACH_EDGE (e, ei, bb->succs)
7130 fprintf (file, "bb_%d ", e->dest->index);
7133 /* Print to FILE the basic block BB following the VERBOSITY level. */
7136 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
7138 char *s_indent = (char *) alloca ((size_t) indent + 1);
7139 memset ((void *) s_indent, ' ', (size_t) indent);
7140 s_indent[indent] = '\0';
7142 /* Print basic_block's header. */
7145 fprintf (file, "%s bb_%d (preds = {", s_indent, bb->index);
7146 print_pred_bbs (file, bb);
7147 fprintf (file, "}, succs = {");
7148 print_succ_bbs (file, bb);
7149 fprintf (file, "})\n");
7152 /* Print basic_block's body. */
7155 fprintf (file, "%s {\n", s_indent);
7156 dump_bb (file, bb, indent + 4, TDF_VOPS|TDF_MEMSYMS);
7157 fprintf (file, "%s }\n", s_indent);
7161 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
7163 /* Pretty print LOOP on FILE, indented INDENT spaces. Following
7164 VERBOSITY level this outputs the contents of the loop, or just its
7168 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
7176 s_indent = (char *) alloca ((size_t) indent + 1);
7177 memset ((void *) s_indent, ' ', (size_t) indent);
7178 s_indent[indent] = '\0';
7180 /* Print loop's header. */
7181 fprintf (file, "%sloop_%d (", s_indent, loop->num);
7183 fprintf (file, "header = %d", loop->header->index);
7186 fprintf (file, "deleted)\n");
7190 fprintf (file, ", latch = %d", loop->latch->index);
7192 fprintf (file, ", multiple latches");
7193 fprintf (file, ", niter = ");
7194 print_generic_expr (file, loop->nb_iterations, 0);
7196 if (loop->any_upper_bound)
7198 fprintf (file, ", upper_bound = ");
7199 dump_double_int (file, loop->nb_iterations_upper_bound, true);
7202 if (loop->any_estimate)
7204 fprintf (file, ", estimate = ");
7205 dump_double_int (file, loop->nb_iterations_estimate, true);
7207 fprintf (file, ")\n");
7209 /* Print loop's body. */
7212 fprintf (file, "%s{\n", s_indent);
7214 if (bb->loop_father == loop)
7215 print_loops_bb (file, bb, indent, verbosity);
7217 print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
7218 fprintf (file, "%s}\n", s_indent);
7222 /* Print the LOOP and its sibling loops on FILE, indented INDENT
7223 spaces. Following VERBOSITY level this outputs the contents of the
7224 loop, or just its structure. */
7227 print_loop_and_siblings (FILE *file, struct loop *loop, int indent,
7233 print_loop (file, loop, indent, verbosity);
7234 print_loop_and_siblings (file, loop->next, indent, verbosity);
7237 /* Follow a CFG edge from the entry point of the program, and on entry
7238 of a loop, pretty print the loop structure on FILE. */
7241 print_loops (FILE *file, int verbosity)
7245 bb = ENTRY_BLOCK_PTR;
7246 if (bb && bb->loop_father)
7247 print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
7253 debug (struct loop &ref)
7255 print_loop (stderr, &ref, 0, /*verbosity*/0);
7259 debug (struct loop *ptr)
7264 fprintf (stderr, "<nil>\n");
7267 /* Dump a loop verbosely. */
7270 debug_verbose (struct loop &ref)
7272 print_loop (stderr, &ref, 0, /*verbosity*/3);
7276 debug_verbose (struct loop *ptr)
7281 fprintf (stderr, "<nil>\n");
7285 /* Debugging loops structure at tree level, at some VERBOSITY level. */
7288 debug_loops (int verbosity)
7290 print_loops (stderr, verbosity);
7293 /* Print on stderr the code of LOOP, at some VERBOSITY level. */
7296 debug_loop (struct loop *loop, int verbosity)
7298 print_loop (stderr, loop, 0, verbosity);
7301 /* Print on stderr the code of loop number NUM, at some VERBOSITY
7305 debug_loop_num (unsigned num, int verbosity)
7307 debug_loop (get_loop (cfun, num), verbosity);
7310 /* Return true if BB ends with a call, possibly followed by some
7311 instructions that must stay with the call. Return false,
7315 gimple_block_ends_with_call_p (basic_block bb)
7317 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
7318 return !gsi_end_p (gsi) && is_gimple_call (gsi_stmt (gsi));
7322 /* Return true if BB ends with a conditional branch. Return false,
7326 gimple_block_ends_with_condjump_p (const_basic_block bb)
7328 gimple stmt = last_stmt (CONST_CAST_BB (bb));
7329 return (stmt && gimple_code (stmt) == GIMPLE_COND);
7333 /* Return true if we need to add fake edge to exit at statement T.
7334 Helper function for gimple_flow_call_edges_add. */
7337 need_fake_edge_p (gimple t)
7339 tree fndecl = NULL_TREE;
7342 /* NORETURN and LONGJMP calls already have an edge to exit.
7343 CONST and PURE calls do not need one.
7344 We don't currently check for CONST and PURE here, although
7345 it would be a good idea, because those attributes are
7346 figured out from the RTL in mark_constant_function, and
7347 the counter incrementation code from -fprofile-arcs
7348 leads to different results from -fbranch-probabilities. */
7349 if (is_gimple_call (t))
7351 fndecl = gimple_call_fndecl (t);
7352 call_flags = gimple_call_flags (t);
7355 if (is_gimple_call (t)
7357 && DECL_BUILT_IN (fndecl)
7358 && (call_flags & ECF_NOTHROW)
7359 && !(call_flags & ECF_RETURNS_TWICE)
7360 /* fork() doesn't really return twice, but the effect of
7361 wrapping it in __gcov_fork() which calls __gcov_flush()
7362 and clears the counters before forking has the same
7363 effect as returning twice. Force a fake edge. */
7364 && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
7365 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK))
7368 if (is_gimple_call (t))
7374 if (!(call_flags & ECF_NORETURN))
7378 FOR_EACH_EDGE (e, ei, bb->succs)
7379 if ((e->flags & EDGE_FAKE) == 0)
7383 if (gimple_code (t) == GIMPLE_ASM
7384 && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
7391 /* Add fake edges to the function exit for any non constant and non
7392 noreturn calls (or noreturn calls with EH/abnormal edges),
7393 volatile inline assembly in the bitmap of blocks specified by BLOCKS
7394 or to the whole CFG if BLOCKS is zero. Return the number of blocks
7397 The goal is to expose cases in which entering a basic block does
7398 not imply that all subsequent instructions must be executed. */
7401 gimple_flow_call_edges_add (sbitmap blocks)
7404 int blocks_split = 0;
7405 int last_bb = last_basic_block;
7406 bool check_last_block = false;
7408 if (n_basic_blocks == NUM_FIXED_BLOCKS)
7412 check_last_block = true;
7414 check_last_block = bitmap_bit_p (blocks, EXIT_BLOCK_PTR->prev_bb->index);
7416 /* In the last basic block, before epilogue generation, there will be
7417 a fallthru edge to EXIT. Special care is required if the last insn
7418 of the last basic block is a call because make_edge folds duplicate
7419 edges, which would result in the fallthru edge also being marked
7420 fake, which would result in the fallthru edge being removed by
7421 remove_fake_edges, which would result in an invalid CFG.
7423 Moreover, we can't elide the outgoing fake edge, since the block
7424 profiler needs to take this into account in order to solve the minimal
7425 spanning tree in the case that the call doesn't return.
7427 Handle this by adding a dummy instruction in a new last basic block. */
7428 if (check_last_block)
7430 basic_block bb = EXIT_BLOCK_PTR->prev_bb;
7431 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
7434 if (!gsi_end_p (gsi))
7437 if (t && need_fake_edge_p (t))
7441 e = find_edge (bb, EXIT_BLOCK_PTR);
7444 gsi_insert_on_edge (e, gimple_build_nop ());
7445 gsi_commit_edge_inserts ();
7450 /* Now add fake edges to the function exit for any non constant
7451 calls since there is no way that we can determine if they will
7453 for (i = 0; i < last_bb; i++)
7455 basic_block bb = BASIC_BLOCK (i);
7456 gimple_stmt_iterator gsi;
7457 gimple stmt, last_stmt;
7462 if (blocks && !bitmap_bit_p (blocks, i))
7465 gsi = gsi_last_nondebug_bb (bb);
7466 if (!gsi_end_p (gsi))
7468 last_stmt = gsi_stmt (gsi);
7471 stmt = gsi_stmt (gsi);
7472 if (need_fake_edge_p (stmt))
7476 /* The handling above of the final block before the
7477 epilogue should be enough to verify that there is
7478 no edge to the exit block in CFG already.
7479 Calling make_edge in such case would cause us to
7480 mark that edge as fake and remove it later. */
7481 #ifdef ENABLE_CHECKING
7482 if (stmt == last_stmt)
7484 e = find_edge (bb, EXIT_BLOCK_PTR);
7485 gcc_assert (e == NULL);
7489 /* Note that the following may create a new basic block
7490 and renumber the existing basic blocks. */
7491 if (stmt != last_stmt)
7493 e = split_block (bb, stmt);
7497 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
7501 while (!gsi_end_p (gsi));
7506 verify_flow_info ();
7508 return blocks_split;
7511 /* Removes edge E and all the blocks dominated by it, and updates dominance
7512 information. The IL in E->src needs to be updated separately.
7513 If dominance info is not available, only the edge E is removed.*/
7516 remove_edge_and_dominated_blocks (edge e)
7518 vec<basic_block> bbs_to_remove = vNULL;
7519 vec<basic_block> bbs_to_fix_dom = vNULL;
7523 bool none_removed = false;
7525 basic_block bb, dbb;
7528 if (!dom_info_available_p (CDI_DOMINATORS))
7534 /* No updating is needed for edges to exit. */
7535 if (e->dest == EXIT_BLOCK_PTR)
7537 if (cfgcleanup_altered_bbs)
7538 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7543 /* First, we find the basic blocks to remove. If E->dest has a predecessor
7544 that is not dominated by E->dest, then this set is empty. Otherwise,
7545 all the basic blocks dominated by E->dest are removed.
7547 Also, to DF_IDOM we store the immediate dominators of the blocks in
7548 the dominance frontier of E (i.e., of the successors of the
7549 removed blocks, if there are any, and of E->dest otherwise). */
7550 FOR_EACH_EDGE (f, ei, e->dest->preds)
7555 if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
7557 none_removed = true;
7562 df = BITMAP_ALLOC (NULL);
7563 df_idom = BITMAP_ALLOC (NULL);
7566 bitmap_set_bit (df_idom,
7567 get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
7570 bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest);
7571 FOR_EACH_VEC_ELT (bbs_to_remove, i, bb)
7573 FOR_EACH_EDGE (f, ei, bb->succs)
7575 if (f->dest != EXIT_BLOCK_PTR)
7576 bitmap_set_bit (df, f->dest->index);
7579 FOR_EACH_VEC_ELT (bbs_to_remove, i, bb)
7580 bitmap_clear_bit (df, bb->index);
7582 EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
7584 bb = BASIC_BLOCK (i);
7585 bitmap_set_bit (df_idom,
7586 get_immediate_dominator (CDI_DOMINATORS, bb)->index);
7590 if (cfgcleanup_altered_bbs)
7592 /* Record the set of the altered basic blocks. */
7593 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7594 bitmap_ior_into (cfgcleanup_altered_bbs, df);
7597 /* Remove E and the cancelled blocks. */
7602 /* Walk backwards so as to get a chance to substitute all
7603 released DEFs into debug stmts. See
7604 eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
7606 for (i = bbs_to_remove.length (); i-- > 0; )
7607 delete_basic_block (bbs_to_remove[i]);
7610 /* Update the dominance information. The immediate dominator may change only
7611 for blocks whose immediate dominator belongs to DF_IDOM:
7613 Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
7614 removal. Let Z the arbitrary block such that idom(Z) = Y and
7615 Z dominates X after the removal. Before removal, there exists a path P
7616 from Y to X that avoids Z. Let F be the last edge on P that is
7617 removed, and let W = F->dest. Before removal, idom(W) = Y (since Y
7618 dominates W, and because of P, Z does not dominate W), and W belongs to
7619 the dominance frontier of E. Therefore, Y belongs to DF_IDOM. */
7620 EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
7622 bb = BASIC_BLOCK (i);
7623 for (dbb = first_dom_son (CDI_DOMINATORS, bb);
7625 dbb = next_dom_son (CDI_DOMINATORS, dbb))
7626 bbs_to_fix_dom.safe_push (dbb);
7629 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
7632 BITMAP_FREE (df_idom);
7633 bbs_to_remove.release ();
7634 bbs_to_fix_dom.release ();
7637 /* Purge dead EH edges from basic block BB. */
7640 gimple_purge_dead_eh_edges (basic_block bb)
7642 bool changed = false;
7645 gimple stmt = last_stmt (bb);
7647 if (stmt && stmt_can_throw_internal (stmt))
7650 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7652 if (e->flags & EDGE_EH)
7654 remove_edge_and_dominated_blocks (e);
7664 /* Purge dead EH edges from basic block listed in BLOCKS. */
7667 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
7669 bool changed = false;
7673 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7675 basic_block bb = BASIC_BLOCK (i);
7677 /* Earlier gimple_purge_dead_eh_edges could have removed
7678 this basic block already. */
7679 gcc_assert (bb || changed);
7681 changed |= gimple_purge_dead_eh_edges (bb);
7687 /* Purge dead abnormal call edges from basic block BB. */
7690 gimple_purge_dead_abnormal_call_edges (basic_block bb)
7692 bool changed = false;
7695 gimple stmt = last_stmt (bb);
7697 if (!cfun->has_nonlocal_label
7698 && !cfun->calls_setjmp)
7701 if (stmt && stmt_can_make_abnormal_goto (stmt))
7704 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7706 if (e->flags & EDGE_ABNORMAL)
7708 if (e->flags & EDGE_FALLTHRU)
7709 e->flags &= ~EDGE_ABNORMAL;
7711 remove_edge_and_dominated_blocks (e);
7721 /* Purge dead abnormal call edges from basic block listed in BLOCKS. */
7724 gimple_purge_all_dead_abnormal_call_edges (const_bitmap blocks)
7726 bool changed = false;
7730 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7732 basic_block bb = BASIC_BLOCK (i);
7734 /* Earlier gimple_purge_dead_abnormal_call_edges could have removed
7735 this basic block already. */
7736 gcc_assert (bb || changed);
7738 changed |= gimple_purge_dead_abnormal_call_edges (bb);
7744 /* This function is called whenever a new edge is created or
7748 gimple_execute_on_growing_pred (edge e)
7750 basic_block bb = e->dest;
7752 if (!gimple_seq_empty_p (phi_nodes (bb)))
7753 reserve_phi_args_for_new_edge (bb);
7756 /* This function is called immediately before edge E is removed from
7757 the edge vector E->dest->preds. */
7760 gimple_execute_on_shrinking_pred (edge e)
7762 if (!gimple_seq_empty_p (phi_nodes (e->dest)))
7763 remove_phi_args (e);
7766 /*---------------------------------------------------------------------------
7767 Helper functions for Loop versioning
7768 ---------------------------------------------------------------------------*/
7770 /* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy
7771 of 'first'. Both of them are dominated by 'new_head' basic block. When
7772 'new_head' was created by 'second's incoming edge it received phi arguments
7773 on the edge by split_edge(). Later, additional edge 'e' was created to
7774 connect 'new_head' and 'first'. Now this routine adds phi args on this
7775 additional edge 'e' that new_head to second edge received as part of edge
7779 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
7780 basic_block new_head, edge e)
7783 gimple_stmt_iterator psi1, psi2;
7785 edge e2 = find_edge (new_head, second);
7787 /* Because NEW_HEAD has been created by splitting SECOND's incoming
7788 edge, we should always have an edge from NEW_HEAD to SECOND. */
7789 gcc_assert (e2 != NULL);
7791 /* Browse all 'second' basic block phi nodes and add phi args to
7792 edge 'e' for 'first' head. PHI args are always in correct order. */
7794 for (psi2 = gsi_start_phis (second),
7795 psi1 = gsi_start_phis (first);
7796 !gsi_end_p (psi2) && !gsi_end_p (psi1);
7797 gsi_next (&psi2), gsi_next (&psi1))
7799 phi1 = gsi_stmt (psi1);
7800 phi2 = gsi_stmt (psi2);
7801 def = PHI_ARG_DEF (phi2, e2->dest_idx);
7802 add_phi_arg (phi1, def, e, gimple_phi_arg_location_from_edge (phi2, e2));
7807 /* Adds a if else statement to COND_BB with condition COND_EXPR.
7808 SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
7809 the destination of the ELSE part. */
7812 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
7813 basic_block second_head ATTRIBUTE_UNUSED,
7814 basic_block cond_bb, void *cond_e)
7816 gimple_stmt_iterator gsi;
7817 gimple new_cond_expr;
7818 tree cond_expr = (tree) cond_e;
7821 /* Build new conditional expr */
7822 new_cond_expr = gimple_build_cond_from_tree (cond_expr,
7823 NULL_TREE, NULL_TREE);
7825 /* Add new cond in cond_bb. */
7826 gsi = gsi_last_bb (cond_bb);
7827 gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
7829 /* Adjust edges appropriately to connect new head with first head
7830 as well as second head. */
7831 e0 = single_succ_edge (cond_bb);
7832 e0->flags &= ~EDGE_FALLTHRU;
7833 e0->flags |= EDGE_FALSE_VALUE;
7837 /* Do book-keeping of basic block BB for the profile consistency checker.
7838 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
7839 then do post-pass accounting. Store the counting in RECORD. */
7841 gimple_account_profile_record (basic_block bb, int after_pass,
7842 struct profile_record *record)
7844 gimple_stmt_iterator i;
7845 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
7847 record->size[after_pass]
7848 += estimate_num_insns (gsi_stmt (i), &eni_size_weights);
7849 if (profile_status == PROFILE_READ)
7850 record->time[after_pass]
7851 += estimate_num_insns (gsi_stmt (i),
7852 &eni_time_weights) * bb->count;
7853 else if (profile_status == PROFILE_GUESSED)
7854 record->time[after_pass]
7855 += estimate_num_insns (gsi_stmt (i),
7856 &eni_time_weights) * bb->frequency;
7860 struct cfg_hooks gimple_cfg_hooks = {
7862 gimple_verify_flow_info,
7863 gimple_dump_bb, /* dump_bb */
7864 gimple_dump_bb_for_graph, /* dump_bb_for_graph */
7865 create_bb, /* create_basic_block */
7866 gimple_redirect_edge_and_branch, /* redirect_edge_and_branch */
7867 gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force */
7868 gimple_can_remove_branch_p, /* can_remove_branch_p */
7869 remove_bb, /* delete_basic_block */
7870 gimple_split_block, /* split_block */
7871 gimple_move_block_after, /* move_block_after */
7872 gimple_can_merge_blocks_p, /* can_merge_blocks_p */
7873 gimple_merge_blocks, /* merge_blocks */
7874 gimple_predict_edge, /* predict_edge */
7875 gimple_predicted_by_p, /* predicted_by_p */
7876 gimple_can_duplicate_bb_p, /* can_duplicate_block_p */
7877 gimple_duplicate_bb, /* duplicate_block */
7878 gimple_split_edge, /* split_edge */
7879 gimple_make_forwarder_block, /* make_forward_block */
7880 NULL, /* tidy_fallthru_edge */
7881 NULL, /* force_nonfallthru */
7882 gimple_block_ends_with_call_p,/* block_ends_with_call_p */
7883 gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
7884 gimple_flow_call_edges_add, /* flow_call_edges_add */
7885 gimple_execute_on_growing_pred, /* execute_on_growing_pred */
7886 gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
7887 gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
7888 gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
7889 gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
7890 extract_true_false_edges_from_block, /* extract_cond_bb_edges */
7891 flush_pending_stmts, /* flush_pending_stmts */
7892 gimple_empty_block_p, /* block_empty_p */
7893 gimple_split_block_before_cond_jump, /* split_block_before_cond_jump */
7894 gimple_account_profile_record,
7898 /* Split all critical edges. */
7901 split_critical_edges (void)
7907 /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
7908 expensive. So we want to enable recording of edge to CASE_LABEL_EXPR
7909 mappings around the calls to split_edge. */
7910 start_recording_case_labels ();
7913 FOR_EACH_EDGE (e, ei, bb->succs)
7915 if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
7917 /* PRE inserts statements to edges and expects that
7918 since split_critical_edges was done beforehand, committing edge
7919 insertions will not split more edges. In addition to critical
7920 edges we must split edges that have multiple successors and
7921 end by control flow statements, such as RESX.
7922 Go ahead and split them too. This matches the logic in
7923 gimple_find_edge_insert_loc. */
7924 else if ((!single_pred_p (e->dest)
7925 || !gimple_seq_empty_p (phi_nodes (e->dest))
7926 || e->dest == EXIT_BLOCK_PTR)
7927 && e->src != ENTRY_BLOCK_PTR
7928 && !(e->flags & EDGE_ABNORMAL))
7930 gimple_stmt_iterator gsi;
7932 gsi = gsi_last_bb (e->src);
7933 if (!gsi_end_p (gsi)
7934 && stmt_ends_bb_p (gsi_stmt (gsi))
7935 && (gimple_code (gsi_stmt (gsi)) != GIMPLE_RETURN
7936 && !gimple_call_builtin_p (gsi_stmt (gsi),
7942 end_recording_case_labels ();
7948 const pass_data pass_data_split_crit_edges =
7950 GIMPLE_PASS, /* type */
7951 "crited", /* name */
7952 OPTGROUP_NONE, /* optinfo_flags */
7953 false, /* has_gate */
7954 true, /* has_execute */
7955 TV_TREE_SPLIT_EDGES, /* tv_id */
7956 PROP_cfg, /* properties_required */
7957 PROP_no_crit_edges, /* properties_provided */
7958 0, /* properties_destroyed */
7959 0, /* todo_flags_start */
7960 TODO_verify_flow, /* todo_flags_finish */
7963 class pass_split_crit_edges : public gimple_opt_pass
7966 pass_split_crit_edges (gcc::context *ctxt)
7967 : gimple_opt_pass (pass_data_split_crit_edges, ctxt)
7970 /* opt_pass methods: */
7971 unsigned int execute () { return split_critical_edges (); }
7973 opt_pass * clone () { return new pass_split_crit_edges (m_ctxt); }
7974 }; // class pass_split_crit_edges
7979 make_pass_split_crit_edges (gcc::context *ctxt)
7981 return new pass_split_crit_edges (ctxt);
7985 /* Build a ternary operation and gimplify it. Emit code before GSI.
7986 Return the gimple_val holding the result. */
7989 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
7990 tree type, tree a, tree b, tree c)
7993 location_t loc = gimple_location (gsi_stmt (*gsi));
7995 ret = fold_build3_loc (loc, code, type, a, b, c);
7998 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
8002 /* Build a binary operation and gimplify it. Emit code before GSI.
8003 Return the gimple_val holding the result. */
8006 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
8007 tree type, tree a, tree b)
8011 ret = fold_build2_loc (gimple_location (gsi_stmt (*gsi)), code, type, a, b);
8014 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
8018 /* Build a unary operation and gimplify it. Emit code before GSI.
8019 Return the gimple_val holding the result. */
8022 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
8027 ret = fold_build1_loc (gimple_location (gsi_stmt (*gsi)), code, type, a);
8030 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
8036 /* Emit return warnings. */
8039 execute_warn_function_return (void)
8041 source_location location;
8046 if (!targetm.warn_func_return (cfun->decl))
8049 /* If we have a path to EXIT, then we do return. */
8050 if (TREE_THIS_VOLATILE (cfun->decl)
8051 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
8053 location = UNKNOWN_LOCATION;
8054 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
8056 last = last_stmt (e->src);
8057 if ((gimple_code (last) == GIMPLE_RETURN
8058 || gimple_call_builtin_p (last, BUILT_IN_RETURN))
8059 && (location = gimple_location (last)) != UNKNOWN_LOCATION)
8062 if (location == UNKNOWN_LOCATION)
8063 location = cfun->function_end_locus;
8064 warning_at (location, 0, "%<noreturn%> function does return");
8067 /* If we see "return;" in some basic block, then we do reach the end
8068 without returning a value. */
8069 else if (warn_return_type
8070 && !TREE_NO_WARNING (cfun->decl)
8071 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
8072 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
8074 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
8076 gimple last = last_stmt (e->src);
8077 if (gimple_code (last) == GIMPLE_RETURN
8078 && gimple_return_retval (last) == NULL
8079 && !gimple_no_warning_p (last))
8081 location = gimple_location (last);
8082 if (location == UNKNOWN_LOCATION)
8083 location = cfun->function_end_locus;
8084 warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
8085 TREE_NO_WARNING (cfun->decl) = 1;
8094 /* Given a basic block B which ends with a conditional and has
8095 precisely two successors, determine which of the edges is taken if
8096 the conditional is true and which is taken if the conditional is
8097 false. Set TRUE_EDGE and FALSE_EDGE appropriately. */
8100 extract_true_false_edges_from_block (basic_block b,
8104 edge e = EDGE_SUCC (b, 0);
8106 if (e->flags & EDGE_TRUE_VALUE)
8109 *false_edge = EDGE_SUCC (b, 1);
8114 *true_edge = EDGE_SUCC (b, 1);
8120 const pass_data pass_data_warn_function_return =
8122 GIMPLE_PASS, /* type */
8123 "*warn_function_return", /* name */
8124 OPTGROUP_NONE, /* optinfo_flags */
8125 false, /* has_gate */
8126 true, /* has_execute */
8127 TV_NONE, /* tv_id */
8128 PROP_cfg, /* properties_required */
8129 0, /* properties_provided */
8130 0, /* properties_destroyed */
8131 0, /* todo_flags_start */
8132 0, /* todo_flags_finish */
8135 class pass_warn_function_return : public gimple_opt_pass
8138 pass_warn_function_return (gcc::context *ctxt)
8139 : gimple_opt_pass (pass_data_warn_function_return, ctxt)
8142 /* opt_pass methods: */
8143 unsigned int execute () { return execute_warn_function_return (); }
8145 }; // class pass_warn_function_return
8150 make_pass_warn_function_return (gcc::context *ctxt)
8152 return new pass_warn_function_return (ctxt);
8155 /* Walk a gimplified function and warn for functions whose return value is
8156 ignored and attribute((warn_unused_result)) is set. This is done before
8157 inlining, so we don't have to worry about that. */
8160 do_warn_unused_result (gimple_seq seq)
8163 gimple_stmt_iterator i;
8165 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
8167 gimple g = gsi_stmt (i);
8169 switch (gimple_code (g))
8172 do_warn_unused_result (gimple_bind_body (g));
8175 do_warn_unused_result (gimple_try_eval (g));
8176 do_warn_unused_result (gimple_try_cleanup (g));
8179 do_warn_unused_result (gimple_catch_handler (g));
8181 case GIMPLE_EH_FILTER:
8182 do_warn_unused_result (gimple_eh_filter_failure (g));
8186 if (gimple_call_lhs (g))
8188 if (gimple_call_internal_p (g))
8191 /* This is a naked call, as opposed to a GIMPLE_CALL with an
8192 LHS. All calls whose value is ignored should be
8193 represented like this. Look for the attribute. */
8194 fdecl = gimple_call_fndecl (g);
8195 ftype = gimple_call_fntype (g);
8197 if (lookup_attribute ("warn_unused_result", TYPE_ATTRIBUTES (ftype)))
8199 location_t loc = gimple_location (g);
8202 warning_at (loc, OPT_Wunused_result,
8203 "ignoring return value of %qD, "
8204 "declared with attribute warn_unused_result",
8207 warning_at (loc, OPT_Wunused_result,
8208 "ignoring return value of function "
8209 "declared with attribute warn_unused_result");
8214 /* Not a container, not a call, or a call whose value is used. */
8221 run_warn_unused_result (void)
8223 do_warn_unused_result (gimple_body (current_function_decl));
8228 gate_warn_unused_result (void)
8230 return flag_warn_unused_result;
8235 const pass_data pass_data_warn_unused_result =
8237 GIMPLE_PASS, /* type */
8238 "*warn_unused_result", /* name */
8239 OPTGROUP_NONE, /* optinfo_flags */
8240 true, /* has_gate */
8241 true, /* has_execute */
8242 TV_NONE, /* tv_id */
8243 PROP_gimple_any, /* properties_required */
8244 0, /* properties_provided */
8245 0, /* properties_destroyed */
8246 0, /* todo_flags_start */
8247 0, /* todo_flags_finish */
8250 class pass_warn_unused_result : public gimple_opt_pass
8253 pass_warn_unused_result (gcc::context *ctxt)
8254 : gimple_opt_pass (pass_data_warn_unused_result, ctxt)
8257 /* opt_pass methods: */
8258 bool gate () { return gate_warn_unused_result (); }
8259 unsigned int execute () { return run_warn_unused_result (); }
8261 }; // class pass_warn_unused_result
8266 make_pass_warn_unused_result (gcc::context *ctxt)
8268 return new pass_warn_unused_result (ctxt);
8271 /* IPA passes, compilation of earlier functions or inlining
8272 might have changed some properties, such as marked functions nothrow,
8273 pure, const or noreturn.
8274 Remove redundant edges and basic blocks, and create new ones if necessary.
8276 This pass can't be executed as stand alone pass from pass manager, because
8277 in between inlining and this fixup the verify_flow_info would fail. */
8280 execute_fixup_cfg (void)
8283 gimple_stmt_iterator gsi;
8284 int todo = gimple_in_ssa_p (cfun) ? TODO_verify_ssa : 0;
8285 gcov_type count_scale;
8290 = GCOV_COMPUTE_SCALE (cgraph_get_node (current_function_decl)->count,
8291 ENTRY_BLOCK_PTR->count);
8293 ENTRY_BLOCK_PTR->count = cgraph_get_node (current_function_decl)->count;
8294 EXIT_BLOCK_PTR->count = apply_scale (EXIT_BLOCK_PTR->count,
8297 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
8298 e->count = apply_scale (e->count, count_scale);
8302 bb->count = apply_scale (bb->count, count_scale);
8303 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
8305 gimple stmt = gsi_stmt (gsi);
8306 tree decl = is_gimple_call (stmt)
8307 ? gimple_call_fndecl (stmt)
8311 int flags = gimple_call_flags (stmt);
8312 if (flags & (ECF_CONST | ECF_PURE | ECF_LOOPING_CONST_OR_PURE))
8314 if (gimple_purge_dead_abnormal_call_edges (bb))
8315 todo |= TODO_cleanup_cfg;
8317 if (gimple_in_ssa_p (cfun))
8319 todo |= TODO_update_ssa | TODO_cleanup_cfg;
8324 if (flags & ECF_NORETURN
8325 && fixup_noreturn_call (stmt))
8326 todo |= TODO_cleanup_cfg;
8329 if (maybe_clean_eh_stmt (stmt)
8330 && gimple_purge_dead_eh_edges (bb))
8331 todo |= TODO_cleanup_cfg;
8334 FOR_EACH_EDGE (e, ei, bb->succs)
8335 e->count = apply_scale (e->count, count_scale);
8337 /* If we have a basic block with no successors that does not
8338 end with a control statement or a noreturn call end it with
8339 a call to __builtin_unreachable. This situation can occur
8340 when inlining a noreturn call that does in fact return. */
8341 if (EDGE_COUNT (bb->succs) == 0)
8343 gimple stmt = last_stmt (bb);
8345 || (!is_ctrl_stmt (stmt)
8346 && (!is_gimple_call (stmt)
8347 || (gimple_call_flags (stmt) & ECF_NORETURN) == 0)))
8349 stmt = gimple_build_call
8350 (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
8351 gimple_stmt_iterator gsi = gsi_last_bb (bb);
8352 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
8356 if (count_scale != REG_BR_PROB_BASE)
8357 compute_function_frequency ();
8359 /* We just processed all calls. */
8360 if (cfun->gimple_df)
8361 vec_free (MODIFIED_NORETURN_CALLS (cfun));
8363 /* Dump a textual representation of the flowgraph. */
8365 gimple_dump_cfg (dump_file, dump_flags);
8368 && (todo & TODO_cleanup_cfg))
8369 loops_state_set (LOOPS_NEED_FIXUP);
8376 const pass_data pass_data_fixup_cfg =
8378 GIMPLE_PASS, /* type */
8379 "*free_cfg_annotations", /* name */
8380 OPTGROUP_NONE, /* optinfo_flags */
8381 false, /* has_gate */
8382 true, /* has_execute */
8383 TV_NONE, /* tv_id */
8384 PROP_cfg, /* properties_required */
8385 0, /* properties_provided */
8386 0, /* properties_destroyed */
8387 0, /* todo_flags_start */
8388 0, /* todo_flags_finish */
8391 class pass_fixup_cfg : public gimple_opt_pass
8394 pass_fixup_cfg (gcc::context *ctxt)
8395 : gimple_opt_pass (pass_data_fixup_cfg, ctxt)
8398 /* opt_pass methods: */
8399 opt_pass * clone () { return new pass_fixup_cfg (m_ctxt); }
8400 unsigned int execute () { return execute_fixup_cfg (); }
8402 }; // class pass_fixup_cfg
8407 make_pass_fixup_cfg (gcc::context *ctxt)
8409 return new pass_fixup_cfg (ctxt);
8412 /* Garbage collection support for edge_def. */
8414 extern void gt_ggc_mx (tree&);
8415 extern void gt_ggc_mx (gimple&);
8416 extern void gt_ggc_mx (rtx&);
8417 extern void gt_ggc_mx (basic_block&);
8420 gt_ggc_mx (edge_def *e)
8422 tree block = LOCATION_BLOCK (e->goto_locus);
8424 gt_ggc_mx (e->dest);
8425 if (current_ir_type () == IR_GIMPLE)
8426 gt_ggc_mx (e->insns.g);
8428 gt_ggc_mx (e->insns.r);
8432 /* PCH support for edge_def. */
8434 extern void gt_pch_nx (tree&);
8435 extern void gt_pch_nx (gimple&);
8436 extern void gt_pch_nx (rtx&);
8437 extern void gt_pch_nx (basic_block&);
8440 gt_pch_nx (edge_def *e)
8442 tree block = LOCATION_BLOCK (e->goto_locus);
8444 gt_pch_nx (e->dest);
8445 if (current_ir_type () == IR_GIMPLE)
8446 gt_pch_nx (e->insns.g);
8448 gt_pch_nx (e->insns.r);
8453 gt_pch_nx (edge_def *e, gt_pointer_operator op, void *cookie)
8455 tree block = LOCATION_BLOCK (e->goto_locus);
8456 op (&(e->src), cookie);
8457 op (&(e->dest), cookie);
8458 if (current_ir_type () == IR_GIMPLE)
8459 op (&(e->insns.g), cookie);
8461 op (&(e->insns.r), cookie);
8462 op (&(block), cookie);