Changelog c-family/
[gcc.git] / gcc / tree-cfg.c
1 /* Control flow functions for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
3 2010 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "tm_p.h"
28 #include "basic-block.h"
29 #include "output.h"
30 #include "flags.h"
31 #include "function.h"
32 #include "ggc.h"
33 #include "langhooks.h"
34 #include "tree-pretty-print.h"
35 #include "gimple-pretty-print.h"
36 #include "tree-flow.h"
37 #include "timevar.h"
38 #include "tree-dump.h"
39 #include "tree-pass.h"
40 #include "diagnostic-core.h"
41 #include "except.h"
42 #include "cfgloop.h"
43 #include "cfglayout.h"
44 #include "tree-ssa-propagate.h"
45 #include "value-prof.h"
46 #include "pointer-set.h"
47 #include "tree-inline.h"
48
49 /* This file contains functions for building the Control Flow Graph (CFG)
50 for a function tree. */
51
52 /* Local declarations. */
53
54 /* Initial capacity for the basic block array. */
55 static const int initial_cfg_capacity = 20;
56
57 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
58 which use a particular edge. The CASE_LABEL_EXPRs are chained together
59 via their TREE_CHAIN field, which we clear after we're done with the
60 hash table to prevent problems with duplication of GIMPLE_SWITCHes.
61
62 Access to this list of CASE_LABEL_EXPRs allows us to efficiently
63 update the case vector in response to edge redirections.
64
65 Right now this table is set up and torn down at key points in the
66 compilation process. It would be nice if we could make the table
67 more persistent. The key is getting notification of changes to
68 the CFG (particularly edge removal, creation and redirection). */
69
70 static struct pointer_map_t *edge_to_cases;
71
72 /* If we record edge_to_cases, this bitmap will hold indexes
73 of basic blocks that end in a GIMPLE_SWITCH which we touched
74 due to edge manipulations. */
75
76 static bitmap touched_switch_bbs;
77
78 /* CFG statistics. */
79 struct cfg_stats_d
80 {
81 long num_merged_labels;
82 };
83
84 static struct cfg_stats_d cfg_stats;
85
86 /* Nonzero if we found a computed goto while building basic blocks. */
87 static bool found_computed_goto;
88
89 /* Hash table to store last discriminator assigned for each locus. */
90 struct locus_discrim_map
91 {
92 location_t locus;
93 int discriminator;
94 };
95 static htab_t discriminator_per_locus;
96
97 /* Basic blocks and flowgraphs. */
98 static void make_blocks (gimple_seq);
99 static void factor_computed_gotos (void);
100
101 /* Edges. */
102 static void make_edges (void);
103 static void make_cond_expr_edges (basic_block);
104 static void make_gimple_switch_edges (basic_block);
105 static void make_goto_expr_edges (basic_block);
106 static void make_gimple_asm_edges (basic_block);
107 static unsigned int locus_map_hash (const void *);
108 static int locus_map_eq (const void *, const void *);
109 static void assign_discriminator (location_t, basic_block);
110 static edge gimple_redirect_edge_and_branch (edge, basic_block);
111 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block);
112 static unsigned int split_critical_edges (void);
113
114 /* Various helpers. */
115 static inline bool stmt_starts_bb_p (gimple, gimple);
116 static int gimple_verify_flow_info (void);
117 static void gimple_make_forwarder_block (edge);
118 static void gimple_cfg2vcg (FILE *);
119 static gimple first_non_label_stmt (basic_block);
120
121 /* Flowgraph optimization and cleanup. */
122 static void gimple_merge_blocks (basic_block, basic_block);
123 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
124 static void remove_bb (basic_block);
125 static edge find_taken_edge_computed_goto (basic_block, tree);
126 static edge find_taken_edge_cond_expr (basic_block, tree);
127 static edge find_taken_edge_switch_expr (basic_block, tree);
128 static tree find_case_label_for_value (gimple, tree);
129 static void group_case_labels_stmt (gimple);
130
131 void
132 init_empty_tree_cfg_for_function (struct function *fn)
133 {
134 /* Initialize the basic block array. */
135 init_flow (fn);
136 profile_status_for_function (fn) = PROFILE_ABSENT;
137 n_basic_blocks_for_function (fn) = NUM_FIXED_BLOCKS;
138 last_basic_block_for_function (fn) = NUM_FIXED_BLOCKS;
139 basic_block_info_for_function (fn)
140 = VEC_alloc (basic_block, gc, initial_cfg_capacity);
141 VEC_safe_grow_cleared (basic_block, gc,
142 basic_block_info_for_function (fn),
143 initial_cfg_capacity);
144
145 /* Build a mapping of labels to their associated blocks. */
146 label_to_block_map_for_function (fn)
147 = VEC_alloc (basic_block, gc, initial_cfg_capacity);
148 VEC_safe_grow_cleared (basic_block, gc,
149 label_to_block_map_for_function (fn),
150 initial_cfg_capacity);
151
152 SET_BASIC_BLOCK_FOR_FUNCTION (fn, ENTRY_BLOCK,
153 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn));
154 SET_BASIC_BLOCK_FOR_FUNCTION (fn, EXIT_BLOCK,
155 EXIT_BLOCK_PTR_FOR_FUNCTION (fn));
156
157 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn)->next_bb
158 = EXIT_BLOCK_PTR_FOR_FUNCTION (fn);
159 EXIT_BLOCK_PTR_FOR_FUNCTION (fn)->prev_bb
160 = ENTRY_BLOCK_PTR_FOR_FUNCTION (fn);
161 }
162
163 void
164 init_empty_tree_cfg (void)
165 {
166 init_empty_tree_cfg_for_function (cfun);
167 }
168
169 /*---------------------------------------------------------------------------
170 Create basic blocks
171 ---------------------------------------------------------------------------*/
172
173 /* Entry point to the CFG builder for trees. SEQ is the sequence of
174 statements to be added to the flowgraph. */
175
176 static void
177 build_gimple_cfg (gimple_seq seq)
178 {
179 /* Register specific gimple functions. */
180 gimple_register_cfg_hooks ();
181
182 memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
183
184 init_empty_tree_cfg ();
185
186 found_computed_goto = 0;
187 make_blocks (seq);
188
189 /* Computed gotos are hell to deal with, especially if there are
190 lots of them with a large number of destinations. So we factor
191 them to a common computed goto location before we build the
192 edge list. After we convert back to normal form, we will un-factor
193 the computed gotos since factoring introduces an unwanted jump. */
194 if (found_computed_goto)
195 factor_computed_gotos ();
196
197 /* Make sure there is always at least one block, even if it's empty. */
198 if (n_basic_blocks == NUM_FIXED_BLOCKS)
199 create_empty_bb (ENTRY_BLOCK_PTR);
200
201 /* Adjust the size of the array. */
202 if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
203 VEC_safe_grow_cleared (basic_block, gc, basic_block_info, n_basic_blocks);
204
205 /* To speed up statement iterator walks, we first purge dead labels. */
206 cleanup_dead_labels ();
207
208 /* Group case nodes to reduce the number of edges.
209 We do this after cleaning up dead labels because otherwise we miss
210 a lot of obvious case merging opportunities. */
211 group_case_labels ();
212
213 /* Create the edges of the flowgraph. */
214 discriminator_per_locus = htab_create (13, locus_map_hash, locus_map_eq,
215 free);
216 make_edges ();
217 cleanup_dead_labels ();
218 htab_delete (discriminator_per_locus);
219
220 /* Debugging dumps. */
221
222 /* Write the flowgraph to a VCG file. */
223 {
224 int local_dump_flags;
225 FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
226 if (vcg_file)
227 {
228 gimple_cfg2vcg (vcg_file);
229 dump_end (TDI_vcg, vcg_file);
230 }
231 }
232 }
233
234 static unsigned int
235 execute_build_cfg (void)
236 {
237 gimple_seq body = gimple_body (current_function_decl);
238
239 build_gimple_cfg (body);
240 gimple_set_body (current_function_decl, NULL);
241 if (dump_file && (dump_flags & TDF_DETAILS))
242 {
243 fprintf (dump_file, "Scope blocks:\n");
244 dump_scope_blocks (dump_file, dump_flags);
245 }
246 return 0;
247 }
248
249 struct gimple_opt_pass pass_build_cfg =
250 {
251 {
252 GIMPLE_PASS,
253 "cfg", /* name */
254 NULL, /* gate */
255 execute_build_cfg, /* execute */
256 NULL, /* sub */
257 NULL, /* next */
258 0, /* static_pass_number */
259 TV_TREE_CFG, /* tv_id */
260 PROP_gimple_leh, /* properties_required */
261 PROP_cfg, /* properties_provided */
262 0, /* properties_destroyed */
263 0, /* todo_flags_start */
264 TODO_verify_stmts | TODO_cleanup_cfg
265 | TODO_dump_func /* todo_flags_finish */
266 }
267 };
268
269
270 /* Return true if T is a computed goto. */
271
272 static bool
273 computed_goto_p (gimple t)
274 {
275 return (gimple_code (t) == GIMPLE_GOTO
276 && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
277 }
278
279
280 /* Search the CFG for any computed gotos. If found, factor them to a
281 common computed goto site. Also record the location of that site so
282 that we can un-factor the gotos after we have converted back to
283 normal form. */
284
285 static void
286 factor_computed_gotos (void)
287 {
288 basic_block bb;
289 tree factored_label_decl = NULL;
290 tree var = NULL;
291 gimple factored_computed_goto_label = NULL;
292 gimple factored_computed_goto = NULL;
293
294 /* We know there are one or more computed gotos in this function.
295 Examine the last statement in each basic block to see if the block
296 ends with a computed goto. */
297
298 FOR_EACH_BB (bb)
299 {
300 gimple_stmt_iterator gsi = gsi_last_bb (bb);
301 gimple last;
302
303 if (gsi_end_p (gsi))
304 continue;
305
306 last = gsi_stmt (gsi);
307
308 /* Ignore the computed goto we create when we factor the original
309 computed gotos. */
310 if (last == factored_computed_goto)
311 continue;
312
313 /* If the last statement is a computed goto, factor it. */
314 if (computed_goto_p (last))
315 {
316 gimple assignment;
317
318 /* The first time we find a computed goto we need to create
319 the factored goto block and the variable each original
320 computed goto will use for their goto destination. */
321 if (!factored_computed_goto)
322 {
323 basic_block new_bb = create_empty_bb (bb);
324 gimple_stmt_iterator new_gsi = gsi_start_bb (new_bb);
325
326 /* Create the destination of the factored goto. Each original
327 computed goto will put its desired destination into this
328 variable and jump to the label we create immediately
329 below. */
330 var = create_tmp_var (ptr_type_node, "gotovar");
331
332 /* Build a label for the new block which will contain the
333 factored computed goto. */
334 factored_label_decl = create_artificial_label (UNKNOWN_LOCATION);
335 factored_computed_goto_label
336 = gimple_build_label (factored_label_decl);
337 gsi_insert_after (&new_gsi, factored_computed_goto_label,
338 GSI_NEW_STMT);
339
340 /* Build our new computed goto. */
341 factored_computed_goto = gimple_build_goto (var);
342 gsi_insert_after (&new_gsi, factored_computed_goto, GSI_NEW_STMT);
343 }
344
345 /* Copy the original computed goto's destination into VAR. */
346 assignment = gimple_build_assign (var, gimple_goto_dest (last));
347 gsi_insert_before (&gsi, assignment, GSI_SAME_STMT);
348
349 /* And re-vector the computed goto to the new destination. */
350 gimple_goto_set_dest (last, factored_label_decl);
351 }
352 }
353 }
354
355
356 /* Build a flowgraph for the sequence of stmts SEQ. */
357
358 static void
359 make_blocks (gimple_seq seq)
360 {
361 gimple_stmt_iterator i = gsi_start (seq);
362 gimple stmt = NULL;
363 bool start_new_block = true;
364 bool first_stmt_of_seq = true;
365 basic_block bb = ENTRY_BLOCK_PTR;
366
367 while (!gsi_end_p (i))
368 {
369 gimple prev_stmt;
370
371 prev_stmt = stmt;
372 stmt = gsi_stmt (i);
373
374 /* If the statement starts a new basic block or if we have determined
375 in a previous pass that we need to create a new block for STMT, do
376 so now. */
377 if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
378 {
379 if (!first_stmt_of_seq)
380 seq = gsi_split_seq_before (&i);
381 bb = create_basic_block (seq, NULL, bb);
382 start_new_block = false;
383 }
384
385 /* Now add STMT to BB and create the subgraphs for special statement
386 codes. */
387 gimple_set_bb (stmt, bb);
388
389 if (computed_goto_p (stmt))
390 found_computed_goto = true;
391
392 /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
393 next iteration. */
394 if (stmt_ends_bb_p (stmt))
395 {
396 /* If the stmt can make abnormal goto use a new temporary
397 for the assignment to the LHS. This makes sure the old value
398 of the LHS is available on the abnormal edge. Otherwise
399 we will end up with overlapping life-ranges for abnormal
400 SSA names. */
401 if (gimple_has_lhs (stmt)
402 && stmt_can_make_abnormal_goto (stmt)
403 && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt))))
404 {
405 tree lhs = gimple_get_lhs (stmt);
406 tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
407 gimple s = gimple_build_assign (lhs, tmp);
408 gimple_set_location (s, gimple_location (stmt));
409 gimple_set_block (s, gimple_block (stmt));
410 gimple_set_lhs (stmt, tmp);
411 if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE
412 || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE)
413 DECL_GIMPLE_REG_P (tmp) = 1;
414 gsi_insert_after (&i, s, GSI_SAME_STMT);
415 }
416 start_new_block = true;
417 }
418
419 gsi_next (&i);
420 first_stmt_of_seq = false;
421 }
422 }
423
424
425 /* Create and return a new empty basic block after bb AFTER. */
426
427 static basic_block
428 create_bb (void *h, void *e, basic_block after)
429 {
430 basic_block bb;
431
432 gcc_assert (!e);
433
434 /* Create and initialize a new basic block. Since alloc_block uses
435 GC allocation that clears memory to allocate a basic block, we do
436 not have to clear the newly allocated basic block here. */
437 bb = alloc_block ();
438
439 bb->index = last_basic_block;
440 bb->flags = BB_NEW;
441 bb->il.gimple = ggc_alloc_cleared_gimple_bb_info ();
442 set_bb_seq (bb, h ? (gimple_seq) h : gimple_seq_alloc ());
443
444 /* Add the new block to the linked list of blocks. */
445 link_block (bb, after);
446
447 /* Grow the basic block array if needed. */
448 if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
449 {
450 size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
451 VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
452 }
453
454 /* Add the newly created block to the array. */
455 SET_BASIC_BLOCK (last_basic_block, bb);
456
457 n_basic_blocks++;
458 last_basic_block++;
459
460 return bb;
461 }
462
463
464 /*---------------------------------------------------------------------------
465 Edge creation
466 ---------------------------------------------------------------------------*/
467
468 /* Fold COND_EXPR_COND of each COND_EXPR. */
469
470 void
471 fold_cond_expr_cond (void)
472 {
473 basic_block bb;
474
475 FOR_EACH_BB (bb)
476 {
477 gimple stmt = last_stmt (bb);
478
479 if (stmt && gimple_code (stmt) == GIMPLE_COND)
480 {
481 location_t loc = gimple_location (stmt);
482 tree cond;
483 bool zerop, onep;
484
485 fold_defer_overflow_warnings ();
486 cond = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node,
487 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
488 if (cond)
489 {
490 zerop = integer_zerop (cond);
491 onep = integer_onep (cond);
492 }
493 else
494 zerop = onep = false;
495
496 fold_undefer_overflow_warnings (zerop || onep,
497 stmt,
498 WARN_STRICT_OVERFLOW_CONDITIONAL);
499 if (zerop)
500 gimple_cond_make_false (stmt);
501 else if (onep)
502 gimple_cond_make_true (stmt);
503 }
504 }
505 }
506
507 /* Join all the blocks in the flowgraph. */
508
509 static void
510 make_edges (void)
511 {
512 basic_block bb;
513 struct omp_region *cur_region = NULL;
514
515 /* Create an edge from entry to the first block with executable
516 statements in it. */
517 make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
518
519 /* Traverse the basic block array placing edges. */
520 FOR_EACH_BB (bb)
521 {
522 gimple last = last_stmt (bb);
523 bool fallthru;
524
525 if (last)
526 {
527 enum gimple_code code = gimple_code (last);
528 switch (code)
529 {
530 case GIMPLE_GOTO:
531 make_goto_expr_edges (bb);
532 fallthru = false;
533 break;
534 case GIMPLE_RETURN:
535 make_edge (bb, EXIT_BLOCK_PTR, 0);
536 fallthru = false;
537 break;
538 case GIMPLE_COND:
539 make_cond_expr_edges (bb);
540 fallthru = false;
541 break;
542 case GIMPLE_SWITCH:
543 make_gimple_switch_edges (bb);
544 fallthru = false;
545 break;
546 case GIMPLE_RESX:
547 make_eh_edges (last);
548 fallthru = false;
549 break;
550 case GIMPLE_EH_DISPATCH:
551 fallthru = make_eh_dispatch_edges (last);
552 break;
553
554 case GIMPLE_CALL:
555 /* If this function receives a nonlocal goto, then we need to
556 make edges from this call site to all the nonlocal goto
557 handlers. */
558 if (stmt_can_make_abnormal_goto (last))
559 make_abnormal_goto_edges (bb, true);
560
561 /* If this statement has reachable exception handlers, then
562 create abnormal edges to them. */
563 make_eh_edges (last);
564
565 /* BUILTIN_RETURN is really a return statement. */
566 if (gimple_call_builtin_p (last, BUILT_IN_RETURN))
567 make_edge (bb, EXIT_BLOCK_PTR, 0), fallthru = false;
568 /* Some calls are known not to return. */
569 else
570 fallthru = !(gimple_call_flags (last) & ECF_NORETURN);
571 break;
572
573 case GIMPLE_ASSIGN:
574 /* A GIMPLE_ASSIGN may throw internally and thus be considered
575 control-altering. */
576 if (is_ctrl_altering_stmt (last))
577 make_eh_edges (last);
578 fallthru = true;
579 break;
580
581 case GIMPLE_ASM:
582 make_gimple_asm_edges (bb);
583 fallthru = true;
584 break;
585
586 case GIMPLE_OMP_PARALLEL:
587 case GIMPLE_OMP_TASK:
588 case GIMPLE_OMP_FOR:
589 case GIMPLE_OMP_SINGLE:
590 case GIMPLE_OMP_MASTER:
591 case GIMPLE_OMP_ORDERED:
592 case GIMPLE_OMP_CRITICAL:
593 case GIMPLE_OMP_SECTION:
594 cur_region = new_omp_region (bb, code, cur_region);
595 fallthru = true;
596 break;
597
598 case GIMPLE_OMP_SECTIONS:
599 cur_region = new_omp_region (bb, code, cur_region);
600 fallthru = true;
601 break;
602
603 case GIMPLE_OMP_SECTIONS_SWITCH:
604 fallthru = false;
605 break;
606
607 case GIMPLE_OMP_ATOMIC_LOAD:
608 case GIMPLE_OMP_ATOMIC_STORE:
609 fallthru = true;
610 break;
611
612 case GIMPLE_OMP_RETURN:
613 /* In the case of a GIMPLE_OMP_SECTION, the edge will go
614 somewhere other than the next block. This will be
615 created later. */
616 cur_region->exit = bb;
617 fallthru = cur_region->type != GIMPLE_OMP_SECTION;
618 cur_region = cur_region->outer;
619 break;
620
621 case GIMPLE_OMP_CONTINUE:
622 cur_region->cont = bb;
623 switch (cur_region->type)
624 {
625 case GIMPLE_OMP_FOR:
626 /* Mark all GIMPLE_OMP_FOR and GIMPLE_OMP_CONTINUE
627 succs edges as abnormal to prevent splitting
628 them. */
629 single_succ_edge (cur_region->entry)->flags |= EDGE_ABNORMAL;
630 /* Make the loopback edge. */
631 make_edge (bb, single_succ (cur_region->entry),
632 EDGE_ABNORMAL);
633
634 /* Create an edge from GIMPLE_OMP_FOR to exit, which
635 corresponds to the case that the body of the loop
636 is not executed at all. */
637 make_edge (cur_region->entry, bb->next_bb, EDGE_ABNORMAL);
638 make_edge (bb, bb->next_bb, EDGE_FALLTHRU | EDGE_ABNORMAL);
639 fallthru = false;
640 break;
641
642 case GIMPLE_OMP_SECTIONS:
643 /* Wire up the edges into and out of the nested sections. */
644 {
645 basic_block switch_bb = single_succ (cur_region->entry);
646
647 struct omp_region *i;
648 for (i = cur_region->inner; i ; i = i->next)
649 {
650 gcc_assert (i->type == GIMPLE_OMP_SECTION);
651 make_edge (switch_bb, i->entry, 0);
652 make_edge (i->exit, bb, EDGE_FALLTHRU);
653 }
654
655 /* Make the loopback edge to the block with
656 GIMPLE_OMP_SECTIONS_SWITCH. */
657 make_edge (bb, switch_bb, 0);
658
659 /* Make the edge from the switch to exit. */
660 make_edge (switch_bb, bb->next_bb, 0);
661 fallthru = false;
662 }
663 break;
664
665 default:
666 gcc_unreachable ();
667 }
668 break;
669
670 default:
671 gcc_assert (!stmt_ends_bb_p (last));
672 fallthru = true;
673 }
674 }
675 else
676 fallthru = true;
677
678 if (fallthru)
679 {
680 make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
681 if (last)
682 assign_discriminator (gimple_location (last), bb->next_bb);
683 }
684 }
685
686 if (root_omp_region)
687 free_omp_regions ();
688
689 /* Fold COND_EXPR_COND of each COND_EXPR. */
690 fold_cond_expr_cond ();
691 }
692
693 /* Trivial hash function for a location_t. ITEM is a pointer to
694 a hash table entry that maps a location_t to a discriminator. */
695
696 static unsigned int
697 locus_map_hash (const void *item)
698 {
699 return ((const struct locus_discrim_map *) item)->locus;
700 }
701
702 /* Equality function for the locus-to-discriminator map. VA and VB
703 point to the two hash table entries to compare. */
704
705 static int
706 locus_map_eq (const void *va, const void *vb)
707 {
708 const struct locus_discrim_map *a = (const struct locus_discrim_map *) va;
709 const struct locus_discrim_map *b = (const struct locus_discrim_map *) vb;
710 return a->locus == b->locus;
711 }
712
713 /* Find the next available discriminator value for LOCUS. The
714 discriminator distinguishes among several basic blocks that
715 share a common locus, allowing for more accurate sample-based
716 profiling. */
717
718 static int
719 next_discriminator_for_locus (location_t locus)
720 {
721 struct locus_discrim_map item;
722 struct locus_discrim_map **slot;
723
724 item.locus = locus;
725 item.discriminator = 0;
726 slot = (struct locus_discrim_map **)
727 htab_find_slot_with_hash (discriminator_per_locus, (void *) &item,
728 (hashval_t) locus, INSERT);
729 gcc_assert (slot);
730 if (*slot == HTAB_EMPTY_ENTRY)
731 {
732 *slot = XNEW (struct locus_discrim_map);
733 gcc_assert (*slot);
734 (*slot)->locus = locus;
735 (*slot)->discriminator = 0;
736 }
737 (*slot)->discriminator++;
738 return (*slot)->discriminator;
739 }
740
741 /* Return TRUE if LOCUS1 and LOCUS2 refer to the same source line. */
742
743 static bool
744 same_line_p (location_t locus1, location_t locus2)
745 {
746 expanded_location from, to;
747
748 if (locus1 == locus2)
749 return true;
750
751 from = expand_location (locus1);
752 to = expand_location (locus2);
753
754 if (from.line != to.line)
755 return false;
756 if (from.file == to.file)
757 return true;
758 return (from.file != NULL
759 && to.file != NULL
760 && filename_cmp (from.file, to.file) == 0);
761 }
762
763 /* Assign a unique discriminator value to block BB if it begins at the same
764 LOCUS as its predecessor block. */
765
766 static void
767 assign_discriminator (location_t locus, basic_block bb)
768 {
769 gimple first_in_to_bb, last_in_to_bb;
770
771 if (locus == 0 || bb->discriminator != 0)
772 return;
773
774 first_in_to_bb = first_non_label_stmt (bb);
775 last_in_to_bb = last_stmt (bb);
776 if ((first_in_to_bb && same_line_p (locus, gimple_location (first_in_to_bb)))
777 || (last_in_to_bb && same_line_p (locus, gimple_location (last_in_to_bb))))
778 bb->discriminator = next_discriminator_for_locus (locus);
779 }
780
781 /* Create the edges for a GIMPLE_COND starting at block BB. */
782
783 static void
784 make_cond_expr_edges (basic_block bb)
785 {
786 gimple entry = last_stmt (bb);
787 gimple then_stmt, else_stmt;
788 basic_block then_bb, else_bb;
789 tree then_label, else_label;
790 edge e;
791 location_t entry_locus;
792
793 gcc_assert (entry);
794 gcc_assert (gimple_code (entry) == GIMPLE_COND);
795
796 entry_locus = gimple_location (entry);
797
798 /* Entry basic blocks for each component. */
799 then_label = gimple_cond_true_label (entry);
800 else_label = gimple_cond_false_label (entry);
801 then_bb = label_to_block (then_label);
802 else_bb = label_to_block (else_label);
803 then_stmt = first_stmt (then_bb);
804 else_stmt = first_stmt (else_bb);
805
806 e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
807 assign_discriminator (entry_locus, then_bb);
808 e->goto_locus = gimple_location (then_stmt);
809 if (e->goto_locus)
810 e->goto_block = gimple_block (then_stmt);
811 e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
812 if (e)
813 {
814 assign_discriminator (entry_locus, else_bb);
815 e->goto_locus = gimple_location (else_stmt);
816 if (e->goto_locus)
817 e->goto_block = gimple_block (else_stmt);
818 }
819
820 /* We do not need the labels anymore. */
821 gimple_cond_set_true_label (entry, NULL_TREE);
822 gimple_cond_set_false_label (entry, NULL_TREE);
823 }
824
825
826 /* Called for each element in the hash table (P) as we delete the
827 edge to cases hash table.
828
829 Clear all the TREE_CHAINs to prevent problems with copying of
830 SWITCH_EXPRs and structure sharing rules, then free the hash table
831 element. */
832
833 static bool
834 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
835 void *data ATTRIBUTE_UNUSED)
836 {
837 tree t, next;
838
839 for (t = (tree) *value; t; t = next)
840 {
841 next = TREE_CHAIN (t);
842 TREE_CHAIN (t) = NULL;
843 }
844
845 *value = NULL;
846 return false;
847 }
848
849 /* Start recording information mapping edges to case labels. */
850
851 void
852 start_recording_case_labels (void)
853 {
854 gcc_assert (edge_to_cases == NULL);
855 edge_to_cases = pointer_map_create ();
856 touched_switch_bbs = BITMAP_ALLOC (NULL);
857 }
858
859 /* Return nonzero if we are recording information for case labels. */
860
861 static bool
862 recording_case_labels_p (void)
863 {
864 return (edge_to_cases != NULL);
865 }
866
867 /* Stop recording information mapping edges to case labels and
868 remove any information we have recorded. */
869 void
870 end_recording_case_labels (void)
871 {
872 bitmap_iterator bi;
873 unsigned i;
874 pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
875 pointer_map_destroy (edge_to_cases);
876 edge_to_cases = NULL;
877 EXECUTE_IF_SET_IN_BITMAP (touched_switch_bbs, 0, i, bi)
878 {
879 basic_block bb = BASIC_BLOCK (i);
880 if (bb)
881 {
882 gimple stmt = last_stmt (bb);
883 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
884 group_case_labels_stmt (stmt);
885 }
886 }
887 BITMAP_FREE (touched_switch_bbs);
888 }
889
890 /* If we are inside a {start,end}_recording_cases block, then return
891 a chain of CASE_LABEL_EXPRs from T which reference E.
892
893 Otherwise return NULL. */
894
895 static tree
896 get_cases_for_edge (edge e, gimple t)
897 {
898 void **slot;
899 size_t i, n;
900
901 /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
902 chains available. Return NULL so the caller can detect this case. */
903 if (!recording_case_labels_p ())
904 return NULL;
905
906 slot = pointer_map_contains (edge_to_cases, e);
907 if (slot)
908 return (tree) *slot;
909
910 /* If we did not find E in the hash table, then this must be the first
911 time we have been queried for information about E & T. Add all the
912 elements from T to the hash table then perform the query again. */
913
914 n = gimple_switch_num_labels (t);
915 for (i = 0; i < n; i++)
916 {
917 tree elt = gimple_switch_label (t, i);
918 tree lab = CASE_LABEL (elt);
919 basic_block label_bb = label_to_block (lab);
920 edge this_edge = find_edge (e->src, label_bb);
921
922 /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
923 a new chain. */
924 slot = pointer_map_insert (edge_to_cases, this_edge);
925 TREE_CHAIN (elt) = (tree) *slot;
926 *slot = elt;
927 }
928
929 return (tree) *pointer_map_contains (edge_to_cases, e);
930 }
931
932 /* Create the edges for a GIMPLE_SWITCH starting at block BB. */
933
934 static void
935 make_gimple_switch_edges (basic_block bb)
936 {
937 gimple entry = last_stmt (bb);
938 location_t entry_locus;
939 size_t i, n;
940
941 entry_locus = gimple_location (entry);
942
943 n = gimple_switch_num_labels (entry);
944
945 for (i = 0; i < n; ++i)
946 {
947 tree lab = CASE_LABEL (gimple_switch_label (entry, i));
948 basic_block label_bb = label_to_block (lab);
949 make_edge (bb, label_bb, 0);
950 assign_discriminator (entry_locus, label_bb);
951 }
952 }
953
954
955 /* Return the basic block holding label DEST. */
956
957 basic_block
958 label_to_block_fn (struct function *ifun, tree dest)
959 {
960 int uid = LABEL_DECL_UID (dest);
961
962 /* We would die hard when faced by an undefined label. Emit a label to
963 the very first basic block. This will hopefully make even the dataflow
964 and undefined variable warnings quite right. */
965 if (seen_error () && uid < 0)
966 {
967 gimple_stmt_iterator gsi = gsi_start_bb (BASIC_BLOCK (NUM_FIXED_BLOCKS));
968 gimple stmt;
969
970 stmt = gimple_build_label (dest);
971 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
972 uid = LABEL_DECL_UID (dest);
973 }
974 if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
975 <= (unsigned int) uid)
976 return NULL;
977 return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
978 }
979
980 /* Create edges for an abnormal goto statement at block BB. If FOR_CALL
981 is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR. */
982
983 void
984 make_abnormal_goto_edges (basic_block bb, bool for_call)
985 {
986 basic_block target_bb;
987 gimple_stmt_iterator gsi;
988
989 FOR_EACH_BB (target_bb)
990 for (gsi = gsi_start_bb (target_bb); !gsi_end_p (gsi); gsi_next (&gsi))
991 {
992 gimple label_stmt = gsi_stmt (gsi);
993 tree target;
994
995 if (gimple_code (label_stmt) != GIMPLE_LABEL)
996 break;
997
998 target = gimple_label_label (label_stmt);
999
1000 /* Make an edge to every label block that has been marked as a
1001 potential target for a computed goto or a non-local goto. */
1002 if ((FORCED_LABEL (target) && !for_call)
1003 || (DECL_NONLOCAL (target) && for_call))
1004 {
1005 make_edge (bb, target_bb, EDGE_ABNORMAL);
1006 break;
1007 }
1008 }
1009 }
1010
1011 /* Create edges for a goto statement at block BB. */
1012
1013 static void
1014 make_goto_expr_edges (basic_block bb)
1015 {
1016 gimple_stmt_iterator last = gsi_last_bb (bb);
1017 gimple goto_t = gsi_stmt (last);
1018
1019 /* A simple GOTO creates normal edges. */
1020 if (simple_goto_p (goto_t))
1021 {
1022 tree dest = gimple_goto_dest (goto_t);
1023 basic_block label_bb = label_to_block (dest);
1024 edge e = make_edge (bb, label_bb, EDGE_FALLTHRU);
1025 e->goto_locus = gimple_location (goto_t);
1026 assign_discriminator (e->goto_locus, label_bb);
1027 if (e->goto_locus)
1028 e->goto_block = gimple_block (goto_t);
1029 gsi_remove (&last, true);
1030 return;
1031 }
1032
1033 /* A computed GOTO creates abnormal edges. */
1034 make_abnormal_goto_edges (bb, false);
1035 }
1036
1037 /* Create edges for an asm statement with labels at block BB. */
1038
1039 static void
1040 make_gimple_asm_edges (basic_block bb)
1041 {
1042 gimple stmt = last_stmt (bb);
1043 location_t stmt_loc = gimple_location (stmt);
1044 int i, n = gimple_asm_nlabels (stmt);
1045
1046 for (i = 0; i < n; ++i)
1047 {
1048 tree label = TREE_VALUE (gimple_asm_label_op (stmt, i));
1049 basic_block label_bb = label_to_block (label);
1050 make_edge (bb, label_bb, 0);
1051 assign_discriminator (stmt_loc, label_bb);
1052 }
1053 }
1054
1055 /*---------------------------------------------------------------------------
1056 Flowgraph analysis
1057 ---------------------------------------------------------------------------*/
1058
1059 /* Cleanup useless labels in basic blocks. This is something we wish
1060 to do early because it allows us to group case labels before creating
1061 the edges for the CFG, and it speeds up block statement iterators in
1062 all passes later on.
1063 We rerun this pass after CFG is created, to get rid of the labels that
1064 are no longer referenced. After then we do not run it any more, since
1065 (almost) no new labels should be created. */
1066
1067 /* A map from basic block index to the leading label of that block. */
1068 static struct label_record
1069 {
1070 /* The label. */
1071 tree label;
1072
1073 /* True if the label is referenced from somewhere. */
1074 bool used;
1075 } *label_for_bb;
1076
1077 /* Given LABEL return the first label in the same basic block. */
1078
1079 static tree
1080 main_block_label (tree label)
1081 {
1082 basic_block bb = label_to_block (label);
1083 tree main_label = label_for_bb[bb->index].label;
1084
1085 /* label_to_block possibly inserted undefined label into the chain. */
1086 if (!main_label)
1087 {
1088 label_for_bb[bb->index].label = label;
1089 main_label = label;
1090 }
1091
1092 label_for_bb[bb->index].used = true;
1093 return main_label;
1094 }
1095
1096 /* Clean up redundant labels within the exception tree. */
1097
1098 static void
1099 cleanup_dead_labels_eh (void)
1100 {
1101 eh_landing_pad lp;
1102 eh_region r;
1103 tree lab;
1104 int i;
1105
1106 if (cfun->eh == NULL)
1107 return;
1108
1109 for (i = 1; VEC_iterate (eh_landing_pad, cfun->eh->lp_array, i, lp); ++i)
1110 if (lp && lp->post_landing_pad)
1111 {
1112 lab = main_block_label (lp->post_landing_pad);
1113 if (lab != lp->post_landing_pad)
1114 {
1115 EH_LANDING_PAD_NR (lp->post_landing_pad) = 0;
1116 EH_LANDING_PAD_NR (lab) = lp->index;
1117 }
1118 }
1119
1120 FOR_ALL_EH_REGION (r)
1121 switch (r->type)
1122 {
1123 case ERT_CLEANUP:
1124 case ERT_MUST_NOT_THROW:
1125 break;
1126
1127 case ERT_TRY:
1128 {
1129 eh_catch c;
1130 for (c = r->u.eh_try.first_catch; c ; c = c->next_catch)
1131 {
1132 lab = c->label;
1133 if (lab)
1134 c->label = main_block_label (lab);
1135 }
1136 }
1137 break;
1138
1139 case ERT_ALLOWED_EXCEPTIONS:
1140 lab = r->u.allowed.label;
1141 if (lab)
1142 r->u.allowed.label = main_block_label (lab);
1143 break;
1144 }
1145 }
1146
1147
1148 /* Cleanup redundant labels. This is a three-step process:
1149 1) Find the leading label for each block.
1150 2) Redirect all references to labels to the leading labels.
1151 3) Cleanup all useless labels. */
1152
1153 void
1154 cleanup_dead_labels (void)
1155 {
1156 basic_block bb;
1157 label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
1158
1159 /* Find a suitable label for each block. We use the first user-defined
1160 label if there is one, or otherwise just the first label we see. */
1161 FOR_EACH_BB (bb)
1162 {
1163 gimple_stmt_iterator i;
1164
1165 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
1166 {
1167 tree label;
1168 gimple stmt = gsi_stmt (i);
1169
1170 if (gimple_code (stmt) != GIMPLE_LABEL)
1171 break;
1172
1173 label = gimple_label_label (stmt);
1174
1175 /* If we have not yet seen a label for the current block,
1176 remember this one and see if there are more labels. */
1177 if (!label_for_bb[bb->index].label)
1178 {
1179 label_for_bb[bb->index].label = label;
1180 continue;
1181 }
1182
1183 /* If we did see a label for the current block already, but it
1184 is an artificially created label, replace it if the current
1185 label is a user defined label. */
1186 if (!DECL_ARTIFICIAL (label)
1187 && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
1188 {
1189 label_for_bb[bb->index].label = label;
1190 break;
1191 }
1192 }
1193 }
1194
1195 /* Now redirect all jumps/branches to the selected label.
1196 First do so for each block ending in a control statement. */
1197 FOR_EACH_BB (bb)
1198 {
1199 gimple stmt = last_stmt (bb);
1200 if (!stmt)
1201 continue;
1202
1203 switch (gimple_code (stmt))
1204 {
1205 case GIMPLE_COND:
1206 {
1207 tree true_label = gimple_cond_true_label (stmt);
1208 tree false_label = gimple_cond_false_label (stmt);
1209
1210 if (true_label)
1211 gimple_cond_set_true_label (stmt, main_block_label (true_label));
1212 if (false_label)
1213 gimple_cond_set_false_label (stmt, main_block_label (false_label));
1214 break;
1215 }
1216
1217 case GIMPLE_SWITCH:
1218 {
1219 size_t i, n = gimple_switch_num_labels (stmt);
1220
1221 /* Replace all destination labels. */
1222 for (i = 0; i < n; ++i)
1223 {
1224 tree case_label = gimple_switch_label (stmt, i);
1225 tree label = main_block_label (CASE_LABEL (case_label));
1226 CASE_LABEL (case_label) = label;
1227 }
1228 break;
1229 }
1230
1231 case GIMPLE_ASM:
1232 {
1233 int i, n = gimple_asm_nlabels (stmt);
1234
1235 for (i = 0; i < n; ++i)
1236 {
1237 tree cons = gimple_asm_label_op (stmt, i);
1238 tree label = main_block_label (TREE_VALUE (cons));
1239 TREE_VALUE (cons) = label;
1240 }
1241 break;
1242 }
1243
1244 /* We have to handle gotos until they're removed, and we don't
1245 remove them until after we've created the CFG edges. */
1246 case GIMPLE_GOTO:
1247 if (!computed_goto_p (stmt))
1248 {
1249 tree new_dest = main_block_label (gimple_goto_dest (stmt));
1250 gimple_goto_set_dest (stmt, new_dest);
1251 }
1252 break;
1253
1254 default:
1255 break;
1256 }
1257 }
1258
1259 /* Do the same for the exception region tree labels. */
1260 cleanup_dead_labels_eh ();
1261
1262 /* Finally, purge dead labels. All user-defined labels and labels that
1263 can be the target of non-local gotos and labels which have their
1264 address taken are preserved. */
1265 FOR_EACH_BB (bb)
1266 {
1267 gimple_stmt_iterator i;
1268 tree label_for_this_bb = label_for_bb[bb->index].label;
1269
1270 if (!label_for_this_bb)
1271 continue;
1272
1273 /* If the main label of the block is unused, we may still remove it. */
1274 if (!label_for_bb[bb->index].used)
1275 label_for_this_bb = NULL;
1276
1277 for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1278 {
1279 tree label;
1280 gimple stmt = gsi_stmt (i);
1281
1282 if (gimple_code (stmt) != GIMPLE_LABEL)
1283 break;
1284
1285 label = gimple_label_label (stmt);
1286
1287 if (label == label_for_this_bb
1288 || !DECL_ARTIFICIAL (label)
1289 || DECL_NONLOCAL (label)
1290 || FORCED_LABEL (label))
1291 gsi_next (&i);
1292 else
1293 gsi_remove (&i, true);
1294 }
1295 }
1296
1297 free (label_for_bb);
1298 }
1299
1300 /* Scan the sorted vector of cases in STMT (a GIMPLE_SWITCH) and combine
1301 the ones jumping to the same label.
1302 Eg. three separate entries 1: 2: 3: become one entry 1..3: */
1303
1304 static void
1305 group_case_labels_stmt (gimple stmt)
1306 {
1307 int old_size = gimple_switch_num_labels (stmt);
1308 int i, j, new_size = old_size;
1309 tree default_case = NULL_TREE;
1310 tree default_label = NULL_TREE;
1311 bool has_default;
1312
1313 /* The default label is always the first case in a switch
1314 statement after gimplification if it was not optimized
1315 away */
1316 if (!CASE_LOW (gimple_switch_default_label (stmt))
1317 && !CASE_HIGH (gimple_switch_default_label (stmt)))
1318 {
1319 default_case = gimple_switch_default_label (stmt);
1320 default_label = CASE_LABEL (default_case);
1321 has_default = true;
1322 }
1323 else
1324 has_default = false;
1325
1326 /* Look for possible opportunities to merge cases. */
1327 if (has_default)
1328 i = 1;
1329 else
1330 i = 0;
1331 while (i < old_size)
1332 {
1333 tree base_case, base_label, base_high;
1334 base_case = gimple_switch_label (stmt, i);
1335
1336 gcc_assert (base_case);
1337 base_label = CASE_LABEL (base_case);
1338
1339 /* Discard cases that have the same destination as the
1340 default case. */
1341 if (base_label == default_label)
1342 {
1343 gimple_switch_set_label (stmt, i, NULL_TREE);
1344 i++;
1345 new_size--;
1346 continue;
1347 }
1348
1349 base_high = CASE_HIGH (base_case)
1350 ? CASE_HIGH (base_case)
1351 : CASE_LOW (base_case);
1352 i++;
1353
1354 /* Try to merge case labels. Break out when we reach the end
1355 of the label vector or when we cannot merge the next case
1356 label with the current one. */
1357 while (i < old_size)
1358 {
1359 tree merge_case = gimple_switch_label (stmt, i);
1360 tree merge_label = CASE_LABEL (merge_case);
1361 tree t = int_const_binop (PLUS_EXPR, base_high,
1362 integer_one_node, 1);
1363
1364 /* Merge the cases if they jump to the same place,
1365 and their ranges are consecutive. */
1366 if (merge_label == base_label
1367 && tree_int_cst_equal (CASE_LOW (merge_case), t))
1368 {
1369 base_high = CASE_HIGH (merge_case) ?
1370 CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1371 CASE_HIGH (base_case) = base_high;
1372 gimple_switch_set_label (stmt, i, NULL_TREE);
1373 new_size--;
1374 i++;
1375 }
1376 else
1377 break;
1378 }
1379 }
1380
1381 /* Compress the case labels in the label vector, and adjust the
1382 length of the vector. */
1383 for (i = 0, j = 0; i < new_size; i++)
1384 {
1385 while (! gimple_switch_label (stmt, j))
1386 j++;
1387 gimple_switch_set_label (stmt, i,
1388 gimple_switch_label (stmt, j++));
1389 }
1390
1391 gcc_assert (new_size <= old_size);
1392 gimple_switch_set_num_labels (stmt, new_size);
1393 }
1394
1395 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
1396 and scan the sorted vector of cases. Combine the ones jumping to the
1397 same label. */
1398
1399 void
1400 group_case_labels (void)
1401 {
1402 basic_block bb;
1403
1404 FOR_EACH_BB (bb)
1405 {
1406 gimple stmt = last_stmt (bb);
1407 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1408 group_case_labels_stmt (stmt);
1409 }
1410 }
1411
1412 /* Checks whether we can merge block B into block A. */
1413
1414 static bool
1415 gimple_can_merge_blocks_p (basic_block a, basic_block b)
1416 {
1417 gimple stmt;
1418 gimple_stmt_iterator gsi;
1419 gimple_seq phis;
1420
1421 if (!single_succ_p (a))
1422 return false;
1423
1424 if (single_succ_edge (a)->flags & (EDGE_ABNORMAL | EDGE_EH))
1425 return false;
1426
1427 if (single_succ (a) != b)
1428 return false;
1429
1430 if (!single_pred_p (b))
1431 return false;
1432
1433 if (b == EXIT_BLOCK_PTR)
1434 return false;
1435
1436 /* If A ends by a statement causing exceptions or something similar, we
1437 cannot merge the blocks. */
1438 stmt = last_stmt (a);
1439 if (stmt && stmt_ends_bb_p (stmt))
1440 return false;
1441
1442 /* Do not allow a block with only a non-local label to be merged. */
1443 if (stmt
1444 && gimple_code (stmt) == GIMPLE_LABEL
1445 && DECL_NONLOCAL (gimple_label_label (stmt)))
1446 return false;
1447
1448 /* Examine the labels at the beginning of B. */
1449 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
1450 {
1451 tree lab;
1452 stmt = gsi_stmt (gsi);
1453 if (gimple_code (stmt) != GIMPLE_LABEL)
1454 break;
1455 lab = gimple_label_label (stmt);
1456
1457 /* Do not remove user labels. */
1458 if (!DECL_ARTIFICIAL (lab))
1459 return false;
1460 }
1461
1462 /* Protect the loop latches. */
1463 if (current_loops && b->loop_father->latch == b)
1464 return false;
1465
1466 /* It must be possible to eliminate all phi nodes in B. If ssa form
1467 is not up-to-date and a name-mapping is registered, we cannot eliminate
1468 any phis. Symbols marked for renaming are never a problem though. */
1469 phis = phi_nodes (b);
1470 if (!gimple_seq_empty_p (phis)
1471 && name_mappings_registered_p ())
1472 return false;
1473
1474 /* When not optimizing, don't merge if we'd lose goto_locus. */
1475 if (!optimize
1476 && single_succ_edge (a)->goto_locus != UNKNOWN_LOCATION)
1477 {
1478 location_t goto_locus = single_succ_edge (a)->goto_locus;
1479 gimple_stmt_iterator prev, next;
1480 prev = gsi_last_nondebug_bb (a);
1481 next = gsi_after_labels (b);
1482 if (!gsi_end_p (next) && is_gimple_debug (gsi_stmt (next)))
1483 gsi_next_nondebug (&next);
1484 if ((gsi_end_p (prev)
1485 || gimple_location (gsi_stmt (prev)) != goto_locus)
1486 && (gsi_end_p (next)
1487 || gimple_location (gsi_stmt (next)) != goto_locus))
1488 return false;
1489 }
1490
1491 return true;
1492 }
1493
1494 /* Return true if the var whose chain of uses starts at PTR has no
1495 nondebug uses. */
1496 bool
1497 has_zero_uses_1 (const ssa_use_operand_t *head)
1498 {
1499 const ssa_use_operand_t *ptr;
1500
1501 for (ptr = head->next; ptr != head; ptr = ptr->next)
1502 if (!is_gimple_debug (USE_STMT (ptr)))
1503 return false;
1504
1505 return true;
1506 }
1507
1508 /* Return true if the var whose chain of uses starts at PTR has a
1509 single nondebug use. Set USE_P and STMT to that single nondebug
1510 use, if so, or to NULL otherwise. */
1511 bool
1512 single_imm_use_1 (const ssa_use_operand_t *head,
1513 use_operand_p *use_p, gimple *stmt)
1514 {
1515 ssa_use_operand_t *ptr, *single_use = 0;
1516
1517 for (ptr = head->next; ptr != head; ptr = ptr->next)
1518 if (!is_gimple_debug (USE_STMT (ptr)))
1519 {
1520 if (single_use)
1521 {
1522 single_use = NULL;
1523 break;
1524 }
1525 single_use = ptr;
1526 }
1527
1528 if (use_p)
1529 *use_p = single_use;
1530
1531 if (stmt)
1532 *stmt = single_use ? single_use->loc.stmt : NULL;
1533
1534 return !!single_use;
1535 }
1536
1537 /* Replaces all uses of NAME by VAL. */
1538
1539 void
1540 replace_uses_by (tree name, tree val)
1541 {
1542 imm_use_iterator imm_iter;
1543 use_operand_p use;
1544 gimple stmt;
1545 edge e;
1546
1547 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1548 {
1549 FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1550 {
1551 replace_exp (use, val);
1552
1553 if (gimple_code (stmt) == GIMPLE_PHI)
1554 {
1555 e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use));
1556 if (e->flags & EDGE_ABNORMAL)
1557 {
1558 /* This can only occur for virtual operands, since
1559 for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1560 would prevent replacement. */
1561 gcc_assert (!is_gimple_reg (name));
1562 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1563 }
1564 }
1565 }
1566
1567 if (gimple_code (stmt) != GIMPLE_PHI)
1568 {
1569 size_t i;
1570
1571 fold_stmt_inplace (stmt);
1572 if (cfgcleanup_altered_bbs && !is_gimple_debug (stmt))
1573 bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1574
1575 /* FIXME. This should go in update_stmt. */
1576 for (i = 0; i < gimple_num_ops (stmt); i++)
1577 {
1578 tree op = gimple_op (stmt, i);
1579 /* Operands may be empty here. For example, the labels
1580 of a GIMPLE_COND are nulled out following the creation
1581 of the corresponding CFG edges. */
1582 if (op && TREE_CODE (op) == ADDR_EXPR)
1583 recompute_tree_invariant_for_addr_expr (op);
1584 }
1585
1586 maybe_clean_or_replace_eh_stmt (stmt, stmt);
1587 update_stmt (stmt);
1588 }
1589 }
1590
1591 gcc_assert (has_zero_uses (name));
1592
1593 /* Also update the trees stored in loop structures. */
1594 if (current_loops)
1595 {
1596 struct loop *loop;
1597 loop_iterator li;
1598
1599 FOR_EACH_LOOP (li, loop, 0)
1600 {
1601 substitute_in_loop_info (loop, name, val);
1602 }
1603 }
1604 }
1605
1606 /* Merge block B into block A. */
1607
1608 static void
1609 gimple_merge_blocks (basic_block a, basic_block b)
1610 {
1611 gimple_stmt_iterator last, gsi, psi;
1612 gimple_seq phis = phi_nodes (b);
1613
1614 if (dump_file)
1615 fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1616
1617 /* Remove all single-valued PHI nodes from block B of the form
1618 V_i = PHI <V_j> by propagating V_j to all the uses of V_i. */
1619 gsi = gsi_last_bb (a);
1620 for (psi = gsi_start (phis); !gsi_end_p (psi); )
1621 {
1622 gimple phi = gsi_stmt (psi);
1623 tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1624 gimple copy;
1625 bool may_replace_uses = !is_gimple_reg (def)
1626 || may_propagate_copy (def, use);
1627
1628 /* In case we maintain loop closed ssa form, do not propagate arguments
1629 of loop exit phi nodes. */
1630 if (current_loops
1631 && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1632 && is_gimple_reg (def)
1633 && TREE_CODE (use) == SSA_NAME
1634 && a->loop_father != b->loop_father)
1635 may_replace_uses = false;
1636
1637 if (!may_replace_uses)
1638 {
1639 gcc_assert (is_gimple_reg (def));
1640
1641 /* Note that just emitting the copies is fine -- there is no problem
1642 with ordering of phi nodes. This is because A is the single
1643 predecessor of B, therefore results of the phi nodes cannot
1644 appear as arguments of the phi nodes. */
1645 copy = gimple_build_assign (def, use);
1646 gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1647 remove_phi_node (&psi, false);
1648 }
1649 else
1650 {
1651 /* If we deal with a PHI for virtual operands, we can simply
1652 propagate these without fussing with folding or updating
1653 the stmt. */
1654 if (!is_gimple_reg (def))
1655 {
1656 imm_use_iterator iter;
1657 use_operand_p use_p;
1658 gimple stmt;
1659
1660 FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1661 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1662 SET_USE (use_p, use);
1663
1664 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
1665 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use) = 1;
1666 }
1667 else
1668 replace_uses_by (def, use);
1669
1670 remove_phi_node (&psi, true);
1671 }
1672 }
1673
1674 /* Ensure that B follows A. */
1675 move_block_after (b, a);
1676
1677 gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1678 gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1679
1680 /* Remove labels from B and set gimple_bb to A for other statements. */
1681 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1682 {
1683 gimple stmt = gsi_stmt (gsi);
1684 if (gimple_code (stmt) == GIMPLE_LABEL)
1685 {
1686 tree label = gimple_label_label (stmt);
1687 int lp_nr;
1688
1689 gsi_remove (&gsi, false);
1690
1691 /* Now that we can thread computed gotos, we might have
1692 a situation where we have a forced label in block B
1693 However, the label at the start of block B might still be
1694 used in other ways (think about the runtime checking for
1695 Fortran assigned gotos). So we can not just delete the
1696 label. Instead we move the label to the start of block A. */
1697 if (FORCED_LABEL (label))
1698 {
1699 gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1700 gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT);
1701 }
1702
1703 lp_nr = EH_LANDING_PAD_NR (label);
1704 if (lp_nr)
1705 {
1706 eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1707 lp->post_landing_pad = NULL;
1708 }
1709 }
1710 else
1711 {
1712 gimple_set_bb (stmt, a);
1713 gsi_next (&gsi);
1714 }
1715 }
1716
1717 /* Merge the sequences. */
1718 last = gsi_last_bb (a);
1719 gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1720 set_bb_seq (b, NULL);
1721
1722 if (cfgcleanup_altered_bbs)
1723 bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1724 }
1725
1726
1727 /* Return the one of two successors of BB that is not reachable by a
1728 complex edge, if there is one. Else, return BB. We use
1729 this in optimizations that use post-dominators for their heuristics,
1730 to catch the cases in C++ where function calls are involved. */
1731
1732 basic_block
1733 single_noncomplex_succ (basic_block bb)
1734 {
1735 edge e0, e1;
1736 if (EDGE_COUNT (bb->succs) != 2)
1737 return bb;
1738
1739 e0 = EDGE_SUCC (bb, 0);
1740 e1 = EDGE_SUCC (bb, 1);
1741 if (e0->flags & EDGE_COMPLEX)
1742 return e1->dest;
1743 if (e1->flags & EDGE_COMPLEX)
1744 return e0->dest;
1745
1746 return bb;
1747 }
1748
1749 /* T is CALL_EXPR. Set current_function_calls_* flags. */
1750
1751 void
1752 notice_special_calls (gimple call)
1753 {
1754 int flags = gimple_call_flags (call);
1755
1756 if (flags & ECF_MAY_BE_ALLOCA)
1757 cfun->calls_alloca = true;
1758 if (flags & ECF_RETURNS_TWICE)
1759 cfun->calls_setjmp = true;
1760 }
1761
1762
1763 /* Clear flags set by notice_special_calls. Used by dead code removal
1764 to update the flags. */
1765
1766 void
1767 clear_special_calls (void)
1768 {
1769 cfun->calls_alloca = false;
1770 cfun->calls_setjmp = false;
1771 }
1772
1773 /* Remove PHI nodes associated with basic block BB and all edges out of BB. */
1774
1775 static void
1776 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1777 {
1778 /* Since this block is no longer reachable, we can just delete all
1779 of its PHI nodes. */
1780 remove_phi_nodes (bb);
1781
1782 /* Remove edges to BB's successors. */
1783 while (EDGE_COUNT (bb->succs) > 0)
1784 remove_edge (EDGE_SUCC (bb, 0));
1785 }
1786
1787
1788 /* Remove statements of basic block BB. */
1789
1790 static void
1791 remove_bb (basic_block bb)
1792 {
1793 gimple_stmt_iterator i;
1794
1795 if (dump_file)
1796 {
1797 fprintf (dump_file, "Removing basic block %d\n", bb->index);
1798 if (dump_flags & TDF_DETAILS)
1799 {
1800 dump_bb (bb, dump_file, 0);
1801 fprintf (dump_file, "\n");
1802 }
1803 }
1804
1805 if (current_loops)
1806 {
1807 struct loop *loop = bb->loop_father;
1808
1809 /* If a loop gets removed, clean up the information associated
1810 with it. */
1811 if (loop->latch == bb
1812 || loop->header == bb)
1813 free_numbers_of_iterations_estimates_loop (loop);
1814 }
1815
1816 /* Remove all the instructions in the block. */
1817 if (bb_seq (bb) != NULL)
1818 {
1819 /* Walk backwards so as to get a chance to substitute all
1820 released DEFs into debug stmts. See
1821 eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
1822 details. */
1823 for (i = gsi_last_bb (bb); !gsi_end_p (i);)
1824 {
1825 gimple stmt = gsi_stmt (i);
1826 if (gimple_code (stmt) == GIMPLE_LABEL
1827 && (FORCED_LABEL (gimple_label_label (stmt))
1828 || DECL_NONLOCAL (gimple_label_label (stmt))))
1829 {
1830 basic_block new_bb;
1831 gimple_stmt_iterator new_gsi;
1832
1833 /* A non-reachable non-local label may still be referenced.
1834 But it no longer needs to carry the extra semantics of
1835 non-locality. */
1836 if (DECL_NONLOCAL (gimple_label_label (stmt)))
1837 {
1838 DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
1839 FORCED_LABEL (gimple_label_label (stmt)) = 1;
1840 }
1841
1842 new_bb = bb->prev_bb;
1843 new_gsi = gsi_start_bb (new_bb);
1844 gsi_remove (&i, false);
1845 gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
1846 }
1847 else
1848 {
1849 /* Release SSA definitions if we are in SSA. Note that we
1850 may be called when not in SSA. For example,
1851 final_cleanup calls this function via
1852 cleanup_tree_cfg. */
1853 if (gimple_in_ssa_p (cfun))
1854 release_defs (stmt);
1855
1856 gsi_remove (&i, true);
1857 }
1858
1859 if (gsi_end_p (i))
1860 i = gsi_last_bb (bb);
1861 else
1862 gsi_prev (&i);
1863 }
1864 }
1865
1866 remove_phi_nodes_and_edges_for_unreachable_block (bb);
1867 bb->il.gimple = NULL;
1868 }
1869
1870
1871 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
1872 predicate VAL, return the edge that will be taken out of the block.
1873 If VAL does not match a unique edge, NULL is returned. */
1874
1875 edge
1876 find_taken_edge (basic_block bb, tree val)
1877 {
1878 gimple stmt;
1879
1880 stmt = last_stmt (bb);
1881
1882 gcc_assert (stmt);
1883 gcc_assert (is_ctrl_stmt (stmt));
1884
1885 if (val == NULL)
1886 return NULL;
1887
1888 if (!is_gimple_min_invariant (val))
1889 return NULL;
1890
1891 if (gimple_code (stmt) == GIMPLE_COND)
1892 return find_taken_edge_cond_expr (bb, val);
1893
1894 if (gimple_code (stmt) == GIMPLE_SWITCH)
1895 return find_taken_edge_switch_expr (bb, val);
1896
1897 if (computed_goto_p (stmt))
1898 {
1899 /* Only optimize if the argument is a label, if the argument is
1900 not a label then we can not construct a proper CFG.
1901
1902 It may be the case that we only need to allow the LABEL_REF to
1903 appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
1904 appear inside a LABEL_EXPR just to be safe. */
1905 if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
1906 && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
1907 return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
1908 return NULL;
1909 }
1910
1911 gcc_unreachable ();
1912 }
1913
1914 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
1915 statement, determine which of the outgoing edges will be taken out of the
1916 block. Return NULL if either edge may be taken. */
1917
1918 static edge
1919 find_taken_edge_computed_goto (basic_block bb, tree val)
1920 {
1921 basic_block dest;
1922 edge e = NULL;
1923
1924 dest = label_to_block (val);
1925 if (dest)
1926 {
1927 e = find_edge (bb, dest);
1928 gcc_assert (e != NULL);
1929 }
1930
1931 return e;
1932 }
1933
1934 /* Given a constant value VAL and the entry block BB to a COND_EXPR
1935 statement, determine which of the two edges will be taken out of the
1936 block. Return NULL if either edge may be taken. */
1937
1938 static edge
1939 find_taken_edge_cond_expr (basic_block bb, tree val)
1940 {
1941 edge true_edge, false_edge;
1942
1943 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1944
1945 gcc_assert (TREE_CODE (val) == INTEGER_CST);
1946 return (integer_zerop (val) ? false_edge : true_edge);
1947 }
1948
1949 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
1950 statement, determine which edge will be taken out of the block. Return
1951 NULL if any edge may be taken. */
1952
1953 static edge
1954 find_taken_edge_switch_expr (basic_block bb, tree val)
1955 {
1956 basic_block dest_bb;
1957 edge e;
1958 gimple switch_stmt;
1959 tree taken_case;
1960
1961 switch_stmt = last_stmt (bb);
1962 taken_case = find_case_label_for_value (switch_stmt, val);
1963 dest_bb = label_to_block (CASE_LABEL (taken_case));
1964
1965 e = find_edge (bb, dest_bb);
1966 gcc_assert (e);
1967 return e;
1968 }
1969
1970
1971 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
1972 We can make optimal use here of the fact that the case labels are
1973 sorted: We can do a binary search for a case matching VAL. */
1974
1975 static tree
1976 find_case_label_for_value (gimple switch_stmt, tree val)
1977 {
1978 size_t low, high, n = gimple_switch_num_labels (switch_stmt);
1979 tree default_case = gimple_switch_default_label (switch_stmt);
1980
1981 for (low = 0, high = n; high - low > 1; )
1982 {
1983 size_t i = (high + low) / 2;
1984 tree t = gimple_switch_label (switch_stmt, i);
1985 int cmp;
1986
1987 /* Cache the result of comparing CASE_LOW and val. */
1988 cmp = tree_int_cst_compare (CASE_LOW (t), val);
1989
1990 if (cmp > 0)
1991 high = i;
1992 else
1993 low = i;
1994
1995 if (CASE_HIGH (t) == NULL)
1996 {
1997 /* A singe-valued case label. */
1998 if (cmp == 0)
1999 return t;
2000 }
2001 else
2002 {
2003 /* A case range. We can only handle integer ranges. */
2004 if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2005 return t;
2006 }
2007 }
2008
2009 return default_case;
2010 }
2011
2012
2013 /* Dump a basic block on stderr. */
2014
2015 void
2016 gimple_debug_bb (basic_block bb)
2017 {
2018 gimple_dump_bb (bb, stderr, 0, TDF_VOPS|TDF_MEMSYMS);
2019 }
2020
2021
2022 /* Dump basic block with index N on stderr. */
2023
2024 basic_block
2025 gimple_debug_bb_n (int n)
2026 {
2027 gimple_debug_bb (BASIC_BLOCK (n));
2028 return BASIC_BLOCK (n);
2029 }
2030
2031
2032 /* Dump the CFG on stderr.
2033
2034 FLAGS are the same used by the tree dumping functions
2035 (see TDF_* in tree-pass.h). */
2036
2037 void
2038 gimple_debug_cfg (int flags)
2039 {
2040 gimple_dump_cfg (stderr, flags);
2041 }
2042
2043
2044 /* Dump the program showing basic block boundaries on the given FILE.
2045
2046 FLAGS are the same used by the tree dumping functions (see TDF_* in
2047 tree.h). */
2048
2049 void
2050 gimple_dump_cfg (FILE *file, int flags)
2051 {
2052 if (flags & TDF_DETAILS)
2053 {
2054 const char *funcname
2055 = lang_hooks.decl_printable_name (current_function_decl, 2);
2056
2057 fputc ('\n', file);
2058 fprintf (file, ";; Function %s\n\n", funcname);
2059 fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2060 n_basic_blocks, n_edges, last_basic_block);
2061
2062 brief_dump_cfg (file);
2063 fprintf (file, "\n");
2064 }
2065
2066 if (flags & TDF_STATS)
2067 dump_cfg_stats (file);
2068
2069 dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2070 }
2071
2072
2073 /* Dump CFG statistics on FILE. */
2074
2075 void
2076 dump_cfg_stats (FILE *file)
2077 {
2078 static long max_num_merged_labels = 0;
2079 unsigned long size, total = 0;
2080 long num_edges;
2081 basic_block bb;
2082 const char * const fmt_str = "%-30s%-13s%12s\n";
2083 const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2084 const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2085 const char * const fmt_str_3 = "%-43s%11lu%c\n";
2086 const char *funcname
2087 = lang_hooks.decl_printable_name (current_function_decl, 2);
2088
2089
2090 fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2091
2092 fprintf (file, "---------------------------------------------------------\n");
2093 fprintf (file, fmt_str, "", " Number of ", "Memory");
2094 fprintf (file, fmt_str, "", " instances ", "used ");
2095 fprintf (file, "---------------------------------------------------------\n");
2096
2097 size = n_basic_blocks * sizeof (struct basic_block_def);
2098 total += size;
2099 fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2100 SCALE (size), LABEL (size));
2101
2102 num_edges = 0;
2103 FOR_EACH_BB (bb)
2104 num_edges += EDGE_COUNT (bb->succs);
2105 size = num_edges * sizeof (struct edge_def);
2106 total += size;
2107 fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2108
2109 fprintf (file, "---------------------------------------------------------\n");
2110 fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2111 LABEL (total));
2112 fprintf (file, "---------------------------------------------------------\n");
2113 fprintf (file, "\n");
2114
2115 if (cfg_stats.num_merged_labels > max_num_merged_labels)
2116 max_num_merged_labels = cfg_stats.num_merged_labels;
2117
2118 fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2119 cfg_stats.num_merged_labels, max_num_merged_labels);
2120
2121 fprintf (file, "\n");
2122 }
2123
2124
2125 /* Dump CFG statistics on stderr. Keep extern so that it's always
2126 linked in the final executable. */
2127
2128 DEBUG_FUNCTION void
2129 debug_cfg_stats (void)
2130 {
2131 dump_cfg_stats (stderr);
2132 }
2133
2134
2135 /* Dump the flowgraph to a .vcg FILE. */
2136
2137 static void
2138 gimple_cfg2vcg (FILE *file)
2139 {
2140 edge e;
2141 edge_iterator ei;
2142 basic_block bb;
2143 const char *funcname
2144 = lang_hooks.decl_printable_name (current_function_decl, 2);
2145
2146 /* Write the file header. */
2147 fprintf (file, "graph: { title: \"%s\"\n", funcname);
2148 fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2149 fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2150
2151 /* Write blocks and edges. */
2152 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2153 {
2154 fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2155 e->dest->index);
2156
2157 if (e->flags & EDGE_FAKE)
2158 fprintf (file, " linestyle: dotted priority: 10");
2159 else
2160 fprintf (file, " linestyle: solid priority: 100");
2161
2162 fprintf (file, " }\n");
2163 }
2164 fputc ('\n', file);
2165
2166 FOR_EACH_BB (bb)
2167 {
2168 enum gimple_code head_code, end_code;
2169 const char *head_name, *end_name;
2170 int head_line = 0;
2171 int end_line = 0;
2172 gimple first = first_stmt (bb);
2173 gimple last = last_stmt (bb);
2174
2175 if (first)
2176 {
2177 head_code = gimple_code (first);
2178 head_name = gimple_code_name[head_code];
2179 head_line = get_lineno (first);
2180 }
2181 else
2182 head_name = "no-statement";
2183
2184 if (last)
2185 {
2186 end_code = gimple_code (last);
2187 end_name = gimple_code_name[end_code];
2188 end_line = get_lineno (last);
2189 }
2190 else
2191 end_name = "no-statement";
2192
2193 fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2194 bb->index, bb->index, head_name, head_line, end_name,
2195 end_line);
2196
2197 FOR_EACH_EDGE (e, ei, bb->succs)
2198 {
2199 if (e->dest == EXIT_BLOCK_PTR)
2200 fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2201 else
2202 fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2203
2204 if (e->flags & EDGE_FAKE)
2205 fprintf (file, " priority: 10 linestyle: dotted");
2206 else
2207 fprintf (file, " priority: 100 linestyle: solid");
2208
2209 fprintf (file, " }\n");
2210 }
2211
2212 if (bb->next_bb != EXIT_BLOCK_PTR)
2213 fputc ('\n', file);
2214 }
2215
2216 fputs ("}\n\n", file);
2217 }
2218
2219
2220
2221 /*---------------------------------------------------------------------------
2222 Miscellaneous helpers
2223 ---------------------------------------------------------------------------*/
2224
2225 /* Return true if T represents a stmt that always transfers control. */
2226
2227 bool
2228 is_ctrl_stmt (gimple t)
2229 {
2230 switch (gimple_code (t))
2231 {
2232 case GIMPLE_COND:
2233 case GIMPLE_SWITCH:
2234 case GIMPLE_GOTO:
2235 case GIMPLE_RETURN:
2236 case GIMPLE_RESX:
2237 return true;
2238 default:
2239 return false;
2240 }
2241 }
2242
2243
2244 /* Return true if T is a statement that may alter the flow of control
2245 (e.g., a call to a non-returning function). */
2246
2247 bool
2248 is_ctrl_altering_stmt (gimple t)
2249 {
2250 gcc_assert (t);
2251
2252 switch (gimple_code (t))
2253 {
2254 case GIMPLE_CALL:
2255 {
2256 int flags = gimple_call_flags (t);
2257
2258 /* A non-pure/const call alters flow control if the current
2259 function has nonlocal labels. */
2260 if (!(flags & (ECF_CONST | ECF_PURE | ECF_LEAF))
2261 && cfun->has_nonlocal_label)
2262 return true;
2263
2264 /* A call also alters control flow if it does not return. */
2265 if (flags & ECF_NORETURN)
2266 return true;
2267
2268 /* BUILT_IN_RETURN call is same as return statement. */
2269 if (gimple_call_builtin_p (t, BUILT_IN_RETURN))
2270 return true;
2271 }
2272 break;
2273
2274 case GIMPLE_EH_DISPATCH:
2275 /* EH_DISPATCH branches to the individual catch handlers at
2276 this level of a try or allowed-exceptions region. It can
2277 fallthru to the next statement as well. */
2278 return true;
2279
2280 case GIMPLE_ASM:
2281 if (gimple_asm_nlabels (t) > 0)
2282 return true;
2283 break;
2284
2285 CASE_GIMPLE_OMP:
2286 /* OpenMP directives alter control flow. */
2287 return true;
2288
2289 default:
2290 break;
2291 }
2292
2293 /* If a statement can throw, it alters control flow. */
2294 return stmt_can_throw_internal (t);
2295 }
2296
2297
2298 /* Return true if T is a simple local goto. */
2299
2300 bool
2301 simple_goto_p (gimple t)
2302 {
2303 return (gimple_code (t) == GIMPLE_GOTO
2304 && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2305 }
2306
2307
2308 /* Return true if T can make an abnormal transfer of control flow.
2309 Transfers of control flow associated with EH are excluded. */
2310
2311 bool
2312 stmt_can_make_abnormal_goto (gimple t)
2313 {
2314 if (computed_goto_p (t))
2315 return true;
2316 if (is_gimple_call (t))
2317 return (gimple_has_side_effects (t) && cfun->has_nonlocal_label
2318 && !(gimple_call_flags (t) & ECF_LEAF));
2319 return false;
2320 }
2321
2322
2323 /* Return true if STMT should start a new basic block. PREV_STMT is
2324 the statement preceding STMT. It is used when STMT is a label or a
2325 case label. Labels should only start a new basic block if their
2326 previous statement wasn't a label. Otherwise, sequence of labels
2327 would generate unnecessary basic blocks that only contain a single
2328 label. */
2329
2330 static inline bool
2331 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2332 {
2333 if (stmt == NULL)
2334 return false;
2335
2336 /* Labels start a new basic block only if the preceding statement
2337 wasn't a label of the same type. This prevents the creation of
2338 consecutive blocks that have nothing but a single label. */
2339 if (gimple_code (stmt) == GIMPLE_LABEL)
2340 {
2341 /* Nonlocal and computed GOTO targets always start a new block. */
2342 if (DECL_NONLOCAL (gimple_label_label (stmt))
2343 || FORCED_LABEL (gimple_label_label (stmt)))
2344 return true;
2345
2346 if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2347 {
2348 if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2349 return true;
2350
2351 cfg_stats.num_merged_labels++;
2352 return false;
2353 }
2354 else
2355 return true;
2356 }
2357
2358 return false;
2359 }
2360
2361
2362 /* Return true if T should end a basic block. */
2363
2364 bool
2365 stmt_ends_bb_p (gimple t)
2366 {
2367 return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2368 }
2369
2370 /* Remove block annotations and other data structures. */
2371
2372 void
2373 delete_tree_cfg_annotations (void)
2374 {
2375 label_to_block_map = NULL;
2376 }
2377
2378
2379 /* Return the first statement in basic block BB. */
2380
2381 gimple
2382 first_stmt (basic_block bb)
2383 {
2384 gimple_stmt_iterator i = gsi_start_bb (bb);
2385 gimple stmt = NULL;
2386
2387 while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2388 {
2389 gsi_next (&i);
2390 stmt = NULL;
2391 }
2392 return stmt;
2393 }
2394
2395 /* Return the first non-label statement in basic block BB. */
2396
2397 static gimple
2398 first_non_label_stmt (basic_block bb)
2399 {
2400 gimple_stmt_iterator i = gsi_start_bb (bb);
2401 while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2402 gsi_next (&i);
2403 return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2404 }
2405
2406 /* Return the last statement in basic block BB. */
2407
2408 gimple
2409 last_stmt (basic_block bb)
2410 {
2411 gimple_stmt_iterator i = gsi_last_bb (bb);
2412 gimple stmt = NULL;
2413
2414 while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2415 {
2416 gsi_prev (&i);
2417 stmt = NULL;
2418 }
2419 return stmt;
2420 }
2421
2422 /* Return the last statement of an otherwise empty block. Return NULL
2423 if the block is totally empty, or if it contains more than one
2424 statement. */
2425
2426 gimple
2427 last_and_only_stmt (basic_block bb)
2428 {
2429 gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
2430 gimple last, prev;
2431
2432 if (gsi_end_p (i))
2433 return NULL;
2434
2435 last = gsi_stmt (i);
2436 gsi_prev_nondebug (&i);
2437 if (gsi_end_p (i))
2438 return last;
2439
2440 /* Empty statements should no longer appear in the instruction stream.
2441 Everything that might have appeared before should be deleted by
2442 remove_useless_stmts, and the optimizers should just gsi_remove
2443 instead of smashing with build_empty_stmt.
2444
2445 Thus the only thing that should appear here in a block containing
2446 one executable statement is a label. */
2447 prev = gsi_stmt (i);
2448 if (gimple_code (prev) == GIMPLE_LABEL)
2449 return last;
2450 else
2451 return NULL;
2452 }
2453
2454 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE. */
2455
2456 static void
2457 reinstall_phi_args (edge new_edge, edge old_edge)
2458 {
2459 edge_var_map_vector v;
2460 edge_var_map *vm;
2461 int i;
2462 gimple_stmt_iterator phis;
2463
2464 v = redirect_edge_var_map_vector (old_edge);
2465 if (!v)
2466 return;
2467
2468 for (i = 0, phis = gsi_start_phis (new_edge->dest);
2469 VEC_iterate (edge_var_map, v, i, vm) && !gsi_end_p (phis);
2470 i++, gsi_next (&phis))
2471 {
2472 gimple phi = gsi_stmt (phis);
2473 tree result = redirect_edge_var_map_result (vm);
2474 tree arg = redirect_edge_var_map_def (vm);
2475
2476 gcc_assert (result == gimple_phi_result (phi));
2477
2478 add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
2479 }
2480
2481 redirect_edge_var_map_clear (old_edge);
2482 }
2483
2484 /* Returns the basic block after which the new basic block created
2485 by splitting edge EDGE_IN should be placed. Tries to keep the new block
2486 near its "logical" location. This is of most help to humans looking
2487 at debugging dumps. */
2488
2489 static basic_block
2490 split_edge_bb_loc (edge edge_in)
2491 {
2492 basic_block dest = edge_in->dest;
2493 basic_block dest_prev = dest->prev_bb;
2494
2495 if (dest_prev)
2496 {
2497 edge e = find_edge (dest_prev, dest);
2498 if (e && !(e->flags & EDGE_COMPLEX))
2499 return edge_in->src;
2500 }
2501 return dest_prev;
2502 }
2503
2504 /* Split a (typically critical) edge EDGE_IN. Return the new block.
2505 Abort on abnormal edges. */
2506
2507 static basic_block
2508 gimple_split_edge (edge edge_in)
2509 {
2510 basic_block new_bb, after_bb, dest;
2511 edge new_edge, e;
2512
2513 /* Abnormal edges cannot be split. */
2514 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2515
2516 dest = edge_in->dest;
2517
2518 after_bb = split_edge_bb_loc (edge_in);
2519
2520 new_bb = create_empty_bb (after_bb);
2521 new_bb->frequency = EDGE_FREQUENCY (edge_in);
2522 new_bb->count = edge_in->count;
2523 new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2524 new_edge->probability = REG_BR_PROB_BASE;
2525 new_edge->count = edge_in->count;
2526
2527 e = redirect_edge_and_branch (edge_in, new_bb);
2528 gcc_assert (e == edge_in);
2529 reinstall_phi_args (new_edge, e);
2530
2531 return new_bb;
2532 }
2533
2534
2535 /* Verify properties of the address expression T with base object BASE. */
2536
2537 static tree
2538 verify_address (tree t, tree base)
2539 {
2540 bool old_constant;
2541 bool old_side_effects;
2542 bool new_constant;
2543 bool new_side_effects;
2544
2545 old_constant = TREE_CONSTANT (t);
2546 old_side_effects = TREE_SIDE_EFFECTS (t);
2547
2548 recompute_tree_invariant_for_addr_expr (t);
2549 new_side_effects = TREE_SIDE_EFFECTS (t);
2550 new_constant = TREE_CONSTANT (t);
2551
2552 if (old_constant != new_constant)
2553 {
2554 error ("constant not recomputed when ADDR_EXPR changed");
2555 return t;
2556 }
2557 if (old_side_effects != new_side_effects)
2558 {
2559 error ("side effects not recomputed when ADDR_EXPR changed");
2560 return t;
2561 }
2562
2563 if (!(TREE_CODE (base) == VAR_DECL
2564 || TREE_CODE (base) == PARM_DECL
2565 || TREE_CODE (base) == RESULT_DECL))
2566 return NULL_TREE;
2567
2568 if (DECL_GIMPLE_REG_P (base))
2569 {
2570 error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2571 return base;
2572 }
2573
2574 return NULL_TREE;
2575 }
2576
2577 /* Callback for walk_tree, check that all elements with address taken are
2578 properly noticed as such. The DATA is an int* that is 1 if TP was seen
2579 inside a PHI node. */
2580
2581 static tree
2582 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2583 {
2584 tree t = *tp, x;
2585
2586 if (TYPE_P (t))
2587 *walk_subtrees = 0;
2588
2589 /* Check operand N for being valid GIMPLE and give error MSG if not. */
2590 #define CHECK_OP(N, MSG) \
2591 do { if (!is_gimple_val (TREE_OPERAND (t, N))) \
2592 { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2593
2594 switch (TREE_CODE (t))
2595 {
2596 case SSA_NAME:
2597 if (SSA_NAME_IN_FREE_LIST (t))
2598 {
2599 error ("SSA name in freelist but still referenced");
2600 return *tp;
2601 }
2602 break;
2603
2604 case INDIRECT_REF:
2605 error ("INDIRECT_REF in gimple IL");
2606 return t;
2607
2608 case MEM_REF:
2609 x = TREE_OPERAND (t, 0);
2610 if (!POINTER_TYPE_P (TREE_TYPE (x))
2611 || !is_gimple_mem_ref_addr (x))
2612 {
2613 error ("invalid first operand of MEM_REF");
2614 return x;
2615 }
2616 if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST
2617 || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1))))
2618 {
2619 error ("invalid offset operand of MEM_REF");
2620 return TREE_OPERAND (t, 1);
2621 }
2622 if (TREE_CODE (x) == ADDR_EXPR
2623 && (x = verify_address (x, TREE_OPERAND (x, 0))))
2624 return x;
2625 *walk_subtrees = 0;
2626 break;
2627
2628 case ASSERT_EXPR:
2629 x = fold (ASSERT_EXPR_COND (t));
2630 if (x == boolean_false_node)
2631 {
2632 error ("ASSERT_EXPR with an always-false condition");
2633 return *tp;
2634 }
2635 break;
2636
2637 case MODIFY_EXPR:
2638 error ("MODIFY_EXPR not expected while having tuples");
2639 return *tp;
2640
2641 case ADDR_EXPR:
2642 {
2643 tree tem;
2644
2645 gcc_assert (is_gimple_address (t));
2646
2647 /* Skip any references (they will be checked when we recurse down the
2648 tree) and ensure that any variable used as a prefix is marked
2649 addressable. */
2650 for (x = TREE_OPERAND (t, 0);
2651 handled_component_p (x);
2652 x = TREE_OPERAND (x, 0))
2653 ;
2654
2655 if ((tem = verify_address (t, x)))
2656 return tem;
2657
2658 if (!(TREE_CODE (x) == VAR_DECL
2659 || TREE_CODE (x) == PARM_DECL
2660 || TREE_CODE (x) == RESULT_DECL))
2661 return NULL;
2662
2663 if (!TREE_ADDRESSABLE (x))
2664 {
2665 error ("address taken, but ADDRESSABLE bit not set");
2666 return x;
2667 }
2668
2669 break;
2670 }
2671
2672 case COND_EXPR:
2673 x = COND_EXPR_COND (t);
2674 if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2675 {
2676 error ("non-integral used in condition");
2677 return x;
2678 }
2679 if (!is_gimple_condexpr (x))
2680 {
2681 error ("invalid conditional operand");
2682 return x;
2683 }
2684 break;
2685
2686 case NON_LVALUE_EXPR:
2687 gcc_unreachable ();
2688
2689 CASE_CONVERT:
2690 case FIX_TRUNC_EXPR:
2691 case FLOAT_EXPR:
2692 case NEGATE_EXPR:
2693 case ABS_EXPR:
2694 case BIT_NOT_EXPR:
2695 case TRUTH_NOT_EXPR:
2696 CHECK_OP (0, "invalid operand to unary operator");
2697 break;
2698
2699 case REALPART_EXPR:
2700 case IMAGPART_EXPR:
2701 case COMPONENT_REF:
2702 case ARRAY_REF:
2703 case ARRAY_RANGE_REF:
2704 case BIT_FIELD_REF:
2705 case VIEW_CONVERT_EXPR:
2706 /* We have a nest of references. Verify that each of the operands
2707 that determine where to reference is either a constant or a variable,
2708 verify that the base is valid, and then show we've already checked
2709 the subtrees. */
2710 while (handled_component_p (t))
2711 {
2712 if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2713 CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2714 else if (TREE_CODE (t) == ARRAY_REF
2715 || TREE_CODE (t) == ARRAY_RANGE_REF)
2716 {
2717 CHECK_OP (1, "invalid array index");
2718 if (TREE_OPERAND (t, 2))
2719 CHECK_OP (2, "invalid array lower bound");
2720 if (TREE_OPERAND (t, 3))
2721 CHECK_OP (3, "invalid array stride");
2722 }
2723 else if (TREE_CODE (t) == BIT_FIELD_REF)
2724 {
2725 if (!host_integerp (TREE_OPERAND (t, 1), 1)
2726 || !host_integerp (TREE_OPERAND (t, 2), 1))
2727 {
2728 error ("invalid position or size operand to BIT_FIELD_REF");
2729 return t;
2730 }
2731 else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2732 && (TYPE_PRECISION (TREE_TYPE (t))
2733 != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2734 {
2735 error ("integral result type precision does not match "
2736 "field size of BIT_FIELD_REF");
2737 return t;
2738 }
2739 if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2740 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2741 != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2742 {
2743 error ("mode precision of non-integral result does not "
2744 "match field size of BIT_FIELD_REF");
2745 return t;
2746 }
2747 }
2748
2749 t = TREE_OPERAND (t, 0);
2750 }
2751
2752 if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2753 {
2754 error ("invalid reference prefix");
2755 return t;
2756 }
2757 *walk_subtrees = 0;
2758 break;
2759 case PLUS_EXPR:
2760 case MINUS_EXPR:
2761 /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2762 POINTER_PLUS_EXPR. */
2763 if (POINTER_TYPE_P (TREE_TYPE (t)))
2764 {
2765 error ("invalid operand to plus/minus, type is a pointer");
2766 return t;
2767 }
2768 CHECK_OP (0, "invalid operand to binary operator");
2769 CHECK_OP (1, "invalid operand to binary operator");
2770 break;
2771
2772 case POINTER_PLUS_EXPR:
2773 /* Check to make sure the first operand is a pointer or reference type. */
2774 if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
2775 {
2776 error ("invalid operand to pointer plus, first operand is not a pointer");
2777 return t;
2778 }
2779 /* Check to make sure the second operand is an integer with type of
2780 sizetype. */
2781 if (!useless_type_conversion_p (sizetype,
2782 TREE_TYPE (TREE_OPERAND (t, 1))))
2783 {
2784 error ("invalid operand to pointer plus, second operand is not an "
2785 "integer with type of sizetype");
2786 return t;
2787 }
2788 /* FALLTHROUGH */
2789 case LT_EXPR:
2790 case LE_EXPR:
2791 case GT_EXPR:
2792 case GE_EXPR:
2793 case EQ_EXPR:
2794 case NE_EXPR:
2795 case UNORDERED_EXPR:
2796 case ORDERED_EXPR:
2797 case UNLT_EXPR:
2798 case UNLE_EXPR:
2799 case UNGT_EXPR:
2800 case UNGE_EXPR:
2801 case UNEQ_EXPR:
2802 case LTGT_EXPR:
2803 case MULT_EXPR:
2804 case TRUNC_DIV_EXPR:
2805 case CEIL_DIV_EXPR:
2806 case FLOOR_DIV_EXPR:
2807 case ROUND_DIV_EXPR:
2808 case TRUNC_MOD_EXPR:
2809 case CEIL_MOD_EXPR:
2810 case FLOOR_MOD_EXPR:
2811 case ROUND_MOD_EXPR:
2812 case RDIV_EXPR:
2813 case EXACT_DIV_EXPR:
2814 case MIN_EXPR:
2815 case MAX_EXPR:
2816 case LSHIFT_EXPR:
2817 case RSHIFT_EXPR:
2818 case LROTATE_EXPR:
2819 case RROTATE_EXPR:
2820 case BIT_IOR_EXPR:
2821 case BIT_XOR_EXPR:
2822 case BIT_AND_EXPR:
2823 CHECK_OP (0, "invalid operand to binary operator");
2824 CHECK_OP (1, "invalid operand to binary operator");
2825 break;
2826
2827 case CONSTRUCTOR:
2828 if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2829 *walk_subtrees = 0;
2830 break;
2831
2832 default:
2833 break;
2834 }
2835 return NULL;
2836
2837 #undef CHECK_OP
2838 }
2839
2840
2841 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
2842 Returns true if there is an error, otherwise false. */
2843
2844 static bool
2845 verify_types_in_gimple_min_lval (tree expr)
2846 {
2847 tree op;
2848
2849 if (is_gimple_id (expr))
2850 return false;
2851
2852 if (TREE_CODE (expr) != TARGET_MEM_REF
2853 && TREE_CODE (expr) != MEM_REF)
2854 {
2855 error ("invalid expression for min lvalue");
2856 return true;
2857 }
2858
2859 /* TARGET_MEM_REFs are strange beasts. */
2860 if (TREE_CODE (expr) == TARGET_MEM_REF)
2861 return false;
2862
2863 op = TREE_OPERAND (expr, 0);
2864 if (!is_gimple_val (op))
2865 {
2866 error ("invalid operand in indirect reference");
2867 debug_generic_stmt (op);
2868 return true;
2869 }
2870 /* Memory references now generally can involve a value conversion. */
2871
2872 return false;
2873 }
2874
2875 /* Verify if EXPR is a valid GIMPLE reference expression. If
2876 REQUIRE_LVALUE is true verifies it is an lvalue. Returns true
2877 if there is an error, otherwise false. */
2878
2879 static bool
2880 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
2881 {
2882 while (handled_component_p (expr))
2883 {
2884 tree op = TREE_OPERAND (expr, 0);
2885
2886 if (TREE_CODE (expr) == ARRAY_REF
2887 || TREE_CODE (expr) == ARRAY_RANGE_REF)
2888 {
2889 if (!is_gimple_val (TREE_OPERAND (expr, 1))
2890 || (TREE_OPERAND (expr, 2)
2891 && !is_gimple_val (TREE_OPERAND (expr, 2)))
2892 || (TREE_OPERAND (expr, 3)
2893 && !is_gimple_val (TREE_OPERAND (expr, 3))))
2894 {
2895 error ("invalid operands to array reference");
2896 debug_generic_stmt (expr);
2897 return true;
2898 }
2899 }
2900
2901 /* Verify if the reference array element types are compatible. */
2902 if (TREE_CODE (expr) == ARRAY_REF
2903 && !useless_type_conversion_p (TREE_TYPE (expr),
2904 TREE_TYPE (TREE_TYPE (op))))
2905 {
2906 error ("type mismatch in array reference");
2907 debug_generic_stmt (TREE_TYPE (expr));
2908 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2909 return true;
2910 }
2911 if (TREE_CODE (expr) == ARRAY_RANGE_REF
2912 && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
2913 TREE_TYPE (TREE_TYPE (op))))
2914 {
2915 error ("type mismatch in array range reference");
2916 debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
2917 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2918 return true;
2919 }
2920
2921 if ((TREE_CODE (expr) == REALPART_EXPR
2922 || TREE_CODE (expr) == IMAGPART_EXPR)
2923 && !useless_type_conversion_p (TREE_TYPE (expr),
2924 TREE_TYPE (TREE_TYPE (op))))
2925 {
2926 error ("type mismatch in real/imagpart reference");
2927 debug_generic_stmt (TREE_TYPE (expr));
2928 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2929 return true;
2930 }
2931
2932 if (TREE_CODE (expr) == COMPONENT_REF
2933 && !useless_type_conversion_p (TREE_TYPE (expr),
2934 TREE_TYPE (TREE_OPERAND (expr, 1))))
2935 {
2936 error ("type mismatch in component reference");
2937 debug_generic_stmt (TREE_TYPE (expr));
2938 debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
2939 return true;
2940 }
2941
2942 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2943 {
2944 /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check
2945 that their operand is not an SSA name or an invariant when
2946 requiring an lvalue (this usually means there is a SRA or IPA-SRA
2947 bug). Otherwise there is nothing to verify, gross mismatches at
2948 most invoke undefined behavior. */
2949 if (require_lvalue
2950 && (TREE_CODE (op) == SSA_NAME
2951 || is_gimple_min_invariant (op)))
2952 {
2953 error ("conversion of an SSA_NAME on the left hand side");
2954 debug_generic_stmt (expr);
2955 return true;
2956 }
2957 else if (TREE_CODE (op) == SSA_NAME
2958 && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op)))
2959 {
2960 error ("conversion of register to a different size");
2961 debug_generic_stmt (expr);
2962 return true;
2963 }
2964 else if (!handled_component_p (op))
2965 return false;
2966 }
2967
2968 expr = op;
2969 }
2970
2971 if (TREE_CODE (expr) == MEM_REF)
2972 {
2973 if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0)))
2974 {
2975 error ("invalid address operand in MEM_REF");
2976 debug_generic_stmt (expr);
2977 return true;
2978 }
2979 if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST
2980 || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
2981 {
2982 error ("invalid offset operand in MEM_REF");
2983 debug_generic_stmt (expr);
2984 return true;
2985 }
2986 }
2987 else if (TREE_CODE (expr) == TARGET_MEM_REF)
2988 {
2989 if (!TMR_BASE (expr)
2990 || !is_gimple_mem_ref_addr (TMR_BASE (expr)))
2991 {
2992 error ("invalid address operand in in TARGET_MEM_REF");
2993 return true;
2994 }
2995 if (!TMR_OFFSET (expr)
2996 || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST
2997 || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr))))
2998 {
2999 error ("invalid offset operand in TARGET_MEM_REF");
3000 debug_generic_stmt (expr);
3001 return true;
3002 }
3003 }
3004
3005 return ((require_lvalue || !is_gimple_min_invariant (expr))
3006 && verify_types_in_gimple_min_lval (expr));
3007 }
3008
3009 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3010 list of pointer-to types that is trivially convertible to DEST. */
3011
3012 static bool
3013 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3014 {
3015 tree src;
3016
3017 if (!TYPE_POINTER_TO (src_obj))
3018 return true;
3019
3020 for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3021 if (useless_type_conversion_p (dest, src))
3022 return true;
3023
3024 return false;
3025 }
3026
3027 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3028 from TYPE2 can be handled by FIXED_CONVERT_EXPR. */
3029
3030 static bool
3031 valid_fixed_convert_types_p (tree type1, tree type2)
3032 {
3033 return (FIXED_POINT_TYPE_P (type1)
3034 && (INTEGRAL_TYPE_P (type2)
3035 || SCALAR_FLOAT_TYPE_P (type2)
3036 || FIXED_POINT_TYPE_P (type2)));
3037 }
3038
3039 /* Verify the contents of a GIMPLE_CALL STMT. Returns true when there
3040 is a problem, otherwise false. */
3041
3042 static bool
3043 verify_gimple_call (gimple stmt)
3044 {
3045 tree fn = gimple_call_fn (stmt);
3046 tree fntype, fndecl;
3047 unsigned i;
3048
3049 if (!is_gimple_call_addr (fn))
3050 {
3051 error ("invalid function in gimple call");
3052 debug_generic_stmt (fn);
3053 return true;
3054 }
3055
3056 if (!POINTER_TYPE_P (TREE_TYPE (fn))
3057 || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3058 && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE))
3059 {
3060 error ("non-function in gimple call");
3061 return true;
3062 }
3063
3064 fndecl = gimple_call_fndecl (stmt);
3065 if (fndecl
3066 && TREE_CODE (fndecl) == FUNCTION_DECL
3067 && DECL_LOOPING_CONST_OR_PURE_P (fndecl)
3068 && !DECL_PURE_P (fndecl)
3069 && !TREE_READONLY (fndecl))
3070 {
3071 error ("invalid pure const state for function");
3072 return true;
3073 }
3074
3075 if (gimple_call_lhs (stmt)
3076 && (!is_gimple_lvalue (gimple_call_lhs (stmt))
3077 || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true)))
3078 {
3079 error ("invalid LHS in gimple call");
3080 return true;
3081 }
3082
3083 if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt))
3084 {
3085 error ("LHS in noreturn call");
3086 return true;
3087 }
3088
3089 fntype = TREE_TYPE (TREE_TYPE (fn));
3090 if (gimple_call_lhs (stmt)
3091 && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3092 TREE_TYPE (fntype))
3093 /* ??? At least C++ misses conversions at assignments from
3094 void * call results.
3095 ??? Java is completely off. Especially with functions
3096 returning java.lang.Object.
3097 For now simply allow arbitrary pointer type conversions. */
3098 && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3099 && POINTER_TYPE_P (TREE_TYPE (fntype))))
3100 {
3101 error ("invalid conversion in gimple call");
3102 debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3103 debug_generic_stmt (TREE_TYPE (fntype));
3104 return true;
3105 }
3106
3107 if (gimple_call_chain (stmt)
3108 && !is_gimple_val (gimple_call_chain (stmt)))
3109 {
3110 error ("invalid static chain in gimple call");
3111 debug_generic_stmt (gimple_call_chain (stmt));
3112 return true;
3113 }
3114
3115 /* If there is a static chain argument, this should not be an indirect
3116 call, and the decl should have DECL_STATIC_CHAIN set. */
3117 if (gimple_call_chain (stmt))
3118 {
3119 if (!gimple_call_fndecl (stmt))
3120 {
3121 error ("static chain in indirect gimple call");
3122 return true;
3123 }
3124 fn = TREE_OPERAND (fn, 0);
3125
3126 if (!DECL_STATIC_CHAIN (fn))
3127 {
3128 error ("static chain with function that doesn%'t use one");
3129 return true;
3130 }
3131 }
3132
3133 /* ??? The C frontend passes unpromoted arguments in case it
3134 didn't see a function declaration before the call. So for now
3135 leave the call arguments mostly unverified. Once we gimplify
3136 unit-at-a-time we have a chance to fix this. */
3137
3138 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3139 {
3140 tree arg = gimple_call_arg (stmt, i);
3141 if ((is_gimple_reg_type (TREE_TYPE (arg))
3142 && !is_gimple_val (arg))
3143 || (!is_gimple_reg_type (TREE_TYPE (arg))
3144 && !is_gimple_lvalue (arg)))
3145 {
3146 error ("invalid argument to gimple call");
3147 debug_generic_expr (arg);
3148 return true;
3149 }
3150 }
3151
3152 return false;
3153 }
3154
3155 /* Verifies the gimple comparison with the result type TYPE and
3156 the operands OP0 and OP1. */
3157
3158 static bool
3159 verify_gimple_comparison (tree type, tree op0, tree op1)
3160 {
3161 tree op0_type = TREE_TYPE (op0);
3162 tree op1_type = TREE_TYPE (op1);
3163
3164 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3165 {
3166 error ("invalid operands in gimple comparison");
3167 return true;
3168 }
3169
3170 /* For comparisons we do not have the operations type as the
3171 effective type the comparison is carried out in. Instead
3172 we require that either the first operand is trivially
3173 convertible into the second, or the other way around.
3174 The resulting type of a comparison may be any integral type.
3175 Because we special-case pointers to void we allow
3176 comparisons of pointers with the same mode as well. */
3177 if ((!useless_type_conversion_p (op0_type, op1_type)
3178 && !useless_type_conversion_p (op1_type, op0_type)
3179 && (!POINTER_TYPE_P (op0_type)
3180 || !POINTER_TYPE_P (op1_type)
3181 || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3182 || !INTEGRAL_TYPE_P (type))
3183 {
3184 error ("type mismatch in comparison expression");
3185 debug_generic_expr (type);
3186 debug_generic_expr (op0_type);
3187 debug_generic_expr (op1_type);
3188 return true;
3189 }
3190
3191 return false;
3192 }
3193
3194 /* Verify a gimple assignment statement STMT with an unary rhs.
3195 Returns true if anything is wrong. */
3196
3197 static bool
3198 verify_gimple_assign_unary (gimple stmt)
3199 {
3200 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3201 tree lhs = gimple_assign_lhs (stmt);
3202 tree lhs_type = TREE_TYPE (lhs);
3203 tree rhs1 = gimple_assign_rhs1 (stmt);
3204 tree rhs1_type = TREE_TYPE (rhs1);
3205
3206 if (!is_gimple_reg (lhs))
3207 {
3208 error ("non-register as LHS of unary operation");
3209 return true;
3210 }
3211
3212 if (!is_gimple_val (rhs1))
3213 {
3214 error ("invalid operand in unary operation");
3215 return true;
3216 }
3217
3218 /* First handle conversions. */
3219 switch (rhs_code)
3220 {
3221 CASE_CONVERT:
3222 {
3223 /* Allow conversions between integral types and pointers only if
3224 there is no sign or zero extension involved.
3225 For targets were the precision of sizetype doesn't match that
3226 of pointers we need to allow arbitrary conversions from and
3227 to sizetype. */
3228 if ((POINTER_TYPE_P (lhs_type)
3229 && INTEGRAL_TYPE_P (rhs1_type)
3230 && (TYPE_PRECISION (lhs_type) >= TYPE_PRECISION (rhs1_type)
3231 || rhs1_type == sizetype))
3232 || (POINTER_TYPE_P (rhs1_type)
3233 && INTEGRAL_TYPE_P (lhs_type)
3234 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3235 || lhs_type == sizetype)))
3236 return false;
3237
3238 /* Allow conversion from integer to offset type and vice versa. */
3239 if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3240 && TREE_CODE (rhs1_type) == INTEGER_TYPE)
3241 || (TREE_CODE (lhs_type) == INTEGER_TYPE
3242 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3243 return false;
3244
3245 /* Otherwise assert we are converting between types of the
3246 same kind. */
3247 if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3248 {
3249 error ("invalid types in nop conversion");
3250 debug_generic_expr (lhs_type);
3251 debug_generic_expr (rhs1_type);
3252 return true;
3253 }
3254
3255 return false;
3256 }
3257
3258 case ADDR_SPACE_CONVERT_EXPR:
3259 {
3260 if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3261 || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3262 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3263 {
3264 error ("invalid types in address space conversion");
3265 debug_generic_expr (lhs_type);
3266 debug_generic_expr (rhs1_type);
3267 return true;
3268 }
3269
3270 return false;
3271 }
3272
3273 case FIXED_CONVERT_EXPR:
3274 {
3275 if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3276 && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3277 {
3278 error ("invalid types in fixed-point conversion");
3279 debug_generic_expr (lhs_type);
3280 debug_generic_expr (rhs1_type);
3281 return true;
3282 }
3283
3284 return false;
3285 }
3286
3287 case FLOAT_EXPR:
3288 {
3289 if (!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3290 {
3291 error ("invalid types in conversion to floating point");
3292 debug_generic_expr (lhs_type);
3293 debug_generic_expr (rhs1_type);
3294 return true;
3295 }
3296
3297 return false;
3298 }
3299
3300 case FIX_TRUNC_EXPR:
3301 {
3302 if (!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3303 {
3304 error ("invalid types in conversion to integer");
3305 debug_generic_expr (lhs_type);
3306 debug_generic_expr (rhs1_type);
3307 return true;
3308 }
3309
3310 return false;
3311 }
3312
3313 case VEC_UNPACK_HI_EXPR:
3314 case VEC_UNPACK_LO_EXPR:
3315 case REDUC_MAX_EXPR:
3316 case REDUC_MIN_EXPR:
3317 case REDUC_PLUS_EXPR:
3318 case VEC_UNPACK_FLOAT_HI_EXPR:
3319 case VEC_UNPACK_FLOAT_LO_EXPR:
3320 /* FIXME. */
3321 return false;
3322
3323 case TRUTH_NOT_EXPR:
3324 case NEGATE_EXPR:
3325 case ABS_EXPR:
3326 case BIT_NOT_EXPR:
3327 case PAREN_EXPR:
3328 case NON_LVALUE_EXPR:
3329 case CONJ_EXPR:
3330 break;
3331
3332 default:
3333 gcc_unreachable ();
3334 }
3335
3336 /* For the remaining codes assert there is no conversion involved. */
3337 if (!useless_type_conversion_p (lhs_type, rhs1_type))
3338 {
3339 error ("non-trivial conversion in unary operation");
3340 debug_generic_expr (lhs_type);
3341 debug_generic_expr (rhs1_type);
3342 return true;
3343 }
3344
3345 return false;
3346 }
3347
3348 /* Verify a gimple assignment statement STMT with a binary rhs.
3349 Returns true if anything is wrong. */
3350
3351 static bool
3352 verify_gimple_assign_binary (gimple stmt)
3353 {
3354 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3355 tree lhs = gimple_assign_lhs (stmt);
3356 tree lhs_type = TREE_TYPE (lhs);
3357 tree rhs1 = gimple_assign_rhs1 (stmt);
3358 tree rhs1_type = TREE_TYPE (rhs1);
3359 tree rhs2 = gimple_assign_rhs2 (stmt);
3360 tree rhs2_type = TREE_TYPE (rhs2);
3361
3362 if (!is_gimple_reg (lhs))
3363 {
3364 error ("non-register as LHS of binary operation");
3365 return true;
3366 }
3367
3368 if (!is_gimple_val (rhs1)
3369 || !is_gimple_val (rhs2))
3370 {
3371 error ("invalid operands in binary operation");
3372 return true;
3373 }
3374
3375 /* First handle operations that involve different types. */
3376 switch (rhs_code)
3377 {
3378 case COMPLEX_EXPR:
3379 {
3380 if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3381 || !(INTEGRAL_TYPE_P (rhs1_type)
3382 || SCALAR_FLOAT_TYPE_P (rhs1_type))
3383 || !(INTEGRAL_TYPE_P (rhs2_type)
3384 || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3385 {
3386 error ("type mismatch in complex expression");
3387 debug_generic_expr (lhs_type);
3388 debug_generic_expr (rhs1_type);
3389 debug_generic_expr (rhs2_type);
3390 return true;
3391 }
3392
3393 return false;
3394 }
3395
3396 case LSHIFT_EXPR:
3397 case RSHIFT_EXPR:
3398 case LROTATE_EXPR:
3399 case RROTATE_EXPR:
3400 {
3401 /* Shifts and rotates are ok on integral types, fixed point
3402 types and integer vector types. */
3403 if ((!INTEGRAL_TYPE_P (rhs1_type)
3404 && !FIXED_POINT_TYPE_P (rhs1_type)
3405 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3406 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3407 || (!INTEGRAL_TYPE_P (rhs2_type)
3408 /* Vector shifts of vectors are also ok. */
3409 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3410 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3411 && TREE_CODE (rhs2_type) == VECTOR_TYPE
3412 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3413 || !useless_type_conversion_p (lhs_type, rhs1_type))
3414 {
3415 error ("type mismatch in shift expression");
3416 debug_generic_expr (lhs_type);
3417 debug_generic_expr (rhs1_type);
3418 debug_generic_expr (rhs2_type);
3419 return true;
3420 }
3421
3422 return false;
3423 }
3424
3425 case VEC_LSHIFT_EXPR:
3426 case VEC_RSHIFT_EXPR:
3427 {
3428 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3429 || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3430 || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3431 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3432 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3433 || (!INTEGRAL_TYPE_P (rhs2_type)
3434 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3435 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3436 || !useless_type_conversion_p (lhs_type, rhs1_type))
3437 {
3438 error ("type mismatch in vector shift expression");
3439 debug_generic_expr (lhs_type);
3440 debug_generic_expr (rhs1_type);
3441 debug_generic_expr (rhs2_type);
3442 return true;
3443 }
3444 /* For shifting a vector of non-integral components we
3445 only allow shifting by a constant multiple of the element size. */
3446 if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3447 && (TREE_CODE (rhs2) != INTEGER_CST
3448 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3449 TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3450 {
3451 error ("non-element sized vector shift of floating point vector");
3452 return true;
3453 }
3454
3455 return false;
3456 }
3457
3458 case PLUS_EXPR:
3459 case MINUS_EXPR:
3460 {
3461 /* We use regular PLUS_EXPR and MINUS_EXPR for vectors.
3462 ??? This just makes the checker happy and may not be what is
3463 intended. */
3464 if (TREE_CODE (lhs_type) == VECTOR_TYPE
3465 && POINTER_TYPE_P (TREE_TYPE (lhs_type)))
3466 {
3467 if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3468 || TREE_CODE (rhs2_type) != VECTOR_TYPE)
3469 {
3470 error ("invalid non-vector operands to vector valued plus");
3471 return true;
3472 }
3473 lhs_type = TREE_TYPE (lhs_type);
3474 rhs1_type = TREE_TYPE (rhs1_type);
3475 rhs2_type = TREE_TYPE (rhs2_type);
3476 /* PLUS_EXPR is commutative, so we might end up canonicalizing
3477 the pointer to 2nd place. */
3478 if (POINTER_TYPE_P (rhs2_type))
3479 {
3480 tree tem = rhs1_type;
3481 rhs1_type = rhs2_type;
3482 rhs2_type = tem;
3483 }
3484 goto do_pointer_plus_expr_check;
3485 }
3486 if (POINTER_TYPE_P (lhs_type)
3487 || POINTER_TYPE_P (rhs1_type)
3488 || POINTER_TYPE_P (rhs2_type))
3489 {
3490 error ("invalid (pointer) operands to plus/minus");
3491 return true;
3492 }
3493
3494 /* Continue with generic binary expression handling. */
3495 break;
3496 }
3497
3498 case POINTER_PLUS_EXPR:
3499 {
3500 do_pointer_plus_expr_check:
3501 if (!POINTER_TYPE_P (rhs1_type)
3502 || !useless_type_conversion_p (lhs_type, rhs1_type)
3503 || !useless_type_conversion_p (sizetype, rhs2_type))
3504 {
3505 error ("type mismatch in pointer plus expression");
3506 debug_generic_stmt (lhs_type);
3507 debug_generic_stmt (rhs1_type);
3508 debug_generic_stmt (rhs2_type);
3509 return true;
3510 }
3511
3512 return false;
3513 }
3514
3515 case TRUTH_ANDIF_EXPR:
3516 case TRUTH_ORIF_EXPR:
3517 gcc_unreachable ();
3518
3519 case TRUTH_AND_EXPR:
3520 case TRUTH_OR_EXPR:
3521 case TRUTH_XOR_EXPR:
3522 {
3523 /* We allow any kind of integral typed argument and result. */
3524 if (!INTEGRAL_TYPE_P (rhs1_type)
3525 || !INTEGRAL_TYPE_P (rhs2_type)
3526 || !INTEGRAL_TYPE_P (lhs_type))
3527 {
3528 error ("type mismatch in binary truth expression");
3529 debug_generic_expr (lhs_type);
3530 debug_generic_expr (rhs1_type);
3531 debug_generic_expr (rhs2_type);
3532 return true;
3533 }
3534
3535 return false;
3536 }
3537
3538 case LT_EXPR:
3539 case LE_EXPR:
3540 case GT_EXPR:
3541 case GE_EXPR:
3542 case EQ_EXPR:
3543 case NE_EXPR:
3544 case UNORDERED_EXPR:
3545 case ORDERED_EXPR:
3546 case UNLT_EXPR:
3547 case UNLE_EXPR:
3548 case UNGT_EXPR:
3549 case UNGE_EXPR:
3550 case UNEQ_EXPR:
3551 case LTGT_EXPR:
3552 /* Comparisons are also binary, but the result type is not
3553 connected to the operand types. */
3554 return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3555
3556 case WIDEN_MULT_EXPR:
3557 if (TREE_CODE (lhs_type) != INTEGER_TYPE)
3558 return true;
3559 return ((2 * TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (lhs_type))
3560 || (TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type)));
3561
3562 case WIDEN_SUM_EXPR:
3563 case VEC_WIDEN_MULT_HI_EXPR:
3564 case VEC_WIDEN_MULT_LO_EXPR:
3565 case VEC_PACK_TRUNC_EXPR:
3566 case VEC_PACK_SAT_EXPR:
3567 case VEC_PACK_FIX_TRUNC_EXPR:
3568 case VEC_EXTRACT_EVEN_EXPR:
3569 case VEC_EXTRACT_ODD_EXPR:
3570 case VEC_INTERLEAVE_HIGH_EXPR:
3571 case VEC_INTERLEAVE_LOW_EXPR:
3572 /* FIXME. */
3573 return false;
3574
3575 case MULT_EXPR:
3576 case TRUNC_DIV_EXPR:
3577 case CEIL_DIV_EXPR:
3578 case FLOOR_DIV_EXPR:
3579 case ROUND_DIV_EXPR:
3580 case TRUNC_MOD_EXPR:
3581 case CEIL_MOD_EXPR:
3582 case FLOOR_MOD_EXPR:
3583 case ROUND_MOD_EXPR:
3584 case RDIV_EXPR:
3585 case EXACT_DIV_EXPR:
3586 case MIN_EXPR:
3587 case MAX_EXPR:
3588 case BIT_IOR_EXPR:
3589 case BIT_XOR_EXPR:
3590 case BIT_AND_EXPR:
3591 /* Continue with generic binary expression handling. */
3592 break;
3593
3594 default:
3595 gcc_unreachable ();
3596 }
3597
3598 if (!useless_type_conversion_p (lhs_type, rhs1_type)
3599 || !useless_type_conversion_p (lhs_type, rhs2_type))
3600 {
3601 error ("type mismatch in binary expression");
3602 debug_generic_stmt (lhs_type);
3603 debug_generic_stmt (rhs1_type);
3604 debug_generic_stmt (rhs2_type);
3605 return true;
3606 }
3607
3608 return false;
3609 }
3610
3611 /* Verify a gimple assignment statement STMT with a ternary rhs.
3612 Returns true if anything is wrong. */
3613
3614 static bool
3615 verify_gimple_assign_ternary (gimple stmt)
3616 {
3617 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3618 tree lhs = gimple_assign_lhs (stmt);
3619 tree lhs_type = TREE_TYPE (lhs);
3620 tree rhs1 = gimple_assign_rhs1 (stmt);
3621 tree rhs1_type = TREE_TYPE (rhs1);
3622 tree rhs2 = gimple_assign_rhs2 (stmt);
3623 tree rhs2_type = TREE_TYPE (rhs2);
3624 tree rhs3 = gimple_assign_rhs3 (stmt);
3625 tree rhs3_type = TREE_TYPE (rhs3);
3626
3627 if (!is_gimple_reg (lhs))
3628 {
3629 error ("non-register as LHS of ternary operation");
3630 return true;
3631 }
3632
3633 if (!is_gimple_val (rhs1)
3634 || !is_gimple_val (rhs2)
3635 || !is_gimple_val (rhs3))
3636 {
3637 error ("invalid operands in ternary operation");
3638 return true;
3639 }
3640
3641 /* First handle operations that involve different types. */
3642 switch (rhs_code)
3643 {
3644 case WIDEN_MULT_PLUS_EXPR:
3645 case WIDEN_MULT_MINUS_EXPR:
3646 if ((!INTEGRAL_TYPE_P (rhs1_type)
3647 && !FIXED_POINT_TYPE_P (rhs1_type))
3648 || !useless_type_conversion_p (rhs1_type, rhs2_type)
3649 || !useless_type_conversion_p (lhs_type, rhs3_type)
3650 || 2 * TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (lhs_type)
3651 || TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type))
3652 {
3653 error ("type mismatch in widening multiply-accumulate expression");
3654 debug_generic_expr (lhs_type);
3655 debug_generic_expr (rhs1_type);
3656 debug_generic_expr (rhs2_type);
3657 debug_generic_expr (rhs3_type);
3658 return true;
3659 }
3660 break;
3661
3662 case FMA_EXPR:
3663 if (!useless_type_conversion_p (lhs_type, rhs1_type)
3664 || !useless_type_conversion_p (lhs_type, rhs2_type)
3665 || !useless_type_conversion_p (lhs_type, rhs3_type))
3666 {
3667 error ("type mismatch in fused multiply-add expression");
3668 debug_generic_expr (lhs_type);
3669 debug_generic_expr (rhs1_type);
3670 debug_generic_expr (rhs2_type);
3671 debug_generic_expr (rhs3_type);
3672 return true;
3673 }
3674 break;
3675
3676 case DOT_PROD_EXPR:
3677 case REALIGN_LOAD_EXPR:
3678 /* FIXME. */
3679 return false;
3680
3681 default:
3682 gcc_unreachable ();
3683 }
3684 return false;
3685 }
3686
3687 /* Verify a gimple assignment statement STMT with a single rhs.
3688 Returns true if anything is wrong. */
3689
3690 static bool
3691 verify_gimple_assign_single (gimple stmt)
3692 {
3693 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3694 tree lhs = gimple_assign_lhs (stmt);
3695 tree lhs_type = TREE_TYPE (lhs);
3696 tree rhs1 = gimple_assign_rhs1 (stmt);
3697 tree rhs1_type = TREE_TYPE (rhs1);
3698 bool res = false;
3699
3700 if (!useless_type_conversion_p (lhs_type, rhs1_type))
3701 {
3702 error ("non-trivial conversion at assignment");
3703 debug_generic_expr (lhs_type);
3704 debug_generic_expr (rhs1_type);
3705 return true;
3706 }
3707
3708 if (handled_component_p (lhs))
3709 res |= verify_types_in_gimple_reference (lhs, true);
3710
3711 /* Special codes we cannot handle via their class. */
3712 switch (rhs_code)
3713 {
3714 case ADDR_EXPR:
3715 {
3716 tree op = TREE_OPERAND (rhs1, 0);
3717 if (!is_gimple_addressable (op))
3718 {
3719 error ("invalid operand in unary expression");
3720 return true;
3721 }
3722
3723 /* Technically there is no longer a need for matching types, but
3724 gimple hygiene asks for this check. In LTO we can end up
3725 combining incompatible units and thus end up with addresses
3726 of globals that change their type to a common one. */
3727 if (!in_lto_p
3728 && !types_compatible_p (TREE_TYPE (op),
3729 TREE_TYPE (TREE_TYPE (rhs1)))
3730 && !one_pointer_to_useless_type_conversion_p (TREE_TYPE (rhs1),
3731 TREE_TYPE (op)))
3732 {
3733 error ("type mismatch in address expression");
3734 debug_generic_stmt (TREE_TYPE (rhs1));
3735 debug_generic_stmt (TREE_TYPE (op));
3736 return true;
3737 }
3738
3739 return verify_types_in_gimple_reference (op, true);
3740 }
3741
3742 /* tcc_reference */
3743 case INDIRECT_REF:
3744 error ("INDIRECT_REF in gimple IL");
3745 return true;
3746
3747 case COMPONENT_REF:
3748 case BIT_FIELD_REF:
3749 case ARRAY_REF:
3750 case ARRAY_RANGE_REF:
3751 case VIEW_CONVERT_EXPR:
3752 case REALPART_EXPR:
3753 case IMAGPART_EXPR:
3754 case TARGET_MEM_REF:
3755 case MEM_REF:
3756 if (!is_gimple_reg (lhs)
3757 && is_gimple_reg_type (TREE_TYPE (lhs)))
3758 {
3759 error ("invalid rhs for gimple memory store");
3760 debug_generic_stmt (lhs);
3761 debug_generic_stmt (rhs1);
3762 return true;
3763 }
3764 return res || verify_types_in_gimple_reference (rhs1, false);
3765
3766 /* tcc_constant */
3767 case SSA_NAME:
3768 case INTEGER_CST:
3769 case REAL_CST:
3770 case FIXED_CST:
3771 case COMPLEX_CST:
3772 case VECTOR_CST:
3773 case STRING_CST:
3774 return res;
3775
3776 /* tcc_declaration */
3777 case CONST_DECL:
3778 return res;
3779 case VAR_DECL:
3780 case PARM_DECL:
3781 if (!is_gimple_reg (lhs)
3782 && !is_gimple_reg (rhs1)
3783 && is_gimple_reg_type (TREE_TYPE (lhs)))
3784 {
3785 error ("invalid rhs for gimple memory store");
3786 debug_generic_stmt (lhs);
3787 debug_generic_stmt (rhs1);
3788 return true;
3789 }
3790 return res;
3791
3792 case COND_EXPR:
3793 if (!is_gimple_reg (lhs)
3794 || (!is_gimple_reg (TREE_OPERAND (rhs1, 0))
3795 && !COMPARISON_CLASS_P (TREE_OPERAND (rhs1, 0)))
3796 || (!is_gimple_reg (TREE_OPERAND (rhs1, 1))
3797 && !is_gimple_min_invariant (TREE_OPERAND (rhs1, 1)))
3798 || (!is_gimple_reg (TREE_OPERAND (rhs1, 2))
3799 && !is_gimple_min_invariant (TREE_OPERAND (rhs1, 2))))
3800 {
3801 error ("invalid COND_EXPR in gimple assignment");
3802 debug_generic_stmt (rhs1);
3803 return true;
3804 }
3805 return res;
3806
3807 case CONSTRUCTOR:
3808 case OBJ_TYPE_REF:
3809 case ASSERT_EXPR:
3810 case WITH_SIZE_EXPR:
3811 case VEC_COND_EXPR:
3812 /* FIXME. */
3813 return res;
3814
3815 default:;
3816 }
3817
3818 return res;
3819 }
3820
3821 /* Verify the contents of a GIMPLE_ASSIGN STMT. Returns true when there
3822 is a problem, otherwise false. */
3823
3824 static bool
3825 verify_gimple_assign (gimple stmt)
3826 {
3827 switch (gimple_assign_rhs_class (stmt))
3828 {
3829 case GIMPLE_SINGLE_RHS:
3830 return verify_gimple_assign_single (stmt);
3831
3832 case GIMPLE_UNARY_RHS:
3833 return verify_gimple_assign_unary (stmt);
3834
3835 case GIMPLE_BINARY_RHS:
3836 return verify_gimple_assign_binary (stmt);
3837
3838 case GIMPLE_TERNARY_RHS:
3839 return verify_gimple_assign_ternary (stmt);
3840
3841 default:
3842 gcc_unreachable ();
3843 }
3844 }
3845
3846 /* Verify the contents of a GIMPLE_RETURN STMT. Returns true when there
3847 is a problem, otherwise false. */
3848
3849 static bool
3850 verify_gimple_return (gimple stmt)
3851 {
3852 tree op = gimple_return_retval (stmt);
3853 tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
3854
3855 /* We cannot test for present return values as we do not fix up missing
3856 return values from the original source. */
3857 if (op == NULL)
3858 return false;
3859
3860 if (!is_gimple_val (op)
3861 && TREE_CODE (op) != RESULT_DECL)
3862 {
3863 error ("invalid operand in return statement");
3864 debug_generic_stmt (op);
3865 return true;
3866 }
3867
3868 if ((TREE_CODE (op) == RESULT_DECL
3869 && DECL_BY_REFERENCE (op))
3870 || (TREE_CODE (op) == SSA_NAME
3871 && TREE_CODE (SSA_NAME_VAR (op)) == RESULT_DECL
3872 && DECL_BY_REFERENCE (SSA_NAME_VAR (op))))
3873 op = TREE_TYPE (op);
3874
3875 if (!useless_type_conversion_p (restype, TREE_TYPE (op)))
3876 {
3877 error ("invalid conversion in return statement");
3878 debug_generic_stmt (restype);
3879 debug_generic_stmt (TREE_TYPE (op));
3880 return true;
3881 }
3882
3883 return false;
3884 }
3885
3886
3887 /* Verify the contents of a GIMPLE_GOTO STMT. Returns true when there
3888 is a problem, otherwise false. */
3889
3890 static bool
3891 verify_gimple_goto (gimple stmt)
3892 {
3893 tree dest = gimple_goto_dest (stmt);
3894
3895 /* ??? We have two canonical forms of direct goto destinations, a
3896 bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL. */
3897 if (TREE_CODE (dest) != LABEL_DECL
3898 && (!is_gimple_val (dest)
3899 || !POINTER_TYPE_P (TREE_TYPE (dest))))
3900 {
3901 error ("goto destination is neither a label nor a pointer");
3902 return true;
3903 }
3904
3905 return false;
3906 }
3907
3908 /* Verify the contents of a GIMPLE_SWITCH STMT. Returns true when there
3909 is a problem, otherwise false. */
3910
3911 static bool
3912 verify_gimple_switch (gimple stmt)
3913 {
3914 if (!is_gimple_val (gimple_switch_index (stmt)))
3915 {
3916 error ("invalid operand to switch statement");
3917 debug_generic_stmt (gimple_switch_index (stmt));
3918 return true;
3919 }
3920
3921 return false;
3922 }
3923
3924
3925 /* Verify a gimple debug statement STMT.
3926 Returns true if anything is wrong. */
3927
3928 static bool
3929 verify_gimple_debug (gimple stmt ATTRIBUTE_UNUSED)
3930 {
3931 /* There isn't much that could be wrong in a gimple debug stmt. A
3932 gimple debug bind stmt, for example, maps a tree, that's usually
3933 a VAR_DECL or a PARM_DECL, but that could also be some scalarized
3934 component or member of an aggregate type, to another tree, that
3935 can be an arbitrary expression. These stmts expand into debug
3936 insns, and are converted to debug notes by var-tracking.c. */
3937 return false;
3938 }
3939
3940 /* Verify a gimple label statement STMT.
3941 Returns true if anything is wrong. */
3942
3943 static bool
3944 verify_gimple_label (gimple stmt)
3945 {
3946 tree decl = gimple_label_label (stmt);
3947 int uid;
3948 bool err = false;
3949
3950 if (TREE_CODE (decl) != LABEL_DECL)
3951 return true;
3952
3953 uid = LABEL_DECL_UID (decl);
3954 if (cfun->cfg
3955 && (uid == -1
3956 || VEC_index (basic_block,
3957 label_to_block_map, uid) != gimple_bb (stmt)))
3958 {
3959 error ("incorrect entry in label_to_block_map");
3960 err |= true;
3961 }
3962
3963 uid = EH_LANDING_PAD_NR (decl);
3964 if (uid)
3965 {
3966 eh_landing_pad lp = get_eh_landing_pad_from_number (uid);
3967 if (decl != lp->post_landing_pad)
3968 {
3969 error ("incorrect setting of landing pad number");
3970 err |= true;
3971 }
3972 }
3973
3974 return err;
3975 }
3976
3977 /* Verify the GIMPLE statement STMT. Returns true if there is an
3978 error, otherwise false. */
3979
3980 static bool
3981 verify_gimple_stmt (gimple stmt)
3982 {
3983 switch (gimple_code (stmt))
3984 {
3985 case GIMPLE_ASSIGN:
3986 return verify_gimple_assign (stmt);
3987
3988 case GIMPLE_LABEL:
3989 return verify_gimple_label (stmt);
3990
3991 case GIMPLE_CALL:
3992 return verify_gimple_call (stmt);
3993
3994 case GIMPLE_COND:
3995 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
3996 {
3997 error ("invalid comparison code in gimple cond");
3998 return true;
3999 }
4000 if (!(!gimple_cond_true_label (stmt)
4001 || TREE_CODE (gimple_cond_true_label (stmt)) == LABEL_DECL)
4002 || !(!gimple_cond_false_label (stmt)
4003 || TREE_CODE (gimple_cond_false_label (stmt)) == LABEL_DECL))
4004 {
4005 error ("invalid labels in gimple cond");
4006 return true;
4007 }
4008
4009 return verify_gimple_comparison (boolean_type_node,
4010 gimple_cond_lhs (stmt),
4011 gimple_cond_rhs (stmt));
4012
4013 case GIMPLE_GOTO:
4014 return verify_gimple_goto (stmt);
4015
4016 case GIMPLE_SWITCH:
4017 return verify_gimple_switch (stmt);
4018
4019 case GIMPLE_RETURN:
4020 return verify_gimple_return (stmt);
4021
4022 case GIMPLE_ASM:
4023 return false;
4024
4025 /* Tuples that do not have tree operands. */
4026 case GIMPLE_NOP:
4027 case GIMPLE_PREDICT:
4028 case GIMPLE_RESX:
4029 case GIMPLE_EH_DISPATCH:
4030 case GIMPLE_EH_MUST_NOT_THROW:
4031 return false;
4032
4033 CASE_GIMPLE_OMP:
4034 /* OpenMP directives are validated by the FE and never operated
4035 on by the optimizers. Furthermore, GIMPLE_OMP_FOR may contain
4036 non-gimple expressions when the main index variable has had
4037 its address taken. This does not affect the loop itself
4038 because the header of an GIMPLE_OMP_FOR is merely used to determine
4039 how to setup the parallel iteration. */
4040 return false;
4041
4042 case GIMPLE_DEBUG:
4043 return verify_gimple_debug (stmt);
4044
4045 default:
4046 gcc_unreachable ();
4047 }
4048 }
4049
4050 /* Verify the contents of a GIMPLE_PHI. Returns true if there is a problem,
4051 and false otherwise. */
4052
4053 static bool
4054 verify_gimple_phi (gimple phi)
4055 {
4056 bool err = false;
4057 unsigned i;
4058 tree phi_result = gimple_phi_result (phi);
4059 bool virtual_p;
4060
4061 if (!phi_result)
4062 {
4063 error ("invalid PHI result");
4064 return true;
4065 }
4066
4067 virtual_p = !is_gimple_reg (phi_result);
4068 if (TREE_CODE (phi_result) != SSA_NAME
4069 || (virtual_p
4070 && SSA_NAME_VAR (phi_result) != gimple_vop (cfun)))
4071 {
4072 error ("invalid PHI result");
4073 err = true;
4074 }
4075
4076 for (i = 0; i < gimple_phi_num_args (phi); i++)
4077 {
4078 tree t = gimple_phi_arg_def (phi, i);
4079
4080 if (!t)
4081 {
4082 error ("missing PHI def");
4083 err |= true;
4084 continue;
4085 }
4086 /* Addressable variables do have SSA_NAMEs but they
4087 are not considered gimple values. */
4088 else if ((TREE_CODE (t) == SSA_NAME
4089 && virtual_p != !is_gimple_reg (t))
4090 || (virtual_p
4091 && (TREE_CODE (t) != SSA_NAME
4092 || SSA_NAME_VAR (t) != gimple_vop (cfun)))
4093 || (!virtual_p
4094 && !is_gimple_val (t)))
4095 {
4096 error ("invalid PHI argument");
4097 debug_generic_expr (t);
4098 err |= true;
4099 }
4100 #ifdef ENABLE_TYPES_CHECKING
4101 if (!useless_type_conversion_p (TREE_TYPE (phi_result), TREE_TYPE (t)))
4102 {
4103 error ("incompatible types in PHI argument %u", i);
4104 debug_generic_stmt (TREE_TYPE (phi_result));
4105 debug_generic_stmt (TREE_TYPE (t));
4106 err |= true;
4107 }
4108 #endif
4109 }
4110
4111 return err;
4112 }
4113
4114 /* Verify the GIMPLE statements inside the sequence STMTS. */
4115
4116 static bool
4117 verify_gimple_in_seq_2 (gimple_seq stmts)
4118 {
4119 gimple_stmt_iterator ittr;
4120 bool err = false;
4121
4122 for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
4123 {
4124 gimple stmt = gsi_stmt (ittr);
4125
4126 switch (gimple_code (stmt))
4127 {
4128 case GIMPLE_BIND:
4129 err |= verify_gimple_in_seq_2 (gimple_bind_body (stmt));
4130 break;
4131
4132 case GIMPLE_TRY:
4133 err |= verify_gimple_in_seq_2 (gimple_try_eval (stmt));
4134 err |= verify_gimple_in_seq_2 (gimple_try_cleanup (stmt));
4135 break;
4136
4137 case GIMPLE_EH_FILTER:
4138 err |= verify_gimple_in_seq_2 (gimple_eh_filter_failure (stmt));
4139 break;
4140
4141 case GIMPLE_CATCH:
4142 err |= verify_gimple_in_seq_2 (gimple_catch_handler (stmt));
4143 break;
4144
4145 default:
4146 {
4147 bool err2 = verify_gimple_stmt (stmt);
4148 if (err2)
4149 debug_gimple_stmt (stmt);
4150 err |= err2;
4151 }
4152 }
4153 }
4154
4155 return err;
4156 }
4157
4158
4159 /* Verify the GIMPLE statements inside the statement list STMTS. */
4160
4161 DEBUG_FUNCTION void
4162 verify_gimple_in_seq (gimple_seq stmts)
4163 {
4164 timevar_push (TV_TREE_STMT_VERIFY);
4165 if (verify_gimple_in_seq_2 (stmts))
4166 internal_error ("verify_gimple failed");
4167 timevar_pop (TV_TREE_STMT_VERIFY);
4168 }
4169
4170 /* Return true when the T can be shared. */
4171
4172 bool
4173 tree_node_can_be_shared (tree t)
4174 {
4175 if (IS_TYPE_OR_DECL_P (t)
4176 || is_gimple_min_invariant (t)
4177 || TREE_CODE (t) == SSA_NAME
4178 || t == error_mark_node
4179 || TREE_CODE (t) == IDENTIFIER_NODE)
4180 return true;
4181
4182 if (TREE_CODE (t) == CASE_LABEL_EXPR)
4183 return true;
4184
4185 while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4186 && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4187 || TREE_CODE (t) == COMPONENT_REF
4188 || TREE_CODE (t) == REALPART_EXPR
4189 || TREE_CODE (t) == IMAGPART_EXPR)
4190 t = TREE_OPERAND (t, 0);
4191
4192 if (DECL_P (t))
4193 return true;
4194
4195 return false;
4196 }
4197
4198 /* Called via walk_gimple_stmt. Verify tree sharing. */
4199
4200 static tree
4201 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4202 {
4203 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4204 struct pointer_set_t *visited = (struct pointer_set_t *) wi->info;
4205
4206 if (tree_node_can_be_shared (*tp))
4207 {
4208 *walk_subtrees = false;
4209 return NULL;
4210 }
4211
4212 if (pointer_set_insert (visited, *tp))
4213 return *tp;
4214
4215 return NULL;
4216 }
4217
4218 static bool eh_error_found;
4219 static int
4220 verify_eh_throw_stmt_node (void **slot, void *data)
4221 {
4222 struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4223 struct pointer_set_t *visited = (struct pointer_set_t *) data;
4224
4225 if (!pointer_set_contains (visited, node->stmt))
4226 {
4227 error ("dead STMT in EH table");
4228 debug_gimple_stmt (node->stmt);
4229 eh_error_found = true;
4230 }
4231 return 1;
4232 }
4233
4234 /* Verify the GIMPLE statements in the CFG of FN. */
4235
4236 DEBUG_FUNCTION void
4237 verify_gimple_in_cfg (struct function *fn)
4238 {
4239 basic_block bb;
4240 bool err = false;
4241 struct pointer_set_t *visited, *visited_stmts;
4242
4243 timevar_push (TV_TREE_STMT_VERIFY);
4244 visited = pointer_set_create ();
4245 visited_stmts = pointer_set_create ();
4246
4247 FOR_EACH_BB_FN (bb, fn)
4248 {
4249 gimple_stmt_iterator gsi;
4250
4251 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4252 {
4253 gimple phi = gsi_stmt (gsi);
4254 bool err2 = false;
4255 unsigned i;
4256
4257 pointer_set_insert (visited_stmts, phi);
4258
4259 if (gimple_bb (phi) != bb)
4260 {
4261 error ("gimple_bb (phi) is set to a wrong basic block");
4262 err2 = true;
4263 }
4264
4265 err2 |= verify_gimple_phi (phi);
4266
4267 for (i = 0; i < gimple_phi_num_args (phi); i++)
4268 {
4269 tree arg = gimple_phi_arg_def (phi, i);
4270 tree addr = walk_tree (&arg, verify_node_sharing, visited, NULL);
4271 if (addr)
4272 {
4273 error ("incorrect sharing of tree nodes");
4274 debug_generic_expr (addr);
4275 err2 |= true;
4276 }
4277 }
4278
4279 if (err2)
4280 debug_gimple_stmt (phi);
4281 err |= err2;
4282 }
4283
4284 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4285 {
4286 gimple stmt = gsi_stmt (gsi);
4287 bool err2 = false;
4288 struct walk_stmt_info wi;
4289 tree addr;
4290 int lp_nr;
4291
4292 pointer_set_insert (visited_stmts, stmt);
4293
4294 if (gimple_bb (stmt) != bb)
4295 {
4296 error ("gimple_bb (stmt) is set to a wrong basic block");
4297 err2 = true;
4298 }
4299
4300 err2 |= verify_gimple_stmt (stmt);
4301
4302 memset (&wi, 0, sizeof (wi));
4303 wi.info = (void *) visited;
4304 addr = walk_gimple_op (stmt, verify_node_sharing, &wi);
4305 if (addr)
4306 {
4307 error ("incorrect sharing of tree nodes");
4308 debug_generic_expr (addr);
4309 err2 |= true;
4310 }
4311
4312 /* ??? Instead of not checking these stmts at all the walker
4313 should know its context via wi. */
4314 if (!is_gimple_debug (stmt)
4315 && !is_gimple_omp (stmt))
4316 {
4317 memset (&wi, 0, sizeof (wi));
4318 addr = walk_gimple_op (stmt, verify_expr, &wi);
4319 if (addr)
4320 {
4321 debug_generic_expr (addr);
4322 inform (gimple_location (stmt), "in statement");
4323 err2 |= true;
4324 }
4325 }
4326
4327 /* If the statement is marked as part of an EH region, then it is
4328 expected that the statement could throw. Verify that when we
4329 have optimizations that simplify statements such that we prove
4330 that they cannot throw, that we update other data structures
4331 to match. */
4332 lp_nr = lookup_stmt_eh_lp (stmt);
4333 if (lp_nr != 0)
4334 {
4335 if (!stmt_could_throw_p (stmt))
4336 {
4337 error ("statement marked for throw, but doesn%'t");
4338 err2 |= true;
4339 }
4340 else if (lp_nr > 0
4341 && !gsi_one_before_end_p (gsi)
4342 && stmt_can_throw_internal (stmt))
4343 {
4344 error ("statement marked for throw in middle of block");
4345 err2 |= true;
4346 }
4347 }
4348
4349 if (err2)
4350 debug_gimple_stmt (stmt);
4351 err |= err2;
4352 }
4353 }
4354
4355 eh_error_found = false;
4356 if (get_eh_throw_stmt_table (cfun))
4357 htab_traverse (get_eh_throw_stmt_table (cfun),
4358 verify_eh_throw_stmt_node,
4359 visited_stmts);
4360
4361 if (err || eh_error_found)
4362 internal_error ("verify_gimple failed");
4363
4364 pointer_set_destroy (visited);
4365 pointer_set_destroy (visited_stmts);
4366 verify_histograms ();
4367 timevar_pop (TV_TREE_STMT_VERIFY);
4368 }
4369
4370
4371 /* Verifies that the flow information is OK. */
4372
4373 static int
4374 gimple_verify_flow_info (void)
4375 {
4376 int err = 0;
4377 basic_block bb;
4378 gimple_stmt_iterator gsi;
4379 gimple stmt;
4380 edge e;
4381 edge_iterator ei;
4382
4383 if (ENTRY_BLOCK_PTR->il.gimple)
4384 {
4385 error ("ENTRY_BLOCK has IL associated with it");
4386 err = 1;
4387 }
4388
4389 if (EXIT_BLOCK_PTR->il.gimple)
4390 {
4391 error ("EXIT_BLOCK has IL associated with it");
4392 err = 1;
4393 }
4394
4395 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4396 if (e->flags & EDGE_FALLTHRU)
4397 {
4398 error ("fallthru to exit from bb %d", e->src->index);
4399 err = 1;
4400 }
4401
4402 FOR_EACH_BB (bb)
4403 {
4404 bool found_ctrl_stmt = false;
4405
4406 stmt = NULL;
4407
4408 /* Skip labels on the start of basic block. */
4409 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4410 {
4411 tree label;
4412 gimple prev_stmt = stmt;
4413
4414 stmt = gsi_stmt (gsi);
4415
4416 if (gimple_code (stmt) != GIMPLE_LABEL)
4417 break;
4418
4419 label = gimple_label_label (stmt);
4420 if (prev_stmt && DECL_NONLOCAL (label))
4421 {
4422 error ("nonlocal label ");
4423 print_generic_expr (stderr, label, 0);
4424 fprintf (stderr, " is not first in a sequence of labels in bb %d",
4425 bb->index);
4426 err = 1;
4427 }
4428
4429 if (prev_stmt && EH_LANDING_PAD_NR (label) != 0)
4430 {
4431 error ("EH landing pad label ");
4432 print_generic_expr (stderr, label, 0);
4433 fprintf (stderr, " is not first in a sequence of labels in bb %d",
4434 bb->index);
4435 err = 1;
4436 }
4437
4438 if (label_to_block (label) != bb)
4439 {
4440 error ("label ");
4441 print_generic_expr (stderr, label, 0);
4442 fprintf (stderr, " to block does not match in bb %d",
4443 bb->index);
4444 err = 1;
4445 }
4446
4447 if (decl_function_context (label) != current_function_decl)
4448 {
4449 error ("label ");
4450 print_generic_expr (stderr, label, 0);
4451 fprintf (stderr, " has incorrect context in bb %d",
4452 bb->index);
4453 err = 1;
4454 }
4455 }
4456
4457 /* Verify that body of basic block BB is free of control flow. */
4458 for (; !gsi_end_p (gsi); gsi_next (&gsi))
4459 {
4460 gimple stmt = gsi_stmt (gsi);
4461
4462 if (found_ctrl_stmt)
4463 {
4464 error ("control flow in the middle of basic block %d",
4465 bb->index);
4466 err = 1;
4467 }
4468
4469 if (stmt_ends_bb_p (stmt))
4470 found_ctrl_stmt = true;
4471
4472 if (gimple_code (stmt) == GIMPLE_LABEL)
4473 {
4474 error ("label ");
4475 print_generic_expr (stderr, gimple_label_label (stmt), 0);
4476 fprintf (stderr, " in the middle of basic block %d", bb->index);
4477 err = 1;
4478 }
4479 }
4480
4481 gsi = gsi_last_bb (bb);
4482 if (gsi_end_p (gsi))
4483 continue;
4484
4485 stmt = gsi_stmt (gsi);
4486
4487 if (gimple_code (stmt) == GIMPLE_LABEL)
4488 continue;
4489
4490 err |= verify_eh_edges (stmt);
4491
4492 if (is_ctrl_stmt (stmt))
4493 {
4494 FOR_EACH_EDGE (e, ei, bb->succs)
4495 if (e->flags & EDGE_FALLTHRU)
4496 {
4497 error ("fallthru edge after a control statement in bb %d",
4498 bb->index);
4499 err = 1;
4500 }
4501 }
4502
4503 if (gimple_code (stmt) != GIMPLE_COND)
4504 {
4505 /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4506 after anything else but if statement. */
4507 FOR_EACH_EDGE (e, ei, bb->succs)
4508 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4509 {
4510 error ("true/false edge after a non-GIMPLE_COND in bb %d",
4511 bb->index);
4512 err = 1;
4513 }
4514 }
4515
4516 switch (gimple_code (stmt))
4517 {
4518 case GIMPLE_COND:
4519 {
4520 edge true_edge;
4521 edge false_edge;
4522
4523 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4524
4525 if (!true_edge
4526 || !false_edge
4527 || !(true_edge->flags & EDGE_TRUE_VALUE)
4528 || !(false_edge->flags & EDGE_FALSE_VALUE)
4529 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4530 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4531 || EDGE_COUNT (bb->succs) >= 3)
4532 {
4533 error ("wrong outgoing edge flags at end of bb %d",
4534 bb->index);
4535 err = 1;
4536 }
4537 }
4538 break;
4539
4540 case GIMPLE_GOTO:
4541 if (simple_goto_p (stmt))
4542 {
4543 error ("explicit goto at end of bb %d", bb->index);
4544 err = 1;
4545 }
4546 else
4547 {
4548 /* FIXME. We should double check that the labels in the
4549 destination blocks have their address taken. */
4550 FOR_EACH_EDGE (e, ei, bb->succs)
4551 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4552 | EDGE_FALSE_VALUE))
4553 || !(e->flags & EDGE_ABNORMAL))
4554 {
4555 error ("wrong outgoing edge flags at end of bb %d",
4556 bb->index);
4557 err = 1;
4558 }
4559 }
4560 break;
4561
4562 case GIMPLE_CALL:
4563 if (!gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
4564 break;
4565 /* ... fallthru ... */
4566 case GIMPLE_RETURN:
4567 if (!single_succ_p (bb)
4568 || (single_succ_edge (bb)->flags
4569 & (EDGE_FALLTHRU | EDGE_ABNORMAL
4570 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4571 {
4572 error ("wrong outgoing edge flags at end of bb %d", bb->index);
4573 err = 1;
4574 }
4575 if (single_succ (bb) != EXIT_BLOCK_PTR)
4576 {
4577 error ("return edge does not point to exit in bb %d",
4578 bb->index);
4579 err = 1;
4580 }
4581 break;
4582
4583 case GIMPLE_SWITCH:
4584 {
4585 tree prev;
4586 edge e;
4587 size_t i, n;
4588
4589 n = gimple_switch_num_labels (stmt);
4590
4591 /* Mark all the destination basic blocks. */
4592 for (i = 0; i < n; ++i)
4593 {
4594 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4595 basic_block label_bb = label_to_block (lab);
4596 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4597 label_bb->aux = (void *)1;
4598 }
4599
4600 /* Verify that the case labels are sorted. */
4601 prev = gimple_switch_label (stmt, 0);
4602 for (i = 1; i < n; ++i)
4603 {
4604 tree c = gimple_switch_label (stmt, i);
4605 if (!CASE_LOW (c))
4606 {
4607 error ("found default case not at the start of "
4608 "case vector");
4609 err = 1;
4610 continue;
4611 }
4612 if (CASE_LOW (prev)
4613 && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4614 {
4615 error ("case labels not sorted: ");
4616 print_generic_expr (stderr, prev, 0);
4617 fprintf (stderr," is greater than ");
4618 print_generic_expr (stderr, c, 0);
4619 fprintf (stderr," but comes before it.\n");
4620 err = 1;
4621 }
4622 prev = c;
4623 }
4624 /* VRP will remove the default case if it can prove it will
4625 never be executed. So do not verify there always exists
4626 a default case here. */
4627
4628 FOR_EACH_EDGE (e, ei, bb->succs)
4629 {
4630 if (!e->dest->aux)
4631 {
4632 error ("extra outgoing edge %d->%d",
4633 bb->index, e->dest->index);
4634 err = 1;
4635 }
4636
4637 e->dest->aux = (void *)2;
4638 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
4639 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4640 {
4641 error ("wrong outgoing edge flags at end of bb %d",
4642 bb->index);
4643 err = 1;
4644 }
4645 }
4646
4647 /* Check that we have all of them. */
4648 for (i = 0; i < n; ++i)
4649 {
4650 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4651 basic_block label_bb = label_to_block (lab);
4652
4653 if (label_bb->aux != (void *)2)
4654 {
4655 error ("missing edge %i->%i", bb->index, label_bb->index);
4656 err = 1;
4657 }
4658 }
4659
4660 FOR_EACH_EDGE (e, ei, bb->succs)
4661 e->dest->aux = (void *)0;
4662 }
4663 break;
4664
4665 case GIMPLE_EH_DISPATCH:
4666 err |= verify_eh_dispatch_edge (stmt);
4667 break;
4668
4669 default:
4670 break;
4671 }
4672 }
4673
4674 if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
4675 verify_dominators (CDI_DOMINATORS);
4676
4677 return err;
4678 }
4679
4680
4681 /* Updates phi nodes after creating a forwarder block joined
4682 by edge FALLTHRU. */
4683
4684 static void
4685 gimple_make_forwarder_block (edge fallthru)
4686 {
4687 edge e;
4688 edge_iterator ei;
4689 basic_block dummy, bb;
4690 tree var;
4691 gimple_stmt_iterator gsi;
4692
4693 dummy = fallthru->src;
4694 bb = fallthru->dest;
4695
4696 if (single_pred_p (bb))
4697 return;
4698
4699 /* If we redirected a branch we must create new PHI nodes at the
4700 start of BB. */
4701 for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
4702 {
4703 gimple phi, new_phi;
4704
4705 phi = gsi_stmt (gsi);
4706 var = gimple_phi_result (phi);
4707 new_phi = create_phi_node (var, bb);
4708 SSA_NAME_DEF_STMT (var) = new_phi;
4709 gimple_phi_set_result (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
4710 add_phi_arg (new_phi, gimple_phi_result (phi), fallthru,
4711 UNKNOWN_LOCATION);
4712 }
4713
4714 /* Add the arguments we have stored on edges. */
4715 FOR_EACH_EDGE (e, ei, bb->preds)
4716 {
4717 if (e == fallthru)
4718 continue;
4719
4720 flush_pending_stmts (e);
4721 }
4722 }
4723
4724
4725 /* Return a non-special label in the head of basic block BLOCK.
4726 Create one if it doesn't exist. */
4727
4728 tree
4729 gimple_block_label (basic_block bb)
4730 {
4731 gimple_stmt_iterator i, s = gsi_start_bb (bb);
4732 bool first = true;
4733 tree label;
4734 gimple stmt;
4735
4736 for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
4737 {
4738 stmt = gsi_stmt (i);
4739 if (gimple_code (stmt) != GIMPLE_LABEL)
4740 break;
4741 label = gimple_label_label (stmt);
4742 if (!DECL_NONLOCAL (label))
4743 {
4744 if (!first)
4745 gsi_move_before (&i, &s);
4746 return label;
4747 }
4748 }
4749
4750 label = create_artificial_label (UNKNOWN_LOCATION);
4751 stmt = gimple_build_label (label);
4752 gsi_insert_before (&s, stmt, GSI_NEW_STMT);
4753 return label;
4754 }
4755
4756
4757 /* Attempt to perform edge redirection by replacing a possibly complex
4758 jump instruction by a goto or by removing the jump completely.
4759 This can apply only if all edges now point to the same block. The
4760 parameters and return values are equivalent to
4761 redirect_edge_and_branch. */
4762
4763 static edge
4764 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
4765 {
4766 basic_block src = e->src;
4767 gimple_stmt_iterator i;
4768 gimple stmt;
4769
4770 /* We can replace or remove a complex jump only when we have exactly
4771 two edges. */
4772 if (EDGE_COUNT (src->succs) != 2
4773 /* Verify that all targets will be TARGET. Specifically, the
4774 edge that is not E must also go to TARGET. */
4775 || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4776 return NULL;
4777
4778 i = gsi_last_bb (src);
4779 if (gsi_end_p (i))
4780 return NULL;
4781
4782 stmt = gsi_stmt (i);
4783
4784 if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
4785 {
4786 gsi_remove (&i, true);
4787 e = ssa_redirect_edge (e, target);
4788 e->flags = EDGE_FALLTHRU;
4789 return e;
4790 }
4791
4792 return NULL;
4793 }
4794
4795
4796 /* Redirect E to DEST. Return NULL on failure. Otherwise, return the
4797 edge representing the redirected branch. */
4798
4799 static edge
4800 gimple_redirect_edge_and_branch (edge e, basic_block dest)
4801 {
4802 basic_block bb = e->src;
4803 gimple_stmt_iterator gsi;
4804 edge ret;
4805 gimple stmt;
4806
4807 if (e->flags & EDGE_ABNORMAL)
4808 return NULL;
4809
4810 if (e->dest == dest)
4811 return NULL;
4812
4813 if (e->flags & EDGE_EH)
4814 return redirect_eh_edge (e, dest);
4815
4816 if (e->src != ENTRY_BLOCK_PTR)
4817 {
4818 ret = gimple_try_redirect_by_replacing_jump (e, dest);
4819 if (ret)
4820 return ret;
4821 }
4822
4823 gsi = gsi_last_bb (bb);
4824 stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
4825
4826 switch (stmt ? gimple_code (stmt) : GIMPLE_ERROR_MARK)
4827 {
4828 case GIMPLE_COND:
4829 /* For COND_EXPR, we only need to redirect the edge. */
4830 break;
4831
4832 case GIMPLE_GOTO:
4833 /* No non-abnormal edges should lead from a non-simple goto, and
4834 simple ones should be represented implicitly. */
4835 gcc_unreachable ();
4836
4837 case GIMPLE_SWITCH:
4838 {
4839 tree label = gimple_block_label (dest);
4840 tree cases = get_cases_for_edge (e, stmt);
4841
4842 /* If we have a list of cases associated with E, then use it
4843 as it's a lot faster than walking the entire case vector. */
4844 if (cases)
4845 {
4846 edge e2 = find_edge (e->src, dest);
4847 tree last, first;
4848
4849 first = cases;
4850 while (cases)
4851 {
4852 last = cases;
4853 CASE_LABEL (cases) = label;
4854 cases = TREE_CHAIN (cases);
4855 }
4856
4857 /* If there was already an edge in the CFG, then we need
4858 to move all the cases associated with E to E2. */
4859 if (e2)
4860 {
4861 tree cases2 = get_cases_for_edge (e2, stmt);
4862
4863 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4864 TREE_CHAIN (cases2) = first;
4865 }
4866 bitmap_set_bit (touched_switch_bbs, gimple_bb (stmt)->index);
4867 }
4868 else
4869 {
4870 size_t i, n = gimple_switch_num_labels (stmt);
4871
4872 for (i = 0; i < n; i++)
4873 {
4874 tree elt = gimple_switch_label (stmt, i);
4875 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4876 CASE_LABEL (elt) = label;
4877 }
4878 }
4879 }
4880 break;
4881
4882 case GIMPLE_ASM:
4883 {
4884 int i, n = gimple_asm_nlabels (stmt);
4885 tree label = NULL;
4886
4887 for (i = 0; i < n; ++i)
4888 {
4889 tree cons = gimple_asm_label_op (stmt, i);
4890 if (label_to_block (TREE_VALUE (cons)) == e->dest)
4891 {
4892 if (!label)
4893 label = gimple_block_label (dest);
4894 TREE_VALUE (cons) = label;
4895 }
4896 }
4897
4898 /* If we didn't find any label matching the former edge in the
4899 asm labels, we must be redirecting the fallthrough
4900 edge. */
4901 gcc_assert (label || (e->flags & EDGE_FALLTHRU));
4902 }
4903 break;
4904
4905 case GIMPLE_RETURN:
4906 gsi_remove (&gsi, true);
4907 e->flags |= EDGE_FALLTHRU;
4908 break;
4909
4910 case GIMPLE_OMP_RETURN:
4911 case GIMPLE_OMP_CONTINUE:
4912 case GIMPLE_OMP_SECTIONS_SWITCH:
4913 case GIMPLE_OMP_FOR:
4914 /* The edges from OMP constructs can be simply redirected. */
4915 break;
4916
4917 case GIMPLE_EH_DISPATCH:
4918 if (!(e->flags & EDGE_FALLTHRU))
4919 redirect_eh_dispatch_edge (stmt, e, dest);
4920 break;
4921
4922 default:
4923 /* Otherwise it must be a fallthru edge, and we don't need to
4924 do anything besides redirecting it. */
4925 gcc_assert (e->flags & EDGE_FALLTHRU);
4926 break;
4927 }
4928
4929 /* Update/insert PHI nodes as necessary. */
4930
4931 /* Now update the edges in the CFG. */
4932 e = ssa_redirect_edge (e, dest);
4933
4934 return e;
4935 }
4936
4937 /* Returns true if it is possible to remove edge E by redirecting
4938 it to the destination of the other edge from E->src. */
4939
4940 static bool
4941 gimple_can_remove_branch_p (const_edge e)
4942 {
4943 if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
4944 return false;
4945
4946 return true;
4947 }
4948
4949 /* Simple wrapper, as we can always redirect fallthru edges. */
4950
4951 static basic_block
4952 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
4953 {
4954 e = gimple_redirect_edge_and_branch (e, dest);
4955 gcc_assert (e);
4956
4957 return NULL;
4958 }
4959
4960
4961 /* Splits basic block BB after statement STMT (but at least after the
4962 labels). If STMT is NULL, BB is split just after the labels. */
4963
4964 static basic_block
4965 gimple_split_block (basic_block bb, void *stmt)
4966 {
4967 gimple_stmt_iterator gsi;
4968 gimple_stmt_iterator gsi_tgt;
4969 gimple act;
4970 gimple_seq list;
4971 basic_block new_bb;
4972 edge e;
4973 edge_iterator ei;
4974
4975 new_bb = create_empty_bb (bb);
4976
4977 /* Redirect the outgoing edges. */
4978 new_bb->succs = bb->succs;
4979 bb->succs = NULL;
4980 FOR_EACH_EDGE (e, ei, new_bb->succs)
4981 e->src = new_bb;
4982
4983 if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
4984 stmt = NULL;
4985
4986 /* Move everything from GSI to the new basic block. */
4987 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4988 {
4989 act = gsi_stmt (gsi);
4990 if (gimple_code (act) == GIMPLE_LABEL)
4991 continue;
4992
4993 if (!stmt)
4994 break;
4995
4996 if (stmt == act)
4997 {
4998 gsi_next (&gsi);
4999 break;
5000 }
5001 }
5002
5003 if (gsi_end_p (gsi))
5004 return new_bb;
5005
5006 /* Split the statement list - avoid re-creating new containers as this
5007 brings ugly quadratic memory consumption in the inliner.
5008 (We are still quadratic since we need to update stmt BB pointers,
5009 sadly.) */
5010 list = gsi_split_seq_before (&gsi);
5011 set_bb_seq (new_bb, list);
5012 for (gsi_tgt = gsi_start (list);
5013 !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
5014 gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
5015
5016 return new_bb;
5017 }
5018
5019
5020 /* Moves basic block BB after block AFTER. */
5021
5022 static bool
5023 gimple_move_block_after (basic_block bb, basic_block after)
5024 {
5025 if (bb->prev_bb == after)
5026 return true;
5027
5028 unlink_block (bb);
5029 link_block (bb, after);
5030
5031 return true;
5032 }
5033
5034
5035 /* Return true if basic_block can be duplicated. */
5036
5037 static bool
5038 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5039 {
5040 return true;
5041 }
5042
5043 /* Create a duplicate of the basic block BB. NOTE: This does not
5044 preserve SSA form. */
5045
5046 static basic_block
5047 gimple_duplicate_bb (basic_block bb)
5048 {
5049 basic_block new_bb;
5050 gimple_stmt_iterator gsi, gsi_tgt;
5051 gimple_seq phis = phi_nodes (bb);
5052 gimple phi, stmt, copy;
5053
5054 new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
5055
5056 /* Copy the PHI nodes. We ignore PHI node arguments here because
5057 the incoming edges have not been setup yet. */
5058 for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
5059 {
5060 phi = gsi_stmt (gsi);
5061 copy = create_phi_node (gimple_phi_result (phi), new_bb);
5062 create_new_def_for (gimple_phi_result (copy), copy,
5063 gimple_phi_result_ptr (copy));
5064 }
5065
5066 gsi_tgt = gsi_start_bb (new_bb);
5067 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5068 {
5069 def_operand_p def_p;
5070 ssa_op_iter op_iter;
5071
5072 stmt = gsi_stmt (gsi);
5073 if (gimple_code (stmt) == GIMPLE_LABEL)
5074 continue;
5075
5076 /* Create a new copy of STMT and duplicate STMT's virtual
5077 operands. */
5078 copy = gimple_copy (stmt);
5079 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
5080
5081 maybe_duplicate_eh_stmt (copy, stmt);
5082 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5083
5084 /* Create new names for all the definitions created by COPY and
5085 add replacement mappings for each new name. */
5086 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5087 create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5088 }
5089
5090 return new_bb;
5091 }
5092
5093 /* Adds phi node arguments for edge E_COPY after basic block duplication. */
5094
5095 static void
5096 add_phi_args_after_copy_edge (edge e_copy)
5097 {
5098 basic_block bb, bb_copy = e_copy->src, dest;
5099 edge e;
5100 edge_iterator ei;
5101 gimple phi, phi_copy;
5102 tree def;
5103 gimple_stmt_iterator psi, psi_copy;
5104
5105 if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
5106 return;
5107
5108 bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5109
5110 if (e_copy->dest->flags & BB_DUPLICATED)
5111 dest = get_bb_original (e_copy->dest);
5112 else
5113 dest = e_copy->dest;
5114
5115 e = find_edge (bb, dest);
5116 if (!e)
5117 {
5118 /* During loop unrolling the target of the latch edge is copied.
5119 In this case we are not looking for edge to dest, but to
5120 duplicated block whose original was dest. */
5121 FOR_EACH_EDGE (e, ei, bb->succs)
5122 {
5123 if ((e->dest->flags & BB_DUPLICATED)
5124 && get_bb_original (e->dest) == dest)
5125 break;
5126 }
5127
5128 gcc_assert (e != NULL);
5129 }
5130
5131 for (psi = gsi_start_phis (e->dest),
5132 psi_copy = gsi_start_phis (e_copy->dest);
5133 !gsi_end_p (psi);
5134 gsi_next (&psi), gsi_next (&psi_copy))
5135 {
5136 phi = gsi_stmt (psi);
5137 phi_copy = gsi_stmt (psi_copy);
5138 def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5139 add_phi_arg (phi_copy, def, e_copy,
5140 gimple_phi_arg_location_from_edge (phi, e));
5141 }
5142 }
5143
5144
5145 /* Basic block BB_COPY was created by code duplication. Add phi node
5146 arguments for edges going out of BB_COPY. The blocks that were
5147 duplicated have BB_DUPLICATED set. */
5148
5149 void
5150 add_phi_args_after_copy_bb (basic_block bb_copy)
5151 {
5152 edge e_copy;
5153 edge_iterator ei;
5154
5155 FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5156 {
5157 add_phi_args_after_copy_edge (e_copy);
5158 }
5159 }
5160
5161 /* Blocks in REGION_COPY array of length N_REGION were created by
5162 duplication of basic blocks. Add phi node arguments for edges
5163 going from these blocks. If E_COPY is not NULL, also add
5164 phi node arguments for its destination.*/
5165
5166 void
5167 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5168 edge e_copy)
5169 {
5170 unsigned i;
5171
5172 for (i = 0; i < n_region; i++)
5173 region_copy[i]->flags |= BB_DUPLICATED;
5174
5175 for (i = 0; i < n_region; i++)
5176 add_phi_args_after_copy_bb (region_copy[i]);
5177 if (e_copy)
5178 add_phi_args_after_copy_edge (e_copy);
5179
5180 for (i = 0; i < n_region; i++)
5181 region_copy[i]->flags &= ~BB_DUPLICATED;
5182 }
5183
5184 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5185 important exit edge EXIT. By important we mean that no SSA name defined
5186 inside region is live over the other exit edges of the region. All entry
5187 edges to the region must go to ENTRY->dest. The edge ENTRY is redirected
5188 to the duplicate of the region. SSA form, dominance and loop information
5189 is updated. The new basic blocks are stored to REGION_COPY in the same
5190 order as they had in REGION, provided that REGION_COPY is not NULL.
5191 The function returns false if it is unable to copy the region,
5192 true otherwise. */
5193
5194 bool
5195 gimple_duplicate_sese_region (edge entry, edge exit,
5196 basic_block *region, unsigned n_region,
5197 basic_block *region_copy)
5198 {
5199 unsigned i;
5200 bool free_region_copy = false, copying_header = false;
5201 struct loop *loop = entry->dest->loop_father;
5202 edge exit_copy;
5203 VEC (basic_block, heap) *doms;
5204 edge redirected;
5205 int total_freq = 0, entry_freq = 0;
5206 gcov_type total_count = 0, entry_count = 0;
5207
5208 if (!can_copy_bbs_p (region, n_region))
5209 return false;
5210
5211 /* Some sanity checking. Note that we do not check for all possible
5212 missuses of the functions. I.e. if you ask to copy something weird,
5213 it will work, but the state of structures probably will not be
5214 correct. */
5215 for (i = 0; i < n_region; i++)
5216 {
5217 /* We do not handle subloops, i.e. all the blocks must belong to the
5218 same loop. */
5219 if (region[i]->loop_father != loop)
5220 return false;
5221
5222 if (region[i] != entry->dest
5223 && region[i] == loop->header)
5224 return false;
5225 }
5226
5227 set_loop_copy (loop, loop);
5228
5229 /* In case the function is used for loop header copying (which is the primary
5230 use), ensure that EXIT and its copy will be new latch and entry edges. */
5231 if (loop->header == entry->dest)
5232 {
5233 copying_header = true;
5234 set_loop_copy (loop, loop_outer (loop));
5235
5236 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5237 return false;
5238
5239 for (i = 0; i < n_region; i++)
5240 if (region[i] != exit->src
5241 && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5242 return false;
5243 }
5244
5245 if (!region_copy)
5246 {
5247 region_copy = XNEWVEC (basic_block, n_region);
5248 free_region_copy = true;
5249 }
5250
5251 gcc_assert (!need_ssa_update_p (cfun));
5252
5253 /* Record blocks outside the region that are dominated by something
5254 inside. */
5255 doms = NULL;
5256 initialize_original_copy_tables ();
5257
5258 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5259
5260 if (entry->dest->count)
5261 {
5262 total_count = entry->dest->count;
5263 entry_count = entry->count;
5264 /* Fix up corner cases, to avoid division by zero or creation of negative
5265 frequencies. */
5266 if (entry_count > total_count)
5267 entry_count = total_count;
5268 }
5269 else
5270 {
5271 total_freq = entry->dest->frequency;
5272 entry_freq = EDGE_FREQUENCY (entry);
5273 /* Fix up corner cases, to avoid division by zero or creation of negative
5274 frequencies. */
5275 if (total_freq == 0)
5276 total_freq = 1;
5277 else if (entry_freq > total_freq)
5278 entry_freq = total_freq;
5279 }
5280
5281 copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5282 split_edge_bb_loc (entry));
5283 if (total_count)
5284 {
5285 scale_bbs_frequencies_gcov_type (region, n_region,
5286 total_count - entry_count,
5287 total_count);
5288 scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5289 total_count);
5290 }
5291 else
5292 {
5293 scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5294 total_freq);
5295 scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5296 }
5297
5298 if (copying_header)
5299 {
5300 loop->header = exit->dest;
5301 loop->latch = exit->src;
5302 }
5303
5304 /* Redirect the entry and add the phi node arguments. */
5305 redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5306 gcc_assert (redirected != NULL);
5307 flush_pending_stmts (entry);
5308
5309 /* Concerning updating of dominators: We must recount dominators
5310 for entry block and its copy. Anything that is outside of the
5311 region, but was dominated by something inside needs recounting as
5312 well. */
5313 set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5314 VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
5315 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5316 VEC_free (basic_block, heap, doms);
5317
5318 /* Add the other PHI node arguments. */
5319 add_phi_args_after_copy (region_copy, n_region, NULL);
5320
5321 /* Update the SSA web. */
5322 update_ssa (TODO_update_ssa);
5323
5324 if (free_region_copy)
5325 free (region_copy);
5326
5327 free_original_copy_tables ();
5328 return true;
5329 }
5330
5331 /* Duplicates REGION consisting of N_REGION blocks. The new blocks
5332 are stored to REGION_COPY in the same order in that they appear
5333 in REGION, if REGION_COPY is not NULL. ENTRY is the entry to
5334 the region, EXIT an exit from it. The condition guarding EXIT
5335 is moved to ENTRY. Returns true if duplication succeeds, false
5336 otherwise.
5337
5338 For example,
5339
5340 some_code;
5341 if (cond)
5342 A;
5343 else
5344 B;
5345
5346 is transformed to
5347
5348 if (cond)
5349 {
5350 some_code;
5351 A;
5352 }
5353 else
5354 {
5355 some_code;
5356 B;
5357 }
5358 */
5359
5360 bool
5361 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
5362 basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
5363 basic_block *region_copy ATTRIBUTE_UNUSED)
5364 {
5365 unsigned i;
5366 bool free_region_copy = false;
5367 struct loop *loop = exit->dest->loop_father;
5368 struct loop *orig_loop = entry->dest->loop_father;
5369 basic_block switch_bb, entry_bb, nentry_bb;
5370 VEC (basic_block, heap) *doms;
5371 int total_freq = 0, exit_freq = 0;
5372 gcov_type total_count = 0, exit_count = 0;
5373 edge exits[2], nexits[2], e;
5374 gimple_stmt_iterator gsi,gsi1;
5375 gimple cond_stmt;
5376 edge sorig, snew;
5377 basic_block exit_bb;
5378 basic_block iters_bb;
5379 tree new_rhs;
5380 gimple_stmt_iterator psi;
5381 gimple phi;
5382 tree def;
5383
5384 gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5385 exits[0] = exit;
5386 exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5387
5388 if (!can_copy_bbs_p (region, n_region))
5389 return false;
5390
5391 initialize_original_copy_tables ();
5392 set_loop_copy (orig_loop, loop);
5393 duplicate_subloops (orig_loop, loop);
5394
5395 if (!region_copy)
5396 {
5397 region_copy = XNEWVEC (basic_block, n_region);
5398 free_region_copy = true;
5399 }
5400
5401 gcc_assert (!need_ssa_update_p (cfun));
5402
5403 /* Record blocks outside the region that are dominated by something
5404 inside. */
5405 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5406
5407 if (exit->src->count)
5408 {
5409 total_count = exit->src->count;
5410 exit_count = exit->count;
5411 /* Fix up corner cases, to avoid division by zero or creation of negative
5412 frequencies. */
5413 if (exit_count > total_count)
5414 exit_count = total_count;
5415 }
5416 else
5417 {
5418 total_freq = exit->src->frequency;
5419 exit_freq = EDGE_FREQUENCY (exit);
5420 /* Fix up corner cases, to avoid division by zero or creation of negative
5421 frequencies. */
5422 if (total_freq == 0)
5423 total_freq = 1;
5424 if (exit_freq > total_freq)
5425 exit_freq = total_freq;
5426 }
5427
5428 copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5429 split_edge_bb_loc (exit));
5430 if (total_count)
5431 {
5432 scale_bbs_frequencies_gcov_type (region, n_region,
5433 total_count - exit_count,
5434 total_count);
5435 scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5436 total_count);
5437 }
5438 else
5439 {
5440 scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5441 total_freq);
5442 scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5443 }
5444
5445 /* Create the switch block, and put the exit condition to it. */
5446 entry_bb = entry->dest;
5447 nentry_bb = get_bb_copy (entry_bb);
5448 if (!last_stmt (entry->src)
5449 || !stmt_ends_bb_p (last_stmt (entry->src)))
5450 switch_bb = entry->src;
5451 else
5452 switch_bb = split_edge (entry);
5453 set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5454
5455 gsi = gsi_last_bb (switch_bb);
5456 cond_stmt = last_stmt (exit->src);
5457 gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
5458 cond_stmt = gimple_copy (cond_stmt);
5459
5460 /* If the block consisting of the exit condition has the latch as
5461 successor, then the body of the loop is executed before
5462 the exit condition is tested. In such case, moving the
5463 condition to the entry, causes that the loop will iterate
5464 one less iteration (which is the wanted outcome, since we
5465 peel out the last iteration). If the body is executed after
5466 the condition, moving the condition to the entry requires
5467 decrementing one iteration. */
5468 if (exits[1]->dest == orig_loop->latch)
5469 new_rhs = gimple_cond_rhs (cond_stmt);
5470 else
5471 {
5472 new_rhs = fold_build2 (MINUS_EXPR, TREE_TYPE (gimple_cond_rhs (cond_stmt)),
5473 gimple_cond_rhs (cond_stmt),
5474 build_int_cst (TREE_TYPE (gimple_cond_rhs (cond_stmt)), 1));
5475
5476 if (TREE_CODE (gimple_cond_rhs (cond_stmt)) == SSA_NAME)
5477 {
5478 iters_bb = gimple_bb (SSA_NAME_DEF_STMT (gimple_cond_rhs (cond_stmt)));
5479 for (gsi1 = gsi_start_bb (iters_bb); !gsi_end_p (gsi1); gsi_next (&gsi1))
5480 if (gsi_stmt (gsi1) == SSA_NAME_DEF_STMT (gimple_cond_rhs (cond_stmt)))
5481 break;
5482
5483 new_rhs = force_gimple_operand_gsi (&gsi1, new_rhs, true,
5484 NULL_TREE,false,GSI_CONTINUE_LINKING);
5485 }
5486 }
5487 gimple_cond_set_rhs (cond_stmt, unshare_expr (new_rhs));
5488 gimple_cond_set_lhs (cond_stmt, unshare_expr (gimple_cond_lhs (cond_stmt)));
5489 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
5490
5491 sorig = single_succ_edge (switch_bb);
5492 sorig->flags = exits[1]->flags;
5493 snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5494
5495 /* Register the new edge from SWITCH_BB in loop exit lists. */
5496 rescan_loop_exit (snew, true, false);
5497
5498 /* Add the PHI node arguments. */
5499 add_phi_args_after_copy (region_copy, n_region, snew);
5500
5501 /* Get rid of now superfluous conditions and associated edges (and phi node
5502 arguments). */
5503 exit_bb = exit->dest;
5504
5505 e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5506 PENDING_STMT (e) = NULL;
5507
5508 /* The latch of ORIG_LOOP was copied, and so was the backedge
5509 to the original header. We redirect this backedge to EXIT_BB. */
5510 for (i = 0; i < n_region; i++)
5511 if (get_bb_original (region_copy[i]) == orig_loop->latch)
5512 {
5513 gcc_assert (single_succ_edge (region_copy[i]));
5514 e = redirect_edge_and_branch (single_succ_edge (region_copy[i]), exit_bb);
5515 PENDING_STMT (e) = NULL;
5516 for (psi = gsi_start_phis (exit_bb);
5517 !gsi_end_p (psi);
5518 gsi_next (&psi))
5519 {
5520 phi = gsi_stmt (psi);
5521 def = PHI_ARG_DEF (phi, nexits[0]->dest_idx);
5522 add_phi_arg (phi, def, e, gimple_phi_arg_location_from_edge (phi, e));
5523 }
5524 }
5525 e = redirect_edge_and_branch (nexits[0], nexits[1]->dest);
5526 PENDING_STMT (e) = NULL;
5527
5528 /* Anything that is outside of the region, but was dominated by something
5529 inside needs to update dominance info. */
5530 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5531 VEC_free (basic_block, heap, doms);
5532 /* Update the SSA web. */
5533 update_ssa (TODO_update_ssa);
5534
5535 if (free_region_copy)
5536 free (region_copy);
5537
5538 free_original_copy_tables ();
5539 return true;
5540 }
5541
5542 /* Add all the blocks dominated by ENTRY to the array BBS_P. Stop
5543 adding blocks when the dominator traversal reaches EXIT. This
5544 function silently assumes that ENTRY strictly dominates EXIT. */
5545
5546 void
5547 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5548 VEC(basic_block,heap) **bbs_p)
5549 {
5550 basic_block son;
5551
5552 for (son = first_dom_son (CDI_DOMINATORS, entry);
5553 son;
5554 son = next_dom_son (CDI_DOMINATORS, son))
5555 {
5556 VEC_safe_push (basic_block, heap, *bbs_p, son);
5557 if (son != exit)
5558 gather_blocks_in_sese_region (son, exit, bbs_p);
5559 }
5560 }
5561
5562 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5563 The duplicates are recorded in VARS_MAP. */
5564
5565 static void
5566 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5567 tree to_context)
5568 {
5569 tree t = *tp, new_t;
5570 struct function *f = DECL_STRUCT_FUNCTION (to_context);
5571 void **loc;
5572
5573 if (DECL_CONTEXT (t) == to_context)
5574 return;
5575
5576 loc = pointer_map_contains (vars_map, t);
5577
5578 if (!loc)
5579 {
5580 loc = pointer_map_insert (vars_map, t);
5581
5582 if (SSA_VAR_P (t))
5583 {
5584 new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5585 add_local_decl (f, new_t);
5586 }
5587 else
5588 {
5589 gcc_assert (TREE_CODE (t) == CONST_DECL);
5590 new_t = copy_node (t);
5591 }
5592 DECL_CONTEXT (new_t) = to_context;
5593
5594 *loc = new_t;
5595 }
5596 else
5597 new_t = (tree) *loc;
5598
5599 *tp = new_t;
5600 }
5601
5602
5603 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5604 VARS_MAP maps old ssa names and var_decls to the new ones. */
5605
5606 static tree
5607 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5608 tree to_context)
5609 {
5610 void **loc;
5611 tree new_name, decl = SSA_NAME_VAR (name);
5612
5613 gcc_assert (is_gimple_reg (name));
5614
5615 loc = pointer_map_contains (vars_map, name);
5616
5617 if (!loc)
5618 {
5619 replace_by_duplicate_decl (&decl, vars_map, to_context);
5620
5621 push_cfun (DECL_STRUCT_FUNCTION (to_context));
5622 if (gimple_in_ssa_p (cfun))
5623 add_referenced_var (decl);
5624
5625 new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5626 if (SSA_NAME_IS_DEFAULT_DEF (name))
5627 set_default_def (decl, new_name);
5628 pop_cfun ();
5629
5630 loc = pointer_map_insert (vars_map, name);
5631 *loc = new_name;
5632 }
5633 else
5634 new_name = (tree) *loc;
5635
5636 return new_name;
5637 }
5638
5639 struct move_stmt_d
5640 {
5641 tree orig_block;
5642 tree new_block;
5643 tree from_context;
5644 tree to_context;
5645 struct pointer_map_t *vars_map;
5646 htab_t new_label_map;
5647 struct pointer_map_t *eh_map;
5648 bool remap_decls_p;
5649 };
5650
5651 /* Helper for move_block_to_fn. Set TREE_BLOCK in every expression
5652 contained in *TP if it has been ORIG_BLOCK previously and change the
5653 DECL_CONTEXT of every local variable referenced in *TP. */
5654
5655 static tree
5656 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
5657 {
5658 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
5659 struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5660 tree t = *tp;
5661
5662 if (EXPR_P (t))
5663 /* We should never have TREE_BLOCK set on non-statements. */
5664 gcc_assert (!TREE_BLOCK (t));
5665
5666 else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
5667 {
5668 if (TREE_CODE (t) == SSA_NAME)
5669 *tp = replace_ssa_name (t, p->vars_map, p->to_context);
5670 else if (TREE_CODE (t) == LABEL_DECL)
5671 {
5672 if (p->new_label_map)
5673 {
5674 struct tree_map in, *out;
5675 in.base.from = t;
5676 out = (struct tree_map *)
5677 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
5678 if (out)
5679 *tp = t = out->to;
5680 }
5681
5682 DECL_CONTEXT (t) = p->to_context;
5683 }
5684 else if (p->remap_decls_p)
5685 {
5686 /* Replace T with its duplicate. T should no longer appear in the
5687 parent function, so this looks wasteful; however, it may appear
5688 in referenced_vars, and more importantly, as virtual operands of
5689 statements, and in alias lists of other variables. It would be
5690 quite difficult to expunge it from all those places. ??? It might
5691 suffice to do this for addressable variables. */
5692 if ((TREE_CODE (t) == VAR_DECL
5693 && !is_global_var (t))
5694 || TREE_CODE (t) == CONST_DECL)
5695 replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
5696
5697 if (SSA_VAR_P (t)
5698 && gimple_in_ssa_p (cfun))
5699 {
5700 push_cfun (DECL_STRUCT_FUNCTION (p->to_context));
5701 add_referenced_var (*tp);
5702 pop_cfun ();
5703 }
5704 }
5705 *walk_subtrees = 0;
5706 }
5707 else if (TYPE_P (t))
5708 *walk_subtrees = 0;
5709
5710 return NULL_TREE;
5711 }
5712
5713 /* Helper for move_stmt_r. Given an EH region number for the source
5714 function, map that to the duplicate EH regio number in the dest. */
5715
5716 static int
5717 move_stmt_eh_region_nr (int old_nr, struct move_stmt_d *p)
5718 {
5719 eh_region old_r, new_r;
5720 void **slot;
5721
5722 old_r = get_eh_region_from_number (old_nr);
5723 slot = pointer_map_contains (p->eh_map, old_r);
5724 new_r = (eh_region) *slot;
5725
5726 return new_r->index;
5727 }
5728
5729 /* Similar, but operate on INTEGER_CSTs. */
5730
5731 static tree
5732 move_stmt_eh_region_tree_nr (tree old_t_nr, struct move_stmt_d *p)
5733 {
5734 int old_nr, new_nr;
5735
5736 old_nr = tree_low_cst (old_t_nr, 0);
5737 new_nr = move_stmt_eh_region_nr (old_nr, p);
5738
5739 return build_int_cst (NULL, new_nr);
5740 }
5741
5742 /* Like move_stmt_op, but for gimple statements.
5743
5744 Helper for move_block_to_fn. Set GIMPLE_BLOCK in every expression
5745 contained in the current statement in *GSI_P and change the
5746 DECL_CONTEXT of every local variable referenced in the current
5747 statement. */
5748
5749 static tree
5750 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
5751 struct walk_stmt_info *wi)
5752 {
5753 struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5754 gimple stmt = gsi_stmt (*gsi_p);
5755 tree block = gimple_block (stmt);
5756
5757 if (p->orig_block == NULL_TREE
5758 || block == p->orig_block
5759 || block == NULL_TREE)
5760 gimple_set_block (stmt, p->new_block);
5761 #ifdef ENABLE_CHECKING
5762 else if (block != p->new_block)
5763 {
5764 while (block && block != p->orig_block)
5765 block = BLOCK_SUPERCONTEXT (block);
5766 gcc_assert (block);
5767 }
5768 #endif
5769
5770 switch (gimple_code (stmt))
5771 {
5772 case GIMPLE_CALL:
5773 /* Remap the region numbers for __builtin_eh_{pointer,filter}. */
5774 {
5775 tree r, fndecl = gimple_call_fndecl (stmt);
5776 if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
5777 switch (DECL_FUNCTION_CODE (fndecl))
5778 {
5779 case BUILT_IN_EH_COPY_VALUES:
5780 r = gimple_call_arg (stmt, 1);
5781 r = move_stmt_eh_region_tree_nr (r, p);
5782 gimple_call_set_arg (stmt, 1, r);
5783 /* FALLTHRU */
5784
5785 case BUILT_IN_EH_POINTER:
5786 case BUILT_IN_EH_FILTER:
5787 r = gimple_call_arg (stmt, 0);
5788 r = move_stmt_eh_region_tree_nr (r, p);
5789 gimple_call_set_arg (stmt, 0, r);
5790 break;
5791
5792 default:
5793 break;
5794 }
5795 }
5796 break;
5797
5798 case GIMPLE_RESX:
5799 {
5800 int r = gimple_resx_region (stmt);
5801 r = move_stmt_eh_region_nr (r, p);
5802 gimple_resx_set_region (stmt, r);
5803 }
5804 break;
5805
5806 case GIMPLE_EH_DISPATCH:
5807 {
5808 int r = gimple_eh_dispatch_region (stmt);
5809 r = move_stmt_eh_region_nr (r, p);
5810 gimple_eh_dispatch_set_region (stmt, r);
5811 }
5812 break;
5813
5814 case GIMPLE_OMP_RETURN:
5815 case GIMPLE_OMP_CONTINUE:
5816 break;
5817 default:
5818 if (is_gimple_omp (stmt))
5819 {
5820 /* Do not remap variables inside OMP directives. Variables
5821 referenced in clauses and directive header belong to the
5822 parent function and should not be moved into the child
5823 function. */
5824 bool save_remap_decls_p = p->remap_decls_p;
5825 p->remap_decls_p = false;
5826 *handled_ops_p = true;
5827
5828 walk_gimple_seq (gimple_omp_body (stmt), move_stmt_r,
5829 move_stmt_op, wi);
5830
5831 p->remap_decls_p = save_remap_decls_p;
5832 }
5833 break;
5834 }
5835
5836 return NULL_TREE;
5837 }
5838
5839 /* Move basic block BB from function CFUN to function DEST_FN. The
5840 block is moved out of the original linked list and placed after
5841 block AFTER in the new list. Also, the block is removed from the
5842 original array of blocks and placed in DEST_FN's array of blocks.
5843 If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
5844 updated to reflect the moved edges.
5845
5846 The local variables are remapped to new instances, VARS_MAP is used
5847 to record the mapping. */
5848
5849 static void
5850 move_block_to_fn (struct function *dest_cfun, basic_block bb,
5851 basic_block after, bool update_edge_count_p,
5852 struct move_stmt_d *d)
5853 {
5854 struct control_flow_graph *cfg;
5855 edge_iterator ei;
5856 edge e;
5857 gimple_stmt_iterator si;
5858 unsigned old_len, new_len;
5859
5860 /* Remove BB from dominance structures. */
5861 delete_from_dominance_info (CDI_DOMINATORS, bb);
5862 if (current_loops)
5863 remove_bb_from_loops (bb);
5864
5865 /* Link BB to the new linked list. */
5866 move_block_after (bb, after);
5867
5868 /* Update the edge count in the corresponding flowgraphs. */
5869 if (update_edge_count_p)
5870 FOR_EACH_EDGE (e, ei, bb->succs)
5871 {
5872 cfun->cfg->x_n_edges--;
5873 dest_cfun->cfg->x_n_edges++;
5874 }
5875
5876 /* Remove BB from the original basic block array. */
5877 VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
5878 cfun->cfg->x_n_basic_blocks--;
5879
5880 /* Grow DEST_CFUN's basic block array if needed. */
5881 cfg = dest_cfun->cfg;
5882 cfg->x_n_basic_blocks++;
5883 if (bb->index >= cfg->x_last_basic_block)
5884 cfg->x_last_basic_block = bb->index + 1;
5885
5886 old_len = VEC_length (basic_block, cfg->x_basic_block_info);
5887 if ((unsigned) cfg->x_last_basic_block >= old_len)
5888 {
5889 new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
5890 VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
5891 new_len);
5892 }
5893
5894 VEC_replace (basic_block, cfg->x_basic_block_info,
5895 bb->index, bb);
5896
5897 /* Remap the variables in phi nodes. */
5898 for (si = gsi_start_phis (bb); !gsi_end_p (si); )
5899 {
5900 gimple phi = gsi_stmt (si);
5901 use_operand_p use;
5902 tree op = PHI_RESULT (phi);
5903 ssa_op_iter oi;
5904
5905 if (!is_gimple_reg (op))
5906 {
5907 /* Remove the phi nodes for virtual operands (alias analysis will be
5908 run for the new function, anyway). */
5909 remove_phi_node (&si, true);
5910 continue;
5911 }
5912
5913 SET_PHI_RESULT (phi,
5914 replace_ssa_name (op, d->vars_map, dest_cfun->decl));
5915 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
5916 {
5917 op = USE_FROM_PTR (use);
5918 if (TREE_CODE (op) == SSA_NAME)
5919 SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
5920 }
5921
5922 gsi_next (&si);
5923 }
5924
5925 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
5926 {
5927 gimple stmt = gsi_stmt (si);
5928 struct walk_stmt_info wi;
5929
5930 memset (&wi, 0, sizeof (wi));
5931 wi.info = d;
5932 walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
5933
5934 if (gimple_code (stmt) == GIMPLE_LABEL)
5935 {
5936 tree label = gimple_label_label (stmt);
5937 int uid = LABEL_DECL_UID (label);
5938
5939 gcc_assert (uid > -1);
5940
5941 old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
5942 if (old_len <= (unsigned) uid)
5943 {
5944 new_len = 3 * uid / 2 + 1;
5945 VEC_safe_grow_cleared (basic_block, gc,
5946 cfg->x_label_to_block_map, new_len);
5947 }
5948
5949 VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
5950 VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
5951
5952 gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
5953
5954 if (uid >= dest_cfun->cfg->last_label_uid)
5955 dest_cfun->cfg->last_label_uid = uid + 1;
5956 }
5957
5958 maybe_duplicate_eh_stmt_fn (dest_cfun, stmt, cfun, stmt, d->eh_map, 0);
5959 remove_stmt_from_eh_lp_fn (cfun, stmt);
5960
5961 gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
5962 gimple_remove_stmt_histograms (cfun, stmt);
5963
5964 /* We cannot leave any operands allocated from the operand caches of
5965 the current function. */
5966 free_stmt_operands (stmt);
5967 push_cfun (dest_cfun);
5968 update_stmt (stmt);
5969 pop_cfun ();
5970 }
5971
5972 FOR_EACH_EDGE (e, ei, bb->succs)
5973 if (e->goto_locus)
5974 {
5975 tree block = e->goto_block;
5976 if (d->orig_block == NULL_TREE
5977 || block == d->orig_block)
5978 e->goto_block = d->new_block;
5979 #ifdef ENABLE_CHECKING
5980 else if (block != d->new_block)
5981 {
5982 while (block && block != d->orig_block)
5983 block = BLOCK_SUPERCONTEXT (block);
5984 gcc_assert (block);
5985 }
5986 #endif
5987 }
5988 }
5989
5990 /* Examine the statements in BB (which is in SRC_CFUN); find and return
5991 the outermost EH region. Use REGION as the incoming base EH region. */
5992
5993 static eh_region
5994 find_outermost_region_in_block (struct function *src_cfun,
5995 basic_block bb, eh_region region)
5996 {
5997 gimple_stmt_iterator si;
5998
5999 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6000 {
6001 gimple stmt = gsi_stmt (si);
6002 eh_region stmt_region;
6003 int lp_nr;
6004
6005 lp_nr = lookup_stmt_eh_lp_fn (src_cfun, stmt);
6006 stmt_region = get_eh_region_from_lp_number_fn (src_cfun, lp_nr);
6007 if (stmt_region)
6008 {
6009 if (region == NULL)
6010 region = stmt_region;
6011 else if (stmt_region != region)
6012 {
6013 region = eh_region_outermost (src_cfun, stmt_region, region);
6014 gcc_assert (region != NULL);
6015 }
6016 }
6017 }
6018
6019 return region;
6020 }
6021
6022 static tree
6023 new_label_mapper (tree decl, void *data)
6024 {
6025 htab_t hash = (htab_t) data;
6026 struct tree_map *m;
6027 void **slot;
6028
6029 gcc_assert (TREE_CODE (decl) == LABEL_DECL);
6030
6031 m = XNEW (struct tree_map);
6032 m->hash = DECL_UID (decl);
6033 m->base.from = decl;
6034 m->to = create_artificial_label (UNKNOWN_LOCATION);
6035 LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
6036 if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
6037 cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
6038
6039 slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
6040 gcc_assert (*slot == NULL);
6041
6042 *slot = m;
6043
6044 return m->to;
6045 }
6046
6047 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
6048 subblocks. */
6049
6050 static void
6051 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map,
6052 tree to_context)
6053 {
6054 tree *tp, t;
6055
6056 for (tp = &BLOCK_VARS (block); *tp; tp = &DECL_CHAIN (*tp))
6057 {
6058 t = *tp;
6059 if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL)
6060 continue;
6061 replace_by_duplicate_decl (&t, vars_map, to_context);
6062 if (t != *tp)
6063 {
6064 if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
6065 {
6066 SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
6067 DECL_HAS_VALUE_EXPR_P (t) = 1;
6068 }
6069 DECL_CHAIN (t) = DECL_CHAIN (*tp);
6070 *tp = t;
6071 }
6072 }
6073
6074 for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
6075 replace_block_vars_by_duplicates (block, vars_map, to_context);
6076 }
6077
6078 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
6079 EXIT_BB to function DEST_CFUN. The whole region is replaced by a
6080 single basic block in the original CFG and the new basic block is
6081 returned. DEST_CFUN must not have a CFG yet.
6082
6083 Note that the region need not be a pure SESE region. Blocks inside
6084 the region may contain calls to abort/exit. The only restriction
6085 is that ENTRY_BB should be the only entry point and it must
6086 dominate EXIT_BB.
6087
6088 Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
6089 functions outermost BLOCK, move all subblocks of ORIG_BLOCK
6090 to the new function.
6091
6092 All local variables referenced in the region are assumed to be in
6093 the corresponding BLOCK_VARS and unexpanded variable lists
6094 associated with DEST_CFUN. */
6095
6096 basic_block
6097 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
6098 basic_block exit_bb, tree orig_block)
6099 {
6100 VEC(basic_block,heap) *bbs, *dom_bbs;
6101 basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
6102 basic_block after, bb, *entry_pred, *exit_succ, abb;
6103 struct function *saved_cfun = cfun;
6104 int *entry_flag, *exit_flag;
6105 unsigned *entry_prob, *exit_prob;
6106 unsigned i, num_entry_edges, num_exit_edges;
6107 edge e;
6108 edge_iterator ei;
6109 htab_t new_label_map;
6110 struct pointer_map_t *vars_map, *eh_map;
6111 struct loop *loop = entry_bb->loop_father;
6112 struct move_stmt_d d;
6113
6114 /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
6115 region. */
6116 gcc_assert (entry_bb != exit_bb
6117 && (!exit_bb
6118 || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
6119
6120 /* Collect all the blocks in the region. Manually add ENTRY_BB
6121 because it won't be added by dfs_enumerate_from. */
6122 bbs = NULL;
6123 VEC_safe_push (basic_block, heap, bbs, entry_bb);
6124 gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
6125
6126 /* The blocks that used to be dominated by something in BBS will now be
6127 dominated by the new block. */
6128 dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
6129 VEC_address (basic_block, bbs),
6130 VEC_length (basic_block, bbs));
6131
6132 /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG. We need to remember
6133 the predecessor edges to ENTRY_BB and the successor edges to
6134 EXIT_BB so that we can re-attach them to the new basic block that
6135 will replace the region. */
6136 num_entry_edges = EDGE_COUNT (entry_bb->preds);
6137 entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
6138 entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
6139 entry_prob = XNEWVEC (unsigned, num_entry_edges);
6140 i = 0;
6141 for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
6142 {
6143 entry_prob[i] = e->probability;
6144 entry_flag[i] = e->flags;
6145 entry_pred[i++] = e->src;
6146 remove_edge (e);
6147 }
6148
6149 if (exit_bb)
6150 {
6151 num_exit_edges = EDGE_COUNT (exit_bb->succs);
6152 exit_succ = (basic_block *) xcalloc (num_exit_edges,
6153 sizeof (basic_block));
6154 exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
6155 exit_prob = XNEWVEC (unsigned, num_exit_edges);
6156 i = 0;
6157 for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6158 {
6159 exit_prob[i] = e->probability;
6160 exit_flag[i] = e->flags;
6161 exit_succ[i++] = e->dest;
6162 remove_edge (e);
6163 }
6164 }
6165 else
6166 {
6167 num_exit_edges = 0;
6168 exit_succ = NULL;
6169 exit_flag = NULL;
6170 exit_prob = NULL;
6171 }
6172
6173 /* Switch context to the child function to initialize DEST_FN's CFG. */
6174 gcc_assert (dest_cfun->cfg == NULL);
6175 push_cfun (dest_cfun);
6176
6177 init_empty_tree_cfg ();
6178
6179 /* Initialize EH information for the new function. */
6180 eh_map = NULL;
6181 new_label_map = NULL;
6182 if (saved_cfun->eh)
6183 {
6184 eh_region region = NULL;
6185
6186 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
6187 region = find_outermost_region_in_block (saved_cfun, bb, region);
6188
6189 init_eh_for_function ();
6190 if (region != NULL)
6191 {
6192 new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6193 eh_map = duplicate_eh_regions (saved_cfun, region, 0,
6194 new_label_mapper, new_label_map);
6195 }
6196 }
6197
6198 pop_cfun ();
6199
6200 /* Move blocks from BBS into DEST_CFUN. */
6201 gcc_assert (VEC_length (basic_block, bbs) >= 2);
6202 after = dest_cfun->cfg->x_entry_block_ptr;
6203 vars_map = pointer_map_create ();
6204
6205 memset (&d, 0, sizeof (d));
6206 d.orig_block = orig_block;
6207 d.new_block = DECL_INITIAL (dest_cfun->decl);
6208 d.from_context = cfun->decl;
6209 d.to_context = dest_cfun->decl;
6210 d.vars_map = vars_map;
6211 d.new_label_map = new_label_map;
6212 d.eh_map = eh_map;
6213 d.remap_decls_p = true;
6214
6215 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
6216 {
6217 /* No need to update edge counts on the last block. It has
6218 already been updated earlier when we detached the region from
6219 the original CFG. */
6220 move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d);
6221 after = bb;
6222 }
6223
6224 /* Rewire BLOCK_SUBBLOCKS of orig_block. */
6225 if (orig_block)
6226 {
6227 tree block;
6228 gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6229 == NULL_TREE);
6230 BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6231 = BLOCK_SUBBLOCKS (orig_block);
6232 for (block = BLOCK_SUBBLOCKS (orig_block);
6233 block; block = BLOCK_CHAIN (block))
6234 BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
6235 BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
6236 }
6237
6238 replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
6239 vars_map, dest_cfun->decl);
6240
6241 if (new_label_map)
6242 htab_delete (new_label_map);
6243 if (eh_map)
6244 pointer_map_destroy (eh_map);
6245 pointer_map_destroy (vars_map);
6246
6247 /* Rewire the entry and exit blocks. The successor to the entry
6248 block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6249 the child function. Similarly, the predecessor of DEST_FN's
6250 EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR. We
6251 need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6252 various CFG manipulation function get to the right CFG.
6253
6254 FIXME, this is silly. The CFG ought to become a parameter to
6255 these helpers. */
6256 push_cfun (dest_cfun);
6257 make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6258 if (exit_bb)
6259 make_edge (exit_bb, EXIT_BLOCK_PTR, 0);
6260 pop_cfun ();
6261
6262 /* Back in the original function, the SESE region has disappeared,
6263 create a new basic block in its place. */
6264 bb = create_empty_bb (entry_pred[0]);
6265 if (current_loops)
6266 add_bb_to_loop (bb, loop);
6267 for (i = 0; i < num_entry_edges; i++)
6268 {
6269 e = make_edge (entry_pred[i], bb, entry_flag[i]);
6270 e->probability = entry_prob[i];
6271 }
6272
6273 for (i = 0; i < num_exit_edges; i++)
6274 {
6275 e = make_edge (bb, exit_succ[i], exit_flag[i]);
6276 e->probability = exit_prob[i];
6277 }
6278
6279 set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6280 FOR_EACH_VEC_ELT (basic_block, dom_bbs, i, abb)
6281 set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6282 VEC_free (basic_block, heap, dom_bbs);
6283
6284 if (exit_bb)
6285 {
6286 free (exit_prob);
6287 free (exit_flag);
6288 free (exit_succ);
6289 }
6290 free (entry_prob);
6291 free (entry_flag);
6292 free (entry_pred);
6293 VEC_free (basic_block, heap, bbs);
6294
6295 return bb;
6296 }
6297
6298
6299 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree-pass.h)
6300 */
6301
6302 void
6303 dump_function_to_file (tree fn, FILE *file, int flags)
6304 {
6305 tree arg, var;
6306 struct function *dsf;
6307 bool ignore_topmost_bind = false, any_var = false;
6308 basic_block bb;
6309 tree chain;
6310
6311 fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
6312
6313 arg = DECL_ARGUMENTS (fn);
6314 while (arg)
6315 {
6316 print_generic_expr (file, TREE_TYPE (arg), dump_flags);
6317 fprintf (file, " ");
6318 print_generic_expr (file, arg, dump_flags);
6319 if (flags & TDF_VERBOSE)
6320 print_node (file, "", arg, 4);
6321 if (DECL_CHAIN (arg))
6322 fprintf (file, ", ");
6323 arg = DECL_CHAIN (arg);
6324 }
6325 fprintf (file, ")\n");
6326
6327 if (flags & TDF_VERBOSE)
6328 print_node (file, "", fn, 2);
6329
6330 dsf = DECL_STRUCT_FUNCTION (fn);
6331 if (dsf && (flags & TDF_EH))
6332 dump_eh_tree (file, dsf);
6333
6334 if (flags & TDF_RAW && !gimple_has_body_p (fn))
6335 {
6336 dump_node (fn, TDF_SLIM | flags, file);
6337 return;
6338 }
6339
6340 /* Switch CFUN to point to FN. */
6341 push_cfun (DECL_STRUCT_FUNCTION (fn));
6342
6343 /* When GIMPLE is lowered, the variables are no longer available in
6344 BIND_EXPRs, so display them separately. */
6345 if (cfun && cfun->decl == fn && !VEC_empty (tree, cfun->local_decls))
6346 {
6347 unsigned ix;
6348 ignore_topmost_bind = true;
6349
6350 fprintf (file, "{\n");
6351 FOR_EACH_LOCAL_DECL (cfun, ix, var)
6352 {
6353 print_generic_decl (file, var, flags);
6354 if (flags & TDF_VERBOSE)
6355 print_node (file, "", var, 4);
6356 fprintf (file, "\n");
6357
6358 any_var = true;
6359 }
6360 }
6361
6362 if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
6363 {
6364 /* If the CFG has been built, emit a CFG-based dump. */
6365 check_bb_profile (ENTRY_BLOCK_PTR, file);
6366 if (!ignore_topmost_bind)
6367 fprintf (file, "{\n");
6368
6369 if (any_var && n_basic_blocks)
6370 fprintf (file, "\n");
6371
6372 FOR_EACH_BB (bb)
6373 gimple_dump_bb (bb, file, 2, flags);
6374
6375 fprintf (file, "}\n");
6376 check_bb_profile (EXIT_BLOCK_PTR, file);
6377 }
6378 else if (DECL_SAVED_TREE (fn) == NULL)
6379 {
6380 /* The function is now in GIMPLE form but the CFG has not been
6381 built yet. Emit the single sequence of GIMPLE statements
6382 that make up its body. */
6383 gimple_seq body = gimple_body (fn);
6384
6385 if (gimple_seq_first_stmt (body)
6386 && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
6387 && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
6388 print_gimple_seq (file, body, 0, flags);
6389 else
6390 {
6391 if (!ignore_topmost_bind)
6392 fprintf (file, "{\n");
6393
6394 if (any_var)
6395 fprintf (file, "\n");
6396
6397 print_gimple_seq (file, body, 2, flags);
6398 fprintf (file, "}\n");
6399 }
6400 }
6401 else
6402 {
6403 int indent;
6404
6405 /* Make a tree based dump. */
6406 chain = DECL_SAVED_TREE (fn);
6407
6408 if (chain && TREE_CODE (chain) == BIND_EXPR)
6409 {
6410 if (ignore_topmost_bind)
6411 {
6412 chain = BIND_EXPR_BODY (chain);
6413 indent = 2;
6414 }
6415 else
6416 indent = 0;
6417 }
6418 else
6419 {
6420 if (!ignore_topmost_bind)
6421 fprintf (file, "{\n");
6422 indent = 2;
6423 }
6424
6425 if (any_var)
6426 fprintf (file, "\n");
6427
6428 print_generic_stmt_indented (file, chain, flags, indent);
6429 if (ignore_topmost_bind)
6430 fprintf (file, "}\n");
6431 }
6432
6433 if (flags & TDF_ENUMERATE_LOCALS)
6434 dump_enumerated_decls (file, flags);
6435 fprintf (file, "\n\n");
6436
6437 /* Restore CFUN. */
6438 pop_cfun ();
6439 }
6440
6441
6442 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h) */
6443
6444 DEBUG_FUNCTION void
6445 debug_function (tree fn, int flags)
6446 {
6447 dump_function_to_file (fn, stderr, flags);
6448 }
6449
6450
6451 /* Print on FILE the indexes for the predecessors of basic_block BB. */
6452
6453 static void
6454 print_pred_bbs (FILE *file, basic_block bb)
6455 {
6456 edge e;
6457 edge_iterator ei;
6458
6459 FOR_EACH_EDGE (e, ei, bb->preds)
6460 fprintf (file, "bb_%d ", e->src->index);
6461 }
6462
6463
6464 /* Print on FILE the indexes for the successors of basic_block BB. */
6465
6466 static void
6467 print_succ_bbs (FILE *file, basic_block bb)
6468 {
6469 edge e;
6470 edge_iterator ei;
6471
6472 FOR_EACH_EDGE (e, ei, bb->succs)
6473 fprintf (file, "bb_%d ", e->dest->index);
6474 }
6475
6476 /* Print to FILE the basic block BB following the VERBOSITY level. */
6477
6478 void
6479 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6480 {
6481 char *s_indent = (char *) alloca ((size_t) indent + 1);
6482 memset ((void *) s_indent, ' ', (size_t) indent);
6483 s_indent[indent] = '\0';
6484
6485 /* Print basic_block's header. */
6486 if (verbosity >= 2)
6487 {
6488 fprintf (file, "%s bb_%d (preds = {", s_indent, bb->index);
6489 print_pred_bbs (file, bb);
6490 fprintf (file, "}, succs = {");
6491 print_succ_bbs (file, bb);
6492 fprintf (file, "})\n");
6493 }
6494
6495 /* Print basic_block's body. */
6496 if (verbosity >= 3)
6497 {
6498 fprintf (file, "%s {\n", s_indent);
6499 gimple_dump_bb (bb, file, indent + 4, TDF_VOPS|TDF_MEMSYMS);
6500 fprintf (file, "%s }\n", s_indent);
6501 }
6502 }
6503
6504 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6505
6506 /* Pretty print LOOP on FILE, indented INDENT spaces. Following
6507 VERBOSITY level this outputs the contents of the loop, or just its
6508 structure. */
6509
6510 static void
6511 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6512 {
6513 char *s_indent;
6514 basic_block bb;
6515
6516 if (loop == NULL)
6517 return;
6518
6519 s_indent = (char *) alloca ((size_t) indent + 1);
6520 memset ((void *) s_indent, ' ', (size_t) indent);
6521 s_indent[indent] = '\0';
6522
6523 /* Print loop's header. */
6524 fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent,
6525 loop->num, loop->header->index, loop->latch->index);
6526 fprintf (file, ", niter = ");
6527 print_generic_expr (file, loop->nb_iterations, 0);
6528
6529 if (loop->any_upper_bound)
6530 {
6531 fprintf (file, ", upper_bound = ");
6532 dump_double_int (file, loop->nb_iterations_upper_bound, true);
6533 }
6534
6535 if (loop->any_estimate)
6536 {
6537 fprintf (file, ", estimate = ");
6538 dump_double_int (file, loop->nb_iterations_estimate, true);
6539 }
6540 fprintf (file, ")\n");
6541
6542 /* Print loop's body. */
6543 if (verbosity >= 1)
6544 {
6545 fprintf (file, "%s{\n", s_indent);
6546 FOR_EACH_BB (bb)
6547 if (bb->loop_father == loop)
6548 print_loops_bb (file, bb, indent, verbosity);
6549
6550 print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
6551 fprintf (file, "%s}\n", s_indent);
6552 }
6553 }
6554
6555 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6556 spaces. Following VERBOSITY level this outputs the contents of the
6557 loop, or just its structure. */
6558
6559 static void
6560 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
6561 {
6562 if (loop == NULL)
6563 return;
6564
6565 print_loop (file, loop, indent, verbosity);
6566 print_loop_and_siblings (file, loop->next, indent, verbosity);
6567 }
6568
6569 /* Follow a CFG edge from the entry point of the program, and on entry
6570 of a loop, pretty print the loop structure on FILE. */
6571
6572 void
6573 print_loops (FILE *file, int verbosity)
6574 {
6575 basic_block bb;
6576
6577 bb = ENTRY_BLOCK_PTR;
6578 if (bb && bb->loop_father)
6579 print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
6580 }
6581
6582
6583 /* Debugging loops structure at tree level, at some VERBOSITY level. */
6584
6585 DEBUG_FUNCTION void
6586 debug_loops (int verbosity)
6587 {
6588 print_loops (stderr, verbosity);
6589 }
6590
6591 /* Print on stderr the code of LOOP, at some VERBOSITY level. */
6592
6593 DEBUG_FUNCTION void
6594 debug_loop (struct loop *loop, int verbosity)
6595 {
6596 print_loop (stderr, loop, 0, verbosity);
6597 }
6598
6599 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6600 level. */
6601
6602 DEBUG_FUNCTION void
6603 debug_loop_num (unsigned num, int verbosity)
6604 {
6605 debug_loop (get_loop (num), verbosity);
6606 }
6607
6608 /* Return true if BB ends with a call, possibly followed by some
6609 instructions that must stay with the call. Return false,
6610 otherwise. */
6611
6612 static bool
6613 gimple_block_ends_with_call_p (basic_block bb)
6614 {
6615 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
6616 return !gsi_end_p (gsi) && is_gimple_call (gsi_stmt (gsi));
6617 }
6618
6619
6620 /* Return true if BB ends with a conditional branch. Return false,
6621 otherwise. */
6622
6623 static bool
6624 gimple_block_ends_with_condjump_p (const_basic_block bb)
6625 {
6626 gimple stmt = last_stmt (CONST_CAST_BB (bb));
6627 return (stmt && gimple_code (stmt) == GIMPLE_COND);
6628 }
6629
6630
6631 /* Return true if we need to add fake edge to exit at statement T.
6632 Helper function for gimple_flow_call_edges_add. */
6633
6634 static bool
6635 need_fake_edge_p (gimple t)
6636 {
6637 tree fndecl = NULL_TREE;
6638 int call_flags = 0;
6639
6640 /* NORETURN and LONGJMP calls already have an edge to exit.
6641 CONST and PURE calls do not need one.
6642 We don't currently check for CONST and PURE here, although
6643 it would be a good idea, because those attributes are
6644 figured out from the RTL in mark_constant_function, and
6645 the counter incrementation code from -fprofile-arcs
6646 leads to different results from -fbranch-probabilities. */
6647 if (is_gimple_call (t))
6648 {
6649 fndecl = gimple_call_fndecl (t);
6650 call_flags = gimple_call_flags (t);
6651 }
6652
6653 if (is_gimple_call (t)
6654 && fndecl
6655 && DECL_BUILT_IN (fndecl)
6656 && (call_flags & ECF_NOTHROW)
6657 && !(call_flags & ECF_RETURNS_TWICE)
6658 /* fork() doesn't really return twice, but the effect of
6659 wrapping it in __gcov_fork() which calls __gcov_flush()
6660 and clears the counters before forking has the same
6661 effect as returning twice. Force a fake edge. */
6662 && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
6663 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK))
6664 return false;
6665
6666 if (is_gimple_call (t)
6667 && !(call_flags & ECF_NORETURN))
6668 return true;
6669
6670 if (gimple_code (t) == GIMPLE_ASM
6671 && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
6672 return true;
6673
6674 return false;
6675 }
6676
6677
6678 /* Add fake edges to the function exit for any non constant and non
6679 noreturn calls, volatile inline assembly in the bitmap of blocks
6680 specified by BLOCKS or to the whole CFG if BLOCKS is zero. Return
6681 the number of blocks that were split.
6682
6683 The goal is to expose cases in which entering a basic block does
6684 not imply that all subsequent instructions must be executed. */
6685
6686 static int
6687 gimple_flow_call_edges_add (sbitmap blocks)
6688 {
6689 int i;
6690 int blocks_split = 0;
6691 int last_bb = last_basic_block;
6692 bool check_last_block = false;
6693
6694 if (n_basic_blocks == NUM_FIXED_BLOCKS)
6695 return 0;
6696
6697 if (! blocks)
6698 check_last_block = true;
6699 else
6700 check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
6701
6702 /* In the last basic block, before epilogue generation, there will be
6703 a fallthru edge to EXIT. Special care is required if the last insn
6704 of the last basic block is a call because make_edge folds duplicate
6705 edges, which would result in the fallthru edge also being marked
6706 fake, which would result in the fallthru edge being removed by
6707 remove_fake_edges, which would result in an invalid CFG.
6708
6709 Moreover, we can't elide the outgoing fake edge, since the block
6710 profiler needs to take this into account in order to solve the minimal
6711 spanning tree in the case that the call doesn't return.
6712
6713 Handle this by adding a dummy instruction in a new last basic block. */
6714 if (check_last_block)
6715 {
6716 basic_block bb = EXIT_BLOCK_PTR->prev_bb;
6717 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
6718 gimple t = NULL;
6719
6720 if (!gsi_end_p (gsi))
6721 t = gsi_stmt (gsi);
6722
6723 if (t && need_fake_edge_p (t))
6724 {
6725 edge e;
6726
6727 e = find_edge (bb, EXIT_BLOCK_PTR);
6728 if (e)
6729 {
6730 gsi_insert_on_edge (e, gimple_build_nop ());
6731 gsi_commit_edge_inserts ();
6732 }
6733 }
6734 }
6735
6736 /* Now add fake edges to the function exit for any non constant
6737 calls since there is no way that we can determine if they will
6738 return or not... */
6739 for (i = 0; i < last_bb; i++)
6740 {
6741 basic_block bb = BASIC_BLOCK (i);
6742 gimple_stmt_iterator gsi;
6743 gimple stmt, last_stmt;
6744
6745 if (!bb)
6746 continue;
6747
6748 if (blocks && !TEST_BIT (blocks, i))
6749 continue;
6750
6751 gsi = gsi_last_nondebug_bb (bb);
6752 if (!gsi_end_p (gsi))
6753 {
6754 last_stmt = gsi_stmt (gsi);
6755 do
6756 {
6757 stmt = gsi_stmt (gsi);
6758 if (need_fake_edge_p (stmt))
6759 {
6760 edge e;
6761
6762 /* The handling above of the final block before the
6763 epilogue should be enough to verify that there is
6764 no edge to the exit block in CFG already.
6765 Calling make_edge in such case would cause us to
6766 mark that edge as fake and remove it later. */
6767 #ifdef ENABLE_CHECKING
6768 if (stmt == last_stmt)
6769 {
6770 e = find_edge (bb, EXIT_BLOCK_PTR);
6771 gcc_assert (e == NULL);
6772 }
6773 #endif
6774
6775 /* Note that the following may create a new basic block
6776 and renumber the existing basic blocks. */
6777 if (stmt != last_stmt)
6778 {
6779 e = split_block (bb, stmt);
6780 if (e)
6781 blocks_split++;
6782 }
6783 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
6784 }
6785 gsi_prev (&gsi);
6786 }
6787 while (!gsi_end_p (gsi));
6788 }
6789 }
6790
6791 if (blocks_split)
6792 verify_flow_info ();
6793
6794 return blocks_split;
6795 }
6796
6797 /* Removes edge E and all the blocks dominated by it, and updates dominance
6798 information. The IL in E->src needs to be updated separately.
6799 If dominance info is not available, only the edge E is removed.*/
6800
6801 void
6802 remove_edge_and_dominated_blocks (edge e)
6803 {
6804 VEC (basic_block, heap) *bbs_to_remove = NULL;
6805 VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
6806 bitmap df, df_idom;
6807 edge f;
6808 edge_iterator ei;
6809 bool none_removed = false;
6810 unsigned i;
6811 basic_block bb, dbb;
6812 bitmap_iterator bi;
6813
6814 if (!dom_info_available_p (CDI_DOMINATORS))
6815 {
6816 remove_edge (e);
6817 return;
6818 }
6819
6820 /* No updating is needed for edges to exit. */
6821 if (e->dest == EXIT_BLOCK_PTR)
6822 {
6823 if (cfgcleanup_altered_bbs)
6824 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6825 remove_edge (e);
6826 return;
6827 }
6828
6829 /* First, we find the basic blocks to remove. If E->dest has a predecessor
6830 that is not dominated by E->dest, then this set is empty. Otherwise,
6831 all the basic blocks dominated by E->dest are removed.
6832
6833 Also, to DF_IDOM we store the immediate dominators of the blocks in
6834 the dominance frontier of E (i.e., of the successors of the
6835 removed blocks, if there are any, and of E->dest otherwise). */
6836 FOR_EACH_EDGE (f, ei, e->dest->preds)
6837 {
6838 if (f == e)
6839 continue;
6840
6841 if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
6842 {
6843 none_removed = true;
6844 break;
6845 }
6846 }
6847
6848 df = BITMAP_ALLOC (NULL);
6849 df_idom = BITMAP_ALLOC (NULL);
6850
6851 if (none_removed)
6852 bitmap_set_bit (df_idom,
6853 get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
6854 else
6855 {
6856 bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest);
6857 FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb)
6858 {
6859 FOR_EACH_EDGE (f, ei, bb->succs)
6860 {
6861 if (f->dest != EXIT_BLOCK_PTR)
6862 bitmap_set_bit (df, f->dest->index);
6863 }
6864 }
6865 FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb)
6866 bitmap_clear_bit (df, bb->index);
6867
6868 EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
6869 {
6870 bb = BASIC_BLOCK (i);
6871 bitmap_set_bit (df_idom,
6872 get_immediate_dominator (CDI_DOMINATORS, bb)->index);
6873 }
6874 }
6875
6876 if (cfgcleanup_altered_bbs)
6877 {
6878 /* Record the set of the altered basic blocks. */
6879 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6880 bitmap_ior_into (cfgcleanup_altered_bbs, df);
6881 }
6882
6883 /* Remove E and the cancelled blocks. */
6884 if (none_removed)
6885 remove_edge (e);
6886 else
6887 {
6888 /* Walk backwards so as to get a chance to substitute all
6889 released DEFs into debug stmts. See
6890 eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
6891 details. */
6892 for (i = VEC_length (basic_block, bbs_to_remove); i-- > 0; )
6893 delete_basic_block (VEC_index (basic_block, bbs_to_remove, i));
6894 }
6895
6896 /* Update the dominance information. The immediate dominator may change only
6897 for blocks whose immediate dominator belongs to DF_IDOM:
6898
6899 Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
6900 removal. Let Z the arbitrary block such that idom(Z) = Y and
6901 Z dominates X after the removal. Before removal, there exists a path P
6902 from Y to X that avoids Z. Let F be the last edge on P that is
6903 removed, and let W = F->dest. Before removal, idom(W) = Y (since Y
6904 dominates W, and because of P, Z does not dominate W), and W belongs to
6905 the dominance frontier of E. Therefore, Y belongs to DF_IDOM. */
6906 EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
6907 {
6908 bb = BASIC_BLOCK (i);
6909 for (dbb = first_dom_son (CDI_DOMINATORS, bb);
6910 dbb;
6911 dbb = next_dom_son (CDI_DOMINATORS, dbb))
6912 VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
6913 }
6914
6915 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
6916
6917 BITMAP_FREE (df);
6918 BITMAP_FREE (df_idom);
6919 VEC_free (basic_block, heap, bbs_to_remove);
6920 VEC_free (basic_block, heap, bbs_to_fix_dom);
6921 }
6922
6923 /* Purge dead EH edges from basic block BB. */
6924
6925 bool
6926 gimple_purge_dead_eh_edges (basic_block bb)
6927 {
6928 bool changed = false;
6929 edge e;
6930 edge_iterator ei;
6931 gimple stmt = last_stmt (bb);
6932
6933 if (stmt && stmt_can_throw_internal (stmt))
6934 return false;
6935
6936 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6937 {
6938 if (e->flags & EDGE_EH)
6939 {
6940 remove_edge_and_dominated_blocks (e);
6941 changed = true;
6942 }
6943 else
6944 ei_next (&ei);
6945 }
6946
6947 return changed;
6948 }
6949
6950 /* Purge dead EH edges from basic block listed in BLOCKS. */
6951
6952 bool
6953 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
6954 {
6955 bool changed = false;
6956 unsigned i;
6957 bitmap_iterator bi;
6958
6959 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
6960 {
6961 basic_block bb = BASIC_BLOCK (i);
6962
6963 /* Earlier gimple_purge_dead_eh_edges could have removed
6964 this basic block already. */
6965 gcc_assert (bb || changed);
6966 if (bb != NULL)
6967 changed |= gimple_purge_dead_eh_edges (bb);
6968 }
6969
6970 return changed;
6971 }
6972
6973 /* Purge dead abnormal call edges from basic block BB. */
6974
6975 bool
6976 gimple_purge_dead_abnormal_call_edges (basic_block bb)
6977 {
6978 bool changed = false;
6979 edge e;
6980 edge_iterator ei;
6981 gimple stmt = last_stmt (bb);
6982
6983 if (!cfun->has_nonlocal_label)
6984 return false;
6985
6986 if (stmt && stmt_can_make_abnormal_goto (stmt))
6987 return false;
6988
6989 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6990 {
6991 if (e->flags & EDGE_ABNORMAL)
6992 {
6993 remove_edge_and_dominated_blocks (e);
6994 changed = true;
6995 }
6996 else
6997 ei_next (&ei);
6998 }
6999
7000 return changed;
7001 }
7002
7003 /* Purge dead abnormal call edges from basic block listed in BLOCKS. */
7004
7005 bool
7006 gimple_purge_all_dead_abnormal_call_edges (const_bitmap blocks)
7007 {
7008 bool changed = false;
7009 unsigned i;
7010 bitmap_iterator bi;
7011
7012 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7013 {
7014 basic_block bb = BASIC_BLOCK (i);
7015
7016 /* Earlier gimple_purge_dead_abnormal_call_edges could have removed
7017 this basic block already. */
7018 gcc_assert (bb || changed);
7019 if (bb != NULL)
7020 changed |= gimple_purge_dead_abnormal_call_edges (bb);
7021 }
7022
7023 return changed;
7024 }
7025
7026 /* This function is called whenever a new edge is created or
7027 redirected. */
7028
7029 static void
7030 gimple_execute_on_growing_pred (edge e)
7031 {
7032 basic_block bb = e->dest;
7033
7034 if (!gimple_seq_empty_p (phi_nodes (bb)))
7035 reserve_phi_args_for_new_edge (bb);
7036 }
7037
7038 /* This function is called immediately before edge E is removed from
7039 the edge vector E->dest->preds. */
7040
7041 static void
7042 gimple_execute_on_shrinking_pred (edge e)
7043 {
7044 if (!gimple_seq_empty_p (phi_nodes (e->dest)))
7045 remove_phi_args (e);
7046 }
7047
7048 /*---------------------------------------------------------------------------
7049 Helper functions for Loop versioning
7050 ---------------------------------------------------------------------------*/
7051
7052 /* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy
7053 of 'first'. Both of them are dominated by 'new_head' basic block. When
7054 'new_head' was created by 'second's incoming edge it received phi arguments
7055 on the edge by split_edge(). Later, additional edge 'e' was created to
7056 connect 'new_head' and 'first'. Now this routine adds phi args on this
7057 additional edge 'e' that new_head to second edge received as part of edge
7058 splitting. */
7059
7060 static void
7061 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
7062 basic_block new_head, edge e)
7063 {
7064 gimple phi1, phi2;
7065 gimple_stmt_iterator psi1, psi2;
7066 tree def;
7067 edge e2 = find_edge (new_head, second);
7068
7069 /* Because NEW_HEAD has been created by splitting SECOND's incoming
7070 edge, we should always have an edge from NEW_HEAD to SECOND. */
7071 gcc_assert (e2 != NULL);
7072
7073 /* Browse all 'second' basic block phi nodes and add phi args to
7074 edge 'e' for 'first' head. PHI args are always in correct order. */
7075
7076 for (psi2 = gsi_start_phis (second),
7077 psi1 = gsi_start_phis (first);
7078 !gsi_end_p (psi2) && !gsi_end_p (psi1);
7079 gsi_next (&psi2), gsi_next (&psi1))
7080 {
7081 phi1 = gsi_stmt (psi1);
7082 phi2 = gsi_stmt (psi2);
7083 def = PHI_ARG_DEF (phi2, e2->dest_idx);
7084 add_phi_arg (phi1, def, e, gimple_phi_arg_location_from_edge (phi2, e2));
7085 }
7086 }
7087
7088
7089 /* Adds a if else statement to COND_BB with condition COND_EXPR.
7090 SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
7091 the destination of the ELSE part. */
7092
7093 static void
7094 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
7095 basic_block second_head ATTRIBUTE_UNUSED,
7096 basic_block cond_bb, void *cond_e)
7097 {
7098 gimple_stmt_iterator gsi;
7099 gimple new_cond_expr;
7100 tree cond_expr = (tree) cond_e;
7101 edge e0;
7102
7103 /* Build new conditional expr */
7104 new_cond_expr = gimple_build_cond_from_tree (cond_expr,
7105 NULL_TREE, NULL_TREE);
7106
7107 /* Add new cond in cond_bb. */
7108 gsi = gsi_last_bb (cond_bb);
7109 gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
7110
7111 /* Adjust edges appropriately to connect new head with first head
7112 as well as second head. */
7113 e0 = single_succ_edge (cond_bb);
7114 e0->flags &= ~EDGE_FALLTHRU;
7115 e0->flags |= EDGE_FALSE_VALUE;
7116 }
7117
7118 struct cfg_hooks gimple_cfg_hooks = {
7119 "gimple",
7120 gimple_verify_flow_info,
7121 gimple_dump_bb, /* dump_bb */
7122 create_bb, /* create_basic_block */
7123 gimple_redirect_edge_and_branch, /* redirect_edge_and_branch */
7124 gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force */
7125 gimple_can_remove_branch_p, /* can_remove_branch_p */
7126 remove_bb, /* delete_basic_block */
7127 gimple_split_block, /* split_block */
7128 gimple_move_block_after, /* move_block_after */
7129 gimple_can_merge_blocks_p, /* can_merge_blocks_p */
7130 gimple_merge_blocks, /* merge_blocks */
7131 gimple_predict_edge, /* predict_edge */
7132 gimple_predicted_by_p, /* predicted_by_p */
7133 gimple_can_duplicate_bb_p, /* can_duplicate_block_p */
7134 gimple_duplicate_bb, /* duplicate_block */
7135 gimple_split_edge, /* split_edge */
7136 gimple_make_forwarder_block, /* make_forward_block */
7137 NULL, /* tidy_fallthru_edge */
7138 gimple_block_ends_with_call_p,/* block_ends_with_call_p */
7139 gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
7140 gimple_flow_call_edges_add, /* flow_call_edges_add */
7141 gimple_execute_on_growing_pred, /* execute_on_growing_pred */
7142 gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
7143 gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
7144 gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
7145 gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
7146 extract_true_false_edges_from_block, /* extract_cond_bb_edges */
7147 flush_pending_stmts /* flush_pending_stmts */
7148 };
7149
7150
7151 /* Split all critical edges. */
7152
7153 static unsigned int
7154 split_critical_edges (void)
7155 {
7156 basic_block bb;
7157 edge e;
7158 edge_iterator ei;
7159
7160 /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
7161 expensive. So we want to enable recording of edge to CASE_LABEL_EXPR
7162 mappings around the calls to split_edge. */
7163 start_recording_case_labels ();
7164 FOR_ALL_BB (bb)
7165 {
7166 FOR_EACH_EDGE (e, ei, bb->succs)
7167 {
7168 if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
7169 split_edge (e);
7170 /* PRE inserts statements to edges and expects that
7171 since split_critical_edges was done beforehand, committing edge
7172 insertions will not split more edges. In addition to critical
7173 edges we must split edges that have multiple successors and
7174 end by control flow statements, such as RESX.
7175 Go ahead and split them too. This matches the logic in
7176 gimple_find_edge_insert_loc. */
7177 else if ((!single_pred_p (e->dest)
7178 || !gimple_seq_empty_p (phi_nodes (e->dest))
7179 || e->dest == EXIT_BLOCK_PTR)
7180 && e->src != ENTRY_BLOCK_PTR
7181 && !(e->flags & EDGE_ABNORMAL))
7182 {
7183 gimple_stmt_iterator gsi;
7184
7185 gsi = gsi_last_bb (e->src);
7186 if (!gsi_end_p (gsi)
7187 && stmt_ends_bb_p (gsi_stmt (gsi))
7188 && (gimple_code (gsi_stmt (gsi)) != GIMPLE_RETURN
7189 && !gimple_call_builtin_p (gsi_stmt (gsi),
7190 BUILT_IN_RETURN)))
7191 split_edge (e);
7192 }
7193 }
7194 }
7195 end_recording_case_labels ();
7196 return 0;
7197 }
7198
7199 struct gimple_opt_pass pass_split_crit_edges =
7200 {
7201 {
7202 GIMPLE_PASS,
7203 "crited", /* name */
7204 NULL, /* gate */
7205 split_critical_edges, /* execute */
7206 NULL, /* sub */
7207 NULL, /* next */
7208 0, /* static_pass_number */
7209 TV_TREE_SPLIT_EDGES, /* tv_id */
7210 PROP_cfg, /* properties required */
7211 PROP_no_crit_edges, /* properties_provided */
7212 0, /* properties_destroyed */
7213 0, /* todo_flags_start */
7214 TODO_dump_func | TODO_verify_flow /* todo_flags_finish */
7215 }
7216 };
7217
7218
7219 /* Build a ternary operation and gimplify it. Emit code before GSI.
7220 Return the gimple_val holding the result. */
7221
7222 tree
7223 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
7224 tree type, tree a, tree b, tree c)
7225 {
7226 tree ret;
7227 location_t loc = gimple_location (gsi_stmt (*gsi));
7228
7229 ret = fold_build3_loc (loc, code, type, a, b, c);
7230 STRIP_NOPS (ret);
7231
7232 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7233 GSI_SAME_STMT);
7234 }
7235
7236 /* Build a binary operation and gimplify it. Emit code before GSI.
7237 Return the gimple_val holding the result. */
7238
7239 tree
7240 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
7241 tree type, tree a, tree b)
7242 {
7243 tree ret;
7244
7245 ret = fold_build2_loc (gimple_location (gsi_stmt (*gsi)), code, type, a, b);
7246 STRIP_NOPS (ret);
7247
7248 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7249 GSI_SAME_STMT);
7250 }
7251
7252 /* Build a unary operation and gimplify it. Emit code before GSI.
7253 Return the gimple_val holding the result. */
7254
7255 tree
7256 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
7257 tree a)
7258 {
7259 tree ret;
7260
7261 ret = fold_build1_loc (gimple_location (gsi_stmt (*gsi)), code, type, a);
7262 STRIP_NOPS (ret);
7263
7264 return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7265 GSI_SAME_STMT);
7266 }
7267
7268
7269 \f
7270 /* Emit return warnings. */
7271
7272 static unsigned int
7273 execute_warn_function_return (void)
7274 {
7275 source_location location;
7276 gimple last;
7277 edge e;
7278 edge_iterator ei;
7279
7280 /* If we have a path to EXIT, then we do return. */
7281 if (TREE_THIS_VOLATILE (cfun->decl)
7282 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
7283 {
7284 location = UNKNOWN_LOCATION;
7285 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7286 {
7287 last = last_stmt (e->src);
7288 if ((gimple_code (last) == GIMPLE_RETURN
7289 || gimple_call_builtin_p (last, BUILT_IN_RETURN))
7290 && (location = gimple_location (last)) != UNKNOWN_LOCATION)
7291 break;
7292 }
7293 if (location == UNKNOWN_LOCATION)
7294 location = cfun->function_end_locus;
7295 warning_at (location, 0, "%<noreturn%> function does return");
7296 }
7297
7298 /* If we see "return;" in some basic block, then we do reach the end
7299 without returning a value. */
7300 else if (warn_return_type
7301 && !TREE_NO_WARNING (cfun->decl)
7302 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
7303 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
7304 {
7305 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7306 {
7307 gimple last = last_stmt (e->src);
7308 if (gimple_code (last) == GIMPLE_RETURN
7309 && gimple_return_retval (last) == NULL
7310 && !gimple_no_warning_p (last))
7311 {
7312 location = gimple_location (last);
7313 if (location == UNKNOWN_LOCATION)
7314 location = cfun->function_end_locus;
7315 warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
7316 TREE_NO_WARNING (cfun->decl) = 1;
7317 break;
7318 }
7319 }
7320 }
7321 return 0;
7322 }
7323
7324
7325 /* Given a basic block B which ends with a conditional and has
7326 precisely two successors, determine which of the edges is taken if
7327 the conditional is true and which is taken if the conditional is
7328 false. Set TRUE_EDGE and FALSE_EDGE appropriately. */
7329
7330 void
7331 extract_true_false_edges_from_block (basic_block b,
7332 edge *true_edge,
7333 edge *false_edge)
7334 {
7335 edge e = EDGE_SUCC (b, 0);
7336
7337 if (e->flags & EDGE_TRUE_VALUE)
7338 {
7339 *true_edge = e;
7340 *false_edge = EDGE_SUCC (b, 1);
7341 }
7342 else
7343 {
7344 *false_edge = e;
7345 *true_edge = EDGE_SUCC (b, 1);
7346 }
7347 }
7348
7349 struct gimple_opt_pass pass_warn_function_return =
7350 {
7351 {
7352 GIMPLE_PASS,
7353 "*warn_function_return", /* name */
7354 NULL, /* gate */
7355 execute_warn_function_return, /* execute */
7356 NULL, /* sub */
7357 NULL, /* next */
7358 0, /* static_pass_number */
7359 TV_NONE, /* tv_id */
7360 PROP_cfg, /* properties_required */
7361 0, /* properties_provided */
7362 0, /* properties_destroyed */
7363 0, /* todo_flags_start */
7364 0 /* todo_flags_finish */
7365 }
7366 };
7367
7368 /* Emit noreturn warnings. */
7369
7370 static unsigned int
7371 execute_warn_function_noreturn (void)
7372 {
7373 if (!TREE_THIS_VOLATILE (current_function_decl)
7374 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0)
7375 warn_function_noreturn (current_function_decl);
7376 return 0;
7377 }
7378
7379 static bool
7380 gate_warn_function_noreturn (void)
7381 {
7382 return warn_suggest_attribute_noreturn;
7383 }
7384
7385 struct gimple_opt_pass pass_warn_function_noreturn =
7386 {
7387 {
7388 GIMPLE_PASS,
7389 "*warn_function_noreturn", /* name */
7390 gate_warn_function_noreturn, /* gate */
7391 execute_warn_function_noreturn, /* execute */
7392 NULL, /* sub */
7393 NULL, /* next */
7394 0, /* static_pass_number */
7395 TV_NONE, /* tv_id */
7396 PROP_cfg, /* properties_required */
7397 0, /* properties_provided */
7398 0, /* properties_destroyed */
7399 0, /* todo_flags_start */
7400 0 /* todo_flags_finish */
7401 }
7402 };
7403
7404
7405 /* Walk a gimplified function and warn for functions whose return value is
7406 ignored and attribute((warn_unused_result)) is set. This is done before
7407 inlining, so we don't have to worry about that. */
7408
7409 static void
7410 do_warn_unused_result (gimple_seq seq)
7411 {
7412 tree fdecl, ftype;
7413 gimple_stmt_iterator i;
7414
7415 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
7416 {
7417 gimple g = gsi_stmt (i);
7418
7419 switch (gimple_code (g))
7420 {
7421 case GIMPLE_BIND:
7422 do_warn_unused_result (gimple_bind_body (g));
7423 break;
7424 case GIMPLE_TRY:
7425 do_warn_unused_result (gimple_try_eval (g));
7426 do_warn_unused_result (gimple_try_cleanup (g));
7427 break;
7428 case GIMPLE_CATCH:
7429 do_warn_unused_result (gimple_catch_handler (g));
7430 break;
7431 case GIMPLE_EH_FILTER:
7432 do_warn_unused_result (gimple_eh_filter_failure (g));
7433 break;
7434
7435 case GIMPLE_CALL:
7436 if (gimple_call_lhs (g))
7437 break;
7438
7439 /* This is a naked call, as opposed to a GIMPLE_CALL with an
7440 LHS. All calls whose value is ignored should be
7441 represented like this. Look for the attribute. */
7442 fdecl = gimple_call_fndecl (g);
7443 ftype = TREE_TYPE (TREE_TYPE (gimple_call_fn (g)));
7444
7445 if (lookup_attribute ("warn_unused_result", TYPE_ATTRIBUTES (ftype)))
7446 {
7447 location_t loc = gimple_location (g);
7448
7449 if (fdecl)
7450 warning_at (loc, OPT_Wunused_result,
7451 "ignoring return value of %qD, "
7452 "declared with attribute warn_unused_result",
7453 fdecl);
7454 else
7455 warning_at (loc, OPT_Wunused_result,
7456 "ignoring return value of function "
7457 "declared with attribute warn_unused_result");
7458 }
7459 break;
7460
7461 default:
7462 /* Not a container, not a call, or a call whose value is used. */
7463 break;
7464 }
7465 }
7466 }
7467
7468 static unsigned int
7469 run_warn_unused_result (void)
7470 {
7471 do_warn_unused_result (gimple_body (current_function_decl));
7472 return 0;
7473 }
7474
7475 static bool
7476 gate_warn_unused_result (void)
7477 {
7478 return flag_warn_unused_result;
7479 }
7480
7481 struct gimple_opt_pass pass_warn_unused_result =
7482 {
7483 {
7484 GIMPLE_PASS,
7485 "*warn_unused_result", /* name */
7486 gate_warn_unused_result, /* gate */
7487 run_warn_unused_result, /* execute */
7488 NULL, /* sub */
7489 NULL, /* next */
7490 0, /* static_pass_number */
7491 TV_NONE, /* tv_id */
7492 PROP_gimple_any, /* properties_required */
7493 0, /* properties_provided */
7494 0, /* properties_destroyed */
7495 0, /* todo_flags_start */
7496 0, /* todo_flags_finish */
7497 }
7498 };
7499