2014-10-24 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / tree-cfg.c
blob3e00d7417c44ce197cd7f5759d45b21b12c81605
1 /* Control flow functions for trees.
2 Copyright (C) 2001-2014 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "hash-table.h"
25 #include "hash-map.h"
26 #include "tm.h"
27 #include "tree.h"
28 #include "trans-mem.h"
29 #include "stor-layout.h"
30 #include "print-tree.h"
31 #include "tm_p.h"
32 #include "basic-block.h"
33 #include "flags.h"
34 #include "hashtab.h"
35 #include "hash-set.h"
36 #include "vec.h"
37 #include "machmode.h"
38 #include "hard-reg-set.h"
39 #include "input.h"
40 #include "function.h"
41 #include "gimple-pretty-print.h"
42 #include "tree-ssa-alias.h"
43 #include "internal-fn.h"
44 #include "gimple-fold.h"
45 #include "tree-eh.h"
46 #include "gimple-expr.h"
47 #include "is-a.h"
48 #include "gimple.h"
49 #include "gimple-iterator.h"
50 #include "gimplify-me.h"
51 #include "gimple-walk.h"
52 #include "gimple-ssa.h"
53 #include "cgraph.h"
54 #include "tree-cfg.h"
55 #include "tree-phinodes.h"
56 #include "ssa-iterators.h"
57 #include "stringpool.h"
58 #include "tree-ssanames.h"
59 #include "tree-ssa-loop-manip.h"
60 #include "tree-ssa-loop-niter.h"
61 #include "tree-into-ssa.h"
62 #include "expr.h"
63 #include "tree-dfa.h"
64 #include "tree-ssa.h"
65 #include "tree-dump.h"
66 #include "tree-pass.h"
67 #include "diagnostic-core.h"
68 #include "except.h"
69 #include "cfgloop.h"
70 #include "tree-ssa-propagate.h"
71 #include "value-prof.h"
72 #include "tree-inline.h"
73 #include "target.h"
74 #include "tree-ssa-live.h"
75 #include "omp-low.h"
76 #include "tree-cfgcleanup.h"
77 #include "wide-int.h"
78 #include "wide-int-print.h"
80 /* This file contains functions for building the Control Flow Graph (CFG)
81 for a function tree. */
83 /* Local declarations. */
85 /* Initial capacity for the basic block array. */
86 static const int initial_cfg_capacity = 20;
88 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
89 which use a particular edge. The CASE_LABEL_EXPRs are chained together
90 via their CASE_CHAIN field, which we clear after we're done with the
91 hash table to prevent problems with duplication of GIMPLE_SWITCHes.
93 Access to this list of CASE_LABEL_EXPRs allows us to efficiently
94 update the case vector in response to edge redirections.
96 Right now this table is set up and torn down at key points in the
97 compilation process. It would be nice if we could make the table
98 more persistent. The key is getting notification of changes to
99 the CFG (particularly edge removal, creation and redirection). */
101 static hash_map<edge, tree> *edge_to_cases;
103 /* If we record edge_to_cases, this bitmap will hold indexes
104 of basic blocks that end in a GIMPLE_SWITCH which we touched
105 due to edge manipulations. */
107 static bitmap touched_switch_bbs;
109 /* CFG statistics. */
110 struct cfg_stats_d
112 long num_merged_labels;
115 static struct cfg_stats_d cfg_stats;
117 /* Hash table to store last discriminator assigned for each locus. */
118 struct locus_discrim_map
120 location_t locus;
121 int discriminator;
124 /* Hashtable helpers. */
126 struct locus_discrim_hasher : typed_free_remove <locus_discrim_map>
128 typedef locus_discrim_map value_type;
129 typedef locus_discrim_map compare_type;
130 static inline hashval_t hash (const value_type *);
131 static inline bool equal (const value_type *, const compare_type *);
134 /* Trivial hash function for a location_t. ITEM is a pointer to
135 a hash table entry that maps a location_t to a discriminator. */
137 inline hashval_t
138 locus_discrim_hasher::hash (const value_type *item)
140 return LOCATION_LINE (item->locus);
143 /* Equality function for the locus-to-discriminator map. A and B
144 point to the two hash table entries to compare. */
146 inline bool
147 locus_discrim_hasher::equal (const value_type *a, const compare_type *b)
149 return LOCATION_LINE (a->locus) == LOCATION_LINE (b->locus);
152 static hash_table<locus_discrim_hasher> *discriminator_per_locus;
154 /* Basic blocks and flowgraphs. */
155 static void make_blocks (gimple_seq);
157 /* Edges. */
158 static void make_edges (void);
159 static void assign_discriminators (void);
160 static void make_cond_expr_edges (basic_block);
161 static void make_gimple_switch_edges (basic_block);
162 static bool make_goto_expr_edges (basic_block);
163 static void make_gimple_asm_edges (basic_block);
164 static edge gimple_redirect_edge_and_branch (edge, basic_block);
165 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block);
167 /* Various helpers. */
168 static inline bool stmt_starts_bb_p (gimple, gimple);
169 static int gimple_verify_flow_info (void);
170 static void gimple_make_forwarder_block (edge);
171 static gimple first_non_label_stmt (basic_block);
172 static bool verify_gimple_transaction (gimple);
173 static bool call_can_make_abnormal_goto (gimple);
175 /* Flowgraph optimization and cleanup. */
176 static void gimple_merge_blocks (basic_block, basic_block);
177 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
178 static void remove_bb (basic_block);
179 static edge find_taken_edge_computed_goto (basic_block, tree);
180 static edge find_taken_edge_cond_expr (basic_block, tree);
181 static edge find_taken_edge_switch_expr (basic_block, tree);
182 static tree find_case_label_for_value (gimple, tree);
184 void
185 init_empty_tree_cfg_for_function (struct function *fn)
187 /* Initialize the basic block array. */
188 init_flow (fn);
189 profile_status_for_fn (fn) = PROFILE_ABSENT;
190 n_basic_blocks_for_fn (fn) = NUM_FIXED_BLOCKS;
191 last_basic_block_for_fn (fn) = NUM_FIXED_BLOCKS;
192 vec_alloc (basic_block_info_for_fn (fn), initial_cfg_capacity);
193 vec_safe_grow_cleared (basic_block_info_for_fn (fn),
194 initial_cfg_capacity);
196 /* Build a mapping of labels to their associated blocks. */
197 vec_alloc (label_to_block_map_for_fn (fn), initial_cfg_capacity);
198 vec_safe_grow_cleared (label_to_block_map_for_fn (fn),
199 initial_cfg_capacity);
201 SET_BASIC_BLOCK_FOR_FN (fn, ENTRY_BLOCK, ENTRY_BLOCK_PTR_FOR_FN (fn));
202 SET_BASIC_BLOCK_FOR_FN (fn, EXIT_BLOCK, EXIT_BLOCK_PTR_FOR_FN (fn));
204 ENTRY_BLOCK_PTR_FOR_FN (fn)->next_bb
205 = EXIT_BLOCK_PTR_FOR_FN (fn);
206 EXIT_BLOCK_PTR_FOR_FN (fn)->prev_bb
207 = ENTRY_BLOCK_PTR_FOR_FN (fn);
210 void
211 init_empty_tree_cfg (void)
213 init_empty_tree_cfg_for_function (cfun);
216 /*---------------------------------------------------------------------------
217 Create basic blocks
218 ---------------------------------------------------------------------------*/
220 /* Entry point to the CFG builder for trees. SEQ is the sequence of
221 statements to be added to the flowgraph. */
223 static void
224 build_gimple_cfg (gimple_seq seq)
226 /* Register specific gimple functions. */
227 gimple_register_cfg_hooks ();
229 memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
231 init_empty_tree_cfg ();
233 make_blocks (seq);
235 /* Make sure there is always at least one block, even if it's empty. */
236 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
237 create_empty_bb (ENTRY_BLOCK_PTR_FOR_FN (cfun));
239 /* Adjust the size of the array. */
240 if (basic_block_info_for_fn (cfun)->length ()
241 < (size_t) n_basic_blocks_for_fn (cfun))
242 vec_safe_grow_cleared (basic_block_info_for_fn (cfun),
243 n_basic_blocks_for_fn (cfun));
245 /* To speed up statement iterator walks, we first purge dead labels. */
246 cleanup_dead_labels ();
248 /* Group case nodes to reduce the number of edges.
249 We do this after cleaning up dead labels because otherwise we miss
250 a lot of obvious case merging opportunities. */
251 group_case_labels ();
253 /* Create the edges of the flowgraph. */
254 discriminator_per_locus = new hash_table<locus_discrim_hasher> (13);
255 make_edges ();
256 assign_discriminators ();
257 cleanup_dead_labels ();
258 delete discriminator_per_locus;
259 discriminator_per_locus = NULL;
263 /* Look for ANNOTATE calls with loop annotation kind; if found, remove
264 them and propagate the information to the loop. We assume that the
265 annotations come immediately before the condition of the loop. */
267 static void
268 replace_loop_annotate ()
270 struct loop *loop;
271 basic_block bb;
272 gimple_stmt_iterator gsi;
273 gimple stmt;
275 FOR_EACH_LOOP (loop, 0)
277 gsi = gsi_last_bb (loop->header);
278 stmt = gsi_stmt (gsi);
279 if (!(stmt && gimple_code (stmt) == GIMPLE_COND))
280 continue;
281 for (gsi_prev_nondebug (&gsi); !gsi_end_p (gsi); gsi_prev (&gsi))
283 stmt = gsi_stmt (gsi);
284 if (gimple_code (stmt) != GIMPLE_CALL)
285 break;
286 if (!gimple_call_internal_p (stmt)
287 || gimple_call_internal_fn (stmt) != IFN_ANNOTATE)
288 break;
289 switch ((annot_expr_kind) tree_to_shwi (gimple_call_arg (stmt, 1)))
291 case annot_expr_ivdep_kind:
292 loop->safelen = INT_MAX;
293 break;
294 case annot_expr_no_vector_kind:
295 loop->dont_vectorize = true;
296 break;
297 case annot_expr_vector_kind:
298 loop->force_vectorize = true;
299 cfun->has_force_vectorize_loops = true;
300 break;
301 default:
302 gcc_unreachable ();
304 stmt = gimple_build_assign (gimple_call_lhs (stmt),
305 gimple_call_arg (stmt, 0));
306 gsi_replace (&gsi, stmt, true);
310 /* Remove IFN_ANNOTATE. Safeguard for the case loop->latch == NULL. */
311 FOR_EACH_BB_FN (bb, cfun)
313 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
315 stmt = gsi_stmt (gsi);
316 if (gimple_code (stmt) != GIMPLE_CALL)
317 break;
318 if (!gimple_call_internal_p (stmt)
319 || gimple_call_internal_fn (stmt) != IFN_ANNOTATE)
320 break;
321 switch ((annot_expr_kind) tree_to_shwi (gimple_call_arg (stmt, 1)))
323 case annot_expr_ivdep_kind:
324 case annot_expr_no_vector_kind:
325 case annot_expr_vector_kind:
326 break;
327 default:
328 gcc_unreachable ();
330 warning_at (gimple_location (stmt), 0, "ignoring loop annotation");
331 stmt = gimple_build_assign (gimple_call_lhs (stmt),
332 gimple_call_arg (stmt, 0));
333 gsi_replace (&gsi, stmt, true);
339 static unsigned int
340 execute_build_cfg (void)
342 gimple_seq body = gimple_body (current_function_decl);
344 build_gimple_cfg (body);
345 gimple_set_body (current_function_decl, NULL);
346 if (dump_file && (dump_flags & TDF_DETAILS))
348 fprintf (dump_file, "Scope blocks:\n");
349 dump_scope_blocks (dump_file, dump_flags);
351 cleanup_tree_cfg ();
352 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
353 replace_loop_annotate ();
354 return 0;
357 namespace {
359 const pass_data pass_data_build_cfg =
361 GIMPLE_PASS, /* type */
362 "cfg", /* name */
363 OPTGROUP_NONE, /* optinfo_flags */
364 TV_TREE_CFG, /* tv_id */
365 PROP_gimple_leh, /* properties_required */
366 ( PROP_cfg | PROP_loops ), /* properties_provided */
367 0, /* properties_destroyed */
368 0, /* todo_flags_start */
369 0, /* todo_flags_finish */
372 class pass_build_cfg : public gimple_opt_pass
374 public:
375 pass_build_cfg (gcc::context *ctxt)
376 : gimple_opt_pass (pass_data_build_cfg, ctxt)
379 /* opt_pass methods: */
380 virtual unsigned int execute (function *) { return execute_build_cfg (); }
382 }; // class pass_build_cfg
384 } // anon namespace
386 gimple_opt_pass *
387 make_pass_build_cfg (gcc::context *ctxt)
389 return new pass_build_cfg (ctxt);
393 /* Return true if T is a computed goto. */
395 bool
396 computed_goto_p (gimple t)
398 return (gimple_code (t) == GIMPLE_GOTO
399 && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
402 /* Returns true for edge E where e->src ends with a GIMPLE_COND and
403 the other edge points to a bb with just __builtin_unreachable ().
404 I.e. return true for C->M edge in:
405 <bb C>:
407 if (something)
408 goto <bb N>;
409 else
410 goto <bb M>;
411 <bb N>:
412 __builtin_unreachable ();
413 <bb M>: */
415 bool
416 assert_unreachable_fallthru_edge_p (edge e)
418 basic_block pred_bb = e->src;
419 gimple last = last_stmt (pred_bb);
420 if (last && gimple_code (last) == GIMPLE_COND)
422 basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest;
423 if (other_bb == e->dest)
424 other_bb = EDGE_SUCC (pred_bb, 1)->dest;
425 if (EDGE_COUNT (other_bb->succs) == 0)
427 gimple_stmt_iterator gsi = gsi_after_labels (other_bb);
428 gimple stmt;
430 if (gsi_end_p (gsi))
431 return false;
432 stmt = gsi_stmt (gsi);
433 while (is_gimple_debug (stmt) || gimple_clobber_p (stmt))
435 gsi_next (&gsi);
436 if (gsi_end_p (gsi))
437 return false;
438 stmt = gsi_stmt (gsi);
440 return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE);
443 return false;
447 /* Initialize GF_CALL_CTRL_ALTERING flag, which indicates the call
448 could alter control flow except via eh. We initialize the flag at
449 CFG build time and only ever clear it later. */
451 static void
452 gimple_call_initialize_ctrl_altering (gimple stmt)
454 int flags = gimple_call_flags (stmt);
456 /* A call alters control flow if it can make an abnormal goto. */
457 if (call_can_make_abnormal_goto (stmt)
458 /* A call also alters control flow if it does not return. */
459 || flags & ECF_NORETURN
460 /* TM ending statements have backedges out of the transaction.
461 Return true so we split the basic block containing them.
462 Note that the TM_BUILTIN test is merely an optimization. */
463 || ((flags & ECF_TM_BUILTIN)
464 && is_tm_ending_fndecl (gimple_call_fndecl (stmt)))
465 /* BUILT_IN_RETURN call is same as return statement. */
466 || gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
467 gimple_call_set_ctrl_altering (stmt, true);
468 else
469 gimple_call_set_ctrl_altering (stmt, false);
473 /* Build a flowgraph for the sequence of stmts SEQ. */
475 static void
476 make_blocks (gimple_seq seq)
478 gimple_stmt_iterator i = gsi_start (seq);
479 gimple stmt = NULL;
480 bool start_new_block = true;
481 bool first_stmt_of_seq = true;
482 basic_block bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
484 while (!gsi_end_p (i))
486 gimple prev_stmt;
488 prev_stmt = stmt;
489 stmt = gsi_stmt (i);
491 if (stmt && is_gimple_call (stmt))
492 gimple_call_initialize_ctrl_altering (stmt);
494 /* If the statement starts a new basic block or if we have determined
495 in a previous pass that we need to create a new block for STMT, do
496 so now. */
497 if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
499 if (!first_stmt_of_seq)
500 gsi_split_seq_before (&i, &seq);
501 bb = create_basic_block (seq, NULL, bb);
502 start_new_block = false;
505 /* Now add STMT to BB and create the subgraphs for special statement
506 codes. */
507 gimple_set_bb (stmt, bb);
509 /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
510 next iteration. */
511 if (stmt_ends_bb_p (stmt))
513 /* If the stmt can make abnormal goto use a new temporary
514 for the assignment to the LHS. This makes sure the old value
515 of the LHS is available on the abnormal edge. Otherwise
516 we will end up with overlapping life-ranges for abnormal
517 SSA names. */
518 if (gimple_has_lhs (stmt)
519 && stmt_can_make_abnormal_goto (stmt)
520 && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt))))
522 tree lhs = gimple_get_lhs (stmt);
523 tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
524 gimple s = gimple_build_assign (lhs, tmp);
525 gimple_set_location (s, gimple_location (stmt));
526 gimple_set_block (s, gimple_block (stmt));
527 gimple_set_lhs (stmt, tmp);
528 if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE
529 || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE)
530 DECL_GIMPLE_REG_P (tmp) = 1;
531 gsi_insert_after (&i, s, GSI_SAME_STMT);
533 start_new_block = true;
536 gsi_next (&i);
537 first_stmt_of_seq = false;
542 /* Create and return a new empty basic block after bb AFTER. */
544 static basic_block
545 create_bb (void *h, void *e, basic_block after)
547 basic_block bb;
549 gcc_assert (!e);
551 /* Create and initialize a new basic block. Since alloc_block uses
552 GC allocation that clears memory to allocate a basic block, we do
553 not have to clear the newly allocated basic block here. */
554 bb = alloc_block ();
556 bb->index = last_basic_block_for_fn (cfun);
557 bb->flags = BB_NEW;
558 set_bb_seq (bb, h ? (gimple_seq) h : NULL);
560 /* Add the new block to the linked list of blocks. */
561 link_block (bb, after);
563 /* Grow the basic block array if needed. */
564 if ((size_t) last_basic_block_for_fn (cfun)
565 == basic_block_info_for_fn (cfun)->length ())
567 size_t new_size =
568 (last_basic_block_for_fn (cfun)
569 + (last_basic_block_for_fn (cfun) + 3) / 4);
570 vec_safe_grow_cleared (basic_block_info_for_fn (cfun), new_size);
573 /* Add the newly created block to the array. */
574 SET_BASIC_BLOCK_FOR_FN (cfun, last_basic_block_for_fn (cfun), bb);
576 n_basic_blocks_for_fn (cfun)++;
577 last_basic_block_for_fn (cfun)++;
579 return bb;
583 /*---------------------------------------------------------------------------
584 Edge creation
585 ---------------------------------------------------------------------------*/
587 /* Fold COND_EXPR_COND of each COND_EXPR. */
589 void
590 fold_cond_expr_cond (void)
592 basic_block bb;
594 FOR_EACH_BB_FN (bb, cfun)
596 gimple stmt = last_stmt (bb);
598 if (stmt && gimple_code (stmt) == GIMPLE_COND)
600 location_t loc = gimple_location (stmt);
601 tree cond;
602 bool zerop, onep;
604 fold_defer_overflow_warnings ();
605 cond = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node,
606 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
607 if (cond)
609 zerop = integer_zerop (cond);
610 onep = integer_onep (cond);
612 else
613 zerop = onep = false;
615 fold_undefer_overflow_warnings (zerop || onep,
616 stmt,
617 WARN_STRICT_OVERFLOW_CONDITIONAL);
618 if (zerop)
619 gimple_cond_make_false (stmt);
620 else if (onep)
621 gimple_cond_make_true (stmt);
626 /* If basic block BB has an abnormal edge to a basic block
627 containing IFN_ABNORMAL_DISPATCHER internal call, return
628 that the dispatcher's basic block, otherwise return NULL. */
630 basic_block
631 get_abnormal_succ_dispatcher (basic_block bb)
633 edge e;
634 edge_iterator ei;
636 FOR_EACH_EDGE (e, ei, bb->succs)
637 if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) == EDGE_ABNORMAL)
639 gimple_stmt_iterator gsi
640 = gsi_start_nondebug_after_labels_bb (e->dest);
641 gimple g = gsi_stmt (gsi);
642 if (g
643 && is_gimple_call (g)
644 && gimple_call_internal_p (g)
645 && gimple_call_internal_fn (g) == IFN_ABNORMAL_DISPATCHER)
646 return e->dest;
648 return NULL;
651 /* Helper function for make_edges. Create a basic block with
652 with ABNORMAL_DISPATCHER internal call in it if needed, and
653 create abnormal edges from BBS to it and from it to FOR_BB
654 if COMPUTED_GOTO is false, otherwise factor the computed gotos. */
656 static void
657 handle_abnormal_edges (basic_block *dispatcher_bbs,
658 basic_block for_bb, int *bb_to_omp_idx,
659 auto_vec<basic_block> *bbs, bool computed_goto)
661 basic_block *dispatcher = dispatcher_bbs + (computed_goto ? 1 : 0);
662 unsigned int idx = 0;
663 basic_block bb;
664 bool inner = false;
666 if (bb_to_omp_idx)
668 dispatcher = dispatcher_bbs + 2 * bb_to_omp_idx[for_bb->index];
669 if (bb_to_omp_idx[for_bb->index] != 0)
670 inner = true;
673 /* If the dispatcher has been created already, then there are basic
674 blocks with abnormal edges to it, so just make a new edge to
675 for_bb. */
676 if (*dispatcher == NULL)
678 /* Check if there are any basic blocks that need to have
679 abnormal edges to this dispatcher. If there are none, return
680 early. */
681 if (bb_to_omp_idx == NULL)
683 if (bbs->is_empty ())
684 return;
686 else
688 FOR_EACH_VEC_ELT (*bbs, idx, bb)
689 if (bb_to_omp_idx[bb->index] == bb_to_omp_idx[for_bb->index])
690 break;
691 if (bb == NULL)
692 return;
695 /* Create the dispatcher bb. */
696 *dispatcher = create_basic_block (NULL, NULL, for_bb);
697 if (computed_goto)
699 /* Factor computed gotos into a common computed goto site. Also
700 record the location of that site so that we can un-factor the
701 gotos after we have converted back to normal form. */
702 gimple_stmt_iterator gsi = gsi_start_bb (*dispatcher);
704 /* Create the destination of the factored goto. Each original
705 computed goto will put its desired destination into this
706 variable and jump to the label we create immediately below. */
707 tree var = create_tmp_var (ptr_type_node, "gotovar");
709 /* Build a label for the new block which will contain the
710 factored computed goto. */
711 tree factored_label_decl
712 = create_artificial_label (UNKNOWN_LOCATION);
713 gimple factored_computed_goto_label
714 = gimple_build_label (factored_label_decl);
715 gsi_insert_after (&gsi, factored_computed_goto_label, GSI_NEW_STMT);
717 /* Build our new computed goto. */
718 gimple factored_computed_goto = gimple_build_goto (var);
719 gsi_insert_after (&gsi, factored_computed_goto, GSI_NEW_STMT);
721 FOR_EACH_VEC_ELT (*bbs, idx, bb)
723 if (bb_to_omp_idx
724 && bb_to_omp_idx[bb->index] != bb_to_omp_idx[for_bb->index])
725 continue;
727 gsi = gsi_last_bb (bb);
728 gimple last = gsi_stmt (gsi);
730 gcc_assert (computed_goto_p (last));
732 /* Copy the original computed goto's destination into VAR. */
733 gimple assignment
734 = gimple_build_assign (var, gimple_goto_dest (last));
735 gsi_insert_before (&gsi, assignment, GSI_SAME_STMT);
737 edge e = make_edge (bb, *dispatcher, EDGE_FALLTHRU);
738 e->goto_locus = gimple_location (last);
739 gsi_remove (&gsi, true);
742 else
744 tree arg = inner ? boolean_true_node : boolean_false_node;
745 gimple g = gimple_build_call_internal (IFN_ABNORMAL_DISPATCHER,
746 1, arg);
747 gimple_stmt_iterator gsi = gsi_after_labels (*dispatcher);
748 gsi_insert_after (&gsi, g, GSI_NEW_STMT);
750 /* Create predecessor edges of the dispatcher. */
751 FOR_EACH_VEC_ELT (*bbs, idx, bb)
753 if (bb_to_omp_idx
754 && bb_to_omp_idx[bb->index] != bb_to_omp_idx[for_bb->index])
755 continue;
756 make_edge (bb, *dispatcher, EDGE_ABNORMAL);
761 make_edge (*dispatcher, for_bb, EDGE_ABNORMAL);
764 /* Join all the blocks in the flowgraph. */
766 static void
767 make_edges (void)
769 basic_block bb;
770 struct omp_region *cur_region = NULL;
771 auto_vec<basic_block> ab_edge_goto;
772 auto_vec<basic_block> ab_edge_call;
773 int *bb_to_omp_idx = NULL;
774 int cur_omp_region_idx = 0;
776 /* Create an edge from entry to the first block with executable
777 statements in it. */
778 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun),
779 BASIC_BLOCK_FOR_FN (cfun, NUM_FIXED_BLOCKS),
780 EDGE_FALLTHRU);
782 /* Traverse the basic block array placing edges. */
783 FOR_EACH_BB_FN (bb, cfun)
785 gimple last = last_stmt (bb);
786 bool fallthru;
788 if (bb_to_omp_idx)
789 bb_to_omp_idx[bb->index] = cur_omp_region_idx;
791 if (last)
793 enum gimple_code code = gimple_code (last);
794 switch (code)
796 case GIMPLE_GOTO:
797 if (make_goto_expr_edges (bb))
798 ab_edge_goto.safe_push (bb);
799 fallthru = false;
800 break;
801 case GIMPLE_RETURN:
803 edge e = make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
804 e->goto_locus = gimple_location (last);
805 fallthru = false;
807 break;
808 case GIMPLE_COND:
809 make_cond_expr_edges (bb);
810 fallthru = false;
811 break;
812 case GIMPLE_SWITCH:
813 make_gimple_switch_edges (bb);
814 fallthru = false;
815 break;
816 case GIMPLE_RESX:
817 make_eh_edges (last);
818 fallthru = false;
819 break;
820 case GIMPLE_EH_DISPATCH:
821 fallthru = make_eh_dispatch_edges (last);
822 break;
824 case GIMPLE_CALL:
825 /* If this function receives a nonlocal goto, then we need to
826 make edges from this call site to all the nonlocal goto
827 handlers. */
828 if (stmt_can_make_abnormal_goto (last))
829 ab_edge_call.safe_push (bb);
831 /* If this statement has reachable exception handlers, then
832 create abnormal edges to them. */
833 make_eh_edges (last);
835 /* BUILTIN_RETURN is really a return statement. */
836 if (gimple_call_builtin_p (last, BUILT_IN_RETURN))
838 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
839 fallthru = false;
841 /* Some calls are known not to return. */
842 else
843 fallthru = !(gimple_call_flags (last) & ECF_NORETURN);
844 break;
846 case GIMPLE_ASSIGN:
847 /* A GIMPLE_ASSIGN may throw internally and thus be considered
848 control-altering. */
849 if (is_ctrl_altering_stmt (last))
850 make_eh_edges (last);
851 fallthru = true;
852 break;
854 case GIMPLE_ASM:
855 make_gimple_asm_edges (bb);
856 fallthru = true;
857 break;
859 CASE_GIMPLE_OMP:
860 fallthru = make_gimple_omp_edges (bb, &cur_region,
861 &cur_omp_region_idx);
862 if (cur_region && bb_to_omp_idx == NULL)
863 bb_to_omp_idx = XCNEWVEC (int, n_basic_blocks_for_fn (cfun));
864 break;
866 case GIMPLE_TRANSACTION:
868 tree abort_label = gimple_transaction_label (last);
869 if (abort_label)
870 make_edge (bb, label_to_block (abort_label), EDGE_TM_ABORT);
871 fallthru = true;
873 break;
875 default:
876 gcc_assert (!stmt_ends_bb_p (last));
877 fallthru = true;
880 else
881 fallthru = true;
883 if (fallthru)
884 make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
887 /* Computed gotos are hell to deal with, especially if there are
888 lots of them with a large number of destinations. So we factor
889 them to a common computed goto location before we build the
890 edge list. After we convert back to normal form, we will un-factor
891 the computed gotos since factoring introduces an unwanted jump.
892 For non-local gotos and abnormal edges from calls to calls that return
893 twice or forced labels, factor the abnormal edges too, by having all
894 abnormal edges from the calls go to a common artificial basic block
895 with ABNORMAL_DISPATCHER internal call and abnormal edges from that
896 basic block to all forced labels and calls returning twice.
897 We do this per-OpenMP structured block, because those regions
898 are guaranteed to be single entry single exit by the standard,
899 so it is not allowed to enter or exit such regions abnormally this way,
900 thus all computed gotos, non-local gotos and setjmp/longjmp calls
901 must not transfer control across SESE region boundaries. */
902 if (!ab_edge_goto.is_empty () || !ab_edge_call.is_empty ())
904 gimple_stmt_iterator gsi;
905 basic_block dispatcher_bb_array[2] = { NULL, NULL };
906 basic_block *dispatcher_bbs = dispatcher_bb_array;
907 int count = n_basic_blocks_for_fn (cfun);
909 if (bb_to_omp_idx)
910 dispatcher_bbs = XCNEWVEC (basic_block, 2 * count);
912 FOR_EACH_BB_FN (bb, cfun)
914 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
916 gimple label_stmt = gsi_stmt (gsi);
917 tree target;
919 if (gimple_code (label_stmt) != GIMPLE_LABEL)
920 break;
922 target = gimple_label_label (label_stmt);
924 /* Make an edge to every label block that has been marked as a
925 potential target for a computed goto or a non-local goto. */
926 if (FORCED_LABEL (target))
927 handle_abnormal_edges (dispatcher_bbs, bb, bb_to_omp_idx,
928 &ab_edge_goto, true);
929 if (DECL_NONLOCAL (target))
931 handle_abnormal_edges (dispatcher_bbs, bb, bb_to_omp_idx,
932 &ab_edge_call, false);
933 break;
937 if (!gsi_end_p (gsi) && is_gimple_debug (gsi_stmt (gsi)))
938 gsi_next_nondebug (&gsi);
939 if (!gsi_end_p (gsi))
941 /* Make an edge to every setjmp-like call. */
942 gimple call_stmt = gsi_stmt (gsi);
943 if (is_gimple_call (call_stmt)
944 && ((gimple_call_flags (call_stmt) & ECF_RETURNS_TWICE)
945 || gimple_call_builtin_p (call_stmt,
946 BUILT_IN_SETJMP_RECEIVER)))
947 handle_abnormal_edges (dispatcher_bbs, bb, bb_to_omp_idx,
948 &ab_edge_call, false);
952 if (bb_to_omp_idx)
953 XDELETE (dispatcher_bbs);
956 XDELETE (bb_to_omp_idx);
958 free_omp_regions ();
960 /* Fold COND_EXPR_COND of each COND_EXPR. */
961 fold_cond_expr_cond ();
964 /* Find the next available discriminator value for LOCUS. The
965 discriminator distinguishes among several basic blocks that
966 share a common locus, allowing for more accurate sample-based
967 profiling. */
969 static int
970 next_discriminator_for_locus (location_t locus)
972 struct locus_discrim_map item;
973 struct locus_discrim_map **slot;
975 item.locus = locus;
976 item.discriminator = 0;
977 slot = discriminator_per_locus->find_slot_with_hash (
978 &item, LOCATION_LINE (locus), INSERT);
979 gcc_assert (slot);
980 if (*slot == HTAB_EMPTY_ENTRY)
982 *slot = XNEW (struct locus_discrim_map);
983 gcc_assert (*slot);
984 (*slot)->locus = locus;
985 (*slot)->discriminator = 0;
987 (*slot)->discriminator++;
988 return (*slot)->discriminator;
991 /* Return TRUE if LOCUS1 and LOCUS2 refer to the same source line. */
993 static bool
994 same_line_p (location_t locus1, location_t locus2)
996 expanded_location from, to;
998 if (locus1 == locus2)
999 return true;
1001 from = expand_location (locus1);
1002 to = expand_location (locus2);
1004 if (from.line != to.line)
1005 return false;
1006 if (from.file == to.file)
1007 return true;
1008 return (from.file != NULL
1009 && to.file != NULL
1010 && filename_cmp (from.file, to.file) == 0);
1013 /* Assign discriminators to each basic block. */
1015 static void
1016 assign_discriminators (void)
1018 basic_block bb;
1020 FOR_EACH_BB_FN (bb, cfun)
1022 edge e;
1023 edge_iterator ei;
1024 gimple last = last_stmt (bb);
1025 location_t locus = last ? gimple_location (last) : UNKNOWN_LOCATION;
1027 if (locus == UNKNOWN_LOCATION)
1028 continue;
1030 FOR_EACH_EDGE (e, ei, bb->succs)
1032 gimple first = first_non_label_stmt (e->dest);
1033 gimple last = last_stmt (e->dest);
1034 if ((first && same_line_p (locus, gimple_location (first)))
1035 || (last && same_line_p (locus, gimple_location (last))))
1037 if (e->dest->discriminator != 0 && bb->discriminator == 0)
1038 bb->discriminator = next_discriminator_for_locus (locus);
1039 else
1040 e->dest->discriminator = next_discriminator_for_locus (locus);
1046 /* Create the edges for a GIMPLE_COND starting at block BB. */
1048 static void
1049 make_cond_expr_edges (basic_block bb)
1051 gimple entry = last_stmt (bb);
1052 gimple then_stmt, else_stmt;
1053 basic_block then_bb, else_bb;
1054 tree then_label, else_label;
1055 edge e;
1057 gcc_assert (entry);
1058 gcc_assert (gimple_code (entry) == GIMPLE_COND);
1060 /* Entry basic blocks for each component. */
1061 then_label = gimple_cond_true_label (entry);
1062 else_label = gimple_cond_false_label (entry);
1063 then_bb = label_to_block (then_label);
1064 else_bb = label_to_block (else_label);
1065 then_stmt = first_stmt (then_bb);
1066 else_stmt = first_stmt (else_bb);
1068 e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
1069 e->goto_locus = gimple_location (then_stmt);
1070 e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
1071 if (e)
1072 e->goto_locus = gimple_location (else_stmt);
1074 /* We do not need the labels anymore. */
1075 gimple_cond_set_true_label (entry, NULL_TREE);
1076 gimple_cond_set_false_label (entry, NULL_TREE);
1080 /* Called for each element in the hash table (P) as we delete the
1081 edge to cases hash table.
1083 Clear all the TREE_CHAINs to prevent problems with copying of
1084 SWITCH_EXPRs and structure sharing rules, then free the hash table
1085 element. */
1087 bool
1088 edge_to_cases_cleanup (edge const &, tree const &value, void *)
1090 tree t, next;
1092 for (t = value; t; t = next)
1094 next = CASE_CHAIN (t);
1095 CASE_CHAIN (t) = NULL;
1098 return true;
1101 /* Start recording information mapping edges to case labels. */
1103 void
1104 start_recording_case_labels (void)
1106 gcc_assert (edge_to_cases == NULL);
1107 edge_to_cases = new hash_map<edge, tree>;
1108 touched_switch_bbs = BITMAP_ALLOC (NULL);
1111 /* Return nonzero if we are recording information for case labels. */
1113 static bool
1114 recording_case_labels_p (void)
1116 return (edge_to_cases != NULL);
1119 /* Stop recording information mapping edges to case labels and
1120 remove any information we have recorded. */
1121 void
1122 end_recording_case_labels (void)
1124 bitmap_iterator bi;
1125 unsigned i;
1126 edge_to_cases->traverse<void *, edge_to_cases_cleanup> (NULL);
1127 delete edge_to_cases;
1128 edge_to_cases = NULL;
1129 EXECUTE_IF_SET_IN_BITMAP (touched_switch_bbs, 0, i, bi)
1131 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1132 if (bb)
1134 gimple stmt = last_stmt (bb);
1135 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1136 group_case_labels_stmt (stmt);
1139 BITMAP_FREE (touched_switch_bbs);
1142 /* If we are inside a {start,end}_recording_cases block, then return
1143 a chain of CASE_LABEL_EXPRs from T which reference E.
1145 Otherwise return NULL. */
1147 static tree
1148 get_cases_for_edge (edge e, gimple t)
1150 tree *slot;
1151 size_t i, n;
1153 /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
1154 chains available. Return NULL so the caller can detect this case. */
1155 if (!recording_case_labels_p ())
1156 return NULL;
1158 slot = edge_to_cases->get (e);
1159 if (slot)
1160 return *slot;
1162 /* If we did not find E in the hash table, then this must be the first
1163 time we have been queried for information about E & T. Add all the
1164 elements from T to the hash table then perform the query again. */
1166 n = gimple_switch_num_labels (t);
1167 for (i = 0; i < n; i++)
1169 tree elt = gimple_switch_label (t, i);
1170 tree lab = CASE_LABEL (elt);
1171 basic_block label_bb = label_to_block (lab);
1172 edge this_edge = find_edge (e->src, label_bb);
1174 /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
1175 a new chain. */
1176 tree &s = edge_to_cases->get_or_insert (this_edge);
1177 CASE_CHAIN (elt) = s;
1178 s = elt;
1181 return *edge_to_cases->get (e);
1184 /* Create the edges for a GIMPLE_SWITCH starting at block BB. */
1186 static void
1187 make_gimple_switch_edges (basic_block bb)
1189 gimple entry = last_stmt (bb);
1190 size_t i, n;
1192 n = gimple_switch_num_labels (entry);
1194 for (i = 0; i < n; ++i)
1196 tree lab = CASE_LABEL (gimple_switch_label (entry, i));
1197 basic_block label_bb = label_to_block (lab);
1198 make_edge (bb, label_bb, 0);
1203 /* Return the basic block holding label DEST. */
1205 basic_block
1206 label_to_block_fn (struct function *ifun, tree dest)
1208 int uid = LABEL_DECL_UID (dest);
1210 /* We would die hard when faced by an undefined label. Emit a label to
1211 the very first basic block. This will hopefully make even the dataflow
1212 and undefined variable warnings quite right. */
1213 if (seen_error () && uid < 0)
1215 gimple_stmt_iterator gsi =
1216 gsi_start_bb (BASIC_BLOCK_FOR_FN (cfun, NUM_FIXED_BLOCKS));
1217 gimple stmt;
1219 stmt = gimple_build_label (dest);
1220 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1221 uid = LABEL_DECL_UID (dest);
1223 if (vec_safe_length (ifun->cfg->x_label_to_block_map) <= (unsigned int) uid)
1224 return NULL;
1225 return (*ifun->cfg->x_label_to_block_map)[uid];
1228 /* Create edges for a goto statement at block BB. Returns true
1229 if abnormal edges should be created. */
1231 static bool
1232 make_goto_expr_edges (basic_block bb)
1234 gimple_stmt_iterator last = gsi_last_bb (bb);
1235 gimple goto_t = gsi_stmt (last);
1237 /* A simple GOTO creates normal edges. */
1238 if (simple_goto_p (goto_t))
1240 tree dest = gimple_goto_dest (goto_t);
1241 basic_block label_bb = label_to_block (dest);
1242 edge e = make_edge (bb, label_bb, EDGE_FALLTHRU);
1243 e->goto_locus = gimple_location (goto_t);
1244 gsi_remove (&last, true);
1245 return false;
1248 /* A computed GOTO creates abnormal edges. */
1249 return true;
1252 /* Create edges for an asm statement with labels at block BB. */
1254 static void
1255 make_gimple_asm_edges (basic_block bb)
1257 gimple stmt = last_stmt (bb);
1258 int i, n = gimple_asm_nlabels (stmt);
1260 for (i = 0; i < n; ++i)
1262 tree label = TREE_VALUE (gimple_asm_label_op (stmt, i));
1263 basic_block label_bb = label_to_block (label);
1264 make_edge (bb, label_bb, 0);
1268 /*---------------------------------------------------------------------------
1269 Flowgraph analysis
1270 ---------------------------------------------------------------------------*/
1272 /* Cleanup useless labels in basic blocks. This is something we wish
1273 to do early because it allows us to group case labels before creating
1274 the edges for the CFG, and it speeds up block statement iterators in
1275 all passes later on.
1276 We rerun this pass after CFG is created, to get rid of the labels that
1277 are no longer referenced. After then we do not run it any more, since
1278 (almost) no new labels should be created. */
1280 /* A map from basic block index to the leading label of that block. */
1281 static struct label_record
1283 /* The label. */
1284 tree label;
1286 /* True if the label is referenced from somewhere. */
1287 bool used;
1288 } *label_for_bb;
1290 /* Given LABEL return the first label in the same basic block. */
1292 static tree
1293 main_block_label (tree label)
1295 basic_block bb = label_to_block (label);
1296 tree main_label = label_for_bb[bb->index].label;
1298 /* label_to_block possibly inserted undefined label into the chain. */
1299 if (!main_label)
1301 label_for_bb[bb->index].label = label;
1302 main_label = label;
1305 label_for_bb[bb->index].used = true;
1306 return main_label;
1309 /* Clean up redundant labels within the exception tree. */
1311 static void
1312 cleanup_dead_labels_eh (void)
1314 eh_landing_pad lp;
1315 eh_region r;
1316 tree lab;
1317 int i;
1319 if (cfun->eh == NULL)
1320 return;
1322 for (i = 1; vec_safe_iterate (cfun->eh->lp_array, i, &lp); ++i)
1323 if (lp && lp->post_landing_pad)
1325 lab = main_block_label (lp->post_landing_pad);
1326 if (lab != lp->post_landing_pad)
1328 EH_LANDING_PAD_NR (lp->post_landing_pad) = 0;
1329 EH_LANDING_PAD_NR (lab) = lp->index;
1333 FOR_ALL_EH_REGION (r)
1334 switch (r->type)
1336 case ERT_CLEANUP:
1337 case ERT_MUST_NOT_THROW:
1338 break;
1340 case ERT_TRY:
1342 eh_catch c;
1343 for (c = r->u.eh_try.first_catch; c ; c = c->next_catch)
1345 lab = c->label;
1346 if (lab)
1347 c->label = main_block_label (lab);
1350 break;
1352 case ERT_ALLOWED_EXCEPTIONS:
1353 lab = r->u.allowed.label;
1354 if (lab)
1355 r->u.allowed.label = main_block_label (lab);
1356 break;
1361 /* Cleanup redundant labels. This is a three-step process:
1362 1) Find the leading label for each block.
1363 2) Redirect all references to labels to the leading labels.
1364 3) Cleanup all useless labels. */
1366 void
1367 cleanup_dead_labels (void)
1369 basic_block bb;
1370 label_for_bb = XCNEWVEC (struct label_record, last_basic_block_for_fn (cfun));
1372 /* Find a suitable label for each block. We use the first user-defined
1373 label if there is one, or otherwise just the first label we see. */
1374 FOR_EACH_BB_FN (bb, cfun)
1376 gimple_stmt_iterator i;
1378 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
1380 tree label;
1381 gimple stmt = gsi_stmt (i);
1383 if (gimple_code (stmt) != GIMPLE_LABEL)
1384 break;
1386 label = gimple_label_label (stmt);
1388 /* If we have not yet seen a label for the current block,
1389 remember this one and see if there are more labels. */
1390 if (!label_for_bb[bb->index].label)
1392 label_for_bb[bb->index].label = label;
1393 continue;
1396 /* If we did see a label for the current block already, but it
1397 is an artificially created label, replace it if the current
1398 label is a user defined label. */
1399 if (!DECL_ARTIFICIAL (label)
1400 && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
1402 label_for_bb[bb->index].label = label;
1403 break;
1408 /* Now redirect all jumps/branches to the selected label.
1409 First do so for each block ending in a control statement. */
1410 FOR_EACH_BB_FN (bb, cfun)
1412 gimple stmt = last_stmt (bb);
1413 tree label, new_label;
1415 if (!stmt)
1416 continue;
1418 switch (gimple_code (stmt))
1420 case GIMPLE_COND:
1421 label = gimple_cond_true_label (stmt);
1422 if (label)
1424 new_label = main_block_label (label);
1425 if (new_label != label)
1426 gimple_cond_set_true_label (stmt, new_label);
1429 label = gimple_cond_false_label (stmt);
1430 if (label)
1432 new_label = main_block_label (label);
1433 if (new_label != label)
1434 gimple_cond_set_false_label (stmt, new_label);
1436 break;
1438 case GIMPLE_SWITCH:
1440 size_t i, n = gimple_switch_num_labels (stmt);
1442 /* Replace all destination labels. */
1443 for (i = 0; i < n; ++i)
1445 tree case_label = gimple_switch_label (stmt, i);
1446 label = CASE_LABEL (case_label);
1447 new_label = main_block_label (label);
1448 if (new_label != label)
1449 CASE_LABEL (case_label) = new_label;
1451 break;
1454 case GIMPLE_ASM:
1456 int i, n = gimple_asm_nlabels (stmt);
1458 for (i = 0; i < n; ++i)
1460 tree cons = gimple_asm_label_op (stmt, i);
1461 tree label = main_block_label (TREE_VALUE (cons));
1462 TREE_VALUE (cons) = label;
1464 break;
1467 /* We have to handle gotos until they're removed, and we don't
1468 remove them until after we've created the CFG edges. */
1469 case GIMPLE_GOTO:
1470 if (!computed_goto_p (stmt))
1472 label = gimple_goto_dest (stmt);
1473 new_label = main_block_label (label);
1474 if (new_label != label)
1475 gimple_goto_set_dest (stmt, new_label);
1477 break;
1479 case GIMPLE_TRANSACTION:
1481 tree label = gimple_transaction_label (stmt);
1482 if (label)
1484 tree new_label = main_block_label (label);
1485 if (new_label != label)
1486 gimple_transaction_set_label (stmt, new_label);
1489 break;
1491 default:
1492 break;
1496 /* Do the same for the exception region tree labels. */
1497 cleanup_dead_labels_eh ();
1499 /* Finally, purge dead labels. All user-defined labels and labels that
1500 can be the target of non-local gotos and labels which have their
1501 address taken are preserved. */
1502 FOR_EACH_BB_FN (bb, cfun)
1504 gimple_stmt_iterator i;
1505 tree label_for_this_bb = label_for_bb[bb->index].label;
1507 if (!label_for_this_bb)
1508 continue;
1510 /* If the main label of the block is unused, we may still remove it. */
1511 if (!label_for_bb[bb->index].used)
1512 label_for_this_bb = NULL;
1514 for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1516 tree label;
1517 gimple stmt = gsi_stmt (i);
1519 if (gimple_code (stmt) != GIMPLE_LABEL)
1520 break;
1522 label = gimple_label_label (stmt);
1524 if (label == label_for_this_bb
1525 || !DECL_ARTIFICIAL (label)
1526 || DECL_NONLOCAL (label)
1527 || FORCED_LABEL (label))
1528 gsi_next (&i);
1529 else
1530 gsi_remove (&i, true);
1534 free (label_for_bb);
1537 /* Scan the sorted vector of cases in STMT (a GIMPLE_SWITCH) and combine
1538 the ones jumping to the same label.
1539 Eg. three separate entries 1: 2: 3: become one entry 1..3: */
1541 void
1542 group_case_labels_stmt (gimple stmt)
1544 int old_size = gimple_switch_num_labels (stmt);
1545 int i, j, new_size = old_size;
1546 basic_block default_bb = NULL;
1548 default_bb = label_to_block (CASE_LABEL (gimple_switch_default_label (stmt)));
1550 /* Look for possible opportunities to merge cases. */
1551 i = 1;
1552 while (i < old_size)
1554 tree base_case, base_high;
1555 basic_block base_bb;
1557 base_case = gimple_switch_label (stmt, i);
1559 gcc_assert (base_case);
1560 base_bb = label_to_block (CASE_LABEL (base_case));
1562 /* Discard cases that have the same destination as the
1563 default case. */
1564 if (base_bb == default_bb)
1566 gimple_switch_set_label (stmt, i, NULL_TREE);
1567 i++;
1568 new_size--;
1569 continue;
1572 base_high = CASE_HIGH (base_case)
1573 ? CASE_HIGH (base_case)
1574 : CASE_LOW (base_case);
1575 i++;
1577 /* Try to merge case labels. Break out when we reach the end
1578 of the label vector or when we cannot merge the next case
1579 label with the current one. */
1580 while (i < old_size)
1582 tree merge_case = gimple_switch_label (stmt, i);
1583 basic_block merge_bb = label_to_block (CASE_LABEL (merge_case));
1584 wide_int bhp1 = wi::add (base_high, 1);
1586 /* Merge the cases if they jump to the same place,
1587 and their ranges are consecutive. */
1588 if (merge_bb == base_bb
1589 && wi::eq_p (CASE_LOW (merge_case), bhp1))
1591 base_high = CASE_HIGH (merge_case) ?
1592 CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1593 CASE_HIGH (base_case) = base_high;
1594 gimple_switch_set_label (stmt, i, NULL_TREE);
1595 new_size--;
1596 i++;
1598 else
1599 break;
1603 /* Compress the case labels in the label vector, and adjust the
1604 length of the vector. */
1605 for (i = 0, j = 0; i < new_size; i++)
1607 while (! gimple_switch_label (stmt, j))
1608 j++;
1609 gimple_switch_set_label (stmt, i,
1610 gimple_switch_label (stmt, j++));
1613 gcc_assert (new_size <= old_size);
1614 gimple_switch_set_num_labels (stmt, new_size);
1617 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
1618 and scan the sorted vector of cases. Combine the ones jumping to the
1619 same label. */
1621 void
1622 group_case_labels (void)
1624 basic_block bb;
1626 FOR_EACH_BB_FN (bb, cfun)
1628 gimple stmt = last_stmt (bb);
1629 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1630 group_case_labels_stmt (stmt);
1634 /* Checks whether we can merge block B into block A. */
1636 static bool
1637 gimple_can_merge_blocks_p (basic_block a, basic_block b)
1639 gimple stmt;
1640 gimple_stmt_iterator gsi;
1642 if (!single_succ_p (a))
1643 return false;
1645 if (single_succ_edge (a)->flags & EDGE_COMPLEX)
1646 return false;
1648 if (single_succ (a) != b)
1649 return false;
1651 if (!single_pred_p (b))
1652 return false;
1654 if (b == EXIT_BLOCK_PTR_FOR_FN (cfun))
1655 return false;
1657 /* If A ends by a statement causing exceptions or something similar, we
1658 cannot merge the blocks. */
1659 stmt = last_stmt (a);
1660 if (stmt && stmt_ends_bb_p (stmt))
1661 return false;
1663 /* Do not allow a block with only a non-local label to be merged. */
1664 if (stmt
1665 && gimple_code (stmt) == GIMPLE_LABEL
1666 && DECL_NONLOCAL (gimple_label_label (stmt)))
1667 return false;
1669 /* Examine the labels at the beginning of B. */
1670 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
1672 tree lab;
1673 stmt = gsi_stmt (gsi);
1674 if (gimple_code (stmt) != GIMPLE_LABEL)
1675 break;
1676 lab = gimple_label_label (stmt);
1678 /* Do not remove user forced labels or for -O0 any user labels. */
1679 if (!DECL_ARTIFICIAL (lab) && (!optimize || FORCED_LABEL (lab)))
1680 return false;
1683 /* Protect simple loop latches. We only want to avoid merging
1684 the latch with the loop header in this case. */
1685 if (current_loops
1686 && b->loop_father->latch == b
1687 && loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES)
1688 && b->loop_father->header == a)
1689 return false;
1691 /* It must be possible to eliminate all phi nodes in B. If ssa form
1692 is not up-to-date and a name-mapping is registered, we cannot eliminate
1693 any phis. Symbols marked for renaming are never a problem though. */
1694 for (gsi = gsi_start_phis (b); !gsi_end_p (gsi); gsi_next (&gsi))
1696 gimple phi = gsi_stmt (gsi);
1697 /* Technically only new names matter. */
1698 if (name_registered_for_update_p (PHI_RESULT (phi)))
1699 return false;
1702 /* When not optimizing, don't merge if we'd lose goto_locus. */
1703 if (!optimize
1704 && single_succ_edge (a)->goto_locus != UNKNOWN_LOCATION)
1706 location_t goto_locus = single_succ_edge (a)->goto_locus;
1707 gimple_stmt_iterator prev, next;
1708 prev = gsi_last_nondebug_bb (a);
1709 next = gsi_after_labels (b);
1710 if (!gsi_end_p (next) && is_gimple_debug (gsi_stmt (next)))
1711 gsi_next_nondebug (&next);
1712 if ((gsi_end_p (prev)
1713 || gimple_location (gsi_stmt (prev)) != goto_locus)
1714 && (gsi_end_p (next)
1715 || gimple_location (gsi_stmt (next)) != goto_locus))
1716 return false;
1719 return true;
1722 /* Replaces all uses of NAME by VAL. */
1724 void
1725 replace_uses_by (tree name, tree val)
1727 imm_use_iterator imm_iter;
1728 use_operand_p use;
1729 gimple stmt;
1730 edge e;
1732 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1734 /* Mark the block if we change the last stmt in it. */
1735 if (cfgcleanup_altered_bbs
1736 && stmt_ends_bb_p (stmt))
1737 bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1739 FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1741 replace_exp (use, val);
1743 if (gimple_code (stmt) == GIMPLE_PHI)
1745 e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use));
1746 if (e->flags & EDGE_ABNORMAL)
1748 /* This can only occur for virtual operands, since
1749 for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1750 would prevent replacement. */
1751 gcc_checking_assert (virtual_operand_p (name));
1752 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1757 if (gimple_code (stmt) != GIMPLE_PHI)
1759 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1760 gimple orig_stmt = stmt;
1761 size_t i;
1763 /* FIXME. It shouldn't be required to keep TREE_CONSTANT
1764 on ADDR_EXPRs up-to-date on GIMPLE. Propagation will
1765 only change sth from non-invariant to invariant, and only
1766 when propagating constants. */
1767 if (is_gimple_min_invariant (val))
1768 for (i = 0; i < gimple_num_ops (stmt); i++)
1770 tree op = gimple_op (stmt, i);
1771 /* Operands may be empty here. For example, the labels
1772 of a GIMPLE_COND are nulled out following the creation
1773 of the corresponding CFG edges. */
1774 if (op && TREE_CODE (op) == ADDR_EXPR)
1775 recompute_tree_invariant_for_addr_expr (op);
1778 if (fold_stmt (&gsi))
1779 stmt = gsi_stmt (gsi);
1781 if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
1782 gimple_purge_dead_eh_edges (gimple_bb (stmt));
1784 update_stmt (stmt);
1788 gcc_checking_assert (has_zero_uses (name));
1790 /* Also update the trees stored in loop structures. */
1791 if (current_loops)
1793 struct loop *loop;
1795 FOR_EACH_LOOP (loop, 0)
1797 substitute_in_loop_info (loop, name, val);
1802 /* Merge block B into block A. */
1804 static void
1805 gimple_merge_blocks (basic_block a, basic_block b)
1807 gimple_stmt_iterator last, gsi, psi;
1809 if (dump_file)
1810 fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1812 /* Remove all single-valued PHI nodes from block B of the form
1813 V_i = PHI <V_j> by propagating V_j to all the uses of V_i. */
1814 gsi = gsi_last_bb (a);
1815 for (psi = gsi_start_phis (b); !gsi_end_p (psi); )
1817 gimple phi = gsi_stmt (psi);
1818 tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1819 gimple copy;
1820 bool may_replace_uses = (virtual_operand_p (def)
1821 || may_propagate_copy (def, use));
1823 /* In case we maintain loop closed ssa form, do not propagate arguments
1824 of loop exit phi nodes. */
1825 if (current_loops
1826 && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1827 && !virtual_operand_p (def)
1828 && TREE_CODE (use) == SSA_NAME
1829 && a->loop_father != b->loop_father)
1830 may_replace_uses = false;
1832 if (!may_replace_uses)
1834 gcc_assert (!virtual_operand_p (def));
1836 /* Note that just emitting the copies is fine -- there is no problem
1837 with ordering of phi nodes. This is because A is the single
1838 predecessor of B, therefore results of the phi nodes cannot
1839 appear as arguments of the phi nodes. */
1840 copy = gimple_build_assign (def, use);
1841 gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1842 remove_phi_node (&psi, false);
1844 else
1846 /* If we deal with a PHI for virtual operands, we can simply
1847 propagate these without fussing with folding or updating
1848 the stmt. */
1849 if (virtual_operand_p (def))
1851 imm_use_iterator iter;
1852 use_operand_p use_p;
1853 gimple stmt;
1855 FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1856 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1857 SET_USE (use_p, use);
1859 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
1860 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use) = 1;
1862 else
1863 replace_uses_by (def, use);
1865 remove_phi_node (&psi, true);
1869 /* Ensure that B follows A. */
1870 move_block_after (b, a);
1872 gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1873 gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1875 /* Remove labels from B and set gimple_bb to A for other statements. */
1876 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1878 gimple stmt = gsi_stmt (gsi);
1879 if (gimple_code (stmt) == GIMPLE_LABEL)
1881 tree label = gimple_label_label (stmt);
1882 int lp_nr;
1884 gsi_remove (&gsi, false);
1886 /* Now that we can thread computed gotos, we might have
1887 a situation where we have a forced label in block B
1888 However, the label at the start of block B might still be
1889 used in other ways (think about the runtime checking for
1890 Fortran assigned gotos). So we can not just delete the
1891 label. Instead we move the label to the start of block A. */
1892 if (FORCED_LABEL (label))
1894 gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1895 gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT);
1897 /* Other user labels keep around in a form of a debug stmt. */
1898 else if (!DECL_ARTIFICIAL (label) && MAY_HAVE_DEBUG_STMTS)
1900 gimple dbg = gimple_build_debug_bind (label,
1901 integer_zero_node,
1902 stmt);
1903 gimple_debug_bind_reset_value (dbg);
1904 gsi_insert_before (&gsi, dbg, GSI_SAME_STMT);
1907 lp_nr = EH_LANDING_PAD_NR (label);
1908 if (lp_nr)
1910 eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1911 lp->post_landing_pad = NULL;
1914 else
1916 gimple_set_bb (stmt, a);
1917 gsi_next (&gsi);
1921 /* When merging two BBs, if their counts are different, the larger count
1922 is selected as the new bb count. This is to handle inconsistent
1923 profiles. */
1924 if (a->loop_father == b->loop_father)
1926 a->count = MAX (a->count, b->count);
1927 a->frequency = MAX (a->frequency, b->frequency);
1930 /* Merge the sequences. */
1931 last = gsi_last_bb (a);
1932 gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1933 set_bb_seq (b, NULL);
1935 if (cfgcleanup_altered_bbs)
1936 bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1940 /* Return the one of two successors of BB that is not reachable by a
1941 complex edge, if there is one. Else, return BB. We use
1942 this in optimizations that use post-dominators for their heuristics,
1943 to catch the cases in C++ where function calls are involved. */
1945 basic_block
1946 single_noncomplex_succ (basic_block bb)
1948 edge e0, e1;
1949 if (EDGE_COUNT (bb->succs) != 2)
1950 return bb;
1952 e0 = EDGE_SUCC (bb, 0);
1953 e1 = EDGE_SUCC (bb, 1);
1954 if (e0->flags & EDGE_COMPLEX)
1955 return e1->dest;
1956 if (e1->flags & EDGE_COMPLEX)
1957 return e0->dest;
1959 return bb;
1962 /* T is CALL_EXPR. Set current_function_calls_* flags. */
1964 void
1965 notice_special_calls (gimple call)
1967 int flags = gimple_call_flags (call);
1969 if (flags & ECF_MAY_BE_ALLOCA)
1970 cfun->calls_alloca = true;
1971 if (flags & ECF_RETURNS_TWICE)
1972 cfun->calls_setjmp = true;
1976 /* Clear flags set by notice_special_calls. Used by dead code removal
1977 to update the flags. */
1979 void
1980 clear_special_calls (void)
1982 cfun->calls_alloca = false;
1983 cfun->calls_setjmp = false;
1986 /* Remove PHI nodes associated with basic block BB and all edges out of BB. */
1988 static void
1989 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1991 /* Since this block is no longer reachable, we can just delete all
1992 of its PHI nodes. */
1993 remove_phi_nodes (bb);
1995 /* Remove edges to BB's successors. */
1996 while (EDGE_COUNT (bb->succs) > 0)
1997 remove_edge (EDGE_SUCC (bb, 0));
2001 /* Remove statements of basic block BB. */
2003 static void
2004 remove_bb (basic_block bb)
2006 gimple_stmt_iterator i;
2008 if (dump_file)
2010 fprintf (dump_file, "Removing basic block %d\n", bb->index);
2011 if (dump_flags & TDF_DETAILS)
2013 dump_bb (dump_file, bb, 0, TDF_BLOCKS);
2014 fprintf (dump_file, "\n");
2018 if (current_loops)
2020 struct loop *loop = bb->loop_father;
2022 /* If a loop gets removed, clean up the information associated
2023 with it. */
2024 if (loop->latch == bb
2025 || loop->header == bb)
2026 free_numbers_of_iterations_estimates_loop (loop);
2029 /* Remove all the instructions in the block. */
2030 if (bb_seq (bb) != NULL)
2032 /* Walk backwards so as to get a chance to substitute all
2033 released DEFs into debug stmts. See
2034 eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
2035 details. */
2036 for (i = gsi_last_bb (bb); !gsi_end_p (i);)
2038 gimple stmt = gsi_stmt (i);
2039 if (gimple_code (stmt) == GIMPLE_LABEL
2040 && (FORCED_LABEL (gimple_label_label (stmt))
2041 || DECL_NONLOCAL (gimple_label_label (stmt))))
2043 basic_block new_bb;
2044 gimple_stmt_iterator new_gsi;
2046 /* A non-reachable non-local label may still be referenced.
2047 But it no longer needs to carry the extra semantics of
2048 non-locality. */
2049 if (DECL_NONLOCAL (gimple_label_label (stmt)))
2051 DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
2052 FORCED_LABEL (gimple_label_label (stmt)) = 1;
2055 new_bb = bb->prev_bb;
2056 new_gsi = gsi_start_bb (new_bb);
2057 gsi_remove (&i, false);
2058 gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
2060 else
2062 /* Release SSA definitions if we are in SSA. Note that we
2063 may be called when not in SSA. For example,
2064 final_cleanup calls this function via
2065 cleanup_tree_cfg. */
2066 if (gimple_in_ssa_p (cfun))
2067 release_defs (stmt);
2069 gsi_remove (&i, true);
2072 if (gsi_end_p (i))
2073 i = gsi_last_bb (bb);
2074 else
2075 gsi_prev (&i);
2079 remove_phi_nodes_and_edges_for_unreachable_block (bb);
2080 bb->il.gimple.seq = NULL;
2081 bb->il.gimple.phi_nodes = NULL;
2085 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2086 predicate VAL, return the edge that will be taken out of the block.
2087 If VAL does not match a unique edge, NULL is returned. */
2089 edge
2090 find_taken_edge (basic_block bb, tree val)
2092 gimple stmt;
2094 stmt = last_stmt (bb);
2096 gcc_assert (stmt);
2097 gcc_assert (is_ctrl_stmt (stmt));
2099 if (val == NULL)
2100 return NULL;
2102 if (!is_gimple_min_invariant (val))
2103 return NULL;
2105 if (gimple_code (stmt) == GIMPLE_COND)
2106 return find_taken_edge_cond_expr (bb, val);
2108 if (gimple_code (stmt) == GIMPLE_SWITCH)
2109 return find_taken_edge_switch_expr (bb, val);
2111 if (computed_goto_p (stmt))
2113 /* Only optimize if the argument is a label, if the argument is
2114 not a label then we can not construct a proper CFG.
2116 It may be the case that we only need to allow the LABEL_REF to
2117 appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
2118 appear inside a LABEL_EXPR just to be safe. */
2119 if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
2120 && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
2121 return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
2122 return NULL;
2125 gcc_unreachable ();
2128 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2129 statement, determine which of the outgoing edges will be taken out of the
2130 block. Return NULL if either edge may be taken. */
2132 static edge
2133 find_taken_edge_computed_goto (basic_block bb, tree val)
2135 basic_block dest;
2136 edge e = NULL;
2138 dest = label_to_block (val);
2139 if (dest)
2141 e = find_edge (bb, dest);
2142 gcc_assert (e != NULL);
2145 return e;
2148 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2149 statement, determine which of the two edges will be taken out of the
2150 block. Return NULL if either edge may be taken. */
2152 static edge
2153 find_taken_edge_cond_expr (basic_block bb, tree val)
2155 edge true_edge, false_edge;
2157 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2159 gcc_assert (TREE_CODE (val) == INTEGER_CST);
2160 return (integer_zerop (val) ? false_edge : true_edge);
2163 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2164 statement, determine which edge will be taken out of the block. Return
2165 NULL if any edge may be taken. */
2167 static edge
2168 find_taken_edge_switch_expr (basic_block bb, tree val)
2170 basic_block dest_bb;
2171 edge e;
2172 gimple switch_stmt;
2173 tree taken_case;
2175 switch_stmt = last_stmt (bb);
2176 taken_case = find_case_label_for_value (switch_stmt, val);
2177 dest_bb = label_to_block (CASE_LABEL (taken_case));
2179 e = find_edge (bb, dest_bb);
2180 gcc_assert (e);
2181 return e;
2185 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
2186 We can make optimal use here of the fact that the case labels are
2187 sorted: We can do a binary search for a case matching VAL. */
2189 static tree
2190 find_case_label_for_value (gimple switch_stmt, tree val)
2192 size_t low, high, n = gimple_switch_num_labels (switch_stmt);
2193 tree default_case = gimple_switch_default_label (switch_stmt);
2195 for (low = 0, high = n; high - low > 1; )
2197 size_t i = (high + low) / 2;
2198 tree t = gimple_switch_label (switch_stmt, i);
2199 int cmp;
2201 /* Cache the result of comparing CASE_LOW and val. */
2202 cmp = tree_int_cst_compare (CASE_LOW (t), val);
2204 if (cmp > 0)
2205 high = i;
2206 else
2207 low = i;
2209 if (CASE_HIGH (t) == NULL)
2211 /* A singe-valued case label. */
2212 if (cmp == 0)
2213 return t;
2215 else
2217 /* A case range. We can only handle integer ranges. */
2218 if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2219 return t;
2223 return default_case;
2227 /* Dump a basic block on stderr. */
2229 void
2230 gimple_debug_bb (basic_block bb)
2232 dump_bb (stderr, bb, 0, TDF_VOPS|TDF_MEMSYMS|TDF_BLOCKS);
2236 /* Dump basic block with index N on stderr. */
2238 basic_block
2239 gimple_debug_bb_n (int n)
2241 gimple_debug_bb (BASIC_BLOCK_FOR_FN (cfun, n));
2242 return BASIC_BLOCK_FOR_FN (cfun, n);
2246 /* Dump the CFG on stderr.
2248 FLAGS are the same used by the tree dumping functions
2249 (see TDF_* in dumpfile.h). */
2251 void
2252 gimple_debug_cfg (int flags)
2254 gimple_dump_cfg (stderr, flags);
2258 /* Dump the program showing basic block boundaries on the given FILE.
2260 FLAGS are the same used by the tree dumping functions (see TDF_* in
2261 tree.h). */
2263 void
2264 gimple_dump_cfg (FILE *file, int flags)
2266 if (flags & TDF_DETAILS)
2268 dump_function_header (file, current_function_decl, flags);
2269 fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2270 n_basic_blocks_for_fn (cfun), n_edges_for_fn (cfun),
2271 last_basic_block_for_fn (cfun));
2273 brief_dump_cfg (file, flags | TDF_COMMENT);
2274 fprintf (file, "\n");
2277 if (flags & TDF_STATS)
2278 dump_cfg_stats (file);
2280 dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2284 /* Dump CFG statistics on FILE. */
2286 void
2287 dump_cfg_stats (FILE *file)
2289 static long max_num_merged_labels = 0;
2290 unsigned long size, total = 0;
2291 long num_edges;
2292 basic_block bb;
2293 const char * const fmt_str = "%-30s%-13s%12s\n";
2294 const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2295 const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2296 const char * const fmt_str_3 = "%-43s%11lu%c\n";
2297 const char *funcname = current_function_name ();
2299 fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2301 fprintf (file, "---------------------------------------------------------\n");
2302 fprintf (file, fmt_str, "", " Number of ", "Memory");
2303 fprintf (file, fmt_str, "", " instances ", "used ");
2304 fprintf (file, "---------------------------------------------------------\n");
2306 size = n_basic_blocks_for_fn (cfun) * sizeof (struct basic_block_def);
2307 total += size;
2308 fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks_for_fn (cfun),
2309 SCALE (size), LABEL (size));
2311 num_edges = 0;
2312 FOR_EACH_BB_FN (bb, cfun)
2313 num_edges += EDGE_COUNT (bb->succs);
2314 size = num_edges * sizeof (struct edge_def);
2315 total += size;
2316 fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2318 fprintf (file, "---------------------------------------------------------\n");
2319 fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2320 LABEL (total));
2321 fprintf (file, "---------------------------------------------------------\n");
2322 fprintf (file, "\n");
2324 if (cfg_stats.num_merged_labels > max_num_merged_labels)
2325 max_num_merged_labels = cfg_stats.num_merged_labels;
2327 fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2328 cfg_stats.num_merged_labels, max_num_merged_labels);
2330 fprintf (file, "\n");
2334 /* Dump CFG statistics on stderr. Keep extern so that it's always
2335 linked in the final executable. */
2337 DEBUG_FUNCTION void
2338 debug_cfg_stats (void)
2340 dump_cfg_stats (stderr);
2343 /*---------------------------------------------------------------------------
2344 Miscellaneous helpers
2345 ---------------------------------------------------------------------------*/
2347 /* Return true if T, a GIMPLE_CALL, can make an abnormal transfer of control
2348 flow. Transfers of control flow associated with EH are excluded. */
2350 static bool
2351 call_can_make_abnormal_goto (gimple t)
2353 /* If the function has no non-local labels, then a call cannot make an
2354 abnormal transfer of control. */
2355 if (!cfun->has_nonlocal_label
2356 && !cfun->calls_setjmp)
2357 return false;
2359 /* Likewise if the call has no side effects. */
2360 if (!gimple_has_side_effects (t))
2361 return false;
2363 /* Likewise if the called function is leaf. */
2364 if (gimple_call_flags (t) & ECF_LEAF)
2365 return false;
2367 return true;
2371 /* Return true if T can make an abnormal transfer of control flow.
2372 Transfers of control flow associated with EH are excluded. */
2374 bool
2375 stmt_can_make_abnormal_goto (gimple t)
2377 if (computed_goto_p (t))
2378 return true;
2379 if (is_gimple_call (t))
2380 return call_can_make_abnormal_goto (t);
2381 return false;
2385 /* Return true if T represents a stmt that always transfers control. */
2387 bool
2388 is_ctrl_stmt (gimple t)
2390 switch (gimple_code (t))
2392 case GIMPLE_COND:
2393 case GIMPLE_SWITCH:
2394 case GIMPLE_GOTO:
2395 case GIMPLE_RETURN:
2396 case GIMPLE_RESX:
2397 return true;
2398 default:
2399 return false;
2404 /* Return true if T is a statement that may alter the flow of control
2405 (e.g., a call to a non-returning function). */
2407 bool
2408 is_ctrl_altering_stmt (gimple t)
2410 gcc_assert (t);
2412 switch (gimple_code (t))
2414 case GIMPLE_CALL:
2415 /* Per stmt call flag indicates whether the call could alter
2416 controlflow. */
2417 if (gimple_call_ctrl_altering_p (t))
2418 return true;
2419 break;
2421 case GIMPLE_EH_DISPATCH:
2422 /* EH_DISPATCH branches to the individual catch handlers at
2423 this level of a try or allowed-exceptions region. It can
2424 fallthru to the next statement as well. */
2425 return true;
2427 case GIMPLE_ASM:
2428 if (gimple_asm_nlabels (t) > 0)
2429 return true;
2430 break;
2432 CASE_GIMPLE_OMP:
2433 /* OpenMP directives alter control flow. */
2434 return true;
2436 case GIMPLE_TRANSACTION:
2437 /* A transaction start alters control flow. */
2438 return true;
2440 default:
2441 break;
2444 /* If a statement can throw, it alters control flow. */
2445 return stmt_can_throw_internal (t);
2449 /* Return true if T is a simple local goto. */
2451 bool
2452 simple_goto_p (gimple t)
2454 return (gimple_code (t) == GIMPLE_GOTO
2455 && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2459 /* Return true if STMT should start a new basic block. PREV_STMT is
2460 the statement preceding STMT. It is used when STMT is a label or a
2461 case label. Labels should only start a new basic block if their
2462 previous statement wasn't a label. Otherwise, sequence of labels
2463 would generate unnecessary basic blocks that only contain a single
2464 label. */
2466 static inline bool
2467 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2469 if (stmt == NULL)
2470 return false;
2472 /* Labels start a new basic block only if the preceding statement
2473 wasn't a label of the same type. This prevents the creation of
2474 consecutive blocks that have nothing but a single label. */
2475 if (gimple_code (stmt) == GIMPLE_LABEL)
2477 /* Nonlocal and computed GOTO targets always start a new block. */
2478 if (DECL_NONLOCAL (gimple_label_label (stmt))
2479 || FORCED_LABEL (gimple_label_label (stmt)))
2480 return true;
2482 if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2484 if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2485 return true;
2487 cfg_stats.num_merged_labels++;
2488 return false;
2490 else
2491 return true;
2493 else if (gimple_code (stmt) == GIMPLE_CALL
2494 && gimple_call_flags (stmt) & ECF_RETURNS_TWICE)
2495 /* setjmp acts similar to a nonlocal GOTO target and thus should
2496 start a new block. */
2497 return true;
2499 return false;
2503 /* Return true if T should end a basic block. */
2505 bool
2506 stmt_ends_bb_p (gimple t)
2508 return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2511 /* Remove block annotations and other data structures. */
2513 void
2514 delete_tree_cfg_annotations (void)
2516 vec_free (label_to_block_map_for_fn (cfun));
2520 /* Return the first statement in basic block BB. */
2522 gimple
2523 first_stmt (basic_block bb)
2525 gimple_stmt_iterator i = gsi_start_bb (bb);
2526 gimple stmt = NULL;
2528 while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2530 gsi_next (&i);
2531 stmt = NULL;
2533 return stmt;
2536 /* Return the first non-label statement in basic block BB. */
2538 static gimple
2539 first_non_label_stmt (basic_block bb)
2541 gimple_stmt_iterator i = gsi_start_bb (bb);
2542 while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2543 gsi_next (&i);
2544 return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2547 /* Return the last statement in basic block BB. */
2549 gimple
2550 last_stmt (basic_block bb)
2552 gimple_stmt_iterator i = gsi_last_bb (bb);
2553 gimple stmt = NULL;
2555 while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2557 gsi_prev (&i);
2558 stmt = NULL;
2560 return stmt;
2563 /* Return the last statement of an otherwise empty block. Return NULL
2564 if the block is totally empty, or if it contains more than one
2565 statement. */
2567 gimple
2568 last_and_only_stmt (basic_block bb)
2570 gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
2571 gimple last, prev;
2573 if (gsi_end_p (i))
2574 return NULL;
2576 last = gsi_stmt (i);
2577 gsi_prev_nondebug (&i);
2578 if (gsi_end_p (i))
2579 return last;
2581 /* Empty statements should no longer appear in the instruction stream.
2582 Everything that might have appeared before should be deleted by
2583 remove_useless_stmts, and the optimizers should just gsi_remove
2584 instead of smashing with build_empty_stmt.
2586 Thus the only thing that should appear here in a block containing
2587 one executable statement is a label. */
2588 prev = gsi_stmt (i);
2589 if (gimple_code (prev) == GIMPLE_LABEL)
2590 return last;
2591 else
2592 return NULL;
2595 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE. */
2597 static void
2598 reinstall_phi_args (edge new_edge, edge old_edge)
2600 edge_var_map *vm;
2601 int i;
2602 gimple_stmt_iterator phis;
2604 vec<edge_var_map> *v = redirect_edge_var_map_vector (old_edge);
2605 if (!v)
2606 return;
2608 for (i = 0, phis = gsi_start_phis (new_edge->dest);
2609 v->iterate (i, &vm) && !gsi_end_p (phis);
2610 i++, gsi_next (&phis))
2612 gimple phi = gsi_stmt (phis);
2613 tree result = redirect_edge_var_map_result (vm);
2614 tree arg = redirect_edge_var_map_def (vm);
2616 gcc_assert (result == gimple_phi_result (phi));
2618 add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
2621 redirect_edge_var_map_clear (old_edge);
2624 /* Returns the basic block after which the new basic block created
2625 by splitting edge EDGE_IN should be placed. Tries to keep the new block
2626 near its "logical" location. This is of most help to humans looking
2627 at debugging dumps. */
2629 static basic_block
2630 split_edge_bb_loc (edge edge_in)
2632 basic_block dest = edge_in->dest;
2633 basic_block dest_prev = dest->prev_bb;
2635 if (dest_prev)
2637 edge e = find_edge (dest_prev, dest);
2638 if (e && !(e->flags & EDGE_COMPLEX))
2639 return edge_in->src;
2641 return dest_prev;
2644 /* Split a (typically critical) edge EDGE_IN. Return the new block.
2645 Abort on abnormal edges. */
2647 static basic_block
2648 gimple_split_edge (edge edge_in)
2650 basic_block new_bb, after_bb, dest;
2651 edge new_edge, e;
2653 /* Abnormal edges cannot be split. */
2654 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2656 dest = edge_in->dest;
2658 after_bb = split_edge_bb_loc (edge_in);
2660 new_bb = create_empty_bb (after_bb);
2661 new_bb->frequency = EDGE_FREQUENCY (edge_in);
2662 new_bb->count = edge_in->count;
2663 new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2664 new_edge->probability = REG_BR_PROB_BASE;
2665 new_edge->count = edge_in->count;
2667 e = redirect_edge_and_branch (edge_in, new_bb);
2668 gcc_assert (e == edge_in);
2669 reinstall_phi_args (new_edge, e);
2671 return new_bb;
2675 /* Verify properties of the address expression T with base object BASE. */
2677 static tree
2678 verify_address (tree t, tree base)
2680 bool old_constant;
2681 bool old_side_effects;
2682 bool new_constant;
2683 bool new_side_effects;
2685 old_constant = TREE_CONSTANT (t);
2686 old_side_effects = TREE_SIDE_EFFECTS (t);
2688 recompute_tree_invariant_for_addr_expr (t);
2689 new_side_effects = TREE_SIDE_EFFECTS (t);
2690 new_constant = TREE_CONSTANT (t);
2692 if (old_constant != new_constant)
2694 error ("constant not recomputed when ADDR_EXPR changed");
2695 return t;
2697 if (old_side_effects != new_side_effects)
2699 error ("side effects not recomputed when ADDR_EXPR changed");
2700 return t;
2703 if (!(TREE_CODE (base) == VAR_DECL
2704 || TREE_CODE (base) == PARM_DECL
2705 || TREE_CODE (base) == RESULT_DECL))
2706 return NULL_TREE;
2708 if (DECL_GIMPLE_REG_P (base))
2710 error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2711 return base;
2714 return NULL_TREE;
2717 /* Callback for walk_tree, check that all elements with address taken are
2718 properly noticed as such. The DATA is an int* that is 1 if TP was seen
2719 inside a PHI node. */
2721 static tree
2722 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2724 tree t = *tp, x;
2726 if (TYPE_P (t))
2727 *walk_subtrees = 0;
2729 /* Check operand N for being valid GIMPLE and give error MSG if not. */
2730 #define CHECK_OP(N, MSG) \
2731 do { if (!is_gimple_val (TREE_OPERAND (t, N))) \
2732 { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2734 switch (TREE_CODE (t))
2736 case SSA_NAME:
2737 if (SSA_NAME_IN_FREE_LIST (t))
2739 error ("SSA name in freelist but still referenced");
2740 return *tp;
2742 break;
2744 case INDIRECT_REF:
2745 error ("INDIRECT_REF in gimple IL");
2746 return t;
2748 case MEM_REF:
2749 x = TREE_OPERAND (t, 0);
2750 if (!POINTER_TYPE_P (TREE_TYPE (x))
2751 || !is_gimple_mem_ref_addr (x))
2753 error ("invalid first operand of MEM_REF");
2754 return x;
2756 if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST
2757 || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1))))
2759 error ("invalid offset operand of MEM_REF");
2760 return TREE_OPERAND (t, 1);
2762 if (TREE_CODE (x) == ADDR_EXPR
2763 && (x = verify_address (x, TREE_OPERAND (x, 0))))
2764 return x;
2765 *walk_subtrees = 0;
2766 break;
2768 case ASSERT_EXPR:
2769 x = fold (ASSERT_EXPR_COND (t));
2770 if (x == boolean_false_node)
2772 error ("ASSERT_EXPR with an always-false condition");
2773 return *tp;
2775 break;
2777 case MODIFY_EXPR:
2778 error ("MODIFY_EXPR not expected while having tuples");
2779 return *tp;
2781 case ADDR_EXPR:
2783 tree tem;
2785 gcc_assert (is_gimple_address (t));
2787 /* Skip any references (they will be checked when we recurse down the
2788 tree) and ensure that any variable used as a prefix is marked
2789 addressable. */
2790 for (x = TREE_OPERAND (t, 0);
2791 handled_component_p (x);
2792 x = TREE_OPERAND (x, 0))
2795 if ((tem = verify_address (t, x)))
2796 return tem;
2798 if (!(TREE_CODE (x) == VAR_DECL
2799 || TREE_CODE (x) == PARM_DECL
2800 || TREE_CODE (x) == RESULT_DECL))
2801 return NULL;
2803 if (!TREE_ADDRESSABLE (x))
2805 error ("address taken, but ADDRESSABLE bit not set");
2806 return x;
2809 break;
2812 case COND_EXPR:
2813 x = COND_EXPR_COND (t);
2814 if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2816 error ("non-integral used in condition");
2817 return x;
2819 if (!is_gimple_condexpr (x))
2821 error ("invalid conditional operand");
2822 return x;
2824 break;
2826 case NON_LVALUE_EXPR:
2827 case TRUTH_NOT_EXPR:
2828 gcc_unreachable ();
2830 CASE_CONVERT:
2831 case FIX_TRUNC_EXPR:
2832 case FLOAT_EXPR:
2833 case NEGATE_EXPR:
2834 case ABS_EXPR:
2835 case BIT_NOT_EXPR:
2836 CHECK_OP (0, "invalid operand to unary operator");
2837 break;
2839 case REALPART_EXPR:
2840 case IMAGPART_EXPR:
2841 case BIT_FIELD_REF:
2842 if (!is_gimple_reg_type (TREE_TYPE (t)))
2844 error ("non-scalar BIT_FIELD_REF, IMAGPART_EXPR or REALPART_EXPR");
2845 return t;
2848 if (TREE_CODE (t) == BIT_FIELD_REF)
2850 tree t0 = TREE_OPERAND (t, 0);
2851 tree t1 = TREE_OPERAND (t, 1);
2852 tree t2 = TREE_OPERAND (t, 2);
2853 if (!tree_fits_uhwi_p (t1)
2854 || !tree_fits_uhwi_p (t2))
2856 error ("invalid position or size operand to BIT_FIELD_REF");
2857 return t;
2859 if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2860 && (TYPE_PRECISION (TREE_TYPE (t))
2861 != tree_to_uhwi (t1)))
2863 error ("integral result type precision does not match "
2864 "field size of BIT_FIELD_REF");
2865 return t;
2867 else if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2868 && TYPE_MODE (TREE_TYPE (t)) != BLKmode
2869 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2870 != tree_to_uhwi (t1)))
2872 error ("mode precision of non-integral result does not "
2873 "match field size of BIT_FIELD_REF");
2874 return t;
2876 if (!AGGREGATE_TYPE_P (TREE_TYPE (t0))
2877 && (tree_to_uhwi (t1) + tree_to_uhwi (t2)
2878 > tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t0)))))
2880 error ("position plus size exceeds size of referenced object in "
2881 "BIT_FIELD_REF");
2882 return t;
2885 t = TREE_OPERAND (t, 0);
2887 /* Fall-through. */
2888 case COMPONENT_REF:
2889 case ARRAY_REF:
2890 case ARRAY_RANGE_REF:
2891 case VIEW_CONVERT_EXPR:
2892 /* We have a nest of references. Verify that each of the operands
2893 that determine where to reference is either a constant or a variable,
2894 verify that the base is valid, and then show we've already checked
2895 the subtrees. */
2896 while (handled_component_p (t))
2898 if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2899 CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2900 else if (TREE_CODE (t) == ARRAY_REF
2901 || TREE_CODE (t) == ARRAY_RANGE_REF)
2903 CHECK_OP (1, "invalid array index");
2904 if (TREE_OPERAND (t, 2))
2905 CHECK_OP (2, "invalid array lower bound");
2906 if (TREE_OPERAND (t, 3))
2907 CHECK_OP (3, "invalid array stride");
2909 else if (TREE_CODE (t) == BIT_FIELD_REF
2910 || TREE_CODE (t) == REALPART_EXPR
2911 || TREE_CODE (t) == IMAGPART_EXPR)
2913 error ("non-top-level BIT_FIELD_REF, IMAGPART_EXPR or "
2914 "REALPART_EXPR");
2915 return t;
2918 t = TREE_OPERAND (t, 0);
2921 if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2923 error ("invalid reference prefix");
2924 return t;
2926 *walk_subtrees = 0;
2927 break;
2928 case PLUS_EXPR:
2929 case MINUS_EXPR:
2930 /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2931 POINTER_PLUS_EXPR. */
2932 if (POINTER_TYPE_P (TREE_TYPE (t)))
2934 error ("invalid operand to plus/minus, type is a pointer");
2935 return t;
2937 CHECK_OP (0, "invalid operand to binary operator");
2938 CHECK_OP (1, "invalid operand to binary operator");
2939 break;
2941 case POINTER_PLUS_EXPR:
2942 /* Check to make sure the first operand is a pointer or reference type. */
2943 if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
2945 error ("invalid operand to pointer plus, first operand is not a pointer");
2946 return t;
2948 /* Check to make sure the second operand is a ptrofftype. */
2949 if (!ptrofftype_p (TREE_TYPE (TREE_OPERAND (t, 1))))
2951 error ("invalid operand to pointer plus, second operand is not an "
2952 "integer type of appropriate width");
2953 return t;
2955 /* FALLTHROUGH */
2956 case LT_EXPR:
2957 case LE_EXPR:
2958 case GT_EXPR:
2959 case GE_EXPR:
2960 case EQ_EXPR:
2961 case NE_EXPR:
2962 case UNORDERED_EXPR:
2963 case ORDERED_EXPR:
2964 case UNLT_EXPR:
2965 case UNLE_EXPR:
2966 case UNGT_EXPR:
2967 case UNGE_EXPR:
2968 case UNEQ_EXPR:
2969 case LTGT_EXPR:
2970 case MULT_EXPR:
2971 case TRUNC_DIV_EXPR:
2972 case CEIL_DIV_EXPR:
2973 case FLOOR_DIV_EXPR:
2974 case ROUND_DIV_EXPR:
2975 case TRUNC_MOD_EXPR:
2976 case CEIL_MOD_EXPR:
2977 case FLOOR_MOD_EXPR:
2978 case ROUND_MOD_EXPR:
2979 case RDIV_EXPR:
2980 case EXACT_DIV_EXPR:
2981 case MIN_EXPR:
2982 case MAX_EXPR:
2983 case LSHIFT_EXPR:
2984 case RSHIFT_EXPR:
2985 case LROTATE_EXPR:
2986 case RROTATE_EXPR:
2987 case BIT_IOR_EXPR:
2988 case BIT_XOR_EXPR:
2989 case BIT_AND_EXPR:
2990 CHECK_OP (0, "invalid operand to binary operator");
2991 CHECK_OP (1, "invalid operand to binary operator");
2992 break;
2994 case CONSTRUCTOR:
2995 if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2996 *walk_subtrees = 0;
2997 break;
2999 case CASE_LABEL_EXPR:
3000 if (CASE_CHAIN (t))
3002 error ("invalid CASE_CHAIN");
3003 return t;
3005 break;
3007 default:
3008 break;
3010 return NULL;
3012 #undef CHECK_OP
3016 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
3017 Returns true if there is an error, otherwise false. */
3019 static bool
3020 verify_types_in_gimple_min_lval (tree expr)
3022 tree op;
3024 if (is_gimple_id (expr))
3025 return false;
3027 if (TREE_CODE (expr) != TARGET_MEM_REF
3028 && TREE_CODE (expr) != MEM_REF)
3030 error ("invalid expression for min lvalue");
3031 return true;
3034 /* TARGET_MEM_REFs are strange beasts. */
3035 if (TREE_CODE (expr) == TARGET_MEM_REF)
3036 return false;
3038 op = TREE_OPERAND (expr, 0);
3039 if (!is_gimple_val (op))
3041 error ("invalid operand in indirect reference");
3042 debug_generic_stmt (op);
3043 return true;
3045 /* Memory references now generally can involve a value conversion. */
3047 return false;
3050 /* Verify if EXPR is a valid GIMPLE reference expression. If
3051 REQUIRE_LVALUE is true verifies it is an lvalue. Returns true
3052 if there is an error, otherwise false. */
3054 static bool
3055 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
3057 while (handled_component_p (expr))
3059 tree op = TREE_OPERAND (expr, 0);
3061 if (TREE_CODE (expr) == ARRAY_REF
3062 || TREE_CODE (expr) == ARRAY_RANGE_REF)
3064 if (!is_gimple_val (TREE_OPERAND (expr, 1))
3065 || (TREE_OPERAND (expr, 2)
3066 && !is_gimple_val (TREE_OPERAND (expr, 2)))
3067 || (TREE_OPERAND (expr, 3)
3068 && !is_gimple_val (TREE_OPERAND (expr, 3))))
3070 error ("invalid operands to array reference");
3071 debug_generic_stmt (expr);
3072 return true;
3076 /* Verify if the reference array element types are compatible. */
3077 if (TREE_CODE (expr) == ARRAY_REF
3078 && !useless_type_conversion_p (TREE_TYPE (expr),
3079 TREE_TYPE (TREE_TYPE (op))))
3081 error ("type mismatch in array reference");
3082 debug_generic_stmt (TREE_TYPE (expr));
3083 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3084 return true;
3086 if (TREE_CODE (expr) == ARRAY_RANGE_REF
3087 && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
3088 TREE_TYPE (TREE_TYPE (op))))
3090 error ("type mismatch in array range reference");
3091 debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
3092 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3093 return true;
3096 if ((TREE_CODE (expr) == REALPART_EXPR
3097 || TREE_CODE (expr) == IMAGPART_EXPR)
3098 && !useless_type_conversion_p (TREE_TYPE (expr),
3099 TREE_TYPE (TREE_TYPE (op))))
3101 error ("type mismatch in real/imagpart reference");
3102 debug_generic_stmt (TREE_TYPE (expr));
3103 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3104 return true;
3107 if (TREE_CODE (expr) == COMPONENT_REF
3108 && !useless_type_conversion_p (TREE_TYPE (expr),
3109 TREE_TYPE (TREE_OPERAND (expr, 1))))
3111 error ("type mismatch in component reference");
3112 debug_generic_stmt (TREE_TYPE (expr));
3113 debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3114 return true;
3117 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
3119 /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check
3120 that their operand is not an SSA name or an invariant when
3121 requiring an lvalue (this usually means there is a SRA or IPA-SRA
3122 bug). Otherwise there is nothing to verify, gross mismatches at
3123 most invoke undefined behavior. */
3124 if (require_lvalue
3125 && (TREE_CODE (op) == SSA_NAME
3126 || is_gimple_min_invariant (op)))
3128 error ("conversion of an SSA_NAME on the left hand side");
3129 debug_generic_stmt (expr);
3130 return true;
3132 else if (TREE_CODE (op) == SSA_NAME
3133 && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op)))
3135 error ("conversion of register to a different size");
3136 debug_generic_stmt (expr);
3137 return true;
3139 else if (!handled_component_p (op))
3140 return false;
3143 expr = op;
3146 if (TREE_CODE (expr) == MEM_REF)
3148 if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0)))
3150 error ("invalid address operand in MEM_REF");
3151 debug_generic_stmt (expr);
3152 return true;
3154 if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST
3155 || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
3157 error ("invalid offset operand in MEM_REF");
3158 debug_generic_stmt (expr);
3159 return true;
3162 else if (TREE_CODE (expr) == TARGET_MEM_REF)
3164 if (!TMR_BASE (expr)
3165 || !is_gimple_mem_ref_addr (TMR_BASE (expr)))
3167 error ("invalid address operand in TARGET_MEM_REF");
3168 return true;
3170 if (!TMR_OFFSET (expr)
3171 || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST
3172 || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr))))
3174 error ("invalid offset operand in TARGET_MEM_REF");
3175 debug_generic_stmt (expr);
3176 return true;
3180 return ((require_lvalue || !is_gimple_min_invariant (expr))
3181 && verify_types_in_gimple_min_lval (expr));
3184 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3185 list of pointer-to types that is trivially convertible to DEST. */
3187 static bool
3188 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3190 tree src;
3192 if (!TYPE_POINTER_TO (src_obj))
3193 return true;
3195 for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3196 if (useless_type_conversion_p (dest, src))
3197 return true;
3199 return false;
3202 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3203 from TYPE2 can be handled by FIXED_CONVERT_EXPR. */
3205 static bool
3206 valid_fixed_convert_types_p (tree type1, tree type2)
3208 return (FIXED_POINT_TYPE_P (type1)
3209 && (INTEGRAL_TYPE_P (type2)
3210 || SCALAR_FLOAT_TYPE_P (type2)
3211 || FIXED_POINT_TYPE_P (type2)));
3214 /* Verify the contents of a GIMPLE_CALL STMT. Returns true when there
3215 is a problem, otherwise false. */
3217 static bool
3218 verify_gimple_call (gimple stmt)
3220 tree fn = gimple_call_fn (stmt);
3221 tree fntype, fndecl;
3222 unsigned i;
3224 if (gimple_call_internal_p (stmt))
3226 if (fn)
3228 error ("gimple call has two targets");
3229 debug_generic_stmt (fn);
3230 return true;
3233 else
3235 if (!fn)
3237 error ("gimple call has no target");
3238 return true;
3242 if (fn && !is_gimple_call_addr (fn))
3244 error ("invalid function in gimple call");
3245 debug_generic_stmt (fn);
3246 return true;
3249 if (fn
3250 && (!POINTER_TYPE_P (TREE_TYPE (fn))
3251 || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3252 && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE)))
3254 error ("non-function in gimple call");
3255 return true;
3258 fndecl = gimple_call_fndecl (stmt);
3259 if (fndecl
3260 && TREE_CODE (fndecl) == FUNCTION_DECL
3261 && DECL_LOOPING_CONST_OR_PURE_P (fndecl)
3262 && !DECL_PURE_P (fndecl)
3263 && !TREE_READONLY (fndecl))
3265 error ("invalid pure const state for function");
3266 return true;
3269 if (gimple_call_lhs (stmt)
3270 && (!is_gimple_lvalue (gimple_call_lhs (stmt))
3271 || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true)))
3273 error ("invalid LHS in gimple call");
3274 return true;
3277 if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt))
3279 error ("LHS in noreturn call");
3280 return true;
3283 fntype = gimple_call_fntype (stmt);
3284 if (fntype
3285 && gimple_call_lhs (stmt)
3286 && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3287 TREE_TYPE (fntype))
3288 /* ??? At least C++ misses conversions at assignments from
3289 void * call results.
3290 ??? Java is completely off. Especially with functions
3291 returning java.lang.Object.
3292 For now simply allow arbitrary pointer type conversions. */
3293 && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3294 && POINTER_TYPE_P (TREE_TYPE (fntype))))
3296 error ("invalid conversion in gimple call");
3297 debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3298 debug_generic_stmt (TREE_TYPE (fntype));
3299 return true;
3302 if (gimple_call_chain (stmt)
3303 && !is_gimple_val (gimple_call_chain (stmt)))
3305 error ("invalid static chain in gimple call");
3306 debug_generic_stmt (gimple_call_chain (stmt));
3307 return true;
3310 /* If there is a static chain argument, this should not be an indirect
3311 call, and the decl should have DECL_STATIC_CHAIN set. */
3312 if (gimple_call_chain (stmt))
3314 if (!gimple_call_fndecl (stmt))
3316 error ("static chain in indirect gimple call");
3317 return true;
3319 fn = TREE_OPERAND (fn, 0);
3321 if (!DECL_STATIC_CHAIN (fn))
3323 error ("static chain with function that doesn%'t use one");
3324 return true;
3328 /* ??? The C frontend passes unpromoted arguments in case it
3329 didn't see a function declaration before the call. So for now
3330 leave the call arguments mostly unverified. Once we gimplify
3331 unit-at-a-time we have a chance to fix this. */
3333 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3335 tree arg = gimple_call_arg (stmt, i);
3336 if ((is_gimple_reg_type (TREE_TYPE (arg))
3337 && !is_gimple_val (arg))
3338 || (!is_gimple_reg_type (TREE_TYPE (arg))
3339 && !is_gimple_lvalue (arg)))
3341 error ("invalid argument to gimple call");
3342 debug_generic_expr (arg);
3343 return true;
3347 return false;
3350 /* Verifies the gimple comparison with the result type TYPE and
3351 the operands OP0 and OP1. */
3353 static bool
3354 verify_gimple_comparison (tree type, tree op0, tree op1)
3356 tree op0_type = TREE_TYPE (op0);
3357 tree op1_type = TREE_TYPE (op1);
3359 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3361 error ("invalid operands in gimple comparison");
3362 return true;
3365 /* For comparisons we do not have the operations type as the
3366 effective type the comparison is carried out in. Instead
3367 we require that either the first operand is trivially
3368 convertible into the second, or the other way around.
3369 Because we special-case pointers to void we allow
3370 comparisons of pointers with the same mode as well. */
3371 if (!useless_type_conversion_p (op0_type, op1_type)
3372 && !useless_type_conversion_p (op1_type, op0_type)
3373 && (!POINTER_TYPE_P (op0_type)
3374 || !POINTER_TYPE_P (op1_type)
3375 || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3377 error ("mismatching comparison operand types");
3378 debug_generic_expr (op0_type);
3379 debug_generic_expr (op1_type);
3380 return true;
3383 /* The resulting type of a comparison may be an effective boolean type. */
3384 if (INTEGRAL_TYPE_P (type)
3385 && (TREE_CODE (type) == BOOLEAN_TYPE
3386 || TYPE_PRECISION (type) == 1))
3388 if (TREE_CODE (op0_type) == VECTOR_TYPE
3389 || TREE_CODE (op1_type) == VECTOR_TYPE)
3391 error ("vector comparison returning a boolean");
3392 debug_generic_expr (op0_type);
3393 debug_generic_expr (op1_type);
3394 return true;
3397 /* Or an integer vector type with the same size and element count
3398 as the comparison operand types. */
3399 else if (TREE_CODE (type) == VECTOR_TYPE
3400 && TREE_CODE (TREE_TYPE (type)) == INTEGER_TYPE)
3402 if (TREE_CODE (op0_type) != VECTOR_TYPE
3403 || TREE_CODE (op1_type) != VECTOR_TYPE)
3405 error ("non-vector operands in vector comparison");
3406 debug_generic_expr (op0_type);
3407 debug_generic_expr (op1_type);
3408 return true;
3411 if (TYPE_VECTOR_SUBPARTS (type) != TYPE_VECTOR_SUBPARTS (op0_type)
3412 || (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (type)))
3413 != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0_type))))
3414 /* The result of a vector comparison is of signed
3415 integral type. */
3416 || TYPE_UNSIGNED (TREE_TYPE (type)))
3418 error ("invalid vector comparison resulting type");
3419 debug_generic_expr (type);
3420 return true;
3423 else
3425 error ("bogus comparison result type");
3426 debug_generic_expr (type);
3427 return true;
3430 return false;
3433 /* Verify a gimple assignment statement STMT with an unary rhs.
3434 Returns true if anything is wrong. */
3436 static bool
3437 verify_gimple_assign_unary (gimple stmt)
3439 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3440 tree lhs = gimple_assign_lhs (stmt);
3441 tree lhs_type = TREE_TYPE (lhs);
3442 tree rhs1 = gimple_assign_rhs1 (stmt);
3443 tree rhs1_type = TREE_TYPE (rhs1);
3445 if (!is_gimple_reg (lhs))
3447 error ("non-register as LHS of unary operation");
3448 return true;
3451 if (!is_gimple_val (rhs1))
3453 error ("invalid operand in unary operation");
3454 return true;
3457 /* First handle conversions. */
3458 switch (rhs_code)
3460 CASE_CONVERT:
3462 /* Allow conversions from pointer type to integral type only if
3463 there is no sign or zero extension involved.
3464 For targets were the precision of ptrofftype doesn't match that
3465 of pointers we need to allow arbitrary conversions to ptrofftype. */
3466 if ((POINTER_TYPE_P (lhs_type)
3467 && INTEGRAL_TYPE_P (rhs1_type))
3468 || (POINTER_TYPE_P (rhs1_type)
3469 && INTEGRAL_TYPE_P (lhs_type)
3470 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3471 || ptrofftype_p (sizetype))))
3472 return false;
3474 /* Allow conversion from integral to offset type and vice versa. */
3475 if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3476 && INTEGRAL_TYPE_P (rhs1_type))
3477 || (INTEGRAL_TYPE_P (lhs_type)
3478 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3479 return false;
3481 /* Otherwise assert we are converting between types of the
3482 same kind. */
3483 if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3485 error ("invalid types in nop conversion");
3486 debug_generic_expr (lhs_type);
3487 debug_generic_expr (rhs1_type);
3488 return true;
3491 return false;
3494 case ADDR_SPACE_CONVERT_EXPR:
3496 if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3497 || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3498 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3500 error ("invalid types in address space conversion");
3501 debug_generic_expr (lhs_type);
3502 debug_generic_expr (rhs1_type);
3503 return true;
3506 return false;
3509 case FIXED_CONVERT_EXPR:
3511 if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3512 && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3514 error ("invalid types in fixed-point conversion");
3515 debug_generic_expr (lhs_type);
3516 debug_generic_expr (rhs1_type);
3517 return true;
3520 return false;
3523 case FLOAT_EXPR:
3525 if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3526 && (!VECTOR_INTEGER_TYPE_P (rhs1_type)
3527 || !VECTOR_FLOAT_TYPE_P (lhs_type)))
3529 error ("invalid types in conversion to floating point");
3530 debug_generic_expr (lhs_type);
3531 debug_generic_expr (rhs1_type);
3532 return true;
3535 return false;
3538 case FIX_TRUNC_EXPR:
3540 if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3541 && (!VECTOR_INTEGER_TYPE_P (lhs_type)
3542 || !VECTOR_FLOAT_TYPE_P (rhs1_type)))
3544 error ("invalid types in conversion to integer");
3545 debug_generic_expr (lhs_type);
3546 debug_generic_expr (rhs1_type);
3547 return true;
3550 return false;
3553 case VEC_UNPACK_HI_EXPR:
3554 case VEC_UNPACK_LO_EXPR:
3555 case REDUC_MAX_EXPR:
3556 case REDUC_MIN_EXPR:
3557 case REDUC_PLUS_EXPR:
3558 case VEC_UNPACK_FLOAT_HI_EXPR:
3559 case VEC_UNPACK_FLOAT_LO_EXPR:
3560 /* FIXME. */
3561 return false;
3563 case NEGATE_EXPR:
3564 case ABS_EXPR:
3565 case BIT_NOT_EXPR:
3566 case PAREN_EXPR:
3567 case CONJ_EXPR:
3568 break;
3570 default:
3571 gcc_unreachable ();
3574 /* For the remaining codes assert there is no conversion involved. */
3575 if (!useless_type_conversion_p (lhs_type, rhs1_type))
3577 error ("non-trivial conversion in unary operation");
3578 debug_generic_expr (lhs_type);
3579 debug_generic_expr (rhs1_type);
3580 return true;
3583 return false;
3586 /* Verify a gimple assignment statement STMT with a binary rhs.
3587 Returns true if anything is wrong. */
3589 static bool
3590 verify_gimple_assign_binary (gimple stmt)
3592 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3593 tree lhs = gimple_assign_lhs (stmt);
3594 tree lhs_type = TREE_TYPE (lhs);
3595 tree rhs1 = gimple_assign_rhs1 (stmt);
3596 tree rhs1_type = TREE_TYPE (rhs1);
3597 tree rhs2 = gimple_assign_rhs2 (stmt);
3598 tree rhs2_type = TREE_TYPE (rhs2);
3600 if (!is_gimple_reg (lhs))
3602 error ("non-register as LHS of binary operation");
3603 return true;
3606 if (!is_gimple_val (rhs1)
3607 || !is_gimple_val (rhs2))
3609 error ("invalid operands in binary operation");
3610 return true;
3613 /* First handle operations that involve different types. */
3614 switch (rhs_code)
3616 case COMPLEX_EXPR:
3618 if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3619 || !(INTEGRAL_TYPE_P (rhs1_type)
3620 || SCALAR_FLOAT_TYPE_P (rhs1_type))
3621 || !(INTEGRAL_TYPE_P (rhs2_type)
3622 || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3624 error ("type mismatch in complex expression");
3625 debug_generic_expr (lhs_type);
3626 debug_generic_expr (rhs1_type);
3627 debug_generic_expr (rhs2_type);
3628 return true;
3631 return false;
3634 case LSHIFT_EXPR:
3635 case RSHIFT_EXPR:
3636 case LROTATE_EXPR:
3637 case RROTATE_EXPR:
3639 /* Shifts and rotates are ok on integral types, fixed point
3640 types and integer vector types. */
3641 if ((!INTEGRAL_TYPE_P (rhs1_type)
3642 && !FIXED_POINT_TYPE_P (rhs1_type)
3643 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3644 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3645 || (!INTEGRAL_TYPE_P (rhs2_type)
3646 /* Vector shifts of vectors are also ok. */
3647 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3648 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3649 && TREE_CODE (rhs2_type) == VECTOR_TYPE
3650 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3651 || !useless_type_conversion_p (lhs_type, rhs1_type))
3653 error ("type mismatch in shift expression");
3654 debug_generic_expr (lhs_type);
3655 debug_generic_expr (rhs1_type);
3656 debug_generic_expr (rhs2_type);
3657 return true;
3660 return false;
3663 case VEC_LSHIFT_EXPR:
3664 case VEC_RSHIFT_EXPR:
3666 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3667 || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3668 || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3669 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3670 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3671 || (!INTEGRAL_TYPE_P (rhs2_type)
3672 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3673 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3674 || !useless_type_conversion_p (lhs_type, rhs1_type))
3676 error ("type mismatch in vector shift expression");
3677 debug_generic_expr (lhs_type);
3678 debug_generic_expr (rhs1_type);
3679 debug_generic_expr (rhs2_type);
3680 return true;
3682 /* For shifting a vector of non-integral components we
3683 only allow shifting by a constant multiple of the element size. */
3684 if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3685 && (TREE_CODE (rhs2) != INTEGER_CST
3686 || !div_if_zero_remainder (rhs2,
3687 TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3689 error ("non-element sized vector shift of floating point vector");
3690 return true;
3693 return false;
3696 case WIDEN_LSHIFT_EXPR:
3698 if (!INTEGRAL_TYPE_P (lhs_type)
3699 || !INTEGRAL_TYPE_P (rhs1_type)
3700 || TREE_CODE (rhs2) != INTEGER_CST
3701 || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)))
3703 error ("type mismatch in widening vector shift expression");
3704 debug_generic_expr (lhs_type);
3705 debug_generic_expr (rhs1_type);
3706 debug_generic_expr (rhs2_type);
3707 return true;
3710 return false;
3713 case VEC_WIDEN_LSHIFT_HI_EXPR:
3714 case VEC_WIDEN_LSHIFT_LO_EXPR:
3716 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3717 || TREE_CODE (lhs_type) != VECTOR_TYPE
3718 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3719 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs_type))
3720 || TREE_CODE (rhs2) != INTEGER_CST
3721 || (2 * TYPE_PRECISION (TREE_TYPE (rhs1_type))
3722 > TYPE_PRECISION (TREE_TYPE (lhs_type))))
3724 error ("type mismatch in widening vector shift expression");
3725 debug_generic_expr (lhs_type);
3726 debug_generic_expr (rhs1_type);
3727 debug_generic_expr (rhs2_type);
3728 return true;
3731 return false;
3734 case PLUS_EXPR:
3735 case MINUS_EXPR:
3737 tree lhs_etype = lhs_type;
3738 tree rhs1_etype = rhs1_type;
3739 tree rhs2_etype = rhs2_type;
3740 if (TREE_CODE (lhs_type) == VECTOR_TYPE)
3742 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3743 || TREE_CODE (rhs2_type) != VECTOR_TYPE)
3745 error ("invalid non-vector operands to vector valued plus");
3746 return true;
3748 lhs_etype = TREE_TYPE (lhs_type);
3749 rhs1_etype = TREE_TYPE (rhs1_type);
3750 rhs2_etype = TREE_TYPE (rhs2_type);
3752 if (POINTER_TYPE_P (lhs_etype)
3753 || POINTER_TYPE_P (rhs1_etype)
3754 || POINTER_TYPE_P (rhs2_etype))
3756 error ("invalid (pointer) operands to plus/minus");
3757 return true;
3760 /* Continue with generic binary expression handling. */
3761 break;
3764 case POINTER_PLUS_EXPR:
3766 if (!POINTER_TYPE_P (rhs1_type)
3767 || !useless_type_conversion_p (lhs_type, rhs1_type)
3768 || !ptrofftype_p (rhs2_type))
3770 error ("type mismatch in pointer plus expression");
3771 debug_generic_stmt (lhs_type);
3772 debug_generic_stmt (rhs1_type);
3773 debug_generic_stmt (rhs2_type);
3774 return true;
3777 return false;
3780 case TRUTH_ANDIF_EXPR:
3781 case TRUTH_ORIF_EXPR:
3782 case TRUTH_AND_EXPR:
3783 case TRUTH_OR_EXPR:
3784 case TRUTH_XOR_EXPR:
3786 gcc_unreachable ();
3788 case LT_EXPR:
3789 case LE_EXPR:
3790 case GT_EXPR:
3791 case GE_EXPR:
3792 case EQ_EXPR:
3793 case NE_EXPR:
3794 case UNORDERED_EXPR:
3795 case ORDERED_EXPR:
3796 case UNLT_EXPR:
3797 case UNLE_EXPR:
3798 case UNGT_EXPR:
3799 case UNGE_EXPR:
3800 case UNEQ_EXPR:
3801 case LTGT_EXPR:
3802 /* Comparisons are also binary, but the result type is not
3803 connected to the operand types. */
3804 return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3806 case WIDEN_MULT_EXPR:
3807 if (TREE_CODE (lhs_type) != INTEGER_TYPE)
3808 return true;
3809 return ((2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type))
3810 || (TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type)));
3812 case WIDEN_SUM_EXPR:
3813 case VEC_WIDEN_MULT_HI_EXPR:
3814 case VEC_WIDEN_MULT_LO_EXPR:
3815 case VEC_WIDEN_MULT_EVEN_EXPR:
3816 case VEC_WIDEN_MULT_ODD_EXPR:
3817 case VEC_PACK_TRUNC_EXPR:
3818 case VEC_PACK_SAT_EXPR:
3819 case VEC_PACK_FIX_TRUNC_EXPR:
3820 /* FIXME. */
3821 return false;
3823 case MULT_EXPR:
3824 case MULT_HIGHPART_EXPR:
3825 case TRUNC_DIV_EXPR:
3826 case CEIL_DIV_EXPR:
3827 case FLOOR_DIV_EXPR:
3828 case ROUND_DIV_EXPR:
3829 case TRUNC_MOD_EXPR:
3830 case CEIL_MOD_EXPR:
3831 case FLOOR_MOD_EXPR:
3832 case ROUND_MOD_EXPR:
3833 case RDIV_EXPR:
3834 case EXACT_DIV_EXPR:
3835 case MIN_EXPR:
3836 case MAX_EXPR:
3837 case BIT_IOR_EXPR:
3838 case BIT_XOR_EXPR:
3839 case BIT_AND_EXPR:
3840 /* Continue with generic binary expression handling. */
3841 break;
3843 default:
3844 gcc_unreachable ();
3847 if (!useless_type_conversion_p (lhs_type, rhs1_type)
3848 || !useless_type_conversion_p (lhs_type, rhs2_type))
3850 error ("type mismatch in binary expression");
3851 debug_generic_stmt (lhs_type);
3852 debug_generic_stmt (rhs1_type);
3853 debug_generic_stmt (rhs2_type);
3854 return true;
3857 return false;
3860 /* Verify a gimple assignment statement STMT with a ternary rhs.
3861 Returns true if anything is wrong. */
3863 static bool
3864 verify_gimple_assign_ternary (gimple stmt)
3866 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3867 tree lhs = gimple_assign_lhs (stmt);
3868 tree lhs_type = TREE_TYPE (lhs);
3869 tree rhs1 = gimple_assign_rhs1 (stmt);
3870 tree rhs1_type = TREE_TYPE (rhs1);
3871 tree rhs2 = gimple_assign_rhs2 (stmt);
3872 tree rhs2_type = TREE_TYPE (rhs2);
3873 tree rhs3 = gimple_assign_rhs3 (stmt);
3874 tree rhs3_type = TREE_TYPE (rhs3);
3876 if (!is_gimple_reg (lhs))
3878 error ("non-register as LHS of ternary operation");
3879 return true;
3882 if (((rhs_code == VEC_COND_EXPR || rhs_code == COND_EXPR)
3883 ? !is_gimple_condexpr (rhs1) : !is_gimple_val (rhs1))
3884 || !is_gimple_val (rhs2)
3885 || !is_gimple_val (rhs3))
3887 error ("invalid operands in ternary operation");
3888 return true;
3891 /* First handle operations that involve different types. */
3892 switch (rhs_code)
3894 case WIDEN_MULT_PLUS_EXPR:
3895 case WIDEN_MULT_MINUS_EXPR:
3896 if ((!INTEGRAL_TYPE_P (rhs1_type)
3897 && !FIXED_POINT_TYPE_P (rhs1_type))
3898 || !useless_type_conversion_p (rhs1_type, rhs2_type)
3899 || !useless_type_conversion_p (lhs_type, rhs3_type)
3900 || 2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)
3901 || TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type))
3903 error ("type mismatch in widening multiply-accumulate expression");
3904 debug_generic_expr (lhs_type);
3905 debug_generic_expr (rhs1_type);
3906 debug_generic_expr (rhs2_type);
3907 debug_generic_expr (rhs3_type);
3908 return true;
3910 break;
3912 case FMA_EXPR:
3913 if (!useless_type_conversion_p (lhs_type, rhs1_type)
3914 || !useless_type_conversion_p (lhs_type, rhs2_type)
3915 || !useless_type_conversion_p (lhs_type, rhs3_type))
3917 error ("type mismatch in fused multiply-add expression");
3918 debug_generic_expr (lhs_type);
3919 debug_generic_expr (rhs1_type);
3920 debug_generic_expr (rhs2_type);
3921 debug_generic_expr (rhs3_type);
3922 return true;
3924 break;
3926 case COND_EXPR:
3927 case VEC_COND_EXPR:
3928 if (!useless_type_conversion_p (lhs_type, rhs2_type)
3929 || !useless_type_conversion_p (lhs_type, rhs3_type))
3931 error ("type mismatch in conditional expression");
3932 debug_generic_expr (lhs_type);
3933 debug_generic_expr (rhs2_type);
3934 debug_generic_expr (rhs3_type);
3935 return true;
3937 break;
3939 case VEC_PERM_EXPR:
3940 if (!useless_type_conversion_p (lhs_type, rhs1_type)
3941 || !useless_type_conversion_p (lhs_type, rhs2_type))
3943 error ("type mismatch in vector permute expression");
3944 debug_generic_expr (lhs_type);
3945 debug_generic_expr (rhs1_type);
3946 debug_generic_expr (rhs2_type);
3947 debug_generic_expr (rhs3_type);
3948 return true;
3951 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3952 || TREE_CODE (rhs2_type) != VECTOR_TYPE
3953 || TREE_CODE (rhs3_type) != VECTOR_TYPE)
3955 error ("vector types expected in vector permute expression");
3956 debug_generic_expr (lhs_type);
3957 debug_generic_expr (rhs1_type);
3958 debug_generic_expr (rhs2_type);
3959 debug_generic_expr (rhs3_type);
3960 return true;
3963 if (TYPE_VECTOR_SUBPARTS (rhs1_type) != TYPE_VECTOR_SUBPARTS (rhs2_type)
3964 || TYPE_VECTOR_SUBPARTS (rhs2_type)
3965 != TYPE_VECTOR_SUBPARTS (rhs3_type)
3966 || TYPE_VECTOR_SUBPARTS (rhs3_type)
3967 != TYPE_VECTOR_SUBPARTS (lhs_type))
3969 error ("vectors with different element number found "
3970 "in vector permute expression");
3971 debug_generic_expr (lhs_type);
3972 debug_generic_expr (rhs1_type);
3973 debug_generic_expr (rhs2_type);
3974 debug_generic_expr (rhs3_type);
3975 return true;
3978 if (TREE_CODE (TREE_TYPE (rhs3_type)) != INTEGER_TYPE
3979 || GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs3_type)))
3980 != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1_type))))
3982 error ("invalid mask type in vector permute expression");
3983 debug_generic_expr (lhs_type);
3984 debug_generic_expr (rhs1_type);
3985 debug_generic_expr (rhs2_type);
3986 debug_generic_expr (rhs3_type);
3987 return true;
3990 return false;
3992 case SAD_EXPR:
3993 if (!useless_type_conversion_p (rhs1_type, rhs2_type)
3994 || !useless_type_conversion_p (lhs_type, rhs3_type)
3995 || 2 * GET_MODE_BITSIZE (GET_MODE_INNER
3996 (TYPE_MODE (TREE_TYPE (rhs1_type))))
3997 > GET_MODE_BITSIZE (GET_MODE_INNER
3998 (TYPE_MODE (TREE_TYPE (lhs_type)))))
4000 error ("type mismatch in sad expression");
4001 debug_generic_expr (lhs_type);
4002 debug_generic_expr (rhs1_type);
4003 debug_generic_expr (rhs2_type);
4004 debug_generic_expr (rhs3_type);
4005 return true;
4008 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
4009 || TREE_CODE (rhs2_type) != VECTOR_TYPE
4010 || TREE_CODE (rhs3_type) != VECTOR_TYPE)
4012 error ("vector types expected in sad expression");
4013 debug_generic_expr (lhs_type);
4014 debug_generic_expr (rhs1_type);
4015 debug_generic_expr (rhs2_type);
4016 debug_generic_expr (rhs3_type);
4017 return true;
4020 return false;
4022 case DOT_PROD_EXPR:
4023 case REALIGN_LOAD_EXPR:
4024 /* FIXME. */
4025 return false;
4027 default:
4028 gcc_unreachable ();
4030 return false;
4033 /* Verify a gimple assignment statement STMT with a single rhs.
4034 Returns true if anything is wrong. */
4036 static bool
4037 verify_gimple_assign_single (gimple stmt)
4039 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
4040 tree lhs = gimple_assign_lhs (stmt);
4041 tree lhs_type = TREE_TYPE (lhs);
4042 tree rhs1 = gimple_assign_rhs1 (stmt);
4043 tree rhs1_type = TREE_TYPE (rhs1);
4044 bool res = false;
4046 if (!useless_type_conversion_p (lhs_type, rhs1_type))
4048 error ("non-trivial conversion at assignment");
4049 debug_generic_expr (lhs_type);
4050 debug_generic_expr (rhs1_type);
4051 return true;
4054 if (gimple_clobber_p (stmt)
4055 && !(DECL_P (lhs) || TREE_CODE (lhs) == MEM_REF))
4057 error ("non-decl/MEM_REF LHS in clobber statement");
4058 debug_generic_expr (lhs);
4059 return true;
4062 if (handled_component_p (lhs)
4063 || TREE_CODE (lhs) == MEM_REF
4064 || TREE_CODE (lhs) == TARGET_MEM_REF)
4065 res |= verify_types_in_gimple_reference (lhs, true);
4067 /* Special codes we cannot handle via their class. */
4068 switch (rhs_code)
4070 case ADDR_EXPR:
4072 tree op = TREE_OPERAND (rhs1, 0);
4073 if (!is_gimple_addressable (op))
4075 error ("invalid operand in unary expression");
4076 return true;
4079 /* Technically there is no longer a need for matching types, but
4080 gimple hygiene asks for this check. In LTO we can end up
4081 combining incompatible units and thus end up with addresses
4082 of globals that change their type to a common one. */
4083 if (!in_lto_p
4084 && !types_compatible_p (TREE_TYPE (op),
4085 TREE_TYPE (TREE_TYPE (rhs1)))
4086 && !one_pointer_to_useless_type_conversion_p (TREE_TYPE (rhs1),
4087 TREE_TYPE (op)))
4089 error ("type mismatch in address expression");
4090 debug_generic_stmt (TREE_TYPE (rhs1));
4091 debug_generic_stmt (TREE_TYPE (op));
4092 return true;
4095 return verify_types_in_gimple_reference (op, true);
4098 /* tcc_reference */
4099 case INDIRECT_REF:
4100 error ("INDIRECT_REF in gimple IL");
4101 return true;
4103 case COMPONENT_REF:
4104 case BIT_FIELD_REF:
4105 case ARRAY_REF:
4106 case ARRAY_RANGE_REF:
4107 case VIEW_CONVERT_EXPR:
4108 case REALPART_EXPR:
4109 case IMAGPART_EXPR:
4110 case TARGET_MEM_REF:
4111 case MEM_REF:
4112 if (!is_gimple_reg (lhs)
4113 && is_gimple_reg_type (TREE_TYPE (lhs)))
4115 error ("invalid rhs for gimple memory store");
4116 debug_generic_stmt (lhs);
4117 debug_generic_stmt (rhs1);
4118 return true;
4120 return res || verify_types_in_gimple_reference (rhs1, false);
4122 /* tcc_constant */
4123 case SSA_NAME:
4124 case INTEGER_CST:
4125 case REAL_CST:
4126 case FIXED_CST:
4127 case COMPLEX_CST:
4128 case VECTOR_CST:
4129 case STRING_CST:
4130 return res;
4132 /* tcc_declaration */
4133 case CONST_DECL:
4134 return res;
4135 case VAR_DECL:
4136 case PARM_DECL:
4137 if (!is_gimple_reg (lhs)
4138 && !is_gimple_reg (rhs1)
4139 && is_gimple_reg_type (TREE_TYPE (lhs)))
4141 error ("invalid rhs for gimple memory store");
4142 debug_generic_stmt (lhs);
4143 debug_generic_stmt (rhs1);
4144 return true;
4146 return res;
4148 case CONSTRUCTOR:
4149 if (TREE_CODE (rhs1_type) == VECTOR_TYPE)
4151 unsigned int i;
4152 tree elt_i, elt_v, elt_t = NULL_TREE;
4154 if (CONSTRUCTOR_NELTS (rhs1) == 0)
4155 return res;
4156 /* For vector CONSTRUCTORs we require that either it is empty
4157 CONSTRUCTOR, or it is a CONSTRUCTOR of smaller vector elements
4158 (then the element count must be correct to cover the whole
4159 outer vector and index must be NULL on all elements, or it is
4160 a CONSTRUCTOR of scalar elements, where we as an exception allow
4161 smaller number of elements (assuming zero filling) and
4162 consecutive indexes as compared to NULL indexes (such
4163 CONSTRUCTORs can appear in the IL from FEs). */
4164 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (rhs1), i, elt_i, elt_v)
4166 if (elt_t == NULL_TREE)
4168 elt_t = TREE_TYPE (elt_v);
4169 if (TREE_CODE (elt_t) == VECTOR_TYPE)
4171 tree elt_t = TREE_TYPE (elt_v);
4172 if (!useless_type_conversion_p (TREE_TYPE (rhs1_type),
4173 TREE_TYPE (elt_t)))
4175 error ("incorrect type of vector CONSTRUCTOR"
4176 " elements");
4177 debug_generic_stmt (rhs1);
4178 return true;
4180 else if (CONSTRUCTOR_NELTS (rhs1)
4181 * TYPE_VECTOR_SUBPARTS (elt_t)
4182 != TYPE_VECTOR_SUBPARTS (rhs1_type))
4184 error ("incorrect number of vector CONSTRUCTOR"
4185 " elements");
4186 debug_generic_stmt (rhs1);
4187 return true;
4190 else if (!useless_type_conversion_p (TREE_TYPE (rhs1_type),
4191 elt_t))
4193 error ("incorrect type of vector CONSTRUCTOR elements");
4194 debug_generic_stmt (rhs1);
4195 return true;
4197 else if (CONSTRUCTOR_NELTS (rhs1)
4198 > TYPE_VECTOR_SUBPARTS (rhs1_type))
4200 error ("incorrect number of vector CONSTRUCTOR elements");
4201 debug_generic_stmt (rhs1);
4202 return true;
4205 else if (!useless_type_conversion_p (elt_t, TREE_TYPE (elt_v)))
4207 error ("incorrect type of vector CONSTRUCTOR elements");
4208 debug_generic_stmt (rhs1);
4209 return true;
4211 if (elt_i != NULL_TREE
4212 && (TREE_CODE (elt_t) == VECTOR_TYPE
4213 || TREE_CODE (elt_i) != INTEGER_CST
4214 || compare_tree_int (elt_i, i) != 0))
4216 error ("vector CONSTRUCTOR with non-NULL element index");
4217 debug_generic_stmt (rhs1);
4218 return true;
4220 if (!is_gimple_val (elt_v))
4222 error ("vector CONSTRUCTOR element is not a GIMPLE value");
4223 debug_generic_stmt (rhs1);
4224 return true;
4228 else if (CONSTRUCTOR_NELTS (rhs1) != 0)
4230 error ("non-vector CONSTRUCTOR with elements");
4231 debug_generic_stmt (rhs1);
4232 return true;
4234 return res;
4235 case OBJ_TYPE_REF:
4236 case ASSERT_EXPR:
4237 case WITH_SIZE_EXPR:
4238 /* FIXME. */
4239 return res;
4241 default:;
4244 return res;
4247 /* Verify the contents of a GIMPLE_ASSIGN STMT. Returns true when there
4248 is a problem, otherwise false. */
4250 static bool
4251 verify_gimple_assign (gimple stmt)
4253 switch (gimple_assign_rhs_class (stmt))
4255 case GIMPLE_SINGLE_RHS:
4256 return verify_gimple_assign_single (stmt);
4258 case GIMPLE_UNARY_RHS:
4259 return verify_gimple_assign_unary (stmt);
4261 case GIMPLE_BINARY_RHS:
4262 return verify_gimple_assign_binary (stmt);
4264 case GIMPLE_TERNARY_RHS:
4265 return verify_gimple_assign_ternary (stmt);
4267 default:
4268 gcc_unreachable ();
4272 /* Verify the contents of a GIMPLE_RETURN STMT. Returns true when there
4273 is a problem, otherwise false. */
4275 static bool
4276 verify_gimple_return (gimple stmt)
4278 tree op = gimple_return_retval (stmt);
4279 tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
4281 /* We cannot test for present return values as we do not fix up missing
4282 return values from the original source. */
4283 if (op == NULL)
4284 return false;
4286 if (!is_gimple_val (op)
4287 && TREE_CODE (op) != RESULT_DECL)
4289 error ("invalid operand in return statement");
4290 debug_generic_stmt (op);
4291 return true;
4294 if ((TREE_CODE (op) == RESULT_DECL
4295 && DECL_BY_REFERENCE (op))
4296 || (TREE_CODE (op) == SSA_NAME
4297 && SSA_NAME_VAR (op)
4298 && TREE_CODE (SSA_NAME_VAR (op)) == RESULT_DECL
4299 && DECL_BY_REFERENCE (SSA_NAME_VAR (op))))
4300 op = TREE_TYPE (op);
4302 if (!useless_type_conversion_p (restype, TREE_TYPE (op)))
4304 error ("invalid conversion in return statement");
4305 debug_generic_stmt (restype);
4306 debug_generic_stmt (TREE_TYPE (op));
4307 return true;
4310 return false;
4314 /* Verify the contents of a GIMPLE_GOTO STMT. Returns true when there
4315 is a problem, otherwise false. */
4317 static bool
4318 verify_gimple_goto (gimple stmt)
4320 tree dest = gimple_goto_dest (stmt);
4322 /* ??? We have two canonical forms of direct goto destinations, a
4323 bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL. */
4324 if (TREE_CODE (dest) != LABEL_DECL
4325 && (!is_gimple_val (dest)
4326 || !POINTER_TYPE_P (TREE_TYPE (dest))))
4328 error ("goto destination is neither a label nor a pointer");
4329 return true;
4332 return false;
4335 /* Verify the contents of a GIMPLE_SWITCH STMT. Returns true when there
4336 is a problem, otherwise false. */
4338 static bool
4339 verify_gimple_switch (gimple stmt)
4341 unsigned int i, n;
4342 tree elt, prev_upper_bound = NULL_TREE;
4343 tree index_type, elt_type = NULL_TREE;
4345 if (!is_gimple_val (gimple_switch_index (stmt)))
4347 error ("invalid operand to switch statement");
4348 debug_generic_stmt (gimple_switch_index (stmt));
4349 return true;
4352 index_type = TREE_TYPE (gimple_switch_index (stmt));
4353 if (! INTEGRAL_TYPE_P (index_type))
4355 error ("non-integral type switch statement");
4356 debug_generic_expr (index_type);
4357 return true;
4360 elt = gimple_switch_label (stmt, 0);
4361 if (CASE_LOW (elt) != NULL_TREE || CASE_HIGH (elt) != NULL_TREE)
4363 error ("invalid default case label in switch statement");
4364 debug_generic_expr (elt);
4365 return true;
4368 n = gimple_switch_num_labels (stmt);
4369 for (i = 1; i < n; i++)
4371 elt = gimple_switch_label (stmt, i);
4373 if (! CASE_LOW (elt))
4375 error ("invalid case label in switch statement");
4376 debug_generic_expr (elt);
4377 return true;
4379 if (CASE_HIGH (elt)
4380 && ! tree_int_cst_lt (CASE_LOW (elt), CASE_HIGH (elt)))
4382 error ("invalid case range in switch statement");
4383 debug_generic_expr (elt);
4384 return true;
4387 if (elt_type)
4389 if (TREE_TYPE (CASE_LOW (elt)) != elt_type
4390 || (CASE_HIGH (elt) && TREE_TYPE (CASE_HIGH (elt)) != elt_type))
4392 error ("type mismatch for case label in switch statement");
4393 debug_generic_expr (elt);
4394 return true;
4397 else
4399 elt_type = TREE_TYPE (CASE_LOW (elt));
4400 if (TYPE_PRECISION (index_type) < TYPE_PRECISION (elt_type))
4402 error ("type precision mismatch in switch statement");
4403 return true;
4407 if (prev_upper_bound)
4409 if (! tree_int_cst_lt (prev_upper_bound, CASE_LOW (elt)))
4411 error ("case labels not sorted in switch statement");
4412 return true;
4416 prev_upper_bound = CASE_HIGH (elt);
4417 if (! prev_upper_bound)
4418 prev_upper_bound = CASE_LOW (elt);
4421 return false;
4424 /* Verify a gimple debug statement STMT.
4425 Returns true if anything is wrong. */
4427 static bool
4428 verify_gimple_debug (gimple stmt ATTRIBUTE_UNUSED)
4430 /* There isn't much that could be wrong in a gimple debug stmt. A
4431 gimple debug bind stmt, for example, maps a tree, that's usually
4432 a VAR_DECL or a PARM_DECL, but that could also be some scalarized
4433 component or member of an aggregate type, to another tree, that
4434 can be an arbitrary expression. These stmts expand into debug
4435 insns, and are converted to debug notes by var-tracking.c. */
4436 return false;
4439 /* Verify a gimple label statement STMT.
4440 Returns true if anything is wrong. */
4442 static bool
4443 verify_gimple_label (gimple stmt)
4445 tree decl = gimple_label_label (stmt);
4446 int uid;
4447 bool err = false;
4449 if (TREE_CODE (decl) != LABEL_DECL)
4450 return true;
4451 if (!DECL_NONLOCAL (decl) && !FORCED_LABEL (decl)
4452 && DECL_CONTEXT (decl) != current_function_decl)
4454 error ("label's context is not the current function decl");
4455 err |= true;
4458 uid = LABEL_DECL_UID (decl);
4459 if (cfun->cfg
4460 && (uid == -1
4461 || (*label_to_block_map_for_fn (cfun))[uid] != gimple_bb (stmt)))
4463 error ("incorrect entry in label_to_block_map");
4464 err |= true;
4467 uid = EH_LANDING_PAD_NR (decl);
4468 if (uid)
4470 eh_landing_pad lp = get_eh_landing_pad_from_number (uid);
4471 if (decl != lp->post_landing_pad)
4473 error ("incorrect setting of landing pad number");
4474 err |= true;
4478 return err;
4481 /* Verify the GIMPLE statement STMT. Returns true if there is an
4482 error, otherwise false. */
4484 static bool
4485 verify_gimple_stmt (gimple stmt)
4487 switch (gimple_code (stmt))
4489 case GIMPLE_ASSIGN:
4490 return verify_gimple_assign (stmt);
4492 case GIMPLE_LABEL:
4493 return verify_gimple_label (stmt);
4495 case GIMPLE_CALL:
4496 return verify_gimple_call (stmt);
4498 case GIMPLE_COND:
4499 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
4501 error ("invalid comparison code in gimple cond");
4502 return true;
4504 if (!(!gimple_cond_true_label (stmt)
4505 || TREE_CODE (gimple_cond_true_label (stmt)) == LABEL_DECL)
4506 || !(!gimple_cond_false_label (stmt)
4507 || TREE_CODE (gimple_cond_false_label (stmt)) == LABEL_DECL))
4509 error ("invalid labels in gimple cond");
4510 return true;
4513 return verify_gimple_comparison (boolean_type_node,
4514 gimple_cond_lhs (stmt),
4515 gimple_cond_rhs (stmt));
4517 case GIMPLE_GOTO:
4518 return verify_gimple_goto (stmt);
4520 case GIMPLE_SWITCH:
4521 return verify_gimple_switch (stmt);
4523 case GIMPLE_RETURN:
4524 return verify_gimple_return (stmt);
4526 case GIMPLE_ASM:
4527 return false;
4529 case GIMPLE_TRANSACTION:
4530 return verify_gimple_transaction (stmt);
4532 /* Tuples that do not have tree operands. */
4533 case GIMPLE_NOP:
4534 case GIMPLE_PREDICT:
4535 case GIMPLE_RESX:
4536 case GIMPLE_EH_DISPATCH:
4537 case GIMPLE_EH_MUST_NOT_THROW:
4538 return false;
4540 CASE_GIMPLE_OMP:
4541 /* OpenMP directives are validated by the FE and never operated
4542 on by the optimizers. Furthermore, GIMPLE_OMP_FOR may contain
4543 non-gimple expressions when the main index variable has had
4544 its address taken. This does not affect the loop itself
4545 because the header of an GIMPLE_OMP_FOR is merely used to determine
4546 how to setup the parallel iteration. */
4547 return false;
4549 case GIMPLE_DEBUG:
4550 return verify_gimple_debug (stmt);
4552 default:
4553 gcc_unreachable ();
4557 /* Verify the contents of a GIMPLE_PHI. Returns true if there is a problem,
4558 and false otherwise. */
4560 static bool
4561 verify_gimple_phi (gimple phi)
4563 bool err = false;
4564 unsigned i;
4565 tree phi_result = gimple_phi_result (phi);
4566 bool virtual_p;
4568 if (!phi_result)
4570 error ("invalid PHI result");
4571 return true;
4574 virtual_p = virtual_operand_p (phi_result);
4575 if (TREE_CODE (phi_result) != SSA_NAME
4576 || (virtual_p
4577 && SSA_NAME_VAR (phi_result) != gimple_vop (cfun)))
4579 error ("invalid PHI result");
4580 err = true;
4583 for (i = 0; i < gimple_phi_num_args (phi); i++)
4585 tree t = gimple_phi_arg_def (phi, i);
4587 if (!t)
4589 error ("missing PHI def");
4590 err |= true;
4591 continue;
4593 /* Addressable variables do have SSA_NAMEs but they
4594 are not considered gimple values. */
4595 else if ((TREE_CODE (t) == SSA_NAME
4596 && virtual_p != virtual_operand_p (t))
4597 || (virtual_p
4598 && (TREE_CODE (t) != SSA_NAME
4599 || SSA_NAME_VAR (t) != gimple_vop (cfun)))
4600 || (!virtual_p
4601 && !is_gimple_val (t)))
4603 error ("invalid PHI argument");
4604 debug_generic_expr (t);
4605 err |= true;
4607 #ifdef ENABLE_TYPES_CHECKING
4608 if (!useless_type_conversion_p (TREE_TYPE (phi_result), TREE_TYPE (t)))
4610 error ("incompatible types in PHI argument %u", i);
4611 debug_generic_stmt (TREE_TYPE (phi_result));
4612 debug_generic_stmt (TREE_TYPE (t));
4613 err |= true;
4615 #endif
4618 return err;
4621 /* Verify the GIMPLE statements inside the sequence STMTS. */
4623 static bool
4624 verify_gimple_in_seq_2 (gimple_seq stmts)
4626 gimple_stmt_iterator ittr;
4627 bool err = false;
4629 for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
4631 gimple stmt = gsi_stmt (ittr);
4633 switch (gimple_code (stmt))
4635 case GIMPLE_BIND:
4636 err |= verify_gimple_in_seq_2 (gimple_bind_body (stmt));
4637 break;
4639 case GIMPLE_TRY:
4640 err |= verify_gimple_in_seq_2 (gimple_try_eval (stmt));
4641 err |= verify_gimple_in_seq_2 (gimple_try_cleanup (stmt));
4642 break;
4644 case GIMPLE_EH_FILTER:
4645 err |= verify_gimple_in_seq_2 (gimple_eh_filter_failure (stmt));
4646 break;
4648 case GIMPLE_EH_ELSE:
4649 err |= verify_gimple_in_seq_2 (gimple_eh_else_n_body (stmt));
4650 err |= verify_gimple_in_seq_2 (gimple_eh_else_e_body (stmt));
4651 break;
4653 case GIMPLE_CATCH:
4654 err |= verify_gimple_in_seq_2 (gimple_catch_handler (stmt));
4655 break;
4657 case GIMPLE_TRANSACTION:
4658 err |= verify_gimple_transaction (stmt);
4659 break;
4661 default:
4663 bool err2 = verify_gimple_stmt (stmt);
4664 if (err2)
4665 debug_gimple_stmt (stmt);
4666 err |= err2;
4671 return err;
4674 /* Verify the contents of a GIMPLE_TRANSACTION. Returns true if there
4675 is a problem, otherwise false. */
4677 static bool
4678 verify_gimple_transaction (gimple stmt)
4680 tree lab = gimple_transaction_label (stmt);
4681 if (lab != NULL && TREE_CODE (lab) != LABEL_DECL)
4682 return true;
4683 return verify_gimple_in_seq_2 (gimple_transaction_body (stmt));
4687 /* Verify the GIMPLE statements inside the statement list STMTS. */
4689 DEBUG_FUNCTION void
4690 verify_gimple_in_seq (gimple_seq stmts)
4692 timevar_push (TV_TREE_STMT_VERIFY);
4693 if (verify_gimple_in_seq_2 (stmts))
4694 internal_error ("verify_gimple failed");
4695 timevar_pop (TV_TREE_STMT_VERIFY);
4698 /* Return true when the T can be shared. */
4700 static bool
4701 tree_node_can_be_shared (tree t)
4703 if (IS_TYPE_OR_DECL_P (t)
4704 || is_gimple_min_invariant (t)
4705 || TREE_CODE (t) == SSA_NAME
4706 || t == error_mark_node
4707 || TREE_CODE (t) == IDENTIFIER_NODE)
4708 return true;
4710 if (TREE_CODE (t) == CASE_LABEL_EXPR)
4711 return true;
4713 if (DECL_P (t))
4714 return true;
4716 return false;
4719 /* Called via walk_tree. Verify tree sharing. */
4721 static tree
4722 verify_node_sharing_1 (tree *tp, int *walk_subtrees, void *data)
4724 hash_set<void *> *visited = (hash_set<void *> *) data;
4726 if (tree_node_can_be_shared (*tp))
4728 *walk_subtrees = false;
4729 return NULL;
4732 if (visited->add (*tp))
4733 return *tp;
4735 return NULL;
4738 /* Called via walk_gimple_stmt. Verify tree sharing. */
4740 static tree
4741 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4743 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4744 return verify_node_sharing_1 (tp, walk_subtrees, wi->info);
4747 static bool eh_error_found;
4748 bool
4749 verify_eh_throw_stmt_node (const gimple &stmt, const int &,
4750 hash_set<gimple> *visited)
4752 if (!visited->contains (stmt))
4754 error ("dead STMT in EH table");
4755 debug_gimple_stmt (stmt);
4756 eh_error_found = true;
4758 return true;
4761 /* Verify if the location LOCs block is in BLOCKS. */
4763 static bool
4764 verify_location (hash_set<tree> *blocks, location_t loc)
4766 tree block = LOCATION_BLOCK (loc);
4767 if (block != NULL_TREE
4768 && !blocks->contains (block))
4770 error ("location references block not in block tree");
4771 return true;
4773 if (block != NULL_TREE)
4774 return verify_location (blocks, BLOCK_SOURCE_LOCATION (block));
4775 return false;
4778 /* Called via walk_tree. Verify that expressions have no blocks. */
4780 static tree
4781 verify_expr_no_block (tree *tp, int *walk_subtrees, void *)
4783 if (!EXPR_P (*tp))
4785 *walk_subtrees = false;
4786 return NULL;
4789 location_t loc = EXPR_LOCATION (*tp);
4790 if (LOCATION_BLOCK (loc) != NULL)
4791 return *tp;
4793 return NULL;
4796 /* Called via walk_tree. Verify locations of expressions. */
4798 static tree
4799 verify_expr_location_1 (tree *tp, int *walk_subtrees, void *data)
4801 hash_set<tree> *blocks = (hash_set<tree> *) data;
4803 if (TREE_CODE (*tp) == VAR_DECL
4804 && DECL_HAS_DEBUG_EXPR_P (*tp))
4806 tree t = DECL_DEBUG_EXPR (*tp);
4807 tree addr = walk_tree (&t, verify_expr_no_block, NULL, NULL);
4808 if (addr)
4809 return addr;
4811 if ((TREE_CODE (*tp) == VAR_DECL
4812 || TREE_CODE (*tp) == PARM_DECL
4813 || TREE_CODE (*tp) == RESULT_DECL)
4814 && DECL_HAS_VALUE_EXPR_P (*tp))
4816 tree t = DECL_VALUE_EXPR (*tp);
4817 tree addr = walk_tree (&t, verify_expr_no_block, NULL, NULL);
4818 if (addr)
4819 return addr;
4822 if (!EXPR_P (*tp))
4824 *walk_subtrees = false;
4825 return NULL;
4828 location_t loc = EXPR_LOCATION (*tp);
4829 if (verify_location (blocks, loc))
4830 return *tp;
4832 return NULL;
4835 /* Called via walk_gimple_op. Verify locations of expressions. */
4837 static tree
4838 verify_expr_location (tree *tp, int *walk_subtrees, void *data)
4840 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4841 return verify_expr_location_1 (tp, walk_subtrees, wi->info);
4844 /* Insert all subblocks of BLOCK into BLOCKS and recurse. */
4846 static void
4847 collect_subblocks (hash_set<tree> *blocks, tree block)
4849 tree t;
4850 for (t = BLOCK_SUBBLOCKS (block); t; t = BLOCK_CHAIN (t))
4852 blocks->add (t);
4853 collect_subblocks (blocks, t);
4857 /* Verify the GIMPLE statements in the CFG of FN. */
4859 DEBUG_FUNCTION void
4860 verify_gimple_in_cfg (struct function *fn, bool verify_nothrow)
4862 basic_block bb;
4863 bool err = false;
4865 timevar_push (TV_TREE_STMT_VERIFY);
4866 hash_set<void *> visited;
4867 hash_set<gimple> visited_stmts;
4869 /* Collect all BLOCKs referenced by the BLOCK tree of FN. */
4870 hash_set<tree> blocks;
4871 if (DECL_INITIAL (fn->decl))
4873 blocks.add (DECL_INITIAL (fn->decl));
4874 collect_subblocks (&blocks, DECL_INITIAL (fn->decl));
4877 FOR_EACH_BB_FN (bb, fn)
4879 gimple_stmt_iterator gsi;
4881 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4883 gimple phi = gsi_stmt (gsi);
4884 bool err2 = false;
4885 unsigned i;
4887 visited_stmts.add (phi);
4889 if (gimple_bb (phi) != bb)
4891 error ("gimple_bb (phi) is set to a wrong basic block");
4892 err2 = true;
4895 err2 |= verify_gimple_phi (phi);
4897 /* Only PHI arguments have locations. */
4898 if (gimple_location (phi) != UNKNOWN_LOCATION)
4900 error ("PHI node with location");
4901 err2 = true;
4904 for (i = 0; i < gimple_phi_num_args (phi); i++)
4906 tree arg = gimple_phi_arg_def (phi, i);
4907 tree addr = walk_tree (&arg, verify_node_sharing_1,
4908 &visited, NULL);
4909 if (addr)
4911 error ("incorrect sharing of tree nodes");
4912 debug_generic_expr (addr);
4913 err2 |= true;
4915 location_t loc = gimple_phi_arg_location (phi, i);
4916 if (virtual_operand_p (gimple_phi_result (phi))
4917 && loc != UNKNOWN_LOCATION)
4919 error ("virtual PHI with argument locations");
4920 err2 = true;
4922 addr = walk_tree (&arg, verify_expr_location_1, &blocks, NULL);
4923 if (addr)
4925 debug_generic_expr (addr);
4926 err2 = true;
4928 err2 |= verify_location (&blocks, loc);
4931 if (err2)
4932 debug_gimple_stmt (phi);
4933 err |= err2;
4936 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4938 gimple stmt = gsi_stmt (gsi);
4939 bool err2 = false;
4940 struct walk_stmt_info wi;
4941 tree addr;
4942 int lp_nr;
4944 visited_stmts.add (stmt);
4946 if (gimple_bb (stmt) != bb)
4948 error ("gimple_bb (stmt) is set to a wrong basic block");
4949 err2 = true;
4952 err2 |= verify_gimple_stmt (stmt);
4953 err2 |= verify_location (&blocks, gimple_location (stmt));
4955 memset (&wi, 0, sizeof (wi));
4956 wi.info = (void *) &visited;
4957 addr = walk_gimple_op (stmt, verify_node_sharing, &wi);
4958 if (addr)
4960 error ("incorrect sharing of tree nodes");
4961 debug_generic_expr (addr);
4962 err2 |= true;
4965 memset (&wi, 0, sizeof (wi));
4966 wi.info = (void *) &blocks;
4967 addr = walk_gimple_op (stmt, verify_expr_location, &wi);
4968 if (addr)
4970 debug_generic_expr (addr);
4971 err2 |= true;
4974 /* ??? Instead of not checking these stmts at all the walker
4975 should know its context via wi. */
4976 if (!is_gimple_debug (stmt)
4977 && !is_gimple_omp (stmt))
4979 memset (&wi, 0, sizeof (wi));
4980 addr = walk_gimple_op (stmt, verify_expr, &wi);
4981 if (addr)
4983 debug_generic_expr (addr);
4984 inform (gimple_location (stmt), "in statement");
4985 err2 |= true;
4989 /* If the statement is marked as part of an EH region, then it is
4990 expected that the statement could throw. Verify that when we
4991 have optimizations that simplify statements such that we prove
4992 that they cannot throw, that we update other data structures
4993 to match. */
4994 lp_nr = lookup_stmt_eh_lp (stmt);
4995 if (lp_nr > 0)
4997 if (!stmt_could_throw_p (stmt))
4999 if (verify_nothrow)
5001 error ("statement marked for throw, but doesn%'t");
5002 err2 |= true;
5005 else if (!gsi_one_before_end_p (gsi))
5007 error ("statement marked for throw in middle of block");
5008 err2 |= true;
5012 if (err2)
5013 debug_gimple_stmt (stmt);
5014 err |= err2;
5018 eh_error_found = false;
5019 hash_map<gimple, int> *eh_table = get_eh_throw_stmt_table (cfun);
5020 if (eh_table)
5021 eh_table->traverse<hash_set<gimple> *, verify_eh_throw_stmt_node>
5022 (&visited_stmts);
5024 if (err || eh_error_found)
5025 internal_error ("verify_gimple failed");
5027 verify_histograms ();
5028 timevar_pop (TV_TREE_STMT_VERIFY);
5032 /* Verifies that the flow information is OK. */
5034 static int
5035 gimple_verify_flow_info (void)
5037 int err = 0;
5038 basic_block bb;
5039 gimple_stmt_iterator gsi;
5040 gimple stmt;
5041 edge e;
5042 edge_iterator ei;
5044 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->il.gimple.seq
5045 || ENTRY_BLOCK_PTR_FOR_FN (cfun)->il.gimple.phi_nodes)
5047 error ("ENTRY_BLOCK has IL associated with it");
5048 err = 1;
5051 if (EXIT_BLOCK_PTR_FOR_FN (cfun)->il.gimple.seq
5052 || EXIT_BLOCK_PTR_FOR_FN (cfun)->il.gimple.phi_nodes)
5054 error ("EXIT_BLOCK has IL associated with it");
5055 err = 1;
5058 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
5059 if (e->flags & EDGE_FALLTHRU)
5061 error ("fallthru to exit from bb %d", e->src->index);
5062 err = 1;
5065 FOR_EACH_BB_FN (bb, cfun)
5067 bool found_ctrl_stmt = false;
5069 stmt = NULL;
5071 /* Skip labels on the start of basic block. */
5072 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5074 tree label;
5075 gimple prev_stmt = stmt;
5077 stmt = gsi_stmt (gsi);
5079 if (gimple_code (stmt) != GIMPLE_LABEL)
5080 break;
5082 label = gimple_label_label (stmt);
5083 if (prev_stmt && DECL_NONLOCAL (label))
5085 error ("nonlocal label ");
5086 print_generic_expr (stderr, label, 0);
5087 fprintf (stderr, " is not first in a sequence of labels in bb %d",
5088 bb->index);
5089 err = 1;
5092 if (prev_stmt && EH_LANDING_PAD_NR (label) != 0)
5094 error ("EH landing pad label ");
5095 print_generic_expr (stderr, label, 0);
5096 fprintf (stderr, " is not first in a sequence of labels in bb %d",
5097 bb->index);
5098 err = 1;
5101 if (label_to_block (label) != bb)
5103 error ("label ");
5104 print_generic_expr (stderr, label, 0);
5105 fprintf (stderr, " to block does not match in bb %d",
5106 bb->index);
5107 err = 1;
5110 if (decl_function_context (label) != current_function_decl)
5112 error ("label ");
5113 print_generic_expr (stderr, label, 0);
5114 fprintf (stderr, " has incorrect context in bb %d",
5115 bb->index);
5116 err = 1;
5120 /* Verify that body of basic block BB is free of control flow. */
5121 for (; !gsi_end_p (gsi); gsi_next (&gsi))
5123 gimple stmt = gsi_stmt (gsi);
5125 if (found_ctrl_stmt)
5127 error ("control flow in the middle of basic block %d",
5128 bb->index);
5129 err = 1;
5132 if (stmt_ends_bb_p (stmt))
5133 found_ctrl_stmt = true;
5135 if (gimple_code (stmt) == GIMPLE_LABEL)
5137 error ("label ");
5138 print_generic_expr (stderr, gimple_label_label (stmt), 0);
5139 fprintf (stderr, " in the middle of basic block %d", bb->index);
5140 err = 1;
5144 gsi = gsi_last_bb (bb);
5145 if (gsi_end_p (gsi))
5146 continue;
5148 stmt = gsi_stmt (gsi);
5150 if (gimple_code (stmt) == GIMPLE_LABEL)
5151 continue;
5153 err |= verify_eh_edges (stmt);
5155 if (is_ctrl_stmt (stmt))
5157 FOR_EACH_EDGE (e, ei, bb->succs)
5158 if (e->flags & EDGE_FALLTHRU)
5160 error ("fallthru edge after a control statement in bb %d",
5161 bb->index);
5162 err = 1;
5166 if (gimple_code (stmt) != GIMPLE_COND)
5168 /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
5169 after anything else but if statement. */
5170 FOR_EACH_EDGE (e, ei, bb->succs)
5171 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
5173 error ("true/false edge after a non-GIMPLE_COND in bb %d",
5174 bb->index);
5175 err = 1;
5179 switch (gimple_code (stmt))
5181 case GIMPLE_COND:
5183 edge true_edge;
5184 edge false_edge;
5186 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
5188 if (!true_edge
5189 || !false_edge
5190 || !(true_edge->flags & EDGE_TRUE_VALUE)
5191 || !(false_edge->flags & EDGE_FALSE_VALUE)
5192 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
5193 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
5194 || EDGE_COUNT (bb->succs) >= 3)
5196 error ("wrong outgoing edge flags at end of bb %d",
5197 bb->index);
5198 err = 1;
5201 break;
5203 case GIMPLE_GOTO:
5204 if (simple_goto_p (stmt))
5206 error ("explicit goto at end of bb %d", bb->index);
5207 err = 1;
5209 else
5211 /* FIXME. We should double check that the labels in the
5212 destination blocks have their address taken. */
5213 FOR_EACH_EDGE (e, ei, bb->succs)
5214 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
5215 | EDGE_FALSE_VALUE))
5216 || !(e->flags & EDGE_ABNORMAL))
5218 error ("wrong outgoing edge flags at end of bb %d",
5219 bb->index);
5220 err = 1;
5223 break;
5225 case GIMPLE_CALL:
5226 if (!gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
5227 break;
5228 /* ... fallthru ... */
5229 case GIMPLE_RETURN:
5230 if (!single_succ_p (bb)
5231 || (single_succ_edge (bb)->flags
5232 & (EDGE_FALLTHRU | EDGE_ABNORMAL
5233 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
5235 error ("wrong outgoing edge flags at end of bb %d", bb->index);
5236 err = 1;
5238 if (single_succ (bb) != EXIT_BLOCK_PTR_FOR_FN (cfun))
5240 error ("return edge does not point to exit in bb %d",
5241 bb->index);
5242 err = 1;
5244 break;
5246 case GIMPLE_SWITCH:
5248 tree prev;
5249 edge e;
5250 size_t i, n;
5252 n = gimple_switch_num_labels (stmt);
5254 /* Mark all the destination basic blocks. */
5255 for (i = 0; i < n; ++i)
5257 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
5258 basic_block label_bb = label_to_block (lab);
5259 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
5260 label_bb->aux = (void *)1;
5263 /* Verify that the case labels are sorted. */
5264 prev = gimple_switch_label (stmt, 0);
5265 for (i = 1; i < n; ++i)
5267 tree c = gimple_switch_label (stmt, i);
5268 if (!CASE_LOW (c))
5270 error ("found default case not at the start of "
5271 "case vector");
5272 err = 1;
5273 continue;
5275 if (CASE_LOW (prev)
5276 && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
5278 error ("case labels not sorted: ");
5279 print_generic_expr (stderr, prev, 0);
5280 fprintf (stderr," is greater than ");
5281 print_generic_expr (stderr, c, 0);
5282 fprintf (stderr," but comes before it.\n");
5283 err = 1;
5285 prev = c;
5287 /* VRP will remove the default case if it can prove it will
5288 never be executed. So do not verify there always exists
5289 a default case here. */
5291 FOR_EACH_EDGE (e, ei, bb->succs)
5293 if (!e->dest->aux)
5295 error ("extra outgoing edge %d->%d",
5296 bb->index, e->dest->index);
5297 err = 1;
5300 e->dest->aux = (void *)2;
5301 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
5302 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
5304 error ("wrong outgoing edge flags at end of bb %d",
5305 bb->index);
5306 err = 1;
5310 /* Check that we have all of them. */
5311 for (i = 0; i < n; ++i)
5313 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
5314 basic_block label_bb = label_to_block (lab);
5316 if (label_bb->aux != (void *)2)
5318 error ("missing edge %i->%i", bb->index, label_bb->index);
5319 err = 1;
5323 FOR_EACH_EDGE (e, ei, bb->succs)
5324 e->dest->aux = (void *)0;
5326 break;
5328 case GIMPLE_EH_DISPATCH:
5329 err |= verify_eh_dispatch_edge (stmt);
5330 break;
5332 default:
5333 break;
5337 if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
5338 verify_dominators (CDI_DOMINATORS);
5340 return err;
5344 /* Updates phi nodes after creating a forwarder block joined
5345 by edge FALLTHRU. */
5347 static void
5348 gimple_make_forwarder_block (edge fallthru)
5350 edge e;
5351 edge_iterator ei;
5352 basic_block dummy, bb;
5353 tree var;
5354 gimple_stmt_iterator gsi;
5356 dummy = fallthru->src;
5357 bb = fallthru->dest;
5359 if (single_pred_p (bb))
5360 return;
5362 /* If we redirected a branch we must create new PHI nodes at the
5363 start of BB. */
5364 for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
5366 gimple phi, new_phi;
5368 phi = gsi_stmt (gsi);
5369 var = gimple_phi_result (phi);
5370 new_phi = create_phi_node (var, bb);
5371 gimple_phi_set_result (phi, copy_ssa_name (var, phi));
5372 add_phi_arg (new_phi, gimple_phi_result (phi), fallthru,
5373 UNKNOWN_LOCATION);
5376 /* Add the arguments we have stored on edges. */
5377 FOR_EACH_EDGE (e, ei, bb->preds)
5379 if (e == fallthru)
5380 continue;
5382 flush_pending_stmts (e);
5387 /* Return a non-special label in the head of basic block BLOCK.
5388 Create one if it doesn't exist. */
5390 tree
5391 gimple_block_label (basic_block bb)
5393 gimple_stmt_iterator i, s = gsi_start_bb (bb);
5394 bool first = true;
5395 tree label;
5396 gimple stmt;
5398 for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
5400 stmt = gsi_stmt (i);
5401 if (gimple_code (stmt) != GIMPLE_LABEL)
5402 break;
5403 label = gimple_label_label (stmt);
5404 if (!DECL_NONLOCAL (label))
5406 if (!first)
5407 gsi_move_before (&i, &s);
5408 return label;
5412 label = create_artificial_label (UNKNOWN_LOCATION);
5413 stmt = gimple_build_label (label);
5414 gsi_insert_before (&s, stmt, GSI_NEW_STMT);
5415 return label;
5419 /* Attempt to perform edge redirection by replacing a possibly complex
5420 jump instruction by a goto or by removing the jump completely.
5421 This can apply only if all edges now point to the same block. The
5422 parameters and return values are equivalent to
5423 redirect_edge_and_branch. */
5425 static edge
5426 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
5428 basic_block src = e->src;
5429 gimple_stmt_iterator i;
5430 gimple stmt;
5432 /* We can replace or remove a complex jump only when we have exactly
5433 two edges. */
5434 if (EDGE_COUNT (src->succs) != 2
5435 /* Verify that all targets will be TARGET. Specifically, the
5436 edge that is not E must also go to TARGET. */
5437 || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
5438 return NULL;
5440 i = gsi_last_bb (src);
5441 if (gsi_end_p (i))
5442 return NULL;
5444 stmt = gsi_stmt (i);
5446 if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
5448 gsi_remove (&i, true);
5449 e = ssa_redirect_edge (e, target);
5450 e->flags = EDGE_FALLTHRU;
5451 return e;
5454 return NULL;
5458 /* Redirect E to DEST. Return NULL on failure. Otherwise, return the
5459 edge representing the redirected branch. */
5461 static edge
5462 gimple_redirect_edge_and_branch (edge e, basic_block dest)
5464 basic_block bb = e->src;
5465 gimple_stmt_iterator gsi;
5466 edge ret;
5467 gimple stmt;
5469 if (e->flags & EDGE_ABNORMAL)
5470 return NULL;
5472 if (e->dest == dest)
5473 return NULL;
5475 if (e->flags & EDGE_EH)
5476 return redirect_eh_edge (e, dest);
5478 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
5480 ret = gimple_try_redirect_by_replacing_jump (e, dest);
5481 if (ret)
5482 return ret;
5485 gsi = gsi_last_bb (bb);
5486 stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
5488 switch (stmt ? gimple_code (stmt) : GIMPLE_ERROR_MARK)
5490 case GIMPLE_COND:
5491 /* For COND_EXPR, we only need to redirect the edge. */
5492 break;
5494 case GIMPLE_GOTO:
5495 /* No non-abnormal edges should lead from a non-simple goto, and
5496 simple ones should be represented implicitly. */
5497 gcc_unreachable ();
5499 case GIMPLE_SWITCH:
5501 tree label = gimple_block_label (dest);
5502 tree cases = get_cases_for_edge (e, stmt);
5504 /* If we have a list of cases associated with E, then use it
5505 as it's a lot faster than walking the entire case vector. */
5506 if (cases)
5508 edge e2 = find_edge (e->src, dest);
5509 tree last, first;
5511 first = cases;
5512 while (cases)
5514 last = cases;
5515 CASE_LABEL (cases) = label;
5516 cases = CASE_CHAIN (cases);
5519 /* If there was already an edge in the CFG, then we need
5520 to move all the cases associated with E to E2. */
5521 if (e2)
5523 tree cases2 = get_cases_for_edge (e2, stmt);
5525 CASE_CHAIN (last) = CASE_CHAIN (cases2);
5526 CASE_CHAIN (cases2) = first;
5528 bitmap_set_bit (touched_switch_bbs, gimple_bb (stmt)->index);
5530 else
5532 size_t i, n = gimple_switch_num_labels (stmt);
5534 for (i = 0; i < n; i++)
5536 tree elt = gimple_switch_label (stmt, i);
5537 if (label_to_block (CASE_LABEL (elt)) == e->dest)
5538 CASE_LABEL (elt) = label;
5542 break;
5544 case GIMPLE_ASM:
5546 int i, n = gimple_asm_nlabels (stmt);
5547 tree label = NULL;
5549 for (i = 0; i < n; ++i)
5551 tree cons = gimple_asm_label_op (stmt, i);
5552 if (label_to_block (TREE_VALUE (cons)) == e->dest)
5554 if (!label)
5555 label = gimple_block_label (dest);
5556 TREE_VALUE (cons) = label;
5560 /* If we didn't find any label matching the former edge in the
5561 asm labels, we must be redirecting the fallthrough
5562 edge. */
5563 gcc_assert (label || (e->flags & EDGE_FALLTHRU));
5565 break;
5567 case GIMPLE_RETURN:
5568 gsi_remove (&gsi, true);
5569 e->flags |= EDGE_FALLTHRU;
5570 break;
5572 case GIMPLE_OMP_RETURN:
5573 case GIMPLE_OMP_CONTINUE:
5574 case GIMPLE_OMP_SECTIONS_SWITCH:
5575 case GIMPLE_OMP_FOR:
5576 /* The edges from OMP constructs can be simply redirected. */
5577 break;
5579 case GIMPLE_EH_DISPATCH:
5580 if (!(e->flags & EDGE_FALLTHRU))
5581 redirect_eh_dispatch_edge (stmt, e, dest);
5582 break;
5584 case GIMPLE_TRANSACTION:
5585 /* The ABORT edge has a stored label associated with it, otherwise
5586 the edges are simply redirectable. */
5587 if (e->flags == 0)
5588 gimple_transaction_set_label (stmt, gimple_block_label (dest));
5589 break;
5591 default:
5592 /* Otherwise it must be a fallthru edge, and we don't need to
5593 do anything besides redirecting it. */
5594 gcc_assert (e->flags & EDGE_FALLTHRU);
5595 break;
5598 /* Update/insert PHI nodes as necessary. */
5600 /* Now update the edges in the CFG. */
5601 e = ssa_redirect_edge (e, dest);
5603 return e;
5606 /* Returns true if it is possible to remove edge E by redirecting
5607 it to the destination of the other edge from E->src. */
5609 static bool
5610 gimple_can_remove_branch_p (const_edge e)
5612 if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
5613 return false;
5615 return true;
5618 /* Simple wrapper, as we can always redirect fallthru edges. */
5620 static basic_block
5621 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
5623 e = gimple_redirect_edge_and_branch (e, dest);
5624 gcc_assert (e);
5626 return NULL;
5630 /* Splits basic block BB after statement STMT (but at least after the
5631 labels). If STMT is NULL, BB is split just after the labels. */
5633 static basic_block
5634 gimple_split_block (basic_block bb, void *stmt)
5636 gimple_stmt_iterator gsi;
5637 gimple_stmt_iterator gsi_tgt;
5638 gimple act;
5639 gimple_seq list;
5640 basic_block new_bb;
5641 edge e;
5642 edge_iterator ei;
5644 new_bb = create_empty_bb (bb);
5646 /* Redirect the outgoing edges. */
5647 new_bb->succs = bb->succs;
5648 bb->succs = NULL;
5649 FOR_EACH_EDGE (e, ei, new_bb->succs)
5650 e->src = new_bb;
5652 if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
5653 stmt = NULL;
5655 /* Move everything from GSI to the new basic block. */
5656 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5658 act = gsi_stmt (gsi);
5659 if (gimple_code (act) == GIMPLE_LABEL)
5660 continue;
5662 if (!stmt)
5663 break;
5665 if (stmt == act)
5667 gsi_next (&gsi);
5668 break;
5672 if (gsi_end_p (gsi))
5673 return new_bb;
5675 /* Split the statement list - avoid re-creating new containers as this
5676 brings ugly quadratic memory consumption in the inliner.
5677 (We are still quadratic since we need to update stmt BB pointers,
5678 sadly.) */
5679 gsi_split_seq_before (&gsi, &list);
5680 set_bb_seq (new_bb, list);
5681 for (gsi_tgt = gsi_start (list);
5682 !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
5683 gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
5685 return new_bb;
5689 /* Moves basic block BB after block AFTER. */
5691 static bool
5692 gimple_move_block_after (basic_block bb, basic_block after)
5694 if (bb->prev_bb == after)
5695 return true;
5697 unlink_block (bb);
5698 link_block (bb, after);
5700 return true;
5704 /* Return TRUE if block BB has no executable statements, otherwise return
5705 FALSE. */
5707 static bool
5708 gimple_empty_block_p (basic_block bb)
5710 /* BB must have no executable statements. */
5711 gimple_stmt_iterator gsi = gsi_after_labels (bb);
5712 if (phi_nodes (bb))
5713 return false;
5714 if (gsi_end_p (gsi))
5715 return true;
5716 if (is_gimple_debug (gsi_stmt (gsi)))
5717 gsi_next_nondebug (&gsi);
5718 return gsi_end_p (gsi);
5722 /* Split a basic block if it ends with a conditional branch and if the
5723 other part of the block is not empty. */
5725 static basic_block
5726 gimple_split_block_before_cond_jump (basic_block bb)
5728 gimple last, split_point;
5729 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
5730 if (gsi_end_p (gsi))
5731 return NULL;
5732 last = gsi_stmt (gsi);
5733 if (gimple_code (last) != GIMPLE_COND
5734 && gimple_code (last) != GIMPLE_SWITCH)
5735 return NULL;
5736 gsi_prev_nondebug (&gsi);
5737 split_point = gsi_stmt (gsi);
5738 return split_block (bb, split_point)->dest;
5742 /* Return true if basic_block can be duplicated. */
5744 static bool
5745 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5747 return true;
5750 /* Create a duplicate of the basic block BB. NOTE: This does not
5751 preserve SSA form. */
5753 static basic_block
5754 gimple_duplicate_bb (basic_block bb)
5756 basic_block new_bb;
5757 gimple_stmt_iterator gsi, gsi_tgt;
5758 gimple_seq phis = phi_nodes (bb);
5759 gimple phi, stmt, copy;
5761 new_bb = create_empty_bb (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
5763 /* Copy the PHI nodes. We ignore PHI node arguments here because
5764 the incoming edges have not been setup yet. */
5765 for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
5767 phi = gsi_stmt (gsi);
5768 copy = create_phi_node (NULL_TREE, new_bb);
5769 create_new_def_for (gimple_phi_result (phi), copy,
5770 gimple_phi_result_ptr (copy));
5771 gimple_set_uid (copy, gimple_uid (phi));
5774 gsi_tgt = gsi_start_bb (new_bb);
5775 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5777 def_operand_p def_p;
5778 ssa_op_iter op_iter;
5779 tree lhs;
5781 stmt = gsi_stmt (gsi);
5782 if (gimple_code (stmt) == GIMPLE_LABEL)
5783 continue;
5785 /* Don't duplicate label debug stmts. */
5786 if (gimple_debug_bind_p (stmt)
5787 && TREE_CODE (gimple_debug_bind_get_var (stmt))
5788 == LABEL_DECL)
5789 continue;
5791 /* Create a new copy of STMT and duplicate STMT's virtual
5792 operands. */
5793 copy = gimple_copy (stmt);
5794 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
5796 maybe_duplicate_eh_stmt (copy, stmt);
5797 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5799 /* When copying around a stmt writing into a local non-user
5800 aggregate, make sure it won't share stack slot with other
5801 vars. */
5802 lhs = gimple_get_lhs (stmt);
5803 if (lhs && TREE_CODE (lhs) != SSA_NAME)
5805 tree base = get_base_address (lhs);
5806 if (base
5807 && (TREE_CODE (base) == VAR_DECL
5808 || TREE_CODE (base) == RESULT_DECL)
5809 && DECL_IGNORED_P (base)
5810 && !TREE_STATIC (base)
5811 && !DECL_EXTERNAL (base)
5812 && (TREE_CODE (base) != VAR_DECL
5813 || !DECL_HAS_VALUE_EXPR_P (base)))
5814 DECL_NONSHAREABLE (base) = 1;
5817 /* Create new names for all the definitions created by COPY and
5818 add replacement mappings for each new name. */
5819 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5820 create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5823 return new_bb;
5826 /* Adds phi node arguments for edge E_COPY after basic block duplication. */
5828 static void
5829 add_phi_args_after_copy_edge (edge e_copy)
5831 basic_block bb, bb_copy = e_copy->src, dest;
5832 edge e;
5833 edge_iterator ei;
5834 gimple phi, phi_copy;
5835 tree def;
5836 gimple_stmt_iterator psi, psi_copy;
5838 if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
5839 return;
5841 bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5843 if (e_copy->dest->flags & BB_DUPLICATED)
5844 dest = get_bb_original (e_copy->dest);
5845 else
5846 dest = e_copy->dest;
5848 e = find_edge (bb, dest);
5849 if (!e)
5851 /* During loop unrolling the target of the latch edge is copied.
5852 In this case we are not looking for edge to dest, but to
5853 duplicated block whose original was dest. */
5854 FOR_EACH_EDGE (e, ei, bb->succs)
5856 if ((e->dest->flags & BB_DUPLICATED)
5857 && get_bb_original (e->dest) == dest)
5858 break;
5861 gcc_assert (e != NULL);
5864 for (psi = gsi_start_phis (e->dest),
5865 psi_copy = gsi_start_phis (e_copy->dest);
5866 !gsi_end_p (psi);
5867 gsi_next (&psi), gsi_next (&psi_copy))
5869 phi = gsi_stmt (psi);
5870 phi_copy = gsi_stmt (psi_copy);
5871 def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5872 add_phi_arg (phi_copy, def, e_copy,
5873 gimple_phi_arg_location_from_edge (phi, e));
5878 /* Basic block BB_COPY was created by code duplication. Add phi node
5879 arguments for edges going out of BB_COPY. The blocks that were
5880 duplicated have BB_DUPLICATED set. */
5882 void
5883 add_phi_args_after_copy_bb (basic_block bb_copy)
5885 edge e_copy;
5886 edge_iterator ei;
5888 FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5890 add_phi_args_after_copy_edge (e_copy);
5894 /* Blocks in REGION_COPY array of length N_REGION were created by
5895 duplication of basic blocks. Add phi node arguments for edges
5896 going from these blocks. If E_COPY is not NULL, also add
5897 phi node arguments for its destination.*/
5899 void
5900 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5901 edge e_copy)
5903 unsigned i;
5905 for (i = 0; i < n_region; i++)
5906 region_copy[i]->flags |= BB_DUPLICATED;
5908 for (i = 0; i < n_region; i++)
5909 add_phi_args_after_copy_bb (region_copy[i]);
5910 if (e_copy)
5911 add_phi_args_after_copy_edge (e_copy);
5913 for (i = 0; i < n_region; i++)
5914 region_copy[i]->flags &= ~BB_DUPLICATED;
5917 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5918 important exit edge EXIT. By important we mean that no SSA name defined
5919 inside region is live over the other exit edges of the region. All entry
5920 edges to the region must go to ENTRY->dest. The edge ENTRY is redirected
5921 to the duplicate of the region. Dominance and loop information is
5922 updated if UPDATE_DOMINANCE is true, but not the SSA web. If
5923 UPDATE_DOMINANCE is false then we assume that the caller will update the
5924 dominance information after calling this function. The new basic
5925 blocks are stored to REGION_COPY in the same order as they had in REGION,
5926 provided that REGION_COPY is not NULL.
5927 The function returns false if it is unable to copy the region,
5928 true otherwise. */
5930 bool
5931 gimple_duplicate_sese_region (edge entry, edge exit,
5932 basic_block *region, unsigned n_region,
5933 basic_block *region_copy,
5934 bool update_dominance)
5936 unsigned i;
5937 bool free_region_copy = false, copying_header = false;
5938 struct loop *loop = entry->dest->loop_father;
5939 edge exit_copy;
5940 vec<basic_block> doms;
5941 edge redirected;
5942 int total_freq = 0, entry_freq = 0;
5943 gcov_type total_count = 0, entry_count = 0;
5945 if (!can_copy_bbs_p (region, n_region))
5946 return false;
5948 /* Some sanity checking. Note that we do not check for all possible
5949 missuses of the functions. I.e. if you ask to copy something weird,
5950 it will work, but the state of structures probably will not be
5951 correct. */
5952 for (i = 0; i < n_region; i++)
5954 /* We do not handle subloops, i.e. all the blocks must belong to the
5955 same loop. */
5956 if (region[i]->loop_father != loop)
5957 return false;
5959 if (region[i] != entry->dest
5960 && region[i] == loop->header)
5961 return false;
5964 /* In case the function is used for loop header copying (which is the primary
5965 use), ensure that EXIT and its copy will be new latch and entry edges. */
5966 if (loop->header == entry->dest)
5968 copying_header = true;
5970 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5971 return false;
5973 for (i = 0; i < n_region; i++)
5974 if (region[i] != exit->src
5975 && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5976 return false;
5979 initialize_original_copy_tables ();
5981 if (copying_header)
5982 set_loop_copy (loop, loop_outer (loop));
5983 else
5984 set_loop_copy (loop, loop);
5986 if (!region_copy)
5988 region_copy = XNEWVEC (basic_block, n_region);
5989 free_region_copy = true;
5992 /* Record blocks outside the region that are dominated by something
5993 inside. */
5994 if (update_dominance)
5996 doms.create (0);
5997 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
6000 if (entry->dest->count)
6002 total_count = entry->dest->count;
6003 entry_count = entry->count;
6004 /* Fix up corner cases, to avoid division by zero or creation of negative
6005 frequencies. */
6006 if (entry_count > total_count)
6007 entry_count = total_count;
6009 else
6011 total_freq = entry->dest->frequency;
6012 entry_freq = EDGE_FREQUENCY (entry);
6013 /* Fix up corner cases, to avoid division by zero or creation of negative
6014 frequencies. */
6015 if (total_freq == 0)
6016 total_freq = 1;
6017 else if (entry_freq > total_freq)
6018 entry_freq = total_freq;
6021 copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
6022 split_edge_bb_loc (entry), update_dominance);
6023 if (total_count)
6025 scale_bbs_frequencies_gcov_type (region, n_region,
6026 total_count - entry_count,
6027 total_count);
6028 scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
6029 total_count);
6031 else
6033 scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
6034 total_freq);
6035 scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
6038 if (copying_header)
6040 loop->header = exit->dest;
6041 loop->latch = exit->src;
6044 /* Redirect the entry and add the phi node arguments. */
6045 redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
6046 gcc_assert (redirected != NULL);
6047 flush_pending_stmts (entry);
6049 /* Concerning updating of dominators: We must recount dominators
6050 for entry block and its copy. Anything that is outside of the
6051 region, but was dominated by something inside needs recounting as
6052 well. */
6053 if (update_dominance)
6055 set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
6056 doms.safe_push (get_bb_original (entry->dest));
6057 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
6058 doms.release ();
6061 /* Add the other PHI node arguments. */
6062 add_phi_args_after_copy (region_copy, n_region, NULL);
6064 if (free_region_copy)
6065 free (region_copy);
6067 free_original_copy_tables ();
6068 return true;
6071 /* Checks if BB is part of the region defined by N_REGION BBS. */
6072 static bool
6073 bb_part_of_region_p (basic_block bb, basic_block* bbs, unsigned n_region)
6075 unsigned int n;
6077 for (n = 0; n < n_region; n++)
6079 if (bb == bbs[n])
6080 return true;
6082 return false;
6085 /* Duplicates REGION consisting of N_REGION blocks. The new blocks
6086 are stored to REGION_COPY in the same order in that they appear
6087 in REGION, if REGION_COPY is not NULL. ENTRY is the entry to
6088 the region, EXIT an exit from it. The condition guarding EXIT
6089 is moved to ENTRY. Returns true if duplication succeeds, false
6090 otherwise.
6092 For example,
6094 some_code;
6095 if (cond)
6097 else
6100 is transformed to
6102 if (cond)
6104 some_code;
6107 else
6109 some_code;
6114 bool
6115 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
6116 basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
6117 basic_block *region_copy ATTRIBUTE_UNUSED)
6119 unsigned i;
6120 bool free_region_copy = false;
6121 struct loop *loop = exit->dest->loop_father;
6122 struct loop *orig_loop = entry->dest->loop_father;
6123 basic_block switch_bb, entry_bb, nentry_bb;
6124 vec<basic_block> doms;
6125 int total_freq = 0, exit_freq = 0;
6126 gcov_type total_count = 0, exit_count = 0;
6127 edge exits[2], nexits[2], e;
6128 gimple_stmt_iterator gsi;
6129 gimple cond_stmt;
6130 edge sorig, snew;
6131 basic_block exit_bb;
6132 gimple_stmt_iterator psi;
6133 gimple phi;
6134 tree def;
6135 struct loop *target, *aloop, *cloop;
6137 gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
6138 exits[0] = exit;
6139 exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
6141 if (!can_copy_bbs_p (region, n_region))
6142 return false;
6144 initialize_original_copy_tables ();
6145 set_loop_copy (orig_loop, loop);
6147 target= loop;
6148 for (aloop = orig_loop->inner; aloop; aloop = aloop->next)
6150 if (bb_part_of_region_p (aloop->header, region, n_region))
6152 cloop = duplicate_loop (aloop, target);
6153 duplicate_subloops (aloop, cloop);
6157 if (!region_copy)
6159 region_copy = XNEWVEC (basic_block, n_region);
6160 free_region_copy = true;
6163 gcc_assert (!need_ssa_update_p (cfun));
6165 /* Record blocks outside the region that are dominated by something
6166 inside. */
6167 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
6169 if (exit->src->count)
6171 total_count = exit->src->count;
6172 exit_count = exit->count;
6173 /* Fix up corner cases, to avoid division by zero or creation of negative
6174 frequencies. */
6175 if (exit_count > total_count)
6176 exit_count = total_count;
6178 else
6180 total_freq = exit->src->frequency;
6181 exit_freq = EDGE_FREQUENCY (exit);
6182 /* Fix up corner cases, to avoid division by zero or creation of negative
6183 frequencies. */
6184 if (total_freq == 0)
6185 total_freq = 1;
6186 if (exit_freq > total_freq)
6187 exit_freq = total_freq;
6190 copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
6191 split_edge_bb_loc (exit), true);
6192 if (total_count)
6194 scale_bbs_frequencies_gcov_type (region, n_region,
6195 total_count - exit_count,
6196 total_count);
6197 scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
6198 total_count);
6200 else
6202 scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
6203 total_freq);
6204 scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
6207 /* Create the switch block, and put the exit condition to it. */
6208 entry_bb = entry->dest;
6209 nentry_bb = get_bb_copy (entry_bb);
6210 if (!last_stmt (entry->src)
6211 || !stmt_ends_bb_p (last_stmt (entry->src)))
6212 switch_bb = entry->src;
6213 else
6214 switch_bb = split_edge (entry);
6215 set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
6217 gsi = gsi_last_bb (switch_bb);
6218 cond_stmt = last_stmt (exit->src);
6219 gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
6220 cond_stmt = gimple_copy (cond_stmt);
6222 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
6224 sorig = single_succ_edge (switch_bb);
6225 sorig->flags = exits[1]->flags;
6226 snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
6228 /* Register the new edge from SWITCH_BB in loop exit lists. */
6229 rescan_loop_exit (snew, true, false);
6231 /* Add the PHI node arguments. */
6232 add_phi_args_after_copy (region_copy, n_region, snew);
6234 /* Get rid of now superfluous conditions and associated edges (and phi node
6235 arguments). */
6236 exit_bb = exit->dest;
6238 e = redirect_edge_and_branch (exits[0], exits[1]->dest);
6239 PENDING_STMT (e) = NULL;
6241 /* The latch of ORIG_LOOP was copied, and so was the backedge
6242 to the original header. We redirect this backedge to EXIT_BB. */
6243 for (i = 0; i < n_region; i++)
6244 if (get_bb_original (region_copy[i]) == orig_loop->latch)
6246 gcc_assert (single_succ_edge (region_copy[i]));
6247 e = redirect_edge_and_branch (single_succ_edge (region_copy[i]), exit_bb);
6248 PENDING_STMT (e) = NULL;
6249 for (psi = gsi_start_phis (exit_bb);
6250 !gsi_end_p (psi);
6251 gsi_next (&psi))
6253 phi = gsi_stmt (psi);
6254 def = PHI_ARG_DEF (phi, nexits[0]->dest_idx);
6255 add_phi_arg (phi, def, e, gimple_phi_arg_location_from_edge (phi, e));
6258 e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
6259 PENDING_STMT (e) = NULL;
6261 /* Anything that is outside of the region, but was dominated by something
6262 inside needs to update dominance info. */
6263 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
6264 doms.release ();
6265 /* Update the SSA web. */
6266 update_ssa (TODO_update_ssa);
6268 if (free_region_copy)
6269 free (region_copy);
6271 free_original_copy_tables ();
6272 return true;
6275 /* Add all the blocks dominated by ENTRY to the array BBS_P. Stop
6276 adding blocks when the dominator traversal reaches EXIT. This
6277 function silently assumes that ENTRY strictly dominates EXIT. */
6279 void
6280 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
6281 vec<basic_block> *bbs_p)
6283 basic_block son;
6285 for (son = first_dom_son (CDI_DOMINATORS, entry);
6286 son;
6287 son = next_dom_son (CDI_DOMINATORS, son))
6289 bbs_p->safe_push (son);
6290 if (son != exit)
6291 gather_blocks_in_sese_region (son, exit, bbs_p);
6295 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
6296 The duplicates are recorded in VARS_MAP. */
6298 static void
6299 replace_by_duplicate_decl (tree *tp, hash_map<tree, tree> *vars_map,
6300 tree to_context)
6302 tree t = *tp, new_t;
6303 struct function *f = DECL_STRUCT_FUNCTION (to_context);
6305 if (DECL_CONTEXT (t) == to_context)
6306 return;
6308 bool existed;
6309 tree &loc = vars_map->get_or_insert (t, &existed);
6311 if (!existed)
6313 if (SSA_VAR_P (t))
6315 new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
6316 add_local_decl (f, new_t);
6318 else
6320 gcc_assert (TREE_CODE (t) == CONST_DECL);
6321 new_t = copy_node (t);
6323 DECL_CONTEXT (new_t) = to_context;
6325 loc = new_t;
6327 else
6328 new_t = loc;
6330 *tp = new_t;
6334 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
6335 VARS_MAP maps old ssa names and var_decls to the new ones. */
6337 static tree
6338 replace_ssa_name (tree name, hash_map<tree, tree> *vars_map,
6339 tree to_context)
6341 tree new_name;
6343 gcc_assert (!virtual_operand_p (name));
6345 tree *loc = vars_map->get (name);
6347 if (!loc)
6349 tree decl = SSA_NAME_VAR (name);
6350 if (decl)
6352 replace_by_duplicate_decl (&decl, vars_map, to_context);
6353 new_name = make_ssa_name_fn (DECL_STRUCT_FUNCTION (to_context),
6354 decl, SSA_NAME_DEF_STMT (name));
6355 if (SSA_NAME_IS_DEFAULT_DEF (name))
6356 set_ssa_default_def (DECL_STRUCT_FUNCTION (to_context),
6357 decl, new_name);
6359 else
6360 new_name = copy_ssa_name_fn (DECL_STRUCT_FUNCTION (to_context),
6361 name, SSA_NAME_DEF_STMT (name));
6363 vars_map->put (name, new_name);
6365 else
6366 new_name = *loc;
6368 return new_name;
6371 struct move_stmt_d
6373 tree orig_block;
6374 tree new_block;
6375 tree from_context;
6376 tree to_context;
6377 hash_map<tree, tree> *vars_map;
6378 htab_t new_label_map;
6379 hash_map<void *, void *> *eh_map;
6380 bool remap_decls_p;
6383 /* Helper for move_block_to_fn. Set TREE_BLOCK in every expression
6384 contained in *TP if it has been ORIG_BLOCK previously and change the
6385 DECL_CONTEXT of every local variable referenced in *TP. */
6387 static tree
6388 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
6390 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
6391 struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
6392 tree t = *tp;
6394 if (EXPR_P (t))
6396 tree block = TREE_BLOCK (t);
6397 if (block == p->orig_block
6398 || (p->orig_block == NULL_TREE
6399 && block != NULL_TREE))
6400 TREE_SET_BLOCK (t, p->new_block);
6401 #ifdef ENABLE_CHECKING
6402 else if (block != NULL_TREE)
6404 while (block && TREE_CODE (block) == BLOCK && block != p->orig_block)
6405 block = BLOCK_SUPERCONTEXT (block);
6406 gcc_assert (block == p->orig_block);
6408 #endif
6410 else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
6412 if (TREE_CODE (t) == SSA_NAME)
6413 *tp = replace_ssa_name (t, p->vars_map, p->to_context);
6414 else if (TREE_CODE (t) == LABEL_DECL)
6416 if (p->new_label_map)
6418 struct tree_map in, *out;
6419 in.base.from = t;
6420 out = (struct tree_map *)
6421 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
6422 if (out)
6423 *tp = t = out->to;
6426 DECL_CONTEXT (t) = p->to_context;
6428 else if (p->remap_decls_p)
6430 /* Replace T with its duplicate. T should no longer appear in the
6431 parent function, so this looks wasteful; however, it may appear
6432 in referenced_vars, and more importantly, as virtual operands of
6433 statements, and in alias lists of other variables. It would be
6434 quite difficult to expunge it from all those places. ??? It might
6435 suffice to do this for addressable variables. */
6436 if ((TREE_CODE (t) == VAR_DECL
6437 && !is_global_var (t))
6438 || TREE_CODE (t) == CONST_DECL)
6439 replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
6441 *walk_subtrees = 0;
6443 else if (TYPE_P (t))
6444 *walk_subtrees = 0;
6446 return NULL_TREE;
6449 /* Helper for move_stmt_r. Given an EH region number for the source
6450 function, map that to the duplicate EH regio number in the dest. */
6452 static int
6453 move_stmt_eh_region_nr (int old_nr, struct move_stmt_d *p)
6455 eh_region old_r, new_r;
6457 old_r = get_eh_region_from_number (old_nr);
6458 new_r = static_cast<eh_region> (*p->eh_map->get (old_r));
6460 return new_r->index;
6463 /* Similar, but operate on INTEGER_CSTs. */
6465 static tree
6466 move_stmt_eh_region_tree_nr (tree old_t_nr, struct move_stmt_d *p)
6468 int old_nr, new_nr;
6470 old_nr = tree_to_shwi (old_t_nr);
6471 new_nr = move_stmt_eh_region_nr (old_nr, p);
6473 return build_int_cst (integer_type_node, new_nr);
6476 /* Like move_stmt_op, but for gimple statements.
6478 Helper for move_block_to_fn. Set GIMPLE_BLOCK in every expression
6479 contained in the current statement in *GSI_P and change the
6480 DECL_CONTEXT of every local variable referenced in the current
6481 statement. */
6483 static tree
6484 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
6485 struct walk_stmt_info *wi)
6487 struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
6488 gimple stmt = gsi_stmt (*gsi_p);
6489 tree block = gimple_block (stmt);
6491 if (block == p->orig_block
6492 || (p->orig_block == NULL_TREE
6493 && block != NULL_TREE))
6494 gimple_set_block (stmt, p->new_block);
6496 switch (gimple_code (stmt))
6498 case GIMPLE_CALL:
6499 /* Remap the region numbers for __builtin_eh_{pointer,filter}. */
6501 tree r, fndecl = gimple_call_fndecl (stmt);
6502 if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
6503 switch (DECL_FUNCTION_CODE (fndecl))
6505 case BUILT_IN_EH_COPY_VALUES:
6506 r = gimple_call_arg (stmt, 1);
6507 r = move_stmt_eh_region_tree_nr (r, p);
6508 gimple_call_set_arg (stmt, 1, r);
6509 /* FALLTHRU */
6511 case BUILT_IN_EH_POINTER:
6512 case BUILT_IN_EH_FILTER:
6513 r = gimple_call_arg (stmt, 0);
6514 r = move_stmt_eh_region_tree_nr (r, p);
6515 gimple_call_set_arg (stmt, 0, r);
6516 break;
6518 default:
6519 break;
6522 break;
6524 case GIMPLE_RESX:
6526 int r = gimple_resx_region (stmt);
6527 r = move_stmt_eh_region_nr (r, p);
6528 gimple_resx_set_region (stmt, r);
6530 break;
6532 case GIMPLE_EH_DISPATCH:
6534 int r = gimple_eh_dispatch_region (stmt);
6535 r = move_stmt_eh_region_nr (r, p);
6536 gimple_eh_dispatch_set_region (stmt, r);
6538 break;
6540 case GIMPLE_OMP_RETURN:
6541 case GIMPLE_OMP_CONTINUE:
6542 break;
6543 default:
6544 if (is_gimple_omp (stmt))
6546 /* Do not remap variables inside OMP directives. Variables
6547 referenced in clauses and directive header belong to the
6548 parent function and should not be moved into the child
6549 function. */
6550 bool save_remap_decls_p = p->remap_decls_p;
6551 p->remap_decls_p = false;
6552 *handled_ops_p = true;
6554 walk_gimple_seq_mod (gimple_omp_body_ptr (stmt), move_stmt_r,
6555 move_stmt_op, wi);
6557 p->remap_decls_p = save_remap_decls_p;
6559 break;
6562 return NULL_TREE;
6565 /* Move basic block BB from function CFUN to function DEST_FN. The
6566 block is moved out of the original linked list and placed after
6567 block AFTER in the new list. Also, the block is removed from the
6568 original array of blocks and placed in DEST_FN's array of blocks.
6569 If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
6570 updated to reflect the moved edges.
6572 The local variables are remapped to new instances, VARS_MAP is used
6573 to record the mapping. */
6575 static void
6576 move_block_to_fn (struct function *dest_cfun, basic_block bb,
6577 basic_block after, bool update_edge_count_p,
6578 struct move_stmt_d *d)
6580 struct control_flow_graph *cfg;
6581 edge_iterator ei;
6582 edge e;
6583 gimple_stmt_iterator si;
6584 unsigned old_len, new_len;
6586 /* Remove BB from dominance structures. */
6587 delete_from_dominance_info (CDI_DOMINATORS, bb);
6589 /* Move BB from its current loop to the copy in the new function. */
6590 if (current_loops)
6592 struct loop *new_loop = (struct loop *)bb->loop_father->aux;
6593 if (new_loop)
6594 bb->loop_father = new_loop;
6597 /* Link BB to the new linked list. */
6598 move_block_after (bb, after);
6600 /* Update the edge count in the corresponding flowgraphs. */
6601 if (update_edge_count_p)
6602 FOR_EACH_EDGE (e, ei, bb->succs)
6604 cfun->cfg->x_n_edges--;
6605 dest_cfun->cfg->x_n_edges++;
6608 /* Remove BB from the original basic block array. */
6609 (*cfun->cfg->x_basic_block_info)[bb->index] = NULL;
6610 cfun->cfg->x_n_basic_blocks--;
6612 /* Grow DEST_CFUN's basic block array if needed. */
6613 cfg = dest_cfun->cfg;
6614 cfg->x_n_basic_blocks++;
6615 if (bb->index >= cfg->x_last_basic_block)
6616 cfg->x_last_basic_block = bb->index + 1;
6618 old_len = vec_safe_length (cfg->x_basic_block_info);
6619 if ((unsigned) cfg->x_last_basic_block >= old_len)
6621 new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
6622 vec_safe_grow_cleared (cfg->x_basic_block_info, new_len);
6625 (*cfg->x_basic_block_info)[bb->index] = bb;
6627 /* Remap the variables in phi nodes. */
6628 for (si = gsi_start_phis (bb); !gsi_end_p (si); )
6630 gimple phi = gsi_stmt (si);
6631 use_operand_p use;
6632 tree op = PHI_RESULT (phi);
6633 ssa_op_iter oi;
6634 unsigned i;
6636 if (virtual_operand_p (op))
6638 /* Remove the phi nodes for virtual operands (alias analysis will be
6639 run for the new function, anyway). */
6640 remove_phi_node (&si, true);
6641 continue;
6644 SET_PHI_RESULT (phi,
6645 replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6646 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
6648 op = USE_FROM_PTR (use);
6649 if (TREE_CODE (op) == SSA_NAME)
6650 SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6653 for (i = 0; i < EDGE_COUNT (bb->preds); i++)
6655 location_t locus = gimple_phi_arg_location (phi, i);
6656 tree block = LOCATION_BLOCK (locus);
6658 if (locus == UNKNOWN_LOCATION)
6659 continue;
6660 if (d->orig_block == NULL_TREE || block == d->orig_block)
6662 if (d->new_block == NULL_TREE)
6663 locus = LOCATION_LOCUS (locus);
6664 else
6665 locus = COMBINE_LOCATION_DATA (line_table, locus, d->new_block);
6666 gimple_phi_arg_set_location (phi, i, locus);
6670 gsi_next (&si);
6673 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6675 gimple stmt = gsi_stmt (si);
6676 struct walk_stmt_info wi;
6678 memset (&wi, 0, sizeof (wi));
6679 wi.info = d;
6680 walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
6682 if (gimple_code (stmt) == GIMPLE_LABEL)
6684 tree label = gimple_label_label (stmt);
6685 int uid = LABEL_DECL_UID (label);
6687 gcc_assert (uid > -1);
6689 old_len = vec_safe_length (cfg->x_label_to_block_map);
6690 if (old_len <= (unsigned) uid)
6692 new_len = 3 * uid / 2 + 1;
6693 vec_safe_grow_cleared (cfg->x_label_to_block_map, new_len);
6696 (*cfg->x_label_to_block_map)[uid] = bb;
6697 (*cfun->cfg->x_label_to_block_map)[uid] = NULL;
6699 gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
6701 if (uid >= dest_cfun->cfg->last_label_uid)
6702 dest_cfun->cfg->last_label_uid = uid + 1;
6705 maybe_duplicate_eh_stmt_fn (dest_cfun, stmt, cfun, stmt, d->eh_map, 0);
6706 remove_stmt_from_eh_lp_fn (cfun, stmt);
6708 gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
6709 gimple_remove_stmt_histograms (cfun, stmt);
6711 /* We cannot leave any operands allocated from the operand caches of
6712 the current function. */
6713 free_stmt_operands (cfun, stmt);
6714 push_cfun (dest_cfun);
6715 update_stmt (stmt);
6716 pop_cfun ();
6719 FOR_EACH_EDGE (e, ei, bb->succs)
6720 if (e->goto_locus != UNKNOWN_LOCATION)
6722 tree block = LOCATION_BLOCK (e->goto_locus);
6723 if (d->orig_block == NULL_TREE
6724 || block == d->orig_block)
6725 e->goto_locus = d->new_block ?
6726 COMBINE_LOCATION_DATA (line_table, e->goto_locus, d->new_block) :
6727 LOCATION_LOCUS (e->goto_locus);
6731 /* Examine the statements in BB (which is in SRC_CFUN); find and return
6732 the outermost EH region. Use REGION as the incoming base EH region. */
6734 static eh_region
6735 find_outermost_region_in_block (struct function *src_cfun,
6736 basic_block bb, eh_region region)
6738 gimple_stmt_iterator si;
6740 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6742 gimple stmt = gsi_stmt (si);
6743 eh_region stmt_region;
6744 int lp_nr;
6746 lp_nr = lookup_stmt_eh_lp_fn (src_cfun, stmt);
6747 stmt_region = get_eh_region_from_lp_number_fn (src_cfun, lp_nr);
6748 if (stmt_region)
6750 if (region == NULL)
6751 region = stmt_region;
6752 else if (stmt_region != region)
6754 region = eh_region_outermost (src_cfun, stmt_region, region);
6755 gcc_assert (region != NULL);
6760 return region;
6763 static tree
6764 new_label_mapper (tree decl, void *data)
6766 htab_t hash = (htab_t) data;
6767 struct tree_map *m;
6768 void **slot;
6770 gcc_assert (TREE_CODE (decl) == LABEL_DECL);
6772 m = XNEW (struct tree_map);
6773 m->hash = DECL_UID (decl);
6774 m->base.from = decl;
6775 m->to = create_artificial_label (UNKNOWN_LOCATION);
6776 LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
6777 if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
6778 cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
6780 slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
6781 gcc_assert (*slot == NULL);
6783 *slot = m;
6785 return m->to;
6788 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
6789 subblocks. */
6791 static void
6792 replace_block_vars_by_duplicates (tree block, hash_map<tree, tree> *vars_map,
6793 tree to_context)
6795 tree *tp, t;
6797 for (tp = &BLOCK_VARS (block); *tp; tp = &DECL_CHAIN (*tp))
6799 t = *tp;
6800 if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL)
6801 continue;
6802 replace_by_duplicate_decl (&t, vars_map, to_context);
6803 if (t != *tp)
6805 if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
6807 SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
6808 DECL_HAS_VALUE_EXPR_P (t) = 1;
6810 DECL_CHAIN (t) = DECL_CHAIN (*tp);
6811 *tp = t;
6815 for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
6816 replace_block_vars_by_duplicates (block, vars_map, to_context);
6819 /* Fixup the loop arrays and numbers after moving LOOP and its subloops
6820 from FN1 to FN2. */
6822 static void
6823 fixup_loop_arrays_after_move (struct function *fn1, struct function *fn2,
6824 struct loop *loop)
6826 /* Discard it from the old loop array. */
6827 (*get_loops (fn1))[loop->num] = NULL;
6829 /* Place it in the new loop array, assigning it a new number. */
6830 loop->num = number_of_loops (fn2);
6831 vec_safe_push (loops_for_fn (fn2)->larray, loop);
6833 /* Recurse to children. */
6834 for (loop = loop->inner; loop; loop = loop->next)
6835 fixup_loop_arrays_after_move (fn1, fn2, loop);
6838 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
6839 EXIT_BB to function DEST_CFUN. The whole region is replaced by a
6840 single basic block in the original CFG and the new basic block is
6841 returned. DEST_CFUN must not have a CFG yet.
6843 Note that the region need not be a pure SESE region. Blocks inside
6844 the region may contain calls to abort/exit. The only restriction
6845 is that ENTRY_BB should be the only entry point and it must
6846 dominate EXIT_BB.
6848 Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
6849 functions outermost BLOCK, move all subblocks of ORIG_BLOCK
6850 to the new function.
6852 All local variables referenced in the region are assumed to be in
6853 the corresponding BLOCK_VARS and unexpanded variable lists
6854 associated with DEST_CFUN. */
6856 basic_block
6857 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
6858 basic_block exit_bb, tree orig_block)
6860 vec<basic_block> bbs, dom_bbs;
6861 basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
6862 basic_block after, bb, *entry_pred, *exit_succ, abb;
6863 struct function *saved_cfun = cfun;
6864 int *entry_flag, *exit_flag;
6865 unsigned *entry_prob, *exit_prob;
6866 unsigned i, num_entry_edges, num_exit_edges, num_nodes;
6867 edge e;
6868 edge_iterator ei;
6869 htab_t new_label_map;
6870 hash_map<void *, void *> *eh_map;
6871 struct loop *loop = entry_bb->loop_father;
6872 struct loop *loop0 = get_loop (saved_cfun, 0);
6873 struct move_stmt_d d;
6875 /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
6876 region. */
6877 gcc_assert (entry_bb != exit_bb
6878 && (!exit_bb
6879 || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
6881 /* Collect all the blocks in the region. Manually add ENTRY_BB
6882 because it won't be added by dfs_enumerate_from. */
6883 bbs.create (0);
6884 bbs.safe_push (entry_bb);
6885 gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
6887 /* The blocks that used to be dominated by something in BBS will now be
6888 dominated by the new block. */
6889 dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
6890 bbs.address (),
6891 bbs.length ());
6893 /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG. We need to remember
6894 the predecessor edges to ENTRY_BB and the successor edges to
6895 EXIT_BB so that we can re-attach them to the new basic block that
6896 will replace the region. */
6897 num_entry_edges = EDGE_COUNT (entry_bb->preds);
6898 entry_pred = XNEWVEC (basic_block, num_entry_edges);
6899 entry_flag = XNEWVEC (int, num_entry_edges);
6900 entry_prob = XNEWVEC (unsigned, num_entry_edges);
6901 i = 0;
6902 for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
6904 entry_prob[i] = e->probability;
6905 entry_flag[i] = e->flags;
6906 entry_pred[i++] = e->src;
6907 remove_edge (e);
6910 if (exit_bb)
6912 num_exit_edges = EDGE_COUNT (exit_bb->succs);
6913 exit_succ = XNEWVEC (basic_block, num_exit_edges);
6914 exit_flag = XNEWVEC (int, num_exit_edges);
6915 exit_prob = XNEWVEC (unsigned, num_exit_edges);
6916 i = 0;
6917 for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6919 exit_prob[i] = e->probability;
6920 exit_flag[i] = e->flags;
6921 exit_succ[i++] = e->dest;
6922 remove_edge (e);
6925 else
6927 num_exit_edges = 0;
6928 exit_succ = NULL;
6929 exit_flag = NULL;
6930 exit_prob = NULL;
6933 /* Switch context to the child function to initialize DEST_FN's CFG. */
6934 gcc_assert (dest_cfun->cfg == NULL);
6935 push_cfun (dest_cfun);
6937 init_empty_tree_cfg ();
6939 /* Initialize EH information for the new function. */
6940 eh_map = NULL;
6941 new_label_map = NULL;
6942 if (saved_cfun->eh)
6944 eh_region region = NULL;
6946 FOR_EACH_VEC_ELT (bbs, i, bb)
6947 region = find_outermost_region_in_block (saved_cfun, bb, region);
6949 init_eh_for_function ();
6950 if (region != NULL)
6952 new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6953 eh_map = duplicate_eh_regions (saved_cfun, region, 0,
6954 new_label_mapper, new_label_map);
6958 /* Initialize an empty loop tree. */
6959 struct loops *loops = ggc_cleared_alloc<struct loops> ();
6960 init_loops_structure (dest_cfun, loops, 1);
6961 loops->state = LOOPS_MAY_HAVE_MULTIPLE_LATCHES;
6962 set_loops_for_fn (dest_cfun, loops);
6964 /* Move the outlined loop tree part. */
6965 num_nodes = bbs.length ();
6966 FOR_EACH_VEC_ELT (bbs, i, bb)
6968 if (bb->loop_father->header == bb)
6970 struct loop *this_loop = bb->loop_father;
6971 struct loop *outer = loop_outer (this_loop);
6972 if (outer == loop
6973 /* If the SESE region contains some bbs ending with
6974 a noreturn call, those are considered to belong
6975 to the outermost loop in saved_cfun, rather than
6976 the entry_bb's loop_father. */
6977 || outer == loop0)
6979 if (outer != loop)
6980 num_nodes -= this_loop->num_nodes;
6981 flow_loop_tree_node_remove (bb->loop_father);
6982 flow_loop_tree_node_add (get_loop (dest_cfun, 0), this_loop);
6983 fixup_loop_arrays_after_move (saved_cfun, cfun, this_loop);
6986 else if (bb->loop_father == loop0 && loop0 != loop)
6987 num_nodes--;
6989 /* Remove loop exits from the outlined region. */
6990 if (loops_for_fn (saved_cfun)->exits)
6991 FOR_EACH_EDGE (e, ei, bb->succs)
6993 struct loops *l = loops_for_fn (saved_cfun);
6994 loop_exit **slot
6995 = l->exits->find_slot_with_hash (e, htab_hash_pointer (e),
6996 NO_INSERT);
6997 if (slot)
6998 l->exits->clear_slot (slot);
7003 /* Adjust the number of blocks in the tree root of the outlined part. */
7004 get_loop (dest_cfun, 0)->num_nodes = bbs.length () + 2;
7006 /* Setup a mapping to be used by move_block_to_fn. */
7007 loop->aux = current_loops->tree_root;
7008 loop0->aux = current_loops->tree_root;
7010 pop_cfun ();
7012 /* Move blocks from BBS into DEST_CFUN. */
7013 gcc_assert (bbs.length () >= 2);
7014 after = dest_cfun->cfg->x_entry_block_ptr;
7015 hash_map<tree, tree> vars_map;
7017 memset (&d, 0, sizeof (d));
7018 d.orig_block = orig_block;
7019 d.new_block = DECL_INITIAL (dest_cfun->decl);
7020 d.from_context = cfun->decl;
7021 d.to_context = dest_cfun->decl;
7022 d.vars_map = &vars_map;
7023 d.new_label_map = new_label_map;
7024 d.eh_map = eh_map;
7025 d.remap_decls_p = true;
7027 FOR_EACH_VEC_ELT (bbs, i, bb)
7029 /* No need to update edge counts on the last block. It has
7030 already been updated earlier when we detached the region from
7031 the original CFG. */
7032 move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d);
7033 after = bb;
7036 loop->aux = NULL;
7037 loop0->aux = NULL;
7038 /* Loop sizes are no longer correct, fix them up. */
7039 loop->num_nodes -= num_nodes;
7040 for (struct loop *outer = loop_outer (loop);
7041 outer; outer = loop_outer (outer))
7042 outer->num_nodes -= num_nodes;
7043 loop0->num_nodes -= bbs.length () - num_nodes;
7045 if (saved_cfun->has_simduid_loops || saved_cfun->has_force_vectorize_loops)
7047 struct loop *aloop;
7048 for (i = 0; vec_safe_iterate (loops->larray, i, &aloop); i++)
7049 if (aloop != NULL)
7051 if (aloop->simduid)
7053 replace_by_duplicate_decl (&aloop->simduid, d.vars_map,
7054 d.to_context);
7055 dest_cfun->has_simduid_loops = true;
7057 if (aloop->force_vectorize)
7058 dest_cfun->has_force_vectorize_loops = true;
7062 /* Rewire BLOCK_SUBBLOCKS of orig_block. */
7063 if (orig_block)
7065 tree block;
7066 gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
7067 == NULL_TREE);
7068 BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
7069 = BLOCK_SUBBLOCKS (orig_block);
7070 for (block = BLOCK_SUBBLOCKS (orig_block);
7071 block; block = BLOCK_CHAIN (block))
7072 BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
7073 BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
7076 replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
7077 &vars_map, dest_cfun->decl);
7079 if (new_label_map)
7080 htab_delete (new_label_map);
7081 if (eh_map)
7082 delete eh_map;
7084 /* Rewire the entry and exit blocks. The successor to the entry
7085 block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
7086 the child function. Similarly, the predecessor of DEST_FN's
7087 EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR. We
7088 need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
7089 various CFG manipulation function get to the right CFG.
7091 FIXME, this is silly. The CFG ought to become a parameter to
7092 these helpers. */
7093 push_cfun (dest_cfun);
7094 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), entry_bb, EDGE_FALLTHRU);
7095 if (exit_bb)
7096 make_edge (exit_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
7097 pop_cfun ();
7099 /* Back in the original function, the SESE region has disappeared,
7100 create a new basic block in its place. */
7101 bb = create_empty_bb (entry_pred[0]);
7102 if (current_loops)
7103 add_bb_to_loop (bb, loop);
7104 for (i = 0; i < num_entry_edges; i++)
7106 e = make_edge (entry_pred[i], bb, entry_flag[i]);
7107 e->probability = entry_prob[i];
7110 for (i = 0; i < num_exit_edges; i++)
7112 e = make_edge (bb, exit_succ[i], exit_flag[i]);
7113 e->probability = exit_prob[i];
7116 set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
7117 FOR_EACH_VEC_ELT (dom_bbs, i, abb)
7118 set_immediate_dominator (CDI_DOMINATORS, abb, bb);
7119 dom_bbs.release ();
7121 if (exit_bb)
7123 free (exit_prob);
7124 free (exit_flag);
7125 free (exit_succ);
7127 free (entry_prob);
7128 free (entry_flag);
7129 free (entry_pred);
7130 bbs.release ();
7132 return bb;
7136 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in dumpfile.h)
7139 void
7140 dump_function_to_file (tree fndecl, FILE *file, int flags)
7142 tree arg, var, old_current_fndecl = current_function_decl;
7143 struct function *dsf;
7144 bool ignore_topmost_bind = false, any_var = false;
7145 basic_block bb;
7146 tree chain;
7147 bool tmclone = (TREE_CODE (fndecl) == FUNCTION_DECL
7148 && decl_is_tm_clone (fndecl));
7149 struct function *fun = DECL_STRUCT_FUNCTION (fndecl);
7151 current_function_decl = fndecl;
7152 fprintf (file, "%s %s(", function_name (fun), tmclone ? "[tm-clone] " : "");
7154 arg = DECL_ARGUMENTS (fndecl);
7155 while (arg)
7157 print_generic_expr (file, TREE_TYPE (arg), dump_flags);
7158 fprintf (file, " ");
7159 print_generic_expr (file, arg, dump_flags);
7160 if (flags & TDF_VERBOSE)
7161 print_node (file, "", arg, 4);
7162 if (DECL_CHAIN (arg))
7163 fprintf (file, ", ");
7164 arg = DECL_CHAIN (arg);
7166 fprintf (file, ")\n");
7168 if (flags & TDF_VERBOSE)
7169 print_node (file, "", fndecl, 2);
7171 dsf = DECL_STRUCT_FUNCTION (fndecl);
7172 if (dsf && (flags & TDF_EH))
7173 dump_eh_tree (file, dsf);
7175 if (flags & TDF_RAW && !gimple_has_body_p (fndecl))
7177 dump_node (fndecl, TDF_SLIM | flags, file);
7178 current_function_decl = old_current_fndecl;
7179 return;
7182 /* When GIMPLE is lowered, the variables are no longer available in
7183 BIND_EXPRs, so display them separately. */
7184 if (fun && fun->decl == fndecl && (fun->curr_properties & PROP_gimple_lcf))
7186 unsigned ix;
7187 ignore_topmost_bind = true;
7189 fprintf (file, "{\n");
7190 if (!vec_safe_is_empty (fun->local_decls))
7191 FOR_EACH_LOCAL_DECL (fun, ix, var)
7193 print_generic_decl (file, var, flags);
7194 if (flags & TDF_VERBOSE)
7195 print_node (file, "", var, 4);
7196 fprintf (file, "\n");
7198 any_var = true;
7200 if (gimple_in_ssa_p (cfun))
7201 for (ix = 1; ix < num_ssa_names; ++ix)
7203 tree name = ssa_name (ix);
7204 if (name && !SSA_NAME_VAR (name))
7206 fprintf (file, " ");
7207 print_generic_expr (file, TREE_TYPE (name), flags);
7208 fprintf (file, " ");
7209 print_generic_expr (file, name, flags);
7210 fprintf (file, ";\n");
7212 any_var = true;
7217 if (fun && fun->decl == fndecl
7218 && fun->cfg
7219 && basic_block_info_for_fn (fun))
7221 /* If the CFG has been built, emit a CFG-based dump. */
7222 if (!ignore_topmost_bind)
7223 fprintf (file, "{\n");
7225 if (any_var && n_basic_blocks_for_fn (fun))
7226 fprintf (file, "\n");
7228 FOR_EACH_BB_FN (bb, fun)
7229 dump_bb (file, bb, 2, flags | TDF_COMMENT);
7231 fprintf (file, "}\n");
7233 else if (DECL_SAVED_TREE (fndecl) == NULL)
7235 /* The function is now in GIMPLE form but the CFG has not been
7236 built yet. Emit the single sequence of GIMPLE statements
7237 that make up its body. */
7238 gimple_seq body = gimple_body (fndecl);
7240 if (gimple_seq_first_stmt (body)
7241 && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
7242 && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
7243 print_gimple_seq (file, body, 0, flags);
7244 else
7246 if (!ignore_topmost_bind)
7247 fprintf (file, "{\n");
7249 if (any_var)
7250 fprintf (file, "\n");
7252 print_gimple_seq (file, body, 2, flags);
7253 fprintf (file, "}\n");
7256 else
7258 int indent;
7260 /* Make a tree based dump. */
7261 chain = DECL_SAVED_TREE (fndecl);
7262 if (chain && TREE_CODE (chain) == BIND_EXPR)
7264 if (ignore_topmost_bind)
7266 chain = BIND_EXPR_BODY (chain);
7267 indent = 2;
7269 else
7270 indent = 0;
7272 else
7274 if (!ignore_topmost_bind)
7275 fprintf (file, "{\n");
7276 indent = 2;
7279 if (any_var)
7280 fprintf (file, "\n");
7282 print_generic_stmt_indented (file, chain, flags, indent);
7283 if (ignore_topmost_bind)
7284 fprintf (file, "}\n");
7287 if (flags & TDF_ENUMERATE_LOCALS)
7288 dump_enumerated_decls (file, flags);
7289 fprintf (file, "\n\n");
7291 current_function_decl = old_current_fndecl;
7294 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h) */
7296 DEBUG_FUNCTION void
7297 debug_function (tree fn, int flags)
7299 dump_function_to_file (fn, stderr, flags);
7303 /* Print on FILE the indexes for the predecessors of basic_block BB. */
7305 static void
7306 print_pred_bbs (FILE *file, basic_block bb)
7308 edge e;
7309 edge_iterator ei;
7311 FOR_EACH_EDGE (e, ei, bb->preds)
7312 fprintf (file, "bb_%d ", e->src->index);
7316 /* Print on FILE the indexes for the successors of basic_block BB. */
7318 static void
7319 print_succ_bbs (FILE *file, basic_block bb)
7321 edge e;
7322 edge_iterator ei;
7324 FOR_EACH_EDGE (e, ei, bb->succs)
7325 fprintf (file, "bb_%d ", e->dest->index);
7328 /* Print to FILE the basic block BB following the VERBOSITY level. */
7330 void
7331 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
7333 char *s_indent = (char *) alloca ((size_t) indent + 1);
7334 memset ((void *) s_indent, ' ', (size_t) indent);
7335 s_indent[indent] = '\0';
7337 /* Print basic_block's header. */
7338 if (verbosity >= 2)
7340 fprintf (file, "%s bb_%d (preds = {", s_indent, bb->index);
7341 print_pred_bbs (file, bb);
7342 fprintf (file, "}, succs = {");
7343 print_succ_bbs (file, bb);
7344 fprintf (file, "})\n");
7347 /* Print basic_block's body. */
7348 if (verbosity >= 3)
7350 fprintf (file, "%s {\n", s_indent);
7351 dump_bb (file, bb, indent + 4, TDF_VOPS|TDF_MEMSYMS);
7352 fprintf (file, "%s }\n", s_indent);
7356 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
7358 /* Pretty print LOOP on FILE, indented INDENT spaces. Following
7359 VERBOSITY level this outputs the contents of the loop, or just its
7360 structure. */
7362 static void
7363 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
7365 char *s_indent;
7366 basic_block bb;
7368 if (loop == NULL)
7369 return;
7371 s_indent = (char *) alloca ((size_t) indent + 1);
7372 memset ((void *) s_indent, ' ', (size_t) indent);
7373 s_indent[indent] = '\0';
7375 /* Print loop's header. */
7376 fprintf (file, "%sloop_%d (", s_indent, loop->num);
7377 if (loop->header)
7378 fprintf (file, "header = %d", loop->header->index);
7379 else
7381 fprintf (file, "deleted)\n");
7382 return;
7384 if (loop->latch)
7385 fprintf (file, ", latch = %d", loop->latch->index);
7386 else
7387 fprintf (file, ", multiple latches");
7388 fprintf (file, ", niter = ");
7389 print_generic_expr (file, loop->nb_iterations, 0);
7391 if (loop->any_upper_bound)
7393 fprintf (file, ", upper_bound = ");
7394 print_decu (loop->nb_iterations_upper_bound, file);
7397 if (loop->any_estimate)
7399 fprintf (file, ", estimate = ");
7400 print_decu (loop->nb_iterations_estimate, file);
7402 fprintf (file, ")\n");
7404 /* Print loop's body. */
7405 if (verbosity >= 1)
7407 fprintf (file, "%s{\n", s_indent);
7408 FOR_EACH_BB_FN (bb, cfun)
7409 if (bb->loop_father == loop)
7410 print_loops_bb (file, bb, indent, verbosity);
7412 print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
7413 fprintf (file, "%s}\n", s_indent);
7417 /* Print the LOOP and its sibling loops on FILE, indented INDENT
7418 spaces. Following VERBOSITY level this outputs the contents of the
7419 loop, or just its structure. */
7421 static void
7422 print_loop_and_siblings (FILE *file, struct loop *loop, int indent,
7423 int verbosity)
7425 if (loop == NULL)
7426 return;
7428 print_loop (file, loop, indent, verbosity);
7429 print_loop_and_siblings (file, loop->next, indent, verbosity);
7432 /* Follow a CFG edge from the entry point of the program, and on entry
7433 of a loop, pretty print the loop structure on FILE. */
7435 void
7436 print_loops (FILE *file, int verbosity)
7438 basic_block bb;
7440 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
7441 if (bb && bb->loop_father)
7442 print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
7445 /* Dump a loop. */
7447 DEBUG_FUNCTION void
7448 debug (struct loop &ref)
7450 print_loop (stderr, &ref, 0, /*verbosity*/0);
7453 DEBUG_FUNCTION void
7454 debug (struct loop *ptr)
7456 if (ptr)
7457 debug (*ptr);
7458 else
7459 fprintf (stderr, "<nil>\n");
7462 /* Dump a loop verbosely. */
7464 DEBUG_FUNCTION void
7465 debug_verbose (struct loop &ref)
7467 print_loop (stderr, &ref, 0, /*verbosity*/3);
7470 DEBUG_FUNCTION void
7471 debug_verbose (struct loop *ptr)
7473 if (ptr)
7474 debug (*ptr);
7475 else
7476 fprintf (stderr, "<nil>\n");
7480 /* Debugging loops structure at tree level, at some VERBOSITY level. */
7482 DEBUG_FUNCTION void
7483 debug_loops (int verbosity)
7485 print_loops (stderr, verbosity);
7488 /* Print on stderr the code of LOOP, at some VERBOSITY level. */
7490 DEBUG_FUNCTION void
7491 debug_loop (struct loop *loop, int verbosity)
7493 print_loop (stderr, loop, 0, verbosity);
7496 /* Print on stderr the code of loop number NUM, at some VERBOSITY
7497 level. */
7499 DEBUG_FUNCTION void
7500 debug_loop_num (unsigned num, int verbosity)
7502 debug_loop (get_loop (cfun, num), verbosity);
7505 /* Return true if BB ends with a call, possibly followed by some
7506 instructions that must stay with the call. Return false,
7507 otherwise. */
7509 static bool
7510 gimple_block_ends_with_call_p (basic_block bb)
7512 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
7513 return !gsi_end_p (gsi) && is_gimple_call (gsi_stmt (gsi));
7517 /* Return true if BB ends with a conditional branch. Return false,
7518 otherwise. */
7520 static bool
7521 gimple_block_ends_with_condjump_p (const_basic_block bb)
7523 gimple stmt = last_stmt (CONST_CAST_BB (bb));
7524 return (stmt && gimple_code (stmt) == GIMPLE_COND);
7528 /* Return true if we need to add fake edge to exit at statement T.
7529 Helper function for gimple_flow_call_edges_add. */
7531 static bool
7532 need_fake_edge_p (gimple t)
7534 tree fndecl = NULL_TREE;
7535 int call_flags = 0;
7537 /* NORETURN and LONGJMP calls already have an edge to exit.
7538 CONST and PURE calls do not need one.
7539 We don't currently check for CONST and PURE here, although
7540 it would be a good idea, because those attributes are
7541 figured out from the RTL in mark_constant_function, and
7542 the counter incrementation code from -fprofile-arcs
7543 leads to different results from -fbranch-probabilities. */
7544 if (is_gimple_call (t))
7546 fndecl = gimple_call_fndecl (t);
7547 call_flags = gimple_call_flags (t);
7550 if (is_gimple_call (t)
7551 && fndecl
7552 && DECL_BUILT_IN (fndecl)
7553 && (call_flags & ECF_NOTHROW)
7554 && !(call_flags & ECF_RETURNS_TWICE)
7555 /* fork() doesn't really return twice, but the effect of
7556 wrapping it in __gcov_fork() which calls __gcov_flush()
7557 and clears the counters before forking has the same
7558 effect as returning twice. Force a fake edge. */
7559 && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
7560 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK))
7561 return false;
7563 if (is_gimple_call (t))
7565 edge_iterator ei;
7566 edge e;
7567 basic_block bb;
7569 if (!(call_flags & ECF_NORETURN))
7570 return true;
7572 bb = gimple_bb (t);
7573 FOR_EACH_EDGE (e, ei, bb->succs)
7574 if ((e->flags & EDGE_FAKE) == 0)
7575 return true;
7578 if (gimple_code (t) == GIMPLE_ASM
7579 && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
7580 return true;
7582 return false;
7586 /* Add fake edges to the function exit for any non constant and non
7587 noreturn calls (or noreturn calls with EH/abnormal edges),
7588 volatile inline assembly in the bitmap of blocks specified by BLOCKS
7589 or to the whole CFG if BLOCKS is zero. Return the number of blocks
7590 that were split.
7592 The goal is to expose cases in which entering a basic block does
7593 not imply that all subsequent instructions must be executed. */
7595 static int
7596 gimple_flow_call_edges_add (sbitmap blocks)
7598 int i;
7599 int blocks_split = 0;
7600 int last_bb = last_basic_block_for_fn (cfun);
7601 bool check_last_block = false;
7603 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
7604 return 0;
7606 if (! blocks)
7607 check_last_block = true;
7608 else
7609 check_last_block = bitmap_bit_p (blocks,
7610 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
7612 /* In the last basic block, before epilogue generation, there will be
7613 a fallthru edge to EXIT. Special care is required if the last insn
7614 of the last basic block is a call because make_edge folds duplicate
7615 edges, which would result in the fallthru edge also being marked
7616 fake, which would result in the fallthru edge being removed by
7617 remove_fake_edges, which would result in an invalid CFG.
7619 Moreover, we can't elide the outgoing fake edge, since the block
7620 profiler needs to take this into account in order to solve the minimal
7621 spanning tree in the case that the call doesn't return.
7623 Handle this by adding a dummy instruction in a new last basic block. */
7624 if (check_last_block)
7626 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
7627 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
7628 gimple t = NULL;
7630 if (!gsi_end_p (gsi))
7631 t = gsi_stmt (gsi);
7633 if (t && need_fake_edge_p (t))
7635 edge e;
7637 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
7638 if (e)
7640 gsi_insert_on_edge (e, gimple_build_nop ());
7641 gsi_commit_edge_inserts ();
7646 /* Now add fake edges to the function exit for any non constant
7647 calls since there is no way that we can determine if they will
7648 return or not... */
7649 for (i = 0; i < last_bb; i++)
7651 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
7652 gimple_stmt_iterator gsi;
7653 gimple stmt, last_stmt;
7655 if (!bb)
7656 continue;
7658 if (blocks && !bitmap_bit_p (blocks, i))
7659 continue;
7661 gsi = gsi_last_nondebug_bb (bb);
7662 if (!gsi_end_p (gsi))
7664 last_stmt = gsi_stmt (gsi);
7667 stmt = gsi_stmt (gsi);
7668 if (need_fake_edge_p (stmt))
7670 edge e;
7672 /* The handling above of the final block before the
7673 epilogue should be enough to verify that there is
7674 no edge to the exit block in CFG already.
7675 Calling make_edge in such case would cause us to
7676 mark that edge as fake and remove it later. */
7677 #ifdef ENABLE_CHECKING
7678 if (stmt == last_stmt)
7680 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
7681 gcc_assert (e == NULL);
7683 #endif
7685 /* Note that the following may create a new basic block
7686 and renumber the existing basic blocks. */
7687 if (stmt != last_stmt)
7689 e = split_block (bb, stmt);
7690 if (e)
7691 blocks_split++;
7693 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
7695 gsi_prev (&gsi);
7697 while (!gsi_end_p (gsi));
7701 if (blocks_split)
7702 verify_flow_info ();
7704 return blocks_split;
7707 /* Removes edge E and all the blocks dominated by it, and updates dominance
7708 information. The IL in E->src needs to be updated separately.
7709 If dominance info is not available, only the edge E is removed.*/
7711 void
7712 remove_edge_and_dominated_blocks (edge e)
7714 vec<basic_block> bbs_to_remove = vNULL;
7715 vec<basic_block> bbs_to_fix_dom = vNULL;
7716 bitmap df, df_idom;
7717 edge f;
7718 edge_iterator ei;
7719 bool none_removed = false;
7720 unsigned i;
7721 basic_block bb, dbb;
7722 bitmap_iterator bi;
7724 if (!dom_info_available_p (CDI_DOMINATORS))
7726 remove_edge (e);
7727 return;
7730 /* No updating is needed for edges to exit. */
7731 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
7733 if (cfgcleanup_altered_bbs)
7734 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7735 remove_edge (e);
7736 return;
7739 /* First, we find the basic blocks to remove. If E->dest has a predecessor
7740 that is not dominated by E->dest, then this set is empty. Otherwise,
7741 all the basic blocks dominated by E->dest are removed.
7743 Also, to DF_IDOM we store the immediate dominators of the blocks in
7744 the dominance frontier of E (i.e., of the successors of the
7745 removed blocks, if there are any, and of E->dest otherwise). */
7746 FOR_EACH_EDGE (f, ei, e->dest->preds)
7748 if (f == e)
7749 continue;
7751 if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
7753 none_removed = true;
7754 break;
7758 df = BITMAP_ALLOC (NULL);
7759 df_idom = BITMAP_ALLOC (NULL);
7761 if (none_removed)
7762 bitmap_set_bit (df_idom,
7763 get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
7764 else
7766 bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest);
7767 FOR_EACH_VEC_ELT (bbs_to_remove, i, bb)
7769 FOR_EACH_EDGE (f, ei, bb->succs)
7771 if (f->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
7772 bitmap_set_bit (df, f->dest->index);
7775 FOR_EACH_VEC_ELT (bbs_to_remove, i, bb)
7776 bitmap_clear_bit (df, bb->index);
7778 EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
7780 bb = BASIC_BLOCK_FOR_FN (cfun, i);
7781 bitmap_set_bit (df_idom,
7782 get_immediate_dominator (CDI_DOMINATORS, bb)->index);
7786 if (cfgcleanup_altered_bbs)
7788 /* Record the set of the altered basic blocks. */
7789 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7790 bitmap_ior_into (cfgcleanup_altered_bbs, df);
7793 /* Remove E and the cancelled blocks. */
7794 if (none_removed)
7795 remove_edge (e);
7796 else
7798 /* Walk backwards so as to get a chance to substitute all
7799 released DEFs into debug stmts. See
7800 eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
7801 details. */
7802 for (i = bbs_to_remove.length (); i-- > 0; )
7803 delete_basic_block (bbs_to_remove[i]);
7806 /* Update the dominance information. The immediate dominator may change only
7807 for blocks whose immediate dominator belongs to DF_IDOM:
7809 Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
7810 removal. Let Z the arbitrary block such that idom(Z) = Y and
7811 Z dominates X after the removal. Before removal, there exists a path P
7812 from Y to X that avoids Z. Let F be the last edge on P that is
7813 removed, and let W = F->dest. Before removal, idom(W) = Y (since Y
7814 dominates W, and because of P, Z does not dominate W), and W belongs to
7815 the dominance frontier of E. Therefore, Y belongs to DF_IDOM. */
7816 EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
7818 bb = BASIC_BLOCK_FOR_FN (cfun, i);
7819 for (dbb = first_dom_son (CDI_DOMINATORS, bb);
7820 dbb;
7821 dbb = next_dom_son (CDI_DOMINATORS, dbb))
7822 bbs_to_fix_dom.safe_push (dbb);
7825 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
7827 BITMAP_FREE (df);
7828 BITMAP_FREE (df_idom);
7829 bbs_to_remove.release ();
7830 bbs_to_fix_dom.release ();
7833 /* Purge dead EH edges from basic block BB. */
7835 bool
7836 gimple_purge_dead_eh_edges (basic_block bb)
7838 bool changed = false;
7839 edge e;
7840 edge_iterator ei;
7841 gimple stmt = last_stmt (bb);
7843 if (stmt && stmt_can_throw_internal (stmt))
7844 return false;
7846 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7848 if (e->flags & EDGE_EH)
7850 remove_edge_and_dominated_blocks (e);
7851 changed = true;
7853 else
7854 ei_next (&ei);
7857 return changed;
7860 /* Purge dead EH edges from basic block listed in BLOCKS. */
7862 bool
7863 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
7865 bool changed = false;
7866 unsigned i;
7867 bitmap_iterator bi;
7869 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7871 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
7873 /* Earlier gimple_purge_dead_eh_edges could have removed
7874 this basic block already. */
7875 gcc_assert (bb || changed);
7876 if (bb != NULL)
7877 changed |= gimple_purge_dead_eh_edges (bb);
7880 return changed;
7883 /* Purge dead abnormal call edges from basic block BB. */
7885 bool
7886 gimple_purge_dead_abnormal_call_edges (basic_block bb)
7888 bool changed = false;
7889 edge e;
7890 edge_iterator ei;
7891 gimple stmt = last_stmt (bb);
7893 if (!cfun->has_nonlocal_label
7894 && !cfun->calls_setjmp)
7895 return false;
7897 if (stmt && stmt_can_make_abnormal_goto (stmt))
7898 return false;
7900 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7902 if (e->flags & EDGE_ABNORMAL)
7904 if (e->flags & EDGE_FALLTHRU)
7905 e->flags &= ~EDGE_ABNORMAL;
7906 else
7907 remove_edge_and_dominated_blocks (e);
7908 changed = true;
7910 else
7911 ei_next (&ei);
7914 return changed;
7917 /* Purge dead abnormal call edges from basic block listed in BLOCKS. */
7919 bool
7920 gimple_purge_all_dead_abnormal_call_edges (const_bitmap blocks)
7922 bool changed = false;
7923 unsigned i;
7924 bitmap_iterator bi;
7926 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7928 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
7930 /* Earlier gimple_purge_dead_abnormal_call_edges could have removed
7931 this basic block already. */
7932 gcc_assert (bb || changed);
7933 if (bb != NULL)
7934 changed |= gimple_purge_dead_abnormal_call_edges (bb);
7937 return changed;
7940 /* This function is called whenever a new edge is created or
7941 redirected. */
7943 static void
7944 gimple_execute_on_growing_pred (edge e)
7946 basic_block bb = e->dest;
7948 if (!gimple_seq_empty_p (phi_nodes (bb)))
7949 reserve_phi_args_for_new_edge (bb);
7952 /* This function is called immediately before edge E is removed from
7953 the edge vector E->dest->preds. */
7955 static void
7956 gimple_execute_on_shrinking_pred (edge e)
7958 if (!gimple_seq_empty_p (phi_nodes (e->dest)))
7959 remove_phi_args (e);
7962 /*---------------------------------------------------------------------------
7963 Helper functions for Loop versioning
7964 ---------------------------------------------------------------------------*/
7966 /* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy
7967 of 'first'. Both of them are dominated by 'new_head' basic block. When
7968 'new_head' was created by 'second's incoming edge it received phi arguments
7969 on the edge by split_edge(). Later, additional edge 'e' was created to
7970 connect 'new_head' and 'first'. Now this routine adds phi args on this
7971 additional edge 'e' that new_head to second edge received as part of edge
7972 splitting. */
7974 static void
7975 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
7976 basic_block new_head, edge e)
7978 gimple phi1, phi2;
7979 gimple_stmt_iterator psi1, psi2;
7980 tree def;
7981 edge e2 = find_edge (new_head, second);
7983 /* Because NEW_HEAD has been created by splitting SECOND's incoming
7984 edge, we should always have an edge from NEW_HEAD to SECOND. */
7985 gcc_assert (e2 != NULL);
7987 /* Browse all 'second' basic block phi nodes and add phi args to
7988 edge 'e' for 'first' head. PHI args are always in correct order. */
7990 for (psi2 = gsi_start_phis (second),
7991 psi1 = gsi_start_phis (first);
7992 !gsi_end_p (psi2) && !gsi_end_p (psi1);
7993 gsi_next (&psi2), gsi_next (&psi1))
7995 phi1 = gsi_stmt (psi1);
7996 phi2 = gsi_stmt (psi2);
7997 def = PHI_ARG_DEF (phi2, e2->dest_idx);
7998 add_phi_arg (phi1, def, e, gimple_phi_arg_location_from_edge (phi2, e2));
8003 /* Adds a if else statement to COND_BB with condition COND_EXPR.
8004 SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
8005 the destination of the ELSE part. */
8007 static void
8008 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
8009 basic_block second_head ATTRIBUTE_UNUSED,
8010 basic_block cond_bb, void *cond_e)
8012 gimple_stmt_iterator gsi;
8013 gimple new_cond_expr;
8014 tree cond_expr = (tree) cond_e;
8015 edge e0;
8017 /* Build new conditional expr */
8018 new_cond_expr = gimple_build_cond_from_tree (cond_expr,
8019 NULL_TREE, NULL_TREE);
8021 /* Add new cond in cond_bb. */
8022 gsi = gsi_last_bb (cond_bb);
8023 gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
8025 /* Adjust edges appropriately to connect new head with first head
8026 as well as second head. */
8027 e0 = single_succ_edge (cond_bb);
8028 e0->flags &= ~EDGE_FALLTHRU;
8029 e0->flags |= EDGE_FALSE_VALUE;
8033 /* Do book-keeping of basic block BB for the profile consistency checker.
8034 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
8035 then do post-pass accounting. Store the counting in RECORD. */
8036 static void
8037 gimple_account_profile_record (basic_block bb, int after_pass,
8038 struct profile_record *record)
8040 gimple_stmt_iterator i;
8041 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
8043 record->size[after_pass]
8044 += estimate_num_insns (gsi_stmt (i), &eni_size_weights);
8045 if (profile_status_for_fn (cfun) == PROFILE_READ)
8046 record->time[after_pass]
8047 += estimate_num_insns (gsi_stmt (i),
8048 &eni_time_weights) * bb->count;
8049 else if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
8050 record->time[after_pass]
8051 += estimate_num_insns (gsi_stmt (i),
8052 &eni_time_weights) * bb->frequency;
8056 struct cfg_hooks gimple_cfg_hooks = {
8057 "gimple",
8058 gimple_verify_flow_info,
8059 gimple_dump_bb, /* dump_bb */
8060 gimple_dump_bb_for_graph, /* dump_bb_for_graph */
8061 create_bb, /* create_basic_block */
8062 gimple_redirect_edge_and_branch, /* redirect_edge_and_branch */
8063 gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force */
8064 gimple_can_remove_branch_p, /* can_remove_branch_p */
8065 remove_bb, /* delete_basic_block */
8066 gimple_split_block, /* split_block */
8067 gimple_move_block_after, /* move_block_after */
8068 gimple_can_merge_blocks_p, /* can_merge_blocks_p */
8069 gimple_merge_blocks, /* merge_blocks */
8070 gimple_predict_edge, /* predict_edge */
8071 gimple_predicted_by_p, /* predicted_by_p */
8072 gimple_can_duplicate_bb_p, /* can_duplicate_block_p */
8073 gimple_duplicate_bb, /* duplicate_block */
8074 gimple_split_edge, /* split_edge */
8075 gimple_make_forwarder_block, /* make_forward_block */
8076 NULL, /* tidy_fallthru_edge */
8077 NULL, /* force_nonfallthru */
8078 gimple_block_ends_with_call_p,/* block_ends_with_call_p */
8079 gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
8080 gimple_flow_call_edges_add, /* flow_call_edges_add */
8081 gimple_execute_on_growing_pred, /* execute_on_growing_pred */
8082 gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
8083 gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
8084 gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
8085 gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
8086 extract_true_false_edges_from_block, /* extract_cond_bb_edges */
8087 flush_pending_stmts, /* flush_pending_stmts */
8088 gimple_empty_block_p, /* block_empty_p */
8089 gimple_split_block_before_cond_jump, /* split_block_before_cond_jump */
8090 gimple_account_profile_record,
8094 /* Split all critical edges. */
8096 unsigned int
8097 split_critical_edges (void)
8099 basic_block bb;
8100 edge e;
8101 edge_iterator ei;
8103 /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
8104 expensive. So we want to enable recording of edge to CASE_LABEL_EXPR
8105 mappings around the calls to split_edge. */
8106 start_recording_case_labels ();
8107 FOR_ALL_BB_FN (bb, cfun)
8109 FOR_EACH_EDGE (e, ei, bb->succs)
8111 if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
8112 split_edge (e);
8113 /* PRE inserts statements to edges and expects that
8114 since split_critical_edges was done beforehand, committing edge
8115 insertions will not split more edges. In addition to critical
8116 edges we must split edges that have multiple successors and
8117 end by control flow statements, such as RESX.
8118 Go ahead and split them too. This matches the logic in
8119 gimple_find_edge_insert_loc. */
8120 else if ((!single_pred_p (e->dest)
8121 || !gimple_seq_empty_p (phi_nodes (e->dest))
8122 || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
8123 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
8124 && !(e->flags & EDGE_ABNORMAL))
8126 gimple_stmt_iterator gsi;
8128 gsi = gsi_last_bb (e->src);
8129 if (!gsi_end_p (gsi)
8130 && stmt_ends_bb_p (gsi_stmt (gsi))
8131 && (gimple_code (gsi_stmt (gsi)) != GIMPLE_RETURN
8132 && !gimple_call_builtin_p (gsi_stmt (gsi),
8133 BUILT_IN_RETURN)))
8134 split_edge (e);
8138 end_recording_case_labels ();
8139 return 0;
8142 namespace {
8144 const pass_data pass_data_split_crit_edges =
8146 GIMPLE_PASS, /* type */
8147 "crited", /* name */
8148 OPTGROUP_NONE, /* optinfo_flags */
8149 TV_TREE_SPLIT_EDGES, /* tv_id */
8150 PROP_cfg, /* properties_required */
8151 PROP_no_crit_edges, /* properties_provided */
8152 0, /* properties_destroyed */
8153 0, /* todo_flags_start */
8154 0, /* todo_flags_finish */
8157 class pass_split_crit_edges : public gimple_opt_pass
8159 public:
8160 pass_split_crit_edges (gcc::context *ctxt)
8161 : gimple_opt_pass (pass_data_split_crit_edges, ctxt)
8164 /* opt_pass methods: */
8165 virtual unsigned int execute (function *) { return split_critical_edges (); }
8167 opt_pass * clone () { return new pass_split_crit_edges (m_ctxt); }
8168 }; // class pass_split_crit_edges
8170 } // anon namespace
8172 gimple_opt_pass *
8173 make_pass_split_crit_edges (gcc::context *ctxt)
8175 return new pass_split_crit_edges (ctxt);
8179 /* Build a ternary operation and gimplify it. Emit code before GSI.
8180 Return the gimple_val holding the result. */
8182 tree
8183 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
8184 tree type, tree a, tree b, tree c)
8186 tree ret;
8187 location_t loc = gimple_location (gsi_stmt (*gsi));
8189 ret = fold_build3_loc (loc, code, type, a, b, c);
8190 STRIP_NOPS (ret);
8192 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
8193 GSI_SAME_STMT);
8196 /* Build a binary operation and gimplify it. Emit code before GSI.
8197 Return the gimple_val holding the result. */
8199 tree
8200 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
8201 tree type, tree a, tree b)
8203 tree ret;
8205 ret = fold_build2_loc (gimple_location (gsi_stmt (*gsi)), code, type, a, b);
8206 STRIP_NOPS (ret);
8208 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
8209 GSI_SAME_STMT);
8212 /* Build a unary operation and gimplify it. Emit code before GSI.
8213 Return the gimple_val holding the result. */
8215 tree
8216 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
8217 tree a)
8219 tree ret;
8221 ret = fold_build1_loc (gimple_location (gsi_stmt (*gsi)), code, type, a);
8222 STRIP_NOPS (ret);
8224 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
8225 GSI_SAME_STMT);
8230 /* Given a basic block B which ends with a conditional and has
8231 precisely two successors, determine which of the edges is taken if
8232 the conditional is true and which is taken if the conditional is
8233 false. Set TRUE_EDGE and FALSE_EDGE appropriately. */
8235 void
8236 extract_true_false_edges_from_block (basic_block b,
8237 edge *true_edge,
8238 edge *false_edge)
8240 edge e = EDGE_SUCC (b, 0);
8242 if (e->flags & EDGE_TRUE_VALUE)
8244 *true_edge = e;
8245 *false_edge = EDGE_SUCC (b, 1);
8247 else
8249 *false_edge = e;
8250 *true_edge = EDGE_SUCC (b, 1);
8254 /* Emit return warnings. */
8256 namespace {
8258 const pass_data pass_data_warn_function_return =
8260 GIMPLE_PASS, /* type */
8261 "*warn_function_return", /* name */
8262 OPTGROUP_NONE, /* optinfo_flags */
8263 TV_NONE, /* tv_id */
8264 PROP_cfg, /* properties_required */
8265 0, /* properties_provided */
8266 0, /* properties_destroyed */
8267 0, /* todo_flags_start */
8268 0, /* todo_flags_finish */
8271 class pass_warn_function_return : public gimple_opt_pass
8273 public:
8274 pass_warn_function_return (gcc::context *ctxt)
8275 : gimple_opt_pass (pass_data_warn_function_return, ctxt)
8278 /* opt_pass methods: */
8279 virtual unsigned int execute (function *);
8281 }; // class pass_warn_function_return
8283 unsigned int
8284 pass_warn_function_return::execute (function *fun)
8286 source_location location;
8287 gimple last;
8288 edge e;
8289 edge_iterator ei;
8291 if (!targetm.warn_func_return (fun->decl))
8292 return 0;
8294 /* If we have a path to EXIT, then we do return. */
8295 if (TREE_THIS_VOLATILE (fun->decl)
8296 && EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (fun)->preds) > 0)
8298 location = UNKNOWN_LOCATION;
8299 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (fun)->preds)
8301 last = last_stmt (e->src);
8302 if ((gimple_code (last) == GIMPLE_RETURN
8303 || gimple_call_builtin_p (last, BUILT_IN_RETURN))
8304 && (location = gimple_location (last)) != UNKNOWN_LOCATION)
8305 break;
8307 if (location == UNKNOWN_LOCATION)
8308 location = cfun->function_end_locus;
8309 warning_at (location, 0, "%<noreturn%> function does return");
8312 /* If we see "return;" in some basic block, then we do reach the end
8313 without returning a value. */
8314 else if (warn_return_type
8315 && !TREE_NO_WARNING (fun->decl)
8316 && EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (fun)->preds) > 0
8317 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fun->decl))))
8319 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (fun)->preds)
8321 gimple last = last_stmt (e->src);
8322 if (gimple_code (last) == GIMPLE_RETURN
8323 && gimple_return_retval (last) == NULL
8324 && !gimple_no_warning_p (last))
8326 location = gimple_location (last);
8327 if (location == UNKNOWN_LOCATION)
8328 location = fun->function_end_locus;
8329 warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
8330 TREE_NO_WARNING (fun->decl) = 1;
8331 break;
8335 return 0;
8338 } // anon namespace
8340 gimple_opt_pass *
8341 make_pass_warn_function_return (gcc::context *ctxt)
8343 return new pass_warn_function_return (ctxt);
8346 /* Walk a gimplified function and warn for functions whose return value is
8347 ignored and attribute((warn_unused_result)) is set. This is done before
8348 inlining, so we don't have to worry about that. */
8350 static void
8351 do_warn_unused_result (gimple_seq seq)
8353 tree fdecl, ftype;
8354 gimple_stmt_iterator i;
8356 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
8358 gimple g = gsi_stmt (i);
8360 switch (gimple_code (g))
8362 case GIMPLE_BIND:
8363 do_warn_unused_result (gimple_bind_body (g));
8364 break;
8365 case GIMPLE_TRY:
8366 do_warn_unused_result (gimple_try_eval (g));
8367 do_warn_unused_result (gimple_try_cleanup (g));
8368 break;
8369 case GIMPLE_CATCH:
8370 do_warn_unused_result (gimple_catch_handler (g));
8371 break;
8372 case GIMPLE_EH_FILTER:
8373 do_warn_unused_result (gimple_eh_filter_failure (g));
8374 break;
8376 case GIMPLE_CALL:
8377 if (gimple_call_lhs (g))
8378 break;
8379 if (gimple_call_internal_p (g))
8380 break;
8382 /* This is a naked call, as opposed to a GIMPLE_CALL with an
8383 LHS. All calls whose value is ignored should be
8384 represented like this. Look for the attribute. */
8385 fdecl = gimple_call_fndecl (g);
8386 ftype = gimple_call_fntype (g);
8388 if (lookup_attribute ("warn_unused_result", TYPE_ATTRIBUTES (ftype)))
8390 location_t loc = gimple_location (g);
8392 if (fdecl)
8393 warning_at (loc, OPT_Wunused_result,
8394 "ignoring return value of %qD, "
8395 "declared with attribute warn_unused_result",
8396 fdecl);
8397 else
8398 warning_at (loc, OPT_Wunused_result,
8399 "ignoring return value of function "
8400 "declared with attribute warn_unused_result");
8402 break;
8404 default:
8405 /* Not a container, not a call, or a call whose value is used. */
8406 break;
8411 namespace {
8413 const pass_data pass_data_warn_unused_result =
8415 GIMPLE_PASS, /* type */
8416 "*warn_unused_result", /* name */
8417 OPTGROUP_NONE, /* optinfo_flags */
8418 TV_NONE, /* tv_id */
8419 PROP_gimple_any, /* properties_required */
8420 0, /* properties_provided */
8421 0, /* properties_destroyed */
8422 0, /* todo_flags_start */
8423 0, /* todo_flags_finish */
8426 class pass_warn_unused_result : public gimple_opt_pass
8428 public:
8429 pass_warn_unused_result (gcc::context *ctxt)
8430 : gimple_opt_pass (pass_data_warn_unused_result, ctxt)
8433 /* opt_pass methods: */
8434 virtual bool gate (function *) { return flag_warn_unused_result; }
8435 virtual unsigned int execute (function *)
8437 do_warn_unused_result (gimple_body (current_function_decl));
8438 return 0;
8441 }; // class pass_warn_unused_result
8443 } // anon namespace
8445 gimple_opt_pass *
8446 make_pass_warn_unused_result (gcc::context *ctxt)
8448 return new pass_warn_unused_result (ctxt);
8451 /* IPA passes, compilation of earlier functions or inlining
8452 might have changed some properties, such as marked functions nothrow,
8453 pure, const or noreturn.
8454 Remove redundant edges and basic blocks, and create new ones if necessary.
8456 This pass can't be executed as stand alone pass from pass manager, because
8457 in between inlining and this fixup the verify_flow_info would fail. */
8459 unsigned int
8460 execute_fixup_cfg (void)
8462 basic_block bb;
8463 gimple_stmt_iterator gsi;
8464 int todo = 0;
8465 gcov_type count_scale;
8466 edge e;
8467 edge_iterator ei;
8469 count_scale
8470 = GCOV_COMPUTE_SCALE (cgraph_node::get (current_function_decl)->count,
8471 ENTRY_BLOCK_PTR_FOR_FN (cfun)->count);
8473 ENTRY_BLOCK_PTR_FOR_FN (cfun)->count =
8474 cgraph_node::get (current_function_decl)->count;
8475 EXIT_BLOCK_PTR_FOR_FN (cfun)->count =
8476 apply_scale (EXIT_BLOCK_PTR_FOR_FN (cfun)->count,
8477 count_scale);
8479 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
8480 e->count = apply_scale (e->count, count_scale);
8482 FOR_EACH_BB_FN (bb, cfun)
8484 bb->count = apply_scale (bb->count, count_scale);
8485 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
8487 gimple stmt = gsi_stmt (gsi);
8488 tree decl = is_gimple_call (stmt)
8489 ? gimple_call_fndecl (stmt)
8490 : NULL;
8491 if (decl)
8493 int flags = gimple_call_flags (stmt);
8494 if (flags & (ECF_CONST | ECF_PURE | ECF_LOOPING_CONST_OR_PURE))
8496 if (gimple_purge_dead_abnormal_call_edges (bb))
8497 todo |= TODO_cleanup_cfg;
8499 if (gimple_in_ssa_p (cfun))
8501 todo |= TODO_update_ssa | TODO_cleanup_cfg;
8502 update_stmt (stmt);
8506 if (flags & ECF_NORETURN
8507 && fixup_noreturn_call (stmt))
8508 todo |= TODO_cleanup_cfg;
8511 /* Remove stores to variables we marked write-only.
8512 Keep access when store has side effect, i.e. in case when source
8513 is volatile. */
8514 if (gimple_store_p (stmt)
8515 && !gimple_has_side_effects (stmt))
8517 tree lhs = get_base_address (gimple_get_lhs (stmt));
8519 if (TREE_CODE (lhs) == VAR_DECL
8520 && (TREE_STATIC (lhs) || DECL_EXTERNAL (lhs))
8521 && varpool_node::get (lhs)->writeonly)
8523 unlink_stmt_vdef (stmt);
8524 gsi_remove (&gsi, true);
8525 release_defs (stmt);
8526 todo |= TODO_update_ssa | TODO_cleanup_cfg;
8527 continue;
8530 /* For calls we can simply remove LHS when it is known
8531 to be write-only. */
8532 if (is_gimple_call (stmt)
8533 && gimple_get_lhs (stmt))
8535 tree lhs = get_base_address (gimple_get_lhs (stmt));
8537 if (TREE_CODE (lhs) == VAR_DECL
8538 && (TREE_STATIC (lhs) || DECL_EXTERNAL (lhs))
8539 && varpool_node::get (lhs)->writeonly)
8541 gimple_call_set_lhs (stmt, NULL);
8542 update_stmt (stmt);
8543 todo |= TODO_update_ssa | TODO_cleanup_cfg;
8547 if (maybe_clean_eh_stmt (stmt)
8548 && gimple_purge_dead_eh_edges (bb))
8549 todo |= TODO_cleanup_cfg;
8550 gsi_next (&gsi);
8553 FOR_EACH_EDGE (e, ei, bb->succs)
8554 e->count = apply_scale (e->count, count_scale);
8556 /* If we have a basic block with no successors that does not
8557 end with a control statement or a noreturn call end it with
8558 a call to __builtin_unreachable. This situation can occur
8559 when inlining a noreturn call that does in fact return. */
8560 if (EDGE_COUNT (bb->succs) == 0)
8562 gimple stmt = last_stmt (bb);
8563 if (!stmt
8564 || (!is_ctrl_stmt (stmt)
8565 && (!is_gimple_call (stmt)
8566 || (gimple_call_flags (stmt) & ECF_NORETURN) == 0)))
8568 if (stmt && is_gimple_call (stmt))
8569 gimple_call_set_ctrl_altering (stmt, false);
8570 stmt = gimple_build_call
8571 (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
8572 gimple_stmt_iterator gsi = gsi_last_bb (bb);
8573 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
8577 if (count_scale != REG_BR_PROB_BASE)
8578 compute_function_frequency ();
8580 /* Dump a textual representation of the flowgraph. */
8581 if (dump_file)
8582 gimple_dump_cfg (dump_file, dump_flags);
8584 if (current_loops
8585 && (todo & TODO_cleanup_cfg))
8586 loops_state_set (LOOPS_NEED_FIXUP);
8588 return todo;
8591 namespace {
8593 const pass_data pass_data_fixup_cfg =
8595 GIMPLE_PASS, /* type */
8596 "*free_cfg_annotations", /* name */
8597 OPTGROUP_NONE, /* optinfo_flags */
8598 TV_NONE, /* tv_id */
8599 PROP_cfg, /* properties_required */
8600 0, /* properties_provided */
8601 0, /* properties_destroyed */
8602 0, /* todo_flags_start */
8603 0, /* todo_flags_finish */
8606 class pass_fixup_cfg : public gimple_opt_pass
8608 public:
8609 pass_fixup_cfg (gcc::context *ctxt)
8610 : gimple_opt_pass (pass_data_fixup_cfg, ctxt)
8613 /* opt_pass methods: */
8614 opt_pass * clone () { return new pass_fixup_cfg (m_ctxt); }
8615 virtual unsigned int execute (function *) { return execute_fixup_cfg (); }
8617 }; // class pass_fixup_cfg
8619 } // anon namespace
8621 gimple_opt_pass *
8622 make_pass_fixup_cfg (gcc::context *ctxt)
8624 return new pass_fixup_cfg (ctxt);
8627 /* Garbage collection support for edge_def. */
8629 extern void gt_ggc_mx (tree&);
8630 extern void gt_ggc_mx (gimple&);
8631 extern void gt_ggc_mx (rtx&);
8632 extern void gt_ggc_mx (basic_block&);
8634 static void
8635 gt_ggc_mx (rtx_insn *& x)
8637 if (x)
8638 gt_ggc_mx_rtx_def ((void *) x);
8641 void
8642 gt_ggc_mx (edge_def *e)
8644 tree block = LOCATION_BLOCK (e->goto_locus);
8645 gt_ggc_mx (e->src);
8646 gt_ggc_mx (e->dest);
8647 if (current_ir_type () == IR_GIMPLE)
8648 gt_ggc_mx (e->insns.g);
8649 else
8650 gt_ggc_mx (e->insns.r);
8651 gt_ggc_mx (block);
8654 /* PCH support for edge_def. */
8656 extern void gt_pch_nx (tree&);
8657 extern void gt_pch_nx (gimple&);
8658 extern void gt_pch_nx (rtx&);
8659 extern void gt_pch_nx (basic_block&);
8661 static void
8662 gt_pch_nx (rtx_insn *& x)
8664 if (x)
8665 gt_pch_nx_rtx_def ((void *) x);
8668 void
8669 gt_pch_nx (edge_def *e)
8671 tree block = LOCATION_BLOCK (e->goto_locus);
8672 gt_pch_nx (e->src);
8673 gt_pch_nx (e->dest);
8674 if (current_ir_type () == IR_GIMPLE)
8675 gt_pch_nx (e->insns.g);
8676 else
8677 gt_pch_nx (e->insns.r);
8678 gt_pch_nx (block);
8681 void
8682 gt_pch_nx (edge_def *e, gt_pointer_operator op, void *cookie)
8684 tree block = LOCATION_BLOCK (e->goto_locus);
8685 op (&(e->src), cookie);
8686 op (&(e->dest), cookie);
8687 if (current_ir_type () == IR_GIMPLE)
8688 op (&(e->insns.g), cookie);
8689 else
8690 op (&(e->insns.r), cookie);
8691 op (&(block), cookie);