gcc/tree-cfg.c

   1 /* Control flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "hard-reg-set.h"
  30 #include "basic-block.h"
  31 #include "output.h"
  32 #include "errors.h"
  33 #include "flags.h"
  34 #include "function.h"
  35 #include "expr.h"
  36 #include "ggc.h"
  37 #include "langhooks.h"
  38 #include "diagnostic.h"
  39 #include "tree-flow.h"
  40 #include "timevar.h"
  41 #include "tree-dump.h"
  42 #include "tree-pass.h"
  43 #include "toplev.h"
  44 #include "except.h"
  45 #include "cfgloop.h"
  46 #include "cfglayout.h"
  47 #include "hashtab.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 /* Mapping of labels to their associated blocks.  This can greatly speed up
  58    building of the CFG in code with lots of gotos.  */
  59 static GTY(()) varray_type label_to_block_map;
  60
  61 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
  62    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
  63    via their TREE_CHAIN field, which we clear after we're done with the
  64    hash table to prevent problems with duplication of SWITCH_EXPRs.
  65
  66    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
  67    update the case vector in response to edge redirections.
  68
  69    Right now this table is set up and torn down at key points in the
  70    compilation process.  It would be nice if we could make the table
  71    more persistent.  The key is getting notification of changes to
  72    the CFG (particularly edge removal, creation and redirection).  */
  73
  74 struct edge_to_cases_elt
  75 {
  76   /* The edge itself.  Necessary for hashing and equality tests.  */
  77   edge e;
  78
  79   /* The case labels associated with this edge.  We link these up via
  80      their TREE_CHAIN field, then we wipe out the TREE_CHAIN fields
  81      when we destroy the hash table.  This prevents problems when copying
  82      SWITCH_EXPRs.  */
  83   tree case_labels;
  84 };
  85
  86 static htab_t edge_to_cases;
  87
  88 /* CFG statistics.  */
  89 struct cfg_stats_d
  90 {
  91   long num_merged_labels;
  92 };
  93
  94 static struct cfg_stats_d cfg_stats;
  95
  96 /* Nonzero if we found a computed goto while building basic blocks.  */
  97 static bool found_computed_goto;
  98
  99 /* Basic blocks and flowgraphs.  */
 100 static basic_block create_bb (void *, void *, basic_block);
 101 static void create_block_annotation (basic_block);
 102 static void free_blocks_annotations (void);
 103 static void clear_blocks_annotations (void);
 104 static void make_blocks (tree);
 105 static void factor_computed_gotos (void);
 106
 107 /* Edges.  */
 108 static void make_edges (void);
 109 static void make_ctrl_stmt_edges (basic_block);
 110 static void make_exit_edges (basic_block);
 111 static void make_cond_expr_edges (basic_block);
 112 static void make_switch_expr_edges (basic_block);
 113 static void make_goto_expr_edges (basic_block);
 114 static edge tree_redirect_edge_and_branch (edge, basic_block);
 115 static edge tree_try_redirect_by_replacing_jump (edge, basic_block);
 116 static void split_critical_edges (void);
 117 static bool remove_fallthru_edge (VEC(edge) *);
 118
 119 /* Various helpers.  */
 120 static inline bool stmt_starts_bb_p (tree, tree);
 121 static int tree_verify_flow_info (void);
 122 static void tree_make_forwarder_block (edge);
 123 static bool tree_forwarder_block_p (basic_block, bool);
 124 static void tree_cfg2vcg (FILE *);
 125
 126 /* Flowgraph optimization and cleanup.  */
 127 static void tree_merge_blocks (basic_block, basic_block);
 128 static bool tree_can_merge_blocks_p (basic_block, basic_block);
 129 static void remove_bb (basic_block);
 130 static bool cleanup_control_flow (void);
 131 static bool cleanup_control_expr_graph (basic_block, block_stmt_iterator);
 132 static edge find_taken_edge_cond_expr (basic_block, tree);
 133 static edge find_taken_edge_switch_expr (basic_block, tree);
 134 static tree find_case_label_for_value (tree, tree);
 135 static bool phi_alternatives_equal (basic_block, edge, edge);
 136 static bool cleanup_forwarder_blocks (void);
 137
 138
 139 /*---------------------------------------------------------------------------
 140                               Create basic blocks
 141 ---------------------------------------------------------------------------*/
 142
 143 /* Entry point to the CFG builder for trees.  TP points to the list of
 144    statements to be added to the flowgraph.  */
 145
 146 static void
 147 build_tree_cfg (tree *tp)
 148 {
 149   /* Register specific tree functions.  */
 150   tree_register_cfg_hooks ();
 151
 152   /* Initialize rbi_pool.  */
 153   alloc_rbi_pool ();
 154
 155   /* Initialize the basic block array.  */
 156   init_flow ();
 157   profile_status = PROFILE_ABSENT;
 158   n_basic_blocks = 0;
 159   last_basic_block = 0;
 160   VARRAY_BB_INIT (basic_block_info, initial_cfg_capacity, "basic_block_info");
 161   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
 162
 163   /* Build a mapping of labels to their associated blocks.  */
 164   VARRAY_BB_INIT (label_to_block_map, initial_cfg_capacity,
 165                   "label to block map");
 166
 167   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 168   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 169
 170   found_computed_goto = 0;
 171   make_blocks (*tp);
 172
 173   /* Computed gotos are hell to deal with, especially if there are
 174      lots of them with a large number of destinations.  So we factor
 175      them to a common computed goto location before we build the
 176      edge list.  After we convert back to normal form, we will un-factor
 177      the computed gotos since factoring introduces an unwanted jump.  */
 178   if (found_computed_goto)
 179     factor_computed_gotos ();
 180
 181   /* Make sure there is always at least one block, even if it's empty.  */
 182   if (n_basic_blocks == 0)
 183     create_empty_bb (ENTRY_BLOCK_PTR);
 184
 185   create_block_annotation (ENTRY_BLOCK_PTR);
 186   create_block_annotation (EXIT_BLOCK_PTR);
 187
 188   /* Adjust the size of the array.  */
 189   VARRAY_GROW (basic_block_info, n_basic_blocks);
 190
 191   /* To speed up statement iterator walks, we first purge dead labels.  */
 192   cleanup_dead_labels ();
 193
 194   /* Group case nodes to reduce the number of edges.
 195      We do this after cleaning up dead labels because otherwise we miss
 196      a lot of obvious case merging opportunities.  */
 197   group_case_labels ();
 198
 199   /* Create the edges of the flowgraph.  */
 200   make_edges ();
 201
 202   /* Debugging dumps.  */
 203
 204   /* Write the flowgraph to a VCG file.  */
 205   {
 206     int local_dump_flags;
 207     FILE *dump_file = dump_begin (TDI_vcg, &local_dump_flags);
 208     if (dump_file)
 209       {
 210         tree_cfg2vcg (dump_file);
 211         dump_end (TDI_vcg, dump_file);
 212       }
 213   }
 214
 215   /* Dump a textual representation of the flowgraph.  */
 216   if (dump_file)
 217     dump_tree_cfg (dump_file, dump_flags);
 218 }
 219
 220 static void
 221 execute_build_cfg (void)
 222 {
 223   build_tree_cfg (&DECL_SAVED_TREE (current_function_decl));
 224 }
 225
 226 struct tree_opt_pass pass_build_cfg =
 227 {
 228   "cfg",                                /* name */
 229   NULL,                                 /* gate */
 230   execute_build_cfg,                    /* execute */
 231   NULL,                                 /* sub */
 232   NULL,                                 /* next */
 233   0,                                    /* static_pass_number */
 234   TV_TREE_CFG,                          /* tv_id */
 235   PROP_gimple_leh,                      /* properties_required */
 236   PROP_cfg,                             /* properties_provided */
 237   0,                                    /* properties_destroyed */
 238   0,                                    /* todo_flags_start */
 239   TODO_verify_stmts,                    /* todo_flags_finish */
 240   0                                     /* letter */
 241 };
 242
 243 /* Search the CFG for any computed gotos.  If found, factor them to a
 244    common computed goto site.  Also record the location of that site so
 245    that we can un-factor the gotos after we have converted back to
 246    normal form.  */
 247
 248 static void
 249 factor_computed_gotos (void)
 250 {
 251   basic_block bb;
 252   tree factored_label_decl = NULL;
 253   tree var = NULL;
 254   tree factored_computed_goto_label = NULL;
 255   tree factored_computed_goto = NULL;
 256
 257   /* We know there are one or more computed gotos in this function.
 258      Examine the last statement in each basic block to see if the block
 259      ends with a computed goto.  */
 260
 261   FOR_EACH_BB (bb)
 262     {
 263       block_stmt_iterator bsi = bsi_last (bb);
 264       tree last;
 265
 266       if (bsi_end_p (bsi))
 267         continue;
 268       last = bsi_stmt (bsi);
 269
 270       /* Ignore the computed goto we create when we factor the original
 271          computed gotos.  */
 272       if (last == factored_computed_goto)
 273         continue;
 274
 275       /* If the last statement is a computed goto, factor it.  */
 276       if (computed_goto_p (last))
 277         {
 278           tree assignment;
 279
 280           /* The first time we find a computed goto we need to create
 281              the factored goto block and the variable each original
 282              computed goto will use for their goto destination.  */
 283           if (! factored_computed_goto)
 284             {
 285               basic_block new_bb = create_empty_bb (bb);
 286               block_stmt_iterator new_bsi = bsi_start (new_bb);
 287
 288               /* Create the destination of the factored goto.  Each original
 289                  computed goto will put its desired destination into this
 290                  variable and jump to the label we create immediately
 291                  below.  */
 292               var = create_tmp_var (ptr_type_node, "gotovar");
 293
 294               /* Build a label for the new block which will contain the
 295                  factored computed goto.  */
 296               factored_label_decl = create_artificial_label ();
 297               factored_computed_goto_label
 298                 = build1 (LABEL_EXPR, void_type_node, factored_label_decl);
 299               bsi_insert_after (&new_bsi, factored_computed_goto_label,
 300                                 BSI_NEW_STMT);
 301
 302               /* Build our new computed goto.  */
 303               factored_computed_goto = build1 (GOTO_EXPR, void_type_node, var);
 304               bsi_insert_after (&new_bsi, factored_computed_goto,
 305                                 BSI_NEW_STMT);
 306             }
 307
 308           /* Copy the original computed goto's destination into VAR.  */
 309           assignment = build (MODIFY_EXPR, ptr_type_node,
 310                               var, GOTO_DESTINATION (last));
 311           bsi_insert_before (&bsi, assignment, BSI_SAME_STMT);
 312
 313           /* And re-vector the computed goto to the new destination.  */
 314           GOTO_DESTINATION (last) = factored_label_decl;
 315         }
 316     }
 317 }
 318
 319
 320 /* Create annotations for a single basic block.  */
 321
 322 static void
 323 create_block_annotation (basic_block bb)
 324 {
 325   /* Verify that the tree_annotations field is clear.  */
 326   gcc_assert (!bb->tree_annotations);
 327   bb->tree_annotations = ggc_alloc_cleared (sizeof (struct bb_ann_d));
 328 }
 329
 330
 331 /* Free the annotations for all the basic blocks.  */
 332
 333 static void free_blocks_annotations (void)
 334 {
 335   clear_blocks_annotations ();
 336 }
 337
 338
 339 /* Clear the annotations for all the basic blocks.  */
 340
 341 static void
 342 clear_blocks_annotations (void)
 343 {
 344   basic_block bb;
 345
 346   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 347     bb->tree_annotations = NULL;
 348 }
 349
 350
 351 /* Build a flowgraph for the statement_list STMT_LIST.  */
 352
 353 static void
 354 make_blocks (tree stmt_list)
 355 {
 356   tree_stmt_iterator i = tsi_start (stmt_list);
 357   tree stmt = NULL;
 358   bool start_new_block = true;
 359   bool first_stmt_of_list = true;
 360   basic_block bb = ENTRY_BLOCK_PTR;
 361
 362   while (!tsi_end_p (i))
 363     {
 364       tree prev_stmt;
 365
 366       prev_stmt = stmt;
 367       stmt = tsi_stmt (i);
 368
 369       /* If the statement starts a new basic block or if we have determined
 370          in a previous pass that we need to create a new block for STMT, do
 371          so now.  */
 372       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
 373         {
 374           if (!first_stmt_of_list)
 375             stmt_list = tsi_split_statement_list_before (&i);
 376           bb = create_basic_block (stmt_list, NULL, bb);
 377           start_new_block = false;
 378         }
 379
 380       /* Now add STMT to BB and create the subgraphs for special statement
 381          codes.  */
 382       set_bb_for_stmt (stmt, bb);
 383
 384       if (computed_goto_p (stmt))
 385         found_computed_goto = true;
 386
 387       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
 388          next iteration.  */
 389       if (stmt_ends_bb_p (stmt))
 390         start_new_block = true;
 391
 392       tsi_next (&i);
 393       first_stmt_of_list = false;
 394     }
 395 }
 396
 397
 398 /* Create and return a new empty basic block after bb AFTER.  */
 399
 400 static basic_block
 401 create_bb (void *h, void *e, basic_block after)
 402 {
 403   basic_block bb;
 404
 405   gcc_assert (!e);
 406
 407   /* Create and initialize a new basic block.  Since alloc_block uses
 408      ggc_alloc_cleared to allocate a basic block, we do not have to
 409      clear the newly allocated basic block here.  */
 410   bb = alloc_block ();
 411
 412   bb->index = last_basic_block;
 413   bb->flags = BB_NEW;
 414   bb->stmt_list = h ? h : alloc_stmt_list ();
 415
 416   /* Add the new block to the linked list of blocks.  */
 417   link_block (bb, after);
 418
 419   /* Grow the basic block array if needed.  */
 420   if ((size_t) last_basic_block == VARRAY_SIZE (basic_block_info))
 421     {
 422       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
 423       VARRAY_GROW (basic_block_info, new_size);
 424     }
 425
 426   /* Add the newly created block to the array.  */
 427   BASIC_BLOCK (last_basic_block) = bb;
 428
 429   create_block_annotation (bb);
 430
 431   n_basic_blocks++;
 432   last_basic_block++;
 433
 434   initialize_bb_rbi (bb);
 435   return bb;
 436 }
 437
 438
 439 /*---------------------------------------------------------------------------
 440                                  Edge creation
 441 ---------------------------------------------------------------------------*/
 442
 443 /* Join all the blocks in the flowgraph.  */
 444
 445 static void
 446 make_edges (void)
 447 {
 448   basic_block bb;
 449
 450   /* Create an edge from entry to the first block with executable
 451      statements in it.  */
 452   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
 453
 454   /* Traverse the basic block array placing edges.  */
 455   FOR_EACH_BB (bb)
 456     {
 457       tree first = first_stmt (bb);
 458       tree last = last_stmt (bb);
 459
 460       if (first)
 461         {
 462           /* Edges for statements that always alter flow control.  */
 463           if (is_ctrl_stmt (last))
 464             make_ctrl_stmt_edges (bb);
 465
 466           /* Edges for statements that sometimes alter flow control.  */
 467           if (is_ctrl_altering_stmt (last))
 468             make_exit_edges (bb);
 469         }
 470
 471       /* Finally, if no edges were created above, this is a regular
 472          basic block that only needs a fallthru edge.  */
 473       if (EDGE_COUNT (bb->succs) == 0)
 474         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 475     }
 476
 477   /* We do not care about fake edges, so remove any that the CFG
 478      builder inserted for completeness.  */
 479   remove_fake_exit_edges ();
 480
 481   /* Clean up the graph and warn for unreachable code.  */
 482   cleanup_tree_cfg ();
 483 }
 484
 485
 486 /* Create edges for control statement at basic block BB.  */
 487
 488 static void
 489 make_ctrl_stmt_edges (basic_block bb)
 490 {
 491   tree last = last_stmt (bb);
 492
 493   gcc_assert (last);
 494   switch (TREE_CODE (last))
 495     {
 496     case GOTO_EXPR:
 497       make_goto_expr_edges (bb);
 498       break;
 499
 500     case RETURN_EXPR:
 501       make_edge (bb, EXIT_BLOCK_PTR, 0);
 502       break;
 503
 504     case COND_EXPR:
 505       make_cond_expr_edges (bb);
 506       break;
 507
 508     case SWITCH_EXPR:
 509       make_switch_expr_edges (bb);
 510       break;
 511
 512     case RESX_EXPR:
 513       make_eh_edges (last);
 514       /* Yet another NORETURN hack.  */
 515       if (EDGE_COUNT (bb->succs) == 0)
 516         make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 517       break;
 518
 519     default:
 520       gcc_unreachable ();
 521     }
 522 }
 523
 524
 525 /* Create exit edges for statements in block BB that alter the flow of
 526    control.  Statements that alter the control flow are 'goto', 'return'
 527    and calls to non-returning functions.  */
 528
 529 static void
 530 make_exit_edges (basic_block bb)
 531 {
 532   tree last = last_stmt (bb), op;
 533
 534   gcc_assert (last);
 535   switch (TREE_CODE (last))
 536     {
 537     case CALL_EXPR:
 538       /* If this function receives a nonlocal goto, then we need to
 539          make edges from this call site to all the nonlocal goto
 540          handlers.  */
 541       if (TREE_SIDE_EFFECTS (last)
 542           && current_function_has_nonlocal_label)
 543         make_goto_expr_edges (bb);
 544
 545       /* If this statement has reachable exception handlers, then
 546          create abnormal edges to them.  */
 547       make_eh_edges (last);
 548
 549       /* Some calls are known not to return.  For such calls we create
 550          a fake edge.
 551
 552          We really need to revamp how we build edges so that it's not
 553          such a bloody pain to avoid creating edges for this case since
 554          all we do is remove these edges when we're done building the
 555          CFG.  */
 556       if (call_expr_flags (last) & ECF_NORETURN)
 557         {
 558           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 559           return;
 560         }
 561
 562       /* Don't forget the fall-thru edge.  */
 563       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 564       break;
 565
 566     case MODIFY_EXPR:
 567       /* A MODIFY_EXPR may have a CALL_EXPR on its RHS and the CALL_EXPR
 568          may have an abnormal edge.  Search the RHS for this case and
 569          create any required edges.  */
 570       op = get_call_expr_in (last);
 571       if (op && TREE_SIDE_EFFECTS (op)
 572           && current_function_has_nonlocal_label)
 573         make_goto_expr_edges (bb);
 574
 575       make_eh_edges (last);
 576       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 577       break;
 578
 579     default:
 580       gcc_unreachable ();
 581     }
 582 }
 583
 584
 585 /* Create the edges for a COND_EXPR starting at block BB.
 586    At this point, both clauses must contain only simple gotos.  */
 587
 588 static void
 589 make_cond_expr_edges (basic_block bb)
 590 {
 591   tree entry = last_stmt (bb);
 592   basic_block then_bb, else_bb;
 593   tree then_label, else_label;
 594
 595   gcc_assert (entry);
 596   gcc_assert (TREE_CODE (entry) == COND_EXPR);
 597
 598   /* Entry basic blocks for each component.  */
 599   then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
 600   else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
 601   then_bb = label_to_block (then_label);
 602   else_bb = label_to_block (else_label);
 603
 604   make_edge (bb, then_bb, EDGE_TRUE_VALUE);
 605   make_edge (bb, else_bb, EDGE_FALSE_VALUE);
 606 }
 607
 608 /* Hashing routine for EDGE_TO_CASES.  */
 609
 610 static hashval_t
 611 edge_to_cases_hash (const void *p)
 612 {
 613   edge e = ((struct edge_to_cases_elt *)p)->e;
 614
 615   /* Hash on the edge itself (which is a pointer).  */
 616   return htab_hash_pointer (e);
 617 }
 618
 619 /* Equality routine for EDGE_TO_CASES, edges are unique, so testing
 620    for equality is just a pointer comparison.  */
 621
 622 static int
 623 edge_to_cases_eq (const void *p1, const void *p2)
 624 {
 625   edge e1 = ((struct edge_to_cases_elt *)p1)->e;
 626   edge e2 = ((struct edge_to_cases_elt *)p2)->e;
 627
 628   return e1 == e2;
 629 }
 630
 631 /* Called for each element in the hash table (P) as we delete the
 632    edge to cases hash table.
 633
 634    Clear all the TREE_CHAINs to prevent problems with copying of
 635    SWITCH_EXPRs and structure sharing rules, then free the hash table
 636    element.  */
 637
 638 static void
 639 edge_to_cases_cleanup (void *p)
 640 {
 641   struct edge_to_cases_elt *elt = p;
 642   tree t, next;
 643
 644   for (t = elt->case_labels; t; t = next)
 645     {
 646       next = TREE_CHAIN (t);
 647       TREE_CHAIN (t) = NULL;
 648     }
 649   free (p);
 650 }
 651
 652 /* Start recording information mapping edges to case labels.  */
 653
 654 static void
 655 start_recording_case_labels (void)
 656 {
 657   gcc_assert (edge_to_cases == NULL);
 658
 659   edge_to_cases = htab_create (37,
 660                                edge_to_cases_hash,
 661                                edge_to_cases_eq,
 662                                edge_to_cases_cleanup);
 663 }
 664
 665 /* Return nonzero if we are recording information for case labels.  */
 666
 667 static bool
 668 recording_case_labels_p (void)
 669 {
 670   return (edge_to_cases != NULL);
 671 }
 672
 673 /* Stop recording information mapping edges to case labels and
 674    remove any information we have recorded.  */
 675 static void
 676 end_recording_case_labels (void)
 677 {
 678   htab_delete (edge_to_cases);
 679   edge_to_cases = NULL;
 680 }
 681
 682 /* Record that CASE_LABEL (a CASE_LABEL_EXPR) references edge E.  */
 683
 684 static void
 685 record_switch_edge (edge e, tree case_label)
 686 {
 687   struct edge_to_cases_elt *elt;
 688   void **slot;
 689
 690   /* Build a hash table element so we can see if E is already
 691      in the table.  */
 692   elt = xmalloc (sizeof (struct edge_to_cases_elt));
 693   elt->e = e;
 694   elt->case_labels = case_label;
 695
 696   slot = htab_find_slot (edge_to_cases, elt, INSERT);
 697
 698   if (*slot == NULL)
 699     {
 700       /* E was not in the hash table.  Install E into the hash table.  */
 701       *slot = (void *)elt;
 702     }
 703   else
 704     {
 705       /* E was already in the hash table.  Free ELT as we do not need it
 706          anymore.  */
 707       free (elt);
 708
 709       /* Get the entry stored in the hash table.  */
 710       elt = (struct edge_to_cases_elt *) *slot;
 711
 712       /* Add it to the chain of CASE_LABEL_EXPRs referencing E.  */
 713       TREE_CHAIN (case_label) = elt->case_labels;
 714       elt->case_labels = case_label;
 715     }
 716 }
 717
 718 /* If we are inside a {start,end}_recording_cases block, then return
 719    a chain of CASE_LABEL_EXPRs from T which reference E.
 720
 721    Otherwise return NULL.  */
 722
 723 static tree
 724 get_cases_for_edge (edge e, tree t)
 725 {
 726   struct edge_to_cases_elt elt, *elt_p;
 727   void **slot;
 728   size_t i, n;
 729   tree vec;
 730
 731   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
 732      chains available.  Return NULL so the caller can detect this case.  */
 733   if (!recording_case_labels_p ())
 734     return NULL;
 735
 736 restart:
 737   elt.e = e;
 738   elt.case_labels = NULL;
 739   slot = htab_find_slot (edge_to_cases, &elt, NO_INSERT);
 740
 741   if (slot)
 742     {
 743       elt_p = (struct edge_to_cases_elt *)*slot;
 744       return elt_p->case_labels;
 745     }
 746
 747   /* If we did not find E in the hash table, then this must be the first
 748      time we have been queried for information about E & T.  Add all the
 749      elements from T to the hash table then perform the query again.  */
 750
 751   vec = SWITCH_LABELS (t);
 752   n = TREE_VEC_LENGTH (vec);
 753   for (i = 0; i < n; i++)
 754     {
 755       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
 756       basic_block label_bb = label_to_block (lab);
 757       record_switch_edge (find_edge (e->src, label_bb), TREE_VEC_ELT (vec, i));
 758     }
 759   goto restart;
 760 }
 761
 762 /* Create the edges for a SWITCH_EXPR starting at block BB.
 763    At this point, the switch body has been lowered and the
 764    SWITCH_LABELS filled in, so this is in effect a multi-way branch.  */
 765
 766 static void
 767 make_switch_expr_edges (basic_block bb)
 768 {
 769   tree entry = last_stmt (bb);
 770   size_t i, n;
 771   tree vec;
 772
 773   vec = SWITCH_LABELS (entry);
 774   n = TREE_VEC_LENGTH (vec);
 775
 776   for (i = 0; i < n; ++i)
 777     {
 778       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
 779       basic_block label_bb = label_to_block (lab);
 780       make_edge (bb, label_bb, 0);
 781     }
 782 }
 783
 784
 785 /* Return the basic block holding label DEST.  */
 786
 787 basic_block
 788 label_to_block (tree dest)
 789 {
 790   int uid = LABEL_DECL_UID (dest);
 791
 792   /* We would die hard when faced by an undefined label.  Emit a label to
 793      the very first basic block.  This will hopefully make even the dataflow
 794      and undefined variable warnings quite right.  */
 795   if ((errorcount || sorrycount) && uid < 0)
 796     {
 797       block_stmt_iterator bsi = bsi_start (BASIC_BLOCK (0));
 798       tree stmt;
 799
 800       stmt = build1 (LABEL_EXPR, void_type_node, dest);
 801       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
 802       uid = LABEL_DECL_UID (dest);
 803     }
 804   return VARRAY_BB (label_to_block_map, uid);
 805 }
 806
 807
 808 /* Create edges for a goto statement at block BB.  */
 809
 810 static void
 811 make_goto_expr_edges (basic_block bb)
 812 {
 813   tree goto_t, dest;
 814   basic_block target_bb;
 815   int for_call;
 816   block_stmt_iterator last = bsi_last (bb);
 817
 818   goto_t = bsi_stmt (last);
 819
 820   /* If the last statement is not a GOTO (i.e., it is a RETURN_EXPR,
 821      CALL_EXPR or MODIFY_EXPR), then the edge is an abnormal edge resulting
 822      from a nonlocal goto.  */
 823   if (TREE_CODE (goto_t) != GOTO_EXPR)
 824     {
 825       dest = error_mark_node;
 826       for_call = 1;
 827     }
 828   else
 829     {
 830       dest = GOTO_DESTINATION (goto_t);
 831       for_call = 0;
 832
 833       /* A GOTO to a local label creates normal edges.  */
 834       if (simple_goto_p (goto_t))
 835         {
 836           edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
 837 #ifdef USE_MAPPED_LOCATION
 838           e->goto_locus = EXPR_LOCATION (goto_t);
 839 #else
 840           e->goto_locus = EXPR_LOCUS (goto_t);
 841 #endif
 842           bsi_remove (&last);
 843           return;
 844         }
 845
 846       /* Nothing more to do for nonlocal gotos.  */
 847       if (TREE_CODE (dest) == LABEL_DECL)
 848         return;
 849
 850       /* Computed gotos remain.  */
 851     }
 852
 853   /* Look for the block starting with the destination label.  In the
 854      case of a computed goto, make an edge to any label block we find
 855      in the CFG.  */
 856   FOR_EACH_BB (target_bb)
 857     {
 858       block_stmt_iterator bsi;
 859
 860       for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
 861         {
 862           tree target = bsi_stmt (bsi);
 863
 864           if (TREE_CODE (target) != LABEL_EXPR)
 865             break;
 866
 867           if (
 868               /* Computed GOTOs.  Make an edge to every label block that has
 869                  been marked as a potential target for a computed goto.  */
 870               (FORCED_LABEL (LABEL_EXPR_LABEL (target)) && for_call == 0)
 871               /* Nonlocal GOTO target.  Make an edge to every label block
 872                  that has been marked as a potential target for a nonlocal
 873                  goto.  */
 874               || (DECL_NONLOCAL (LABEL_EXPR_LABEL (target)) && for_call == 1))
 875             {
 876               make_edge (bb, target_bb, EDGE_ABNORMAL);
 877               break;
 878             }
 879         }
 880     }
 881
 882   /* Degenerate case of computed goto with no labels.  */
 883   if (!for_call && EDGE_COUNT (bb->succs) == 0)
 884     make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 885 }
 886
 887
 888 /*---------------------------------------------------------------------------
 889                                Flowgraph analysis
 890 ---------------------------------------------------------------------------*/
 891
 892 /* Remove unreachable blocks and other miscellaneous clean up work.  */
 893
 894 bool
 895 cleanup_tree_cfg (void)
 896 {
 897   bool retval = false;
 898
 899   timevar_push (TV_TREE_CLEANUP_CFG);
 900
 901   retval = cleanup_control_flow ();
 902   retval |= delete_unreachable_blocks ();
 903
 904   /* cleanup_forwarder_blocks can redirect edges out of SWITCH_EXPRs,
 905      which can get expensive.  So we want to enable recording of edge
 906      to CASE_LABEL_EXPR mappings around the call to
 907      cleanup_forwarder_blocks.  */
 908   start_recording_case_labels ();
 909   retval |= cleanup_forwarder_blocks ();
 910   end_recording_case_labels ();
 911
 912 #ifdef ENABLE_CHECKING
 913   if (retval)
 914     {
 915       gcc_assert (!cleanup_control_flow ());
 916       gcc_assert (!delete_unreachable_blocks ());
 917       gcc_assert (!cleanup_forwarder_blocks ());
 918     }
 919 #endif
 920
 921   /* Merging the blocks creates no new opportunities for the other
 922      optimizations, so do it here.  */
 923   retval |= merge_seq_blocks ();
 924
 925   compact_blocks ();
 926
 927 #ifdef ENABLE_CHECKING
 928   verify_flow_info ();
 929 #endif
 930   timevar_pop (TV_TREE_CLEANUP_CFG);
 931   return retval;
 932 }
 933
 934
 935 /* Cleanup useless labels in basic blocks.  This is something we wish
 936    to do early because it allows us to group case labels before creating
 937    the edges for the CFG, and it speeds up block statement iterators in
 938    all passes later on.
 939    We only run this pass once, running it more than once is probably not
 940    profitable.  */
 941
 942 /* A map from basic block index to the leading label of that block.  */
 943 static tree *label_for_bb;
 944
 945 /* Callback for for_each_eh_region.  Helper for cleanup_dead_labels.  */
 946 static void
 947 update_eh_label (struct eh_region *region)
 948 {
 949   tree old_label = get_eh_region_tree_label (region);
 950   if (old_label)
 951     {
 952       tree new_label;
 953       basic_block bb = label_to_block (old_label);
 954
 955       /* ??? After optimizing, there may be EH regions with labels
 956          that have already been removed from the function body, so
 957          there is no basic block for them.  */
 958       if (! bb)
 959         return;
 960
 961       new_label = label_for_bb[bb->index];
 962       set_eh_region_tree_label (region, new_label);
 963     }
 964 }
 965
 966 /* Given LABEL return the first label in the same basic block.  */
 967 static tree
 968 main_block_label (tree label)
 969 {
 970   basic_block bb = label_to_block (label);
 971
 972   /* label_to_block possibly inserted undefined label into the chain.  */
 973   if (!label_for_bb[bb->index])
 974     label_for_bb[bb->index] = label;
 975   return label_for_bb[bb->index];
 976 }
 977
 978 /* Cleanup redundant labels.  This is a three-step process:
 979      1) Find the leading label for each block.
 980      2) Redirect all references to labels to the leading labels.
 981      3) Cleanup all useless labels.  */
 982
 983 void
 984 cleanup_dead_labels (void)
 985 {
 986   basic_block bb;
 987   label_for_bb = xcalloc (last_basic_block, sizeof (tree));
 988
 989   /* Find a suitable label for each block.  We use the first user-defined
 990      label if there is one, or otherwise just the first label we see.  */
 991   FOR_EACH_BB (bb)
 992     {
 993       block_stmt_iterator i;
 994
 995       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 996         {
 997           tree label, stmt = bsi_stmt (i);
 998
 999           if (TREE_CODE (stmt) != LABEL_EXPR)
1000             break;
1001
1002           label = LABEL_EXPR_LABEL (stmt);
1003
1004           /* If we have not yet seen a label for the current block,
1005              remember this one and see if there are more labels.  */
1006           if (! label_for_bb[bb->index])
1007             {
1008               label_for_bb[bb->index] = label;
1009               continue;
1010             }
1011
1012           /* If we did see a label for the current block already, but it
1013              is an artificially created label, replace it if the current
1014              label is a user defined label.  */
1015           if (! DECL_ARTIFICIAL (label)
1016               && DECL_ARTIFICIAL (label_for_bb[bb->index]))
1017             {
1018               label_for_bb[bb->index] = label;
1019               break;
1020             }
1021         }
1022     }
1023
1024   /* Now redirect all jumps/branches to the selected label.
1025      First do so for each block ending in a control statement.  */
1026   FOR_EACH_BB (bb)
1027     {
1028       tree stmt = last_stmt (bb);
1029       if (!stmt)
1030         continue;
1031
1032       switch (TREE_CODE (stmt))
1033         {
1034         case COND_EXPR:
1035           {
1036             tree true_branch, false_branch;
1037
1038             true_branch = COND_EXPR_THEN (stmt);
1039             false_branch = COND_EXPR_ELSE (stmt);
1040
1041             GOTO_DESTINATION (true_branch)
1042               = main_block_label (GOTO_DESTINATION (true_branch));
1043             GOTO_DESTINATION (false_branch)
1044               = main_block_label (GOTO_DESTINATION (false_branch));
1045
1046             break;
1047           }
1048
1049         case SWITCH_EXPR:
1050           {
1051             size_t i;
1052             tree vec = SWITCH_LABELS (stmt);
1053             size_t n = TREE_VEC_LENGTH (vec);
1054
1055             /* Replace all destination labels.  */
1056             for (i = 0; i < n; ++i)
1057               {
1058                 tree elt = TREE_VEC_ELT (vec, i);
1059                 tree label = main_block_label (CASE_LABEL (elt));
1060                 CASE_LABEL (elt) = label;
1061               }
1062             break;
1063           }
1064
1065         /* We have to handle GOTO_EXPRs until they're removed, and we don't
1066            remove them until after we've created the CFG edges.  */
1067         case GOTO_EXPR:
1068           if (! computed_goto_p (stmt))
1069             {
1070               GOTO_DESTINATION (stmt)
1071                 = main_block_label (GOTO_DESTINATION (stmt));
1072               break;
1073             }
1074
1075         default:
1076           break;
1077       }
1078     }
1079
1080   for_each_eh_region (update_eh_label);
1081
1082   /* Finally, purge dead labels.  All user-defined labels and labels that
1083      can be the target of non-local gotos are preserved.  */
1084   FOR_EACH_BB (bb)
1085     {
1086       block_stmt_iterator i;
1087       tree label_for_this_bb = label_for_bb[bb->index];
1088
1089       if (! label_for_this_bb)
1090         continue;
1091
1092       for (i = bsi_start (bb); !bsi_end_p (i); )
1093         {
1094           tree label, stmt = bsi_stmt (i);
1095
1096           if (TREE_CODE (stmt) != LABEL_EXPR)
1097             break;
1098
1099           label = LABEL_EXPR_LABEL (stmt);
1100
1101           if (label == label_for_this_bb
1102               || ! DECL_ARTIFICIAL (label)
1103               || DECL_NONLOCAL (label))
1104             bsi_next (&i);
1105           else
1106             bsi_remove (&i);
1107         }
1108     }
1109
1110   free (label_for_bb);
1111 }
1112
1113 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
1114    and scan the sorted vector of cases.  Combine the ones jumping to the
1115    same label.
1116    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1117
1118 void
1119 group_case_labels (void)
1120 {
1121   basic_block bb;
1122
1123   FOR_EACH_BB (bb)
1124     {
1125       tree stmt = last_stmt (bb);
1126       if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
1127         {
1128           tree labels = SWITCH_LABELS (stmt);
1129           int old_size = TREE_VEC_LENGTH (labels);
1130           int i, j, new_size = old_size;
1131           tree default_case = TREE_VEC_ELT (labels, old_size - 1);
1132           tree default_label;
1133
1134           /* The default label is always the last case in a switch
1135              statement after gimplification.  */
1136           default_label = CASE_LABEL (default_case);
1137
1138           /* Look for possible opportunities to merge cases.
1139              Ignore the last element of the label vector because it
1140              must be the default case.  */
1141           i = 0;
1142           while (i < old_size - 1)
1143             {
1144               tree base_case, base_label, base_high, type;
1145               base_case = TREE_VEC_ELT (labels, i);
1146
1147               gcc_assert (base_case);
1148               base_label = CASE_LABEL (base_case);
1149
1150               /* Discard cases that have the same destination as the
1151                  default case.  */
1152               if (base_label == default_label)
1153                 {
1154                   TREE_VEC_ELT (labels, i) = NULL_TREE;
1155                   i++;
1156                   new_size--;
1157                   continue;
1158                 }
1159
1160               type = TREE_TYPE (CASE_LOW (base_case));
1161               base_high = CASE_HIGH (base_case) ?
1162                 CASE_HIGH (base_case) : CASE_LOW (base_case);
1163               i++;
1164               /* Try to merge case labels.  Break out when we reach the end
1165                  of the label vector or when we cannot merge the next case
1166                  label with the current one.  */
1167               while (i < old_size - 1)
1168                 {
1169                   tree merge_case = TREE_VEC_ELT (labels, i);
1170                   tree merge_label = CASE_LABEL (merge_case);
1171                   tree t = int_const_binop (PLUS_EXPR, base_high,
1172                                             integer_one_node, 1);
1173
1174                   /* Merge the cases if they jump to the same place,
1175                      and their ranges are consecutive.  */
1176                   if (merge_label == base_label
1177                       && tree_int_cst_equal (CASE_LOW (merge_case), t))
1178                     {
1179                       base_high = CASE_HIGH (merge_case) ?
1180                         CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1181                       CASE_HIGH (base_case) = base_high;
1182                       TREE_VEC_ELT (labels, i) = NULL_TREE;
1183                       new_size--;
1184                       i++;
1185                     }
1186                   else
1187                     break;
1188                 }
1189             }
1190
1191           /* Compress the case labels in the label vector, and adjust the
1192              length of the vector.  */
1193           for (i = 0, j = 0; i < new_size; i++)
1194             {
1195               while (! TREE_VEC_ELT (labels, j))
1196                 j++;
1197               TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
1198             }
1199           TREE_VEC_LENGTH (labels) = new_size;
1200         }
1201     }
1202 }
1203
1204 /* Checks whether we can merge block B into block A.  */
1205
1206 static bool
1207 tree_can_merge_blocks_p (basic_block a, basic_block b)
1208 {
1209   tree stmt;
1210   block_stmt_iterator bsi;
1211
1212   if (EDGE_COUNT (a->succs) != 1)
1213     return false;
1214
1215   if (EDGE_SUCC (a, 0)->flags & EDGE_ABNORMAL)
1216     return false;
1217
1218   if (EDGE_SUCC (a, 0)->dest != b)
1219     return false;
1220
1221   if (EDGE_COUNT (b->preds) > 1)
1222     return false;
1223
1224   if (b == EXIT_BLOCK_PTR)
1225     return false;
1226
1227   /* If A ends by a statement causing exceptions or something similar, we
1228      cannot merge the blocks.  */
1229   stmt = last_stmt (a);
1230   if (stmt && stmt_ends_bb_p (stmt))
1231     return false;
1232
1233   /* Do not allow a block with only a non-local label to be merged.  */
1234   if (stmt && TREE_CODE (stmt) == LABEL_EXPR
1235       && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
1236     return false;
1237
1238   /* There may be no phi nodes at the start of b.  Most of these degenerate
1239      phi nodes should be cleaned up by kill_redundant_phi_nodes.  */
1240   if (phi_nodes (b))
1241     return false;
1242
1243   /* Do not remove user labels.  */
1244   for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
1245     {
1246       stmt = bsi_stmt (bsi);
1247       if (TREE_CODE (stmt) != LABEL_EXPR)
1248         break;
1249       if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt)))
1250         return false;
1251     }
1252
1253   return true;
1254 }
1255
1256
1257 /* Merge block B into block A.  */
1258
1259 static void
1260 tree_merge_blocks (basic_block a, basic_block b)
1261 {
1262   block_stmt_iterator bsi;
1263   tree_stmt_iterator last;
1264
1265   if (dump_file)
1266     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1267
1268   /* Ensure that B follows A.  */
1269   move_block_after (b, a);
1270
1271   gcc_assert (EDGE_SUCC (a, 0)->flags & EDGE_FALLTHRU);
1272   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1273
1274   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1275   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1276     {
1277       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1278         bsi_remove (&bsi);
1279       else
1280         {
1281           set_bb_for_stmt (bsi_stmt (bsi), a);
1282           bsi_next (&bsi);
1283         }
1284     }
1285
1286   /* Merge the chains.  */
1287   last = tsi_last (a->stmt_list);
1288   tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
1289   b->stmt_list = NULL;
1290 }
1291
1292
1293 /* Walk the function tree removing unnecessary statements.
1294
1295      * Empty statement nodes are removed
1296
1297      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1298
1299      * Unnecessary COND_EXPRs are removed
1300
1301      * Some unnecessary BIND_EXPRs are removed
1302
1303    Clearly more work could be done.  The trick is doing the analysis
1304    and removal fast enough to be a net improvement in compile times.
1305
1306    Note that when we remove a control structure such as a COND_EXPR
1307    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1308    to ensure we eliminate all the useless code.  */
1309
1310 struct rus_data
1311 {
1312   tree *last_goto;
1313   bool repeat;
1314   bool may_throw;
1315   bool may_branch;
1316   bool has_label;
1317 };
1318
1319 static void remove_useless_stmts_1 (tree *, struct rus_data *);
1320
1321 static bool
1322 remove_useless_stmts_warn_notreached (tree stmt)
1323 {
1324   if (EXPR_HAS_LOCATION (stmt))
1325     {
1326       location_t loc = EXPR_LOCATION (stmt);
1327       if (LOCATION_LINE (loc) > 0)
1328         {
1329           warning ("%Hwill never be executed", &loc);
1330           return true;
1331         }
1332     }
1333
1334   switch (TREE_CODE (stmt))
1335     {
1336     case STATEMENT_LIST:
1337       {
1338         tree_stmt_iterator i;
1339         for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
1340           if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
1341             return true;
1342       }
1343       break;
1344
1345     case COND_EXPR:
1346       if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
1347         return true;
1348       if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
1349         return true;
1350       if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
1351         return true;
1352       break;
1353
1354     case TRY_FINALLY_EXPR:
1355     case TRY_CATCH_EXPR:
1356       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
1357         return true;
1358       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
1359         return true;
1360       break;
1361
1362     case CATCH_EXPR:
1363       return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
1364     case EH_FILTER_EXPR:
1365       return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
1366     case BIND_EXPR:
1367       return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
1368
1369     default:
1370       /* Not a live container.  */
1371       break;
1372     }
1373
1374   return false;
1375 }
1376
1377 static void
1378 remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
1379 {
1380   tree then_clause, else_clause, cond;
1381   bool save_has_label, then_has_label, else_has_label;
1382
1383   save_has_label = data->has_label;
1384   data->has_label = false;
1385   data->last_goto = NULL;
1386
1387   remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
1388
1389   then_has_label = data->has_label;
1390   data->has_label = false;
1391   data->last_goto = NULL;
1392
1393   remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
1394
1395   else_has_label = data->has_label;
1396   data->has_label = save_has_label | then_has_label | else_has_label;
1397
1398   then_clause = COND_EXPR_THEN (*stmt_p);
1399   else_clause = COND_EXPR_ELSE (*stmt_p);
1400   cond = fold (COND_EXPR_COND (*stmt_p));
1401
1402   /* If neither arm does anything at all, we can remove the whole IF.  */
1403   if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
1404     {
1405       *stmt_p = build_empty_stmt ();
1406       data->repeat = true;
1407     }
1408
1409   /* If there are no reachable statements in an arm, then we can
1410      zap the entire conditional.  */
1411   else if (integer_nonzerop (cond) && !else_has_label)
1412     {
1413       if (warn_notreached)
1414         remove_useless_stmts_warn_notreached (else_clause);
1415       *stmt_p = then_clause;
1416       data->repeat = true;
1417     }
1418   else if (integer_zerop (cond) && !then_has_label)
1419     {
1420       if (warn_notreached)
1421         remove_useless_stmts_warn_notreached (then_clause);
1422       *stmt_p = else_clause;
1423       data->repeat = true;
1424     }
1425
1426   /* Check a couple of simple things on then/else with single stmts.  */
1427   else
1428     {
1429       tree then_stmt = expr_only (then_clause);
1430       tree else_stmt = expr_only (else_clause);
1431
1432       /* Notice branches to a common destination.  */
1433       if (then_stmt && else_stmt
1434           && TREE_CODE (then_stmt) == GOTO_EXPR
1435           && TREE_CODE (else_stmt) == GOTO_EXPR
1436           && (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
1437         {
1438           *stmt_p = then_stmt;
1439           data->repeat = true;
1440         }
1441
1442       /* If the THEN/ELSE clause merely assigns a value to a variable or
1443          parameter which is already known to contain that value, then
1444          remove the useless THEN/ELSE clause.  */
1445       else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1446         {
1447           if (else_stmt
1448               && TREE_CODE (else_stmt) == MODIFY_EXPR
1449               && TREE_OPERAND (else_stmt, 0) == cond
1450               && integer_zerop (TREE_OPERAND (else_stmt, 1)))
1451             COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
1452         }
1453       else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1454                && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1455                    || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1456                && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
1457         {
1458           tree stmt = (TREE_CODE (cond) == EQ_EXPR
1459                        ? then_stmt : else_stmt);
1460           tree *location = (TREE_CODE (cond) == EQ_EXPR
1461                             ? &COND_EXPR_THEN (*stmt_p)
1462                             : &COND_EXPR_ELSE (*stmt_p));
1463
1464           if (stmt
1465               && TREE_CODE (stmt) == MODIFY_EXPR
1466               && TREE_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
1467               && TREE_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
1468             *location = alloc_stmt_list ();
1469         }
1470     }
1471
1472   /* Protect GOTOs in the arm of COND_EXPRs from being removed.  They
1473      would be re-introduced during lowering.  */
1474   data->last_goto = NULL;
1475 }
1476
1477
1478 static void
1479 remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
1480 {
1481   bool save_may_branch, save_may_throw;
1482   bool this_may_branch, this_may_throw;
1483
1484   /* Collect may_branch and may_throw information for the body only.  */
1485   save_may_branch = data->may_branch;
1486   save_may_throw = data->may_throw;
1487   data->may_branch = false;
1488   data->may_throw = false;
1489   data->last_goto = NULL;
1490
1491   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1492
1493   this_may_branch = data->may_branch;
1494   this_may_throw = data->may_throw;
1495   data->may_branch |= save_may_branch;
1496   data->may_throw |= save_may_throw;
1497   data->last_goto = NULL;
1498
1499   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1500
1501   /* If the body is empty, then we can emit the FINALLY block without
1502      the enclosing TRY_FINALLY_EXPR.  */
1503   if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
1504     {
1505       *stmt_p = TREE_OPERAND (*stmt_p, 1);
1506       data->repeat = true;
1507     }
1508
1509   /* If the handler is empty, then we can emit the TRY block without
1510      the enclosing TRY_FINALLY_EXPR.  */
1511   else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1512     {
1513       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1514       data->repeat = true;
1515     }
1516
1517   /* If the body neither throws, nor branches, then we can safely
1518      string the TRY and FINALLY blocks together.  */
1519   else if (!this_may_branch && !this_may_throw)
1520     {
1521       tree stmt = *stmt_p;
1522       *stmt_p = TREE_OPERAND (stmt, 0);
1523       append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
1524       data->repeat = true;
1525     }
1526 }
1527
1528
1529 static void
1530 remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
1531 {
1532   bool save_may_throw, this_may_throw;
1533   tree_stmt_iterator i;
1534   tree stmt;
1535
1536   /* Collect may_throw information for the body only.  */
1537   save_may_throw = data->may_throw;
1538   data->may_throw = false;
1539   data->last_goto = NULL;
1540
1541   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1542
1543   this_may_throw = data->may_throw;
1544   data->may_throw = save_may_throw;
1545
1546   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1547   if (!this_may_throw)
1548     {
1549       if (warn_notreached)
1550         remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
1551       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1552       data->repeat = true;
1553       return;
1554     }
1555
1556   /* Process the catch clause specially.  We may be able to tell that
1557      no exceptions propagate past this point.  */
1558
1559   this_may_throw = true;
1560   i = tsi_start (TREE_OPERAND (*stmt_p, 1));
1561   stmt = tsi_stmt (i);
1562   data->last_goto = NULL;
1563
1564   switch (TREE_CODE (stmt))
1565     {
1566     case CATCH_EXPR:
1567       for (; !tsi_end_p (i); tsi_next (&i))
1568         {
1569           stmt = tsi_stmt (i);
1570           /* If we catch all exceptions, then the body does not
1571              propagate exceptions past this point.  */
1572           if (CATCH_TYPES (stmt) == NULL)
1573             this_may_throw = false;
1574           data->last_goto = NULL;
1575           remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
1576         }
1577       break;
1578
1579     case EH_FILTER_EXPR:
1580       if (EH_FILTER_MUST_NOT_THROW (stmt))
1581         this_may_throw = false;
1582       else if (EH_FILTER_TYPES (stmt) == NULL)
1583         this_may_throw = false;
1584       remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
1585       break;
1586
1587     default:
1588       /* Otherwise this is a cleanup.  */
1589       remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1590
1591       /* If the cleanup is empty, then we can emit the TRY block without
1592          the enclosing TRY_CATCH_EXPR.  */
1593       if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1594         {
1595           *stmt_p = TREE_OPERAND (*stmt_p, 0);
1596           data->repeat = true;
1597         }
1598       break;
1599     }
1600   data->may_throw |= this_may_throw;
1601 }
1602
1603
1604 static void
1605 remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
1606 {
1607   tree block;
1608
1609   /* First remove anything underneath the BIND_EXPR.  */
1610   remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
1611
1612   /* If the BIND_EXPR has no variables, then we can pull everything
1613      up one level and remove the BIND_EXPR, unless this is the toplevel
1614      BIND_EXPR for the current function or an inlined function.
1615
1616      When this situation occurs we will want to apply this
1617      optimization again.  */
1618   block = BIND_EXPR_BLOCK (*stmt_p);
1619   if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
1620       && *stmt_p != DECL_SAVED_TREE (current_function_decl)
1621       && (! block
1622           || ! BLOCK_ABSTRACT_ORIGIN (block)
1623           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1624               != FUNCTION_DECL)))
1625     {
1626       *stmt_p = BIND_EXPR_BODY (*stmt_p);
1627       data->repeat = true;
1628     }
1629 }
1630
1631
1632 static void
1633 remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
1634 {
1635   tree dest = GOTO_DESTINATION (*stmt_p);
1636
1637   data->may_branch = true;
1638   data->last_goto = NULL;
1639
1640   /* Record the last goto expr, so that we can delete it if unnecessary.  */
1641   if (TREE_CODE (dest) == LABEL_DECL)
1642     data->last_goto = stmt_p;
1643 }
1644
1645
1646 static void
1647 remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
1648 {
1649   tree label = LABEL_EXPR_LABEL (*stmt_p);
1650
1651   data->has_label = true;
1652
1653   /* We do want to jump across non-local label receiver code.  */
1654   if (DECL_NONLOCAL (label))
1655     data->last_goto = NULL;
1656
1657   else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
1658     {
1659       *data->last_goto = build_empty_stmt ();
1660       data->repeat = true;
1661     }
1662
1663   /* ??? Add something here to delete unused labels.  */
1664 }
1665
1666
1667 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1668    decl.  This allows us to eliminate redundant or useless
1669    calls to "const" functions.
1670
1671    Gimplifier already does the same operation, but we may notice functions
1672    being const and pure once their calls has been gimplified, so we need
1673    to update the flag.  */
1674
1675 static void
1676 update_call_expr_flags (tree call)
1677 {
1678   tree decl = get_callee_fndecl (call);
1679   if (!decl)
1680     return;
1681   if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1682     TREE_SIDE_EFFECTS (call) = 0;
1683   if (TREE_NOTHROW (decl))
1684     TREE_NOTHROW (call) = 1;
1685 }
1686
1687
1688 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1689
1690 void
1691 notice_special_calls (tree t)
1692 {
1693   int flags = call_expr_flags (t);
1694
1695   if (flags & ECF_MAY_BE_ALLOCA)
1696     current_function_calls_alloca = true;
1697   if (flags & ECF_RETURNS_TWICE)
1698     current_function_calls_setjmp = true;
1699 }
1700
1701
1702 /* Clear flags set by notice_special_calls.  Used by dead code removal
1703    to update the flags.  */
1704
1705 void
1706 clear_special_calls (void)
1707 {
1708   current_function_calls_alloca = false;
1709   current_function_calls_setjmp = false;
1710 }
1711
1712
1713 static void
1714 remove_useless_stmts_1 (tree *tp, struct rus_data *data)
1715 {
1716   tree t = *tp, op;
1717
1718   switch (TREE_CODE (t))
1719     {
1720     case COND_EXPR:
1721       remove_useless_stmts_cond (tp, data);
1722       break;
1723
1724     case TRY_FINALLY_EXPR:
1725       remove_useless_stmts_tf (tp, data);
1726       break;
1727
1728     case TRY_CATCH_EXPR:
1729       remove_useless_stmts_tc (tp, data);
1730       break;
1731
1732     case BIND_EXPR:
1733       remove_useless_stmts_bind (tp, data);
1734       break;
1735
1736     case GOTO_EXPR:
1737       remove_useless_stmts_goto (tp, data);
1738       break;
1739
1740     case LABEL_EXPR:
1741       remove_useless_stmts_label (tp, data);
1742       break;
1743
1744     case RETURN_EXPR:
1745       fold_stmt (tp);
1746       data->last_goto = NULL;
1747       data->may_branch = true;
1748       break;
1749
1750     case CALL_EXPR:
1751       fold_stmt (tp);
1752       data->last_goto = NULL;
1753       notice_special_calls (t);
1754       update_call_expr_flags (t);
1755       if (tree_could_throw_p (t))
1756         data->may_throw = true;
1757       break;
1758
1759     case MODIFY_EXPR:
1760       data->last_goto = NULL;
1761       fold_stmt (tp);
1762       op = get_call_expr_in (t);
1763       if (op)
1764         {
1765           update_call_expr_flags (op);
1766           notice_special_calls (op);
1767         }
1768       if (tree_could_throw_p (t))
1769         data->may_throw = true;
1770       break;
1771
1772     case STATEMENT_LIST:
1773       {
1774         tree_stmt_iterator i = tsi_start (t);
1775         while (!tsi_end_p (i))
1776           {
1777             t = tsi_stmt (i);
1778             if (IS_EMPTY_STMT (t))
1779               {
1780                 tsi_delink (&i);
1781                 continue;
1782               }
1783
1784             remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
1785
1786             t = tsi_stmt (i);
1787             if (TREE_CODE (t) == STATEMENT_LIST)
1788               {
1789                 tsi_link_before (&i, t, TSI_SAME_STMT);
1790                 tsi_delink (&i);
1791               }
1792             else
1793               tsi_next (&i);
1794           }
1795       }
1796       break;
1797     case ASM_EXPR:
1798       fold_stmt (tp);
1799       data->last_goto = NULL;
1800       break;
1801
1802     default:
1803       data->last_goto = NULL;
1804       break;
1805     }
1806 }
1807
1808 static void
1809 remove_useless_stmts (void)
1810 {
1811   struct rus_data data;
1812
1813   clear_special_calls ();
1814
1815   do
1816     {
1817       memset (&data, 0, sizeof (data));
1818       remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1819     }
1820   while (data.repeat);
1821 }
1822
1823
1824 struct tree_opt_pass pass_remove_useless_stmts =
1825 {
1826   "useless",                            /* name */
1827   NULL,                                 /* gate */
1828   remove_useless_stmts,                 /* execute */
1829   NULL,                                 /* sub */
1830   NULL,                                 /* next */
1831   0,                                    /* static_pass_number */
1832   0,                                    /* tv_id */
1833   PROP_gimple_any,                      /* properties_required */
1834   0,                                    /* properties_provided */
1835   0,                                    /* properties_destroyed */
1836   0,                                    /* todo_flags_start */
1837   TODO_dump_func,                       /* todo_flags_finish */
1838   0                                     /* letter */
1839 };
1840
1841
1842 /* Remove obviously useless statements in basic block BB.  */
1843
1844 static void
1845 cfg_remove_useless_stmts_bb (basic_block bb)
1846 {
1847   block_stmt_iterator bsi;
1848   tree stmt = NULL_TREE;
1849   tree cond, var = NULL_TREE, val = NULL_TREE;
1850   struct var_ann_d *ann;
1851
1852   /* Check whether we come here from a condition, and if so, get the
1853      condition.  */
1854   if (EDGE_COUNT (bb->preds) != 1
1855       || !(EDGE_PRED (bb, 0)->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1856     return;
1857
1858   cond = COND_EXPR_COND (last_stmt (EDGE_PRED (bb, 0)->src));
1859
1860   if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1861     {
1862       var = cond;
1863       val = (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE
1864              ? boolean_false_node : boolean_true_node);
1865     }
1866   else if (TREE_CODE (cond) == TRUTH_NOT_EXPR
1867            && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1868                || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL))
1869     {
1870       var = TREE_OPERAND (cond, 0);
1871       val = (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE
1872              ? boolean_true_node : boolean_false_node);
1873     }
1874   else
1875     {
1876       if (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE)
1877         cond = invert_truthvalue (cond);
1878       if (TREE_CODE (cond) == EQ_EXPR
1879           && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1880               || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1881           && (TREE_CODE (TREE_OPERAND (cond, 1)) == VAR_DECL
1882               || TREE_CODE (TREE_OPERAND (cond, 1)) == PARM_DECL
1883               || TREE_CONSTANT (TREE_OPERAND (cond, 1))))
1884         {
1885           var = TREE_OPERAND (cond, 0);
1886           val = TREE_OPERAND (cond, 1);
1887         }
1888       else
1889         return;
1890     }
1891
1892   /* Only work for normal local variables.  */
1893   ann = var_ann (var);
1894   if (!ann
1895       || ann->may_aliases
1896       || TREE_ADDRESSABLE (var))
1897     return;
1898
1899   if (! TREE_CONSTANT (val))
1900     {
1901       ann = var_ann (val);
1902       if (!ann
1903           || ann->may_aliases
1904           || TREE_ADDRESSABLE (val))
1905         return;
1906     }
1907
1908   /* Ignore floating point variables, since comparison behaves weird for
1909      them.  */
1910   if (FLOAT_TYPE_P (TREE_TYPE (var)))
1911     return;
1912
1913   for (bsi = bsi_start (bb); !bsi_end_p (bsi);)
1914     {
1915       stmt = bsi_stmt (bsi);
1916
1917       /* If the THEN/ELSE clause merely assigns a value to a variable/parameter
1918          which is already known to contain that value, then remove the useless
1919          THEN/ELSE clause.  */
1920       if (TREE_CODE (stmt) == MODIFY_EXPR
1921           && TREE_OPERAND (stmt, 0) == var
1922           && operand_equal_p (val, TREE_OPERAND (stmt, 1), 0))
1923         {
1924           bsi_remove (&bsi);
1925           continue;
1926         }
1927
1928       /* Invalidate the var if we encounter something that could modify it.
1929          Likewise for the value it was previously set to.  Note that we only
1930          consider values that are either a VAR_DECL or PARM_DECL so we
1931          can test for conflict very simply.  */
1932       if (TREE_CODE (stmt) == ASM_EXPR
1933           || (TREE_CODE (stmt) == MODIFY_EXPR
1934               && (TREE_OPERAND (stmt, 0) == var
1935                   || TREE_OPERAND (stmt, 0) == val)))
1936         return;
1937
1938       bsi_next (&bsi);
1939     }
1940 }
1941
1942
1943 /* A CFG-aware version of remove_useless_stmts.  */
1944
1945 void
1946 cfg_remove_useless_stmts (void)
1947 {
1948   basic_block bb;
1949
1950 #ifdef ENABLE_CHECKING
1951   verify_flow_info ();
1952 #endif
1953
1954   FOR_EACH_BB (bb)
1955     {
1956       cfg_remove_useless_stmts_bb (bb);
1957     }
1958 }
1959
1960
1961 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1962
1963 static void
1964 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1965 {
1966   tree phi;
1967
1968   /* Since this block is no longer reachable, we can just delete all
1969      of its PHI nodes.  */
1970   phi = phi_nodes (bb);
1971   while (phi)
1972     {
1973       tree next = PHI_CHAIN (phi);
1974       remove_phi_node (phi, NULL_TREE, bb);
1975       phi = next;
1976     }
1977
1978   /* Remove edges to BB's successors.  */
1979   while (EDGE_COUNT (bb->succs) > 0)
1980     remove_edge (EDGE_SUCC (bb, 0));
1981 }
1982
1983
1984 /* Remove statements of basic block BB.  */
1985
1986 static void
1987 remove_bb (basic_block bb)
1988 {
1989   block_stmt_iterator i;
1990   source_locus loc = 0;
1991
1992   if (dump_file)
1993     {
1994       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1995       if (dump_flags & TDF_DETAILS)
1996         {
1997           dump_bb (bb, dump_file, 0);
1998           fprintf (dump_file, "\n");
1999         }
2000     }
2001
2002   /* Remove all the instructions in the block.  */
2003   for (i = bsi_start (bb); !bsi_end_p (i);)
2004     {
2005       tree stmt = bsi_stmt (i);
2006       if (TREE_CODE (stmt) == LABEL_EXPR
2007           && FORCED_LABEL (LABEL_EXPR_LABEL (stmt)))
2008         {
2009           basic_block new_bb = bb->prev_bb;
2010           block_stmt_iterator new_bsi = bsi_start (new_bb);
2011
2012           bsi_remove (&i);
2013           bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
2014         }
2015       else
2016         {
2017           release_defs (stmt);
2018
2019           set_bb_for_stmt (stmt, NULL);
2020           bsi_remove (&i);
2021         }
2022
2023       /* Don't warn for removed gotos.  Gotos are often removed due to
2024          jump threading, thus resulting in bogus warnings.  Not great,
2025          since this way we lose warnings for gotos in the original
2026          program that are indeed unreachable.  */
2027       if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
2028         {
2029           source_locus t;
2030
2031 #ifdef USE_MAPPED_LOCATION
2032           t = EXPR_LOCATION (stmt);
2033 #else
2034           t = EXPR_LOCUS (stmt);
2035 #endif
2036           if (t && LOCATION_LINE (*t) > 0)
2037             loc = t;
2038         }
2039     }
2040
2041   /* If requested, give a warning that the first statement in the
2042      block is unreachable.  We walk statements backwards in the
2043      loop above, so the last statement we process is the first statement
2044      in the block.  */
2045   if (warn_notreached && loc)
2046 #ifdef USE_MAPPED_LOCATION
2047     warning ("%Hwill never be executed", &loc);
2048 #else
2049     warning ("%Hwill never be executed", loc);
2050 #endif
2051
2052   remove_phi_nodes_and_edges_for_unreachable_block (bb);
2053 }
2054
2055 /* Try to remove superfluous control structures.  */
2056
2057 static bool
2058 cleanup_control_flow (void)
2059 {
2060   basic_block bb;
2061   block_stmt_iterator bsi;
2062   bool retval = false;
2063   tree stmt, call;
2064
2065   FOR_EACH_BB (bb)
2066     {
2067       bsi = bsi_last (bb);
2068
2069       if (bsi_end_p (bsi))
2070         continue;
2071
2072       stmt = bsi_stmt (bsi);
2073       if (TREE_CODE (stmt) == COND_EXPR
2074           || TREE_CODE (stmt) == SWITCH_EXPR)
2075         retval |= cleanup_control_expr_graph (bb, bsi);
2076
2077       /* Check for indirect calls that have been turned into
2078          noreturn calls.  */
2079       call = get_call_expr_in (stmt);
2080       if (call != 0
2081           && (call_expr_flags (call) & ECF_NORETURN) != 0
2082           && remove_fallthru_edge (bb->succs))
2083         {
2084           free_dominance_info (CDI_DOMINATORS);
2085           retval = true;
2086         }
2087     }
2088   return retval;
2089 }
2090
2091
2092 /* Disconnect an unreachable block in the control expression starting
2093    at block BB.  */
2094
2095 static bool
2096 cleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi)
2097 {
2098   edge taken_edge;
2099   bool retval = false;
2100   tree expr = bsi_stmt (bsi), val;
2101
2102   if (EDGE_COUNT (bb->succs) > 1)
2103     {
2104       edge e;
2105       edge_iterator ei;
2106
2107       switch (TREE_CODE (expr))
2108         {
2109         case COND_EXPR:
2110           val = COND_EXPR_COND (expr);
2111           break;
2112
2113         case SWITCH_EXPR:
2114           val = SWITCH_COND (expr);
2115           if (TREE_CODE (val) != INTEGER_CST)
2116             return false;
2117           break;
2118
2119         default:
2120           gcc_unreachable ();
2121         }
2122
2123       taken_edge = find_taken_edge (bb, val);
2124       if (!taken_edge)
2125         return false;
2126
2127       /* Remove all the edges except the one that is always executed.  */
2128       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2129         {
2130           if (e != taken_edge)
2131             {
2132               taken_edge->probability += e->probability;
2133               taken_edge->count += e->count;
2134               remove_edge (e);
2135               retval = true;
2136             }
2137           else
2138             ei_next (&ei);
2139         }
2140       if (taken_edge->probability > REG_BR_PROB_BASE)
2141         taken_edge->probability = REG_BR_PROB_BASE;
2142     }
2143   else
2144     taken_edge = EDGE_SUCC (bb, 0);
2145
2146   bsi_remove (&bsi);
2147   taken_edge->flags = EDGE_FALLTHRU;
2148
2149   /* We removed some paths from the cfg.  */
2150   free_dominance_info (CDI_DOMINATORS);
2151
2152   return retval;
2153 }
2154
2155 /* Remove any fallthru edge from EV.  Return true if an edge was removed.  */
2156
2157 static bool
2158 remove_fallthru_edge (VEC(edge) *ev)
2159 {
2160   edge_iterator ei;
2161   edge e;
2162
2163   FOR_EACH_EDGE (e, ei, ev)
2164     if ((e->flags & EDGE_FALLTHRU) != 0)
2165       {
2166         remove_edge (e);
2167         return true;
2168       }
2169   return false;
2170 }
2171
2172 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2173    predicate VAL, return the edge that will be taken out of the block.
2174    If VAL does not match a unique edge, NULL is returned.  */
2175
2176 edge
2177 find_taken_edge (basic_block bb, tree val)
2178 {
2179   tree stmt;
2180
2181   stmt = last_stmt (bb);
2182
2183   gcc_assert (stmt);
2184   gcc_assert (is_ctrl_stmt (stmt));
2185   gcc_assert (val);
2186
2187   /* If VAL is a predicate of the form N RELOP N, where N is an
2188      SSA_NAME, we can usually determine its truth value.  */
2189   if (COMPARISON_CLASS_P (val))
2190     val = fold (val);
2191
2192   /* If VAL is not a constant, we can't determine which edge might
2193      be taken.  */
2194   if (!really_constant_p (val))
2195     return NULL;
2196
2197   if (TREE_CODE (stmt) == COND_EXPR)
2198     return find_taken_edge_cond_expr (bb, val);
2199
2200   if (TREE_CODE (stmt) == SWITCH_EXPR)
2201     return find_taken_edge_switch_expr (bb, val);
2202
2203   gcc_unreachable ();
2204 }
2205
2206
2207 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2208    statement, determine which of the two edges will be taken out of the
2209    block.  Return NULL if either edge may be taken.  */
2210
2211 static edge
2212 find_taken_edge_cond_expr (basic_block bb, tree val)
2213 {
2214   edge true_edge, false_edge;
2215
2216   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2217
2218   /* Otherwise, try to determine which branch of the if() will be taken.
2219      If VAL is a constant but it can't be reduced to a 0 or a 1, then
2220      we don't really know which edge will be taken at runtime.  This
2221      may happen when comparing addresses (e.g., if (&var1 == 4)).  */
2222   if (integer_nonzerop (val))
2223     return true_edge;
2224   else if (integer_zerop (val))
2225     return false_edge;
2226   else
2227     return NULL;
2228 }
2229
2230
2231 /* Given a constant value VAL and the entry block BB to a SWITCH_EXPR
2232    statement, determine which edge will be taken out of the block.  Return
2233    NULL if any edge may be taken.  */
2234
2235 static edge
2236 find_taken_edge_switch_expr (basic_block bb, tree val)
2237 {
2238   tree switch_expr, taken_case;
2239   basic_block dest_bb;
2240   edge e;
2241
2242   if (TREE_CODE (val) != INTEGER_CST)
2243     return NULL;
2244
2245   switch_expr = last_stmt (bb);
2246   taken_case = find_case_label_for_value (switch_expr, val);
2247   dest_bb = label_to_block (CASE_LABEL (taken_case));
2248
2249   e = find_edge (bb, dest_bb);
2250   gcc_assert (e);
2251   return e;
2252 }
2253
2254
2255 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2256    We can make optimal use here of the fact that the case labels are
2257    sorted: We can do a binary search for a case matching VAL.  */
2258
2259 static tree
2260 find_case_label_for_value (tree switch_expr, tree val)
2261 {
2262   tree vec = SWITCH_LABELS (switch_expr);
2263   size_t low, high, n = TREE_VEC_LENGTH (vec);
2264   tree default_case = TREE_VEC_ELT (vec, n - 1);
2265
2266   for (low = -1, high = n - 1; high - low > 1; )
2267     {
2268       size_t i = (high + low) / 2;
2269       tree t = TREE_VEC_ELT (vec, i);
2270       int cmp;
2271
2272       /* Cache the result of comparing CASE_LOW and val.  */
2273       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2274
2275       if (cmp > 0)
2276         high = i;
2277       else
2278         low = i;
2279
2280       if (CASE_HIGH (t) == NULL)
2281         {
2282           /* A singe-valued case label.  */
2283           if (cmp == 0)
2284             return t;
2285         }
2286       else
2287         {
2288           /* A case range.  We can only handle integer ranges.  */
2289           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2290             return t;
2291         }
2292     }
2293
2294   return default_case;
2295 }
2296
2297
2298 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
2299    those alternatives are equal in each of the PHI nodes, then return
2300    true, else return false.  */
2301
2302 static bool
2303 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
2304 {
2305   int n1 = e1->dest_idx;
2306   int n2 = e2->dest_idx;
2307   tree phi;
2308
2309   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
2310     {
2311       tree val1 = PHI_ARG_DEF (phi, n1);
2312       tree val2 = PHI_ARG_DEF (phi, n2);
2313
2314       gcc_assert (val1 != NULL_TREE);
2315       gcc_assert (val2 != NULL_TREE);
2316
2317       if (!operand_equal_for_phi_arg_p (val1, val2))
2318         return false;
2319     }
2320
2321   return true;
2322 }
2323
2324
2325 /*---------------------------------------------------------------------------
2326                               Debugging functions
2327 ---------------------------------------------------------------------------*/
2328
2329 /* Dump tree-specific information of block BB to file OUTF.  */
2330
2331 void
2332 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2333 {
2334   dump_generic_bb (outf, bb, indent, TDF_VOPS);
2335 }
2336
2337
2338 /* Dump a basic block on stderr.  */
2339
2340 void
2341 debug_tree_bb (basic_block bb)
2342 {
2343   dump_bb (bb, stderr, 0);
2344 }
2345
2346
2347 /* Dump basic block with index N on stderr.  */
2348
2349 basic_block
2350 debug_tree_bb_n (int n)
2351 {
2352   debug_tree_bb (BASIC_BLOCK (n));
2353   return BASIC_BLOCK (n);
2354 }
2355
2356
2357 /* Dump the CFG on stderr.
2358
2359    FLAGS are the same used by the tree dumping functions
2360    (see TDF_* in tree.h).  */
2361
2362 void
2363 debug_tree_cfg (int flags)
2364 {
2365   dump_tree_cfg (stderr, flags);
2366 }
2367
2368
2369 /* Dump the program showing basic block boundaries on the given FILE.
2370
2371    FLAGS are the same used by the tree dumping functions (see TDF_* in
2372    tree.h).  */
2373
2374 void
2375 dump_tree_cfg (FILE *file, int flags)
2376 {
2377   if (flags & TDF_DETAILS)
2378     {
2379       const char *funcname
2380         = lang_hooks.decl_printable_name (current_function_decl, 2);
2381
2382       fputc ('\n', file);
2383       fprintf (file, ";; Function %s\n\n", funcname);
2384       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2385                n_basic_blocks, n_edges, last_basic_block);
2386
2387       brief_dump_cfg (file);
2388       fprintf (file, "\n");
2389     }
2390
2391   if (flags & TDF_STATS)
2392     dump_cfg_stats (file);
2393
2394   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2395 }
2396
2397
2398 /* Dump CFG statistics on FILE.  */
2399
2400 void
2401 dump_cfg_stats (FILE *file)
2402 {
2403   static long max_num_merged_labels = 0;
2404   unsigned long size, total = 0;
2405   int n_edges;
2406   basic_block bb;
2407   const char * const fmt_str   = "%-30s%-13s%12s\n";
2408   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2409   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2410   const char *funcname
2411     = lang_hooks.decl_printable_name (current_function_decl, 2);
2412
2413
2414   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2415
2416   fprintf (file, "---------------------------------------------------------\n");
2417   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2418   fprintf (file, fmt_str, "", "  instances  ", "used ");
2419   fprintf (file, "---------------------------------------------------------\n");
2420
2421   size = n_basic_blocks * sizeof (struct basic_block_def);
2422   total += size;
2423   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2424            SCALE (size), LABEL (size));
2425
2426   n_edges = 0;
2427   FOR_EACH_BB (bb)
2428     n_edges += EDGE_COUNT (bb->succs);
2429   size = n_edges * sizeof (struct edge_def);
2430   total += size;
2431   fprintf (file, fmt_str_1, "Edges", n_edges, SCALE (size), LABEL (size));
2432
2433   size = n_basic_blocks * sizeof (struct bb_ann_d);
2434   total += size;
2435   fprintf (file, fmt_str_1, "Basic block annotations", n_basic_blocks,
2436            SCALE (size), LABEL (size));
2437
2438   fprintf (file, "---------------------------------------------------------\n");
2439   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2440            LABEL (total));
2441   fprintf (file, "---------------------------------------------------------\n");
2442   fprintf (file, "\n");
2443
2444   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2445     max_num_merged_labels = cfg_stats.num_merged_labels;
2446
2447   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2448            cfg_stats.num_merged_labels, max_num_merged_labels);
2449
2450   fprintf (file, "\n");
2451 }
2452
2453
2454 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2455    linked in the final executable.  */
2456
2457 void
2458 debug_cfg_stats (void)
2459 {
2460   dump_cfg_stats (stderr);
2461 }
2462
2463
2464 /* Dump the flowgraph to a .vcg FILE.  */
2465
2466 static void
2467 tree_cfg2vcg (FILE *file)
2468 {
2469   edge e;
2470   edge_iterator ei;
2471   basic_block bb;
2472   const char *funcname
2473     = lang_hooks.decl_printable_name (current_function_decl, 2);
2474
2475   /* Write the file header.  */
2476   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2477   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2478   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2479
2480   /* Write blocks and edges.  */
2481   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2482     {
2483       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2484                e->dest->index);
2485
2486       if (e->flags & EDGE_FAKE)
2487         fprintf (file, " linestyle: dotted priority: 10");
2488       else
2489         fprintf (file, " linestyle: solid priority: 100");
2490
2491       fprintf (file, " }\n");
2492     }
2493   fputc ('\n', file);
2494
2495   FOR_EACH_BB (bb)
2496     {
2497       enum tree_code head_code, end_code;
2498       const char *head_name, *end_name;
2499       int head_line = 0;
2500       int end_line = 0;
2501       tree first = first_stmt (bb);
2502       tree last = last_stmt (bb);
2503
2504       if (first)
2505         {
2506           head_code = TREE_CODE (first);
2507           head_name = tree_code_name[head_code];
2508           head_line = get_lineno (first);
2509         }
2510       else
2511         head_name = "no-statement";
2512
2513       if (last)
2514         {
2515           end_code = TREE_CODE (last);
2516           end_name = tree_code_name[end_code];
2517           end_line = get_lineno (last);
2518         }
2519       else
2520         end_name = "no-statement";
2521
2522       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2523                bb->index, bb->index, head_name, head_line, end_name,
2524                end_line);
2525
2526       FOR_EACH_EDGE (e, ei, bb->succs)
2527         {
2528           if (e->dest == EXIT_BLOCK_PTR)
2529             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2530           else
2531             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2532
2533           if (e->flags & EDGE_FAKE)
2534             fprintf (file, " priority: 10 linestyle: dotted");
2535           else
2536             fprintf (file, " priority: 100 linestyle: solid");
2537
2538           fprintf (file, " }\n");
2539         }
2540
2541       if (bb->next_bb != EXIT_BLOCK_PTR)
2542         fputc ('\n', file);
2543     }
2544
2545   fputs ("}\n\n", file);
2546 }
2547
2548
2549
2550 /*---------------------------------------------------------------------------
2551                              Miscellaneous helpers
2552 ---------------------------------------------------------------------------*/
2553
2554 /* Return true if T represents a stmt that always transfers control.  */
2555
2556 bool
2557 is_ctrl_stmt (tree t)
2558 {
2559   return (TREE_CODE (t) == COND_EXPR
2560           || TREE_CODE (t) == SWITCH_EXPR
2561           || TREE_CODE (t) == GOTO_EXPR
2562           || TREE_CODE (t) == RETURN_EXPR
2563           || TREE_CODE (t) == RESX_EXPR);
2564 }
2565
2566
2567 /* Return true if T is a statement that may alter the flow of control
2568    (e.g., a call to a non-returning function).  */
2569
2570 bool
2571 is_ctrl_altering_stmt (tree t)
2572 {
2573   tree call;
2574
2575   gcc_assert (t);
2576   call = get_call_expr_in (t);
2577   if (call)
2578     {
2579       /* A non-pure/const CALL_EXPR alters flow control if the current
2580          function has nonlocal labels.  */
2581       if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
2582         return true;
2583
2584       /* A CALL_EXPR also alters control flow if it does not return.  */
2585       if (call_expr_flags (call) & ECF_NORETURN)
2586         return true;
2587     }
2588
2589   /* If a statement can throw, it alters control flow.  */
2590   return tree_can_throw_internal (t);
2591 }
2592
2593
2594 /* Return true if T is a computed goto.  */
2595
2596 bool
2597 computed_goto_p (tree t)
2598 {
2599   return (TREE_CODE (t) == GOTO_EXPR
2600           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2601 }
2602
2603
2604 /* Checks whether EXPR is a simple local goto.  */
2605
2606 bool
2607 simple_goto_p (tree expr)
2608 {
2609   return (TREE_CODE (expr) == GOTO_EXPR
2610           && TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL);
2611 }
2612
2613
2614 /* Return true if T should start a new basic block.  PREV_T is the
2615    statement preceding T.  It is used when T is a label or a case label.
2616    Labels should only start a new basic block if their previous statement
2617    wasn't a label.  Otherwise, sequence of labels would generate
2618    unnecessary basic blocks that only contain a single label.  */
2619
2620 static inline bool
2621 stmt_starts_bb_p (tree t, tree prev_t)
2622 {
2623   enum tree_code code;
2624
2625   if (t == NULL_TREE)
2626     return false;
2627
2628   /* LABEL_EXPRs start a new basic block only if the preceding
2629      statement wasn't a label of the same type.  This prevents the
2630      creation of consecutive blocks that have nothing but a single
2631      label.  */
2632   code = TREE_CODE (t);
2633   if (code == LABEL_EXPR)
2634     {
2635       /* Nonlocal and computed GOTO targets always start a new block.  */
2636       if (code == LABEL_EXPR
2637           && (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2638               || FORCED_LABEL (LABEL_EXPR_LABEL (t))))
2639         return true;
2640
2641       if (prev_t && TREE_CODE (prev_t) == code)
2642         {
2643           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2644             return true;
2645
2646           cfg_stats.num_merged_labels++;
2647           return false;
2648         }
2649       else
2650         return true;
2651     }
2652
2653   return false;
2654 }
2655
2656
2657 /* Return true if T should end a basic block.  */
2658
2659 bool
2660 stmt_ends_bb_p (tree t)
2661 {
2662   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2663 }
2664
2665
2666 /* Add gotos that used to be represented implicitly in the CFG.  */
2667
2668 void
2669 disband_implicit_edges (void)
2670 {
2671   basic_block bb;
2672   block_stmt_iterator last;
2673   edge e;
2674   edge_iterator ei;
2675   tree stmt, label;
2676
2677   FOR_EACH_BB (bb)
2678     {
2679       last = bsi_last (bb);
2680       stmt = last_stmt (bb);
2681
2682       if (stmt && TREE_CODE (stmt) == COND_EXPR)
2683         {
2684           /* Remove superfluous gotos from COND_EXPR branches.  Moved
2685              from cfg_remove_useless_stmts here since it violates the
2686              invariants for tree--cfg correspondence and thus fits better
2687              here where we do it anyway.  */
2688           e = find_edge (bb, bb->next_bb);
2689           if (e)
2690             {
2691               if (e->flags & EDGE_TRUE_VALUE)
2692                 COND_EXPR_THEN (stmt) = build_empty_stmt ();
2693               else if (e->flags & EDGE_FALSE_VALUE)
2694                 COND_EXPR_ELSE (stmt) = build_empty_stmt ();
2695               else
2696                 gcc_unreachable ();
2697               e->flags |= EDGE_FALLTHRU;
2698             }
2699
2700           continue;
2701         }
2702
2703       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
2704         {
2705           /* Remove the RETURN_EXPR if we may fall though to the exit
2706              instead.  */
2707           gcc_assert (EDGE_COUNT (bb->succs) == 1);
2708           gcc_assert (EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR);
2709
2710           if (bb->next_bb == EXIT_BLOCK_PTR
2711               && !TREE_OPERAND (stmt, 0))
2712             {
2713               bsi_remove (&last);
2714               EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
2715             }
2716           continue;
2717         }
2718
2719       /* There can be no fallthru edge if the last statement is a control
2720          one.  */
2721       if (stmt && is_ctrl_stmt (stmt))
2722         continue;
2723
2724       /* Find a fallthru edge and emit the goto if necessary.  */
2725       FOR_EACH_EDGE (e, ei, bb->succs)
2726         if (e->flags & EDGE_FALLTHRU)
2727           break;
2728
2729       if (!e || e->dest == bb->next_bb)
2730         continue;
2731
2732       gcc_assert (e->dest != EXIT_BLOCK_PTR);
2733       label = tree_block_label (e->dest);
2734
2735       stmt = build1 (GOTO_EXPR, void_type_node, label);
2736 #ifdef USE_MAPPED_LOCATION
2737       SET_EXPR_LOCATION (stmt, e->goto_locus);
2738 #else
2739       SET_EXPR_LOCUS (stmt, e->goto_locus);
2740 #endif
2741       bsi_insert_after (&last, stmt, BSI_NEW_STMT);
2742       e->flags &= ~EDGE_FALLTHRU;
2743     }
2744 }
2745
2746 /* Remove block annotations and other datastructures.  */
2747
2748 void
2749 delete_tree_cfg_annotations (void)
2750 {
2751   basic_block bb;
2752   if (n_basic_blocks > 0)
2753     free_blocks_annotations ();
2754
2755   label_to_block_map = NULL;
2756   free_rbi_pool ();
2757   FOR_EACH_BB (bb)
2758     bb->rbi = NULL;
2759 }
2760
2761
2762 /* Return the first statement in basic block BB.  */
2763
2764 tree
2765 first_stmt (basic_block bb)
2766 {
2767   block_stmt_iterator i = bsi_start (bb);
2768   return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2769 }
2770
2771
2772 /* Return the last statement in basic block BB.  */
2773
2774 tree
2775 last_stmt (basic_block bb)
2776 {
2777   block_stmt_iterator b = bsi_last (bb);
2778   return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2779 }
2780
2781
2782 /* Return a pointer to the last statement in block BB.  */
2783
2784 tree *
2785 last_stmt_ptr (basic_block bb)
2786 {
2787   block_stmt_iterator last = bsi_last (bb);
2788   return !bsi_end_p (last) ? bsi_stmt_ptr (last) : NULL;
2789 }
2790
2791
2792 /* Return the last statement of an otherwise empty block.  Return NULL
2793    if the block is totally empty, or if it contains more than one
2794    statement.  */
2795
2796 tree
2797 last_and_only_stmt (basic_block bb)
2798 {
2799   block_stmt_iterator i = bsi_last (bb);
2800   tree last, prev;
2801
2802   if (bsi_end_p (i))
2803     return NULL_TREE;
2804
2805   last = bsi_stmt (i);
2806   bsi_prev (&i);
2807   if (bsi_end_p (i))
2808     return last;
2809
2810   /* Empty statements should no longer appear in the instruction stream.
2811      Everything that might have appeared before should be deleted by
2812      remove_useless_stmts, and the optimizers should just bsi_remove
2813      instead of smashing with build_empty_stmt.
2814
2815      Thus the only thing that should appear here in a block containing
2816      one executable statement is a label.  */
2817   prev = bsi_stmt (i);
2818   if (TREE_CODE (prev) == LABEL_EXPR)
2819     return last;
2820   else
2821     return NULL_TREE;
2822 }
2823
2824
2825 /* Mark BB as the basic block holding statement T.  */
2826
2827 void
2828 set_bb_for_stmt (tree t, basic_block bb)
2829 {
2830   if (TREE_CODE (t) == PHI_NODE)
2831     PHI_BB (t) = bb;
2832   else if (TREE_CODE (t) == STATEMENT_LIST)
2833     {
2834       tree_stmt_iterator i;
2835       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2836         set_bb_for_stmt (tsi_stmt (i), bb);
2837     }
2838   else
2839     {
2840       stmt_ann_t ann = get_stmt_ann (t);
2841       ann->bb = bb;
2842
2843       /* If the statement is a label, add the label to block-to-labels map
2844          so that we can speed up edge creation for GOTO_EXPRs.  */
2845       if (TREE_CODE (t) == LABEL_EXPR)
2846         {
2847           int uid;
2848
2849           t = LABEL_EXPR_LABEL (t);
2850           uid = LABEL_DECL_UID (t);
2851           if (uid == -1)
2852             {
2853               LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
2854               if (VARRAY_SIZE (label_to_block_map) <= (unsigned) uid)
2855                 VARRAY_GROW (label_to_block_map, 3 * uid / 2);
2856             }
2857           else
2858             /* We're moving an existing label.  Make sure that we've
2859                 removed it from the old block.  */
2860             gcc_assert (!bb || !VARRAY_BB (label_to_block_map, uid));
2861           VARRAY_BB (label_to_block_map, uid) = bb;
2862         }
2863     }
2864 }
2865
2866 /* Finds iterator for STMT.  */
2867
2868 extern block_stmt_iterator
2869 bsi_for_stmt (tree stmt)
2870 {
2871   block_stmt_iterator bsi;
2872
2873   for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2874     if (bsi_stmt (bsi) == stmt)
2875       return bsi;
2876
2877   gcc_unreachable ();
2878 }
2879
2880 /* Insert statement (or statement list) T before the statement
2881    pointed-to by iterator I.  M specifies how to update iterator I
2882    after insertion (see enum bsi_iterator_update).  */
2883
2884 void
2885 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2886 {
2887   set_bb_for_stmt (t, i->bb);
2888   tsi_link_before (&i->tsi, t, m);
2889   modify_stmt (t);
2890 }
2891
2892
2893 /* Insert statement (or statement list) T after the statement
2894    pointed-to by iterator I.  M specifies how to update iterator I
2895    after insertion (see enum bsi_iterator_update).  */
2896
2897 void
2898 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2899 {
2900   set_bb_for_stmt (t, i->bb);
2901   tsi_link_after (&i->tsi, t, m);
2902   modify_stmt (t);
2903 }
2904
2905
2906 /* Remove the statement pointed to by iterator I.  The iterator is updated
2907    to the next statement.  */
2908
2909 void
2910 bsi_remove (block_stmt_iterator *i)
2911 {
2912   tree t = bsi_stmt (*i);
2913   set_bb_for_stmt (t, NULL);
2914   tsi_delink (&i->tsi);
2915 }
2916
2917
2918 /* Move the statement at FROM so it comes right after the statement at TO.  */
2919
2920 void
2921 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2922 {
2923   tree stmt = bsi_stmt (*from);
2924   bsi_remove (from);
2925   bsi_insert_after (to, stmt, BSI_SAME_STMT);
2926 }
2927
2928
2929 /* Move the statement at FROM so it comes right before the statement at TO.  */
2930
2931 void
2932 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2933 {
2934   tree stmt = bsi_stmt (*from);
2935   bsi_remove (from);
2936   bsi_insert_before (to, stmt, BSI_SAME_STMT);
2937 }
2938
2939
2940 /* Move the statement at FROM to the end of basic block BB.  */
2941
2942 void
2943 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2944 {
2945   block_stmt_iterator last = bsi_last (bb);
2946
2947   /* Have to check bsi_end_p because it could be an empty block.  */
2948   if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2949     bsi_move_before (from, &last);
2950   else
2951     bsi_move_after (from, &last);
2952 }
2953
2954
2955 /* Replace the contents of the statement pointed to by iterator BSI
2956    with STMT.  If PRESERVE_EH_INFO is true, the exception handling
2957    information of the original statement is preserved.  */
2958
2959 void
2960 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool preserve_eh_info)
2961 {
2962   int eh_region;
2963   tree orig_stmt = bsi_stmt (*bsi);
2964
2965   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2966   set_bb_for_stmt (stmt, bsi->bb);
2967
2968   /* Preserve EH region information from the original statement, if
2969      requested by the caller.  */
2970   if (preserve_eh_info)
2971     {
2972       eh_region = lookup_stmt_eh_region (orig_stmt);
2973       if (eh_region >= 0)
2974         add_stmt_to_eh_region (stmt, eh_region);
2975     }
2976
2977   *bsi_stmt_ptr (*bsi) = stmt;
2978   modify_stmt (stmt);
2979 }
2980
2981
2982 /* Insert the statement pointed-to by BSI into edge E.  Every attempt
2983    is made to place the statement in an existing basic block, but
2984    sometimes that isn't possible.  When it isn't possible, the edge is
2985    split and the statement is added to the new block.
2986
2987    In all cases, the returned *BSI points to the correct location.  The
2988    return value is true if insertion should be done after the location,
2989    or false if it should be done before the location.  If new basic block
2990    has to be created, it is stored in *NEW_BB.  */
2991
2992 static bool
2993 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2994                            basic_block *new_bb)
2995 {
2996   basic_block dest, src;
2997   tree tmp;
2998
2999   dest = e->dest;
3000  restart:
3001
3002   /* If the destination has one predecessor which has no PHI nodes,
3003      insert there.  Except for the exit block.
3004
3005      The requirement for no PHI nodes could be relaxed.  Basically we
3006      would have to examine the PHIs to prove that none of them used
3007      the value set by the statement we want to insert on E.  That
3008      hardly seems worth the effort.  */
3009   if (EDGE_COUNT (dest->preds) == 1
3010       && ! phi_nodes (dest)
3011       && dest != EXIT_BLOCK_PTR)
3012     {
3013       *bsi = bsi_start (dest);
3014       if (bsi_end_p (*bsi))
3015         return true;
3016
3017       /* Make sure we insert after any leading labels.  */
3018       tmp = bsi_stmt (*bsi);
3019       while (TREE_CODE (tmp) == LABEL_EXPR)
3020         {
3021           bsi_next (bsi);
3022           if (bsi_end_p (*bsi))
3023             break;
3024           tmp = bsi_stmt (*bsi);
3025         }
3026
3027       if (bsi_end_p (*bsi))
3028         {
3029           *bsi = bsi_last (dest);
3030           return true;
3031         }
3032       else
3033         return false;
3034     }
3035
3036   /* If the source has one successor, the edge is not abnormal and
3037      the last statement does not end a basic block, insert there.
3038      Except for the entry block.  */
3039   src = e->src;
3040   if ((e->flags & EDGE_ABNORMAL) == 0
3041       && EDGE_COUNT (src->succs) == 1
3042       && src != ENTRY_BLOCK_PTR)
3043     {
3044       *bsi = bsi_last (src);
3045       if (bsi_end_p (*bsi))
3046         return true;
3047
3048       tmp = bsi_stmt (*bsi);
3049       if (!stmt_ends_bb_p (tmp))
3050         return true;
3051
3052       /* Insert code just before returning the value.  We may need to decompose
3053          the return in the case it contains non-trivial operand.  */
3054       if (TREE_CODE (tmp) == RETURN_EXPR)
3055         {
3056           tree op = TREE_OPERAND (tmp, 0);
3057           if (!is_gimple_val (op))
3058             {
3059               gcc_assert (TREE_CODE (op) == MODIFY_EXPR);
3060               bsi_insert_before (bsi, op, BSI_NEW_STMT);
3061               TREE_OPERAND (tmp, 0) = TREE_OPERAND (op, 0);
3062             }
3063           bsi_prev (bsi);
3064           return true;
3065         }
3066     }
3067
3068   /* Otherwise, create a new basic block, and split this edge.  */
3069   dest = split_edge (e);
3070   if (new_bb)
3071     *new_bb = dest;
3072   e = EDGE_PRED (dest, 0);
3073   goto restart;
3074 }
3075
3076
3077 /* This routine will commit all pending edge insertions, creating any new
3078    basic blocks which are necessary.  */
3079
3080 void
3081 bsi_commit_edge_inserts (void)
3082 {
3083   basic_block bb;
3084   edge e;
3085   edge_iterator ei;
3086
3087   bsi_commit_one_edge_insert (EDGE_SUCC (ENTRY_BLOCK_PTR, 0), NULL);
3088
3089   FOR_EACH_BB (bb)
3090     FOR_EACH_EDGE (e, ei, bb->succs)
3091       bsi_commit_one_edge_insert (e, NULL);
3092 }
3093
3094
3095 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
3096    to this block, otherwise set it to NULL.  */
3097
3098 void
3099 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
3100 {
3101   if (new_bb)
3102     *new_bb = NULL;
3103   if (PENDING_STMT (e))
3104     {
3105       block_stmt_iterator bsi;
3106       tree stmt = PENDING_STMT (e);
3107
3108       PENDING_STMT (e) = NULL_TREE;
3109
3110       if (tree_find_edge_insert_loc (e, &bsi, new_bb))
3111         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3112       else
3113         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3114     }
3115 }
3116
3117
3118 /* Add STMT to the pending list of edge E.  No actual insertion is
3119    made until a call to bsi_commit_edge_inserts () is made.  */
3120
3121 void
3122 bsi_insert_on_edge (edge e, tree stmt)
3123 {
3124   append_to_statement_list (stmt, &PENDING_STMT (e));
3125 }
3126
3127 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If a new
3128    block has to be created, it is returned.  */
3129
3130 basic_block
3131 bsi_insert_on_edge_immediate (edge e, tree stmt)
3132 {
3133   block_stmt_iterator bsi;
3134   basic_block new_bb = NULL;
3135
3136   gcc_assert (!PENDING_STMT (e));
3137
3138   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3139     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3140   else
3141     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3142
3143   return new_bb;
3144 }
3145
3146 /*---------------------------------------------------------------------------
3147              Tree specific functions for CFG manipulation
3148 ---------------------------------------------------------------------------*/
3149
3150 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
3151
3152 static void
3153 reinstall_phi_args (edge new_edge, edge old_edge)
3154 {
3155   tree var, phi;
3156
3157   if (!PENDING_STMT (old_edge))
3158     return;
3159
3160   for (var = PENDING_STMT (old_edge), phi = phi_nodes (new_edge->dest);
3161        var && phi;
3162        var = TREE_CHAIN (var), phi = PHI_CHAIN (phi))
3163     {
3164       tree result = TREE_PURPOSE (var);
3165       tree arg = TREE_VALUE (var);
3166
3167       gcc_assert (result == PHI_RESULT (phi));
3168
3169       add_phi_arg (phi, arg, new_edge);
3170     }
3171
3172   PENDING_STMT (old_edge) = NULL;
3173 }
3174
3175 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3176    Abort on abnormal edges.  */
3177
3178 static basic_block
3179 tree_split_edge (edge edge_in)
3180 {
3181   basic_block new_bb, after_bb, dest, src;
3182   edge new_edge, e;
3183
3184   /* Abnormal edges cannot be split.  */
3185   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3186
3187   src = edge_in->src;
3188   dest = edge_in->dest;
3189
3190   /* Place the new block in the block list.  Try to keep the new block
3191      near its "logical" location.  This is of most help to humans looking
3192      at debugging dumps.  */
3193   if (dest->prev_bb && find_edge (dest->prev_bb, dest))
3194     after_bb = edge_in->src;
3195   else
3196     after_bb = dest->prev_bb;
3197
3198   new_bb = create_empty_bb (after_bb);
3199   new_bb->frequency = EDGE_FREQUENCY (edge_in);
3200   new_bb->count = edge_in->count;
3201   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3202   new_edge->probability = REG_BR_PROB_BASE;
3203   new_edge->count = edge_in->count;
3204
3205   e = redirect_edge_and_branch (edge_in, new_bb);
3206   gcc_assert (e);
3207   reinstall_phi_args (new_edge, e);
3208
3209   return new_bb;
3210 }
3211
3212
3213 /* Return true when BB has label LABEL in it.  */
3214
3215 static bool
3216 has_label_p (basic_block bb, tree label)
3217 {
3218   block_stmt_iterator bsi;
3219
3220   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3221     {
3222       tree stmt = bsi_stmt (bsi);
3223
3224       if (TREE_CODE (stmt) != LABEL_EXPR)
3225         return false;
3226       if (LABEL_EXPR_LABEL (stmt) == label)
3227         return true;
3228     }
3229   return false;
3230 }
3231
3232
3233 /* Callback for walk_tree, check that all elements with address taken are
3234    properly noticed as such.  */
3235
3236 static tree
3237 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3238 {
3239   tree t = *tp, x;
3240
3241   if (TYPE_P (t))
3242     *walk_subtrees = 0;
3243
3244   /* Check operand N for being valid GIMPLE and give error MSG if not.
3245      We check for constants explicitly since they are not considered
3246      gimple invariants if they overflowed.  */
3247 #define CHECK_OP(N, MSG) \
3248   do { if (!CONSTANT_CLASS_P (TREE_OPERAND (t, N))              \
3249          && !is_gimple_val (TREE_OPERAND (t, N)))               \
3250        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3251
3252   switch (TREE_CODE (t))
3253     {
3254     case SSA_NAME:
3255       if (SSA_NAME_IN_FREE_LIST (t))
3256         {
3257           error ("SSA name in freelist but still referenced");
3258           return *tp;
3259         }
3260       break;
3261
3262     case MODIFY_EXPR:
3263       x = TREE_OPERAND (t, 0);
3264       if (TREE_CODE (x) == BIT_FIELD_REF
3265           && is_gimple_reg (TREE_OPERAND (x, 0)))
3266         {
3267           error ("GIMPLE register modified with BIT_FIELD_REF");
3268           return t;
3269         }
3270       break;
3271
3272     case ADDR_EXPR:
3273       /* Skip any references (they will be checked when we recurse down the
3274          tree) and ensure that any variable used as a prefix is marked
3275          addressable.  */
3276       for (x = TREE_OPERAND (t, 0);
3277            handled_component_p (x);
3278            x = TREE_OPERAND (x, 0))
3279         ;
3280
3281       if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3282         return NULL;
3283       if (!TREE_ADDRESSABLE (x))
3284         {
3285           error ("address taken, but ADDRESSABLE bit not set");
3286           return x;
3287         }
3288       break;
3289
3290     case COND_EXPR:
3291       x = COND_EXPR_COND (t);
3292       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3293         {
3294           error ("non-boolean used in condition");
3295           return x;
3296         }
3297       break;
3298
3299     case NOP_EXPR:
3300     case CONVERT_EXPR:
3301     case FIX_TRUNC_EXPR:
3302     case FIX_CEIL_EXPR:
3303     case FIX_FLOOR_EXPR:
3304     case FIX_ROUND_EXPR:
3305     case FLOAT_EXPR:
3306     case NEGATE_EXPR:
3307     case ABS_EXPR:
3308     case BIT_NOT_EXPR:
3309     case NON_LVALUE_EXPR:
3310     case TRUTH_NOT_EXPR:
3311       CHECK_OP (0, "Invalid operand to unary operator");
3312       break;
3313
3314     case REALPART_EXPR:
3315     case IMAGPART_EXPR:
3316     case COMPONENT_REF:
3317     case ARRAY_REF:
3318     case ARRAY_RANGE_REF:
3319     case BIT_FIELD_REF:
3320     case VIEW_CONVERT_EXPR:
3321       /* We have a nest of references.  Verify that each of the operands
3322          that determine where to reference is either a constant or a variable,
3323          verify that the base is valid, and then show we've already checked
3324          the subtrees.  */
3325       while (handled_component_p (t))
3326         {
3327           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3328             CHECK_OP (2, "Invalid COMPONENT_REF offset operator");
3329           else if (TREE_CODE (t) == ARRAY_REF
3330                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3331             {
3332               CHECK_OP (1, "Invalid array index.");
3333               if (TREE_OPERAND (t, 2))
3334                 CHECK_OP (2, "Invalid array lower bound.");
3335               if (TREE_OPERAND (t, 3))
3336                 CHECK_OP (3, "Invalid array stride.");
3337             }
3338           else if (TREE_CODE (t) == BIT_FIELD_REF)
3339             {
3340               CHECK_OP (1, "Invalid operand to BIT_FIELD_REF");
3341               CHECK_OP (2, "Invalid operand to BIT_FIELD_REF");
3342             }
3343
3344           t = TREE_OPERAND (t, 0);
3345         }
3346
3347       if (!CONSTANT_CLASS_P (t) && !is_gimple_lvalue (t))
3348         {
3349           error ("Invalid reference prefix.");
3350           return t;
3351         }
3352       *walk_subtrees = 0;
3353       break;
3354
3355     case LT_EXPR:
3356     case LE_EXPR:
3357     case GT_EXPR:
3358     case GE_EXPR:
3359     case EQ_EXPR:
3360     case NE_EXPR:
3361     case UNORDERED_EXPR:
3362     case ORDERED_EXPR:
3363     case UNLT_EXPR:
3364     case UNLE_EXPR:
3365     case UNGT_EXPR:
3366     case UNGE_EXPR:
3367     case UNEQ_EXPR:
3368     case LTGT_EXPR:
3369     case PLUS_EXPR:
3370     case MINUS_EXPR:
3371     case MULT_EXPR:
3372     case TRUNC_DIV_EXPR:
3373     case CEIL_DIV_EXPR:
3374     case FLOOR_DIV_EXPR:
3375     case ROUND_DIV_EXPR:
3376     case TRUNC_MOD_EXPR:
3377     case CEIL_MOD_EXPR:
3378     case FLOOR_MOD_EXPR:
3379     case ROUND_MOD_EXPR:
3380     case RDIV_EXPR:
3381     case EXACT_DIV_EXPR:
3382     case MIN_EXPR:
3383     case MAX_EXPR:
3384     case LSHIFT_EXPR:
3385     case RSHIFT_EXPR:
3386     case LROTATE_EXPR:
3387     case RROTATE_EXPR:
3388     case BIT_IOR_EXPR:
3389     case BIT_XOR_EXPR:
3390     case BIT_AND_EXPR:
3391       CHECK_OP (0, "Invalid operand to binary operator");
3392       CHECK_OP (1, "Invalid operand to binary operator");
3393       break;
3394
3395     default:
3396       break;
3397     }
3398   return NULL;
3399
3400 #undef CHECK_OP
3401 }
3402
3403
3404 /* Verify STMT, return true if STMT is not in GIMPLE form.
3405    TODO: Implement type checking.  */
3406
3407 static bool
3408 verify_stmt (tree stmt, bool last_in_block)
3409 {
3410   tree addr;
3411
3412   if (!is_gimple_stmt (stmt))
3413     {
3414       error ("Is not a valid GIMPLE statement.");
3415       goto fail;
3416     }
3417
3418   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3419   if (addr)
3420     {
3421       debug_generic_stmt (addr);
3422       return true;
3423     }
3424
3425   /* If the statement is marked as part of an EH region, then it is
3426      expected that the statement could throw.  Verify that when we
3427      have optimizations that simplify statements such that we prove
3428      that they cannot throw, that we update other data structures
3429      to match.  */
3430   if (lookup_stmt_eh_region (stmt) >= 0)
3431     {
3432       if (!tree_could_throw_p (stmt))
3433         {
3434           error ("Statement marked for throw, but doesn%'t.");
3435           goto fail;
3436         }
3437       if (!last_in_block && tree_can_throw_internal (stmt))
3438         {
3439           error ("Statement marked for throw in middle of block.");
3440           goto fail;
3441         }
3442     }
3443
3444   return false;
3445
3446  fail:
3447   debug_generic_stmt (stmt);
3448   return true;
3449 }
3450
3451
3452 /* Return true when the T can be shared.  */
3453
3454 static bool
3455 tree_node_can_be_shared (tree t)
3456 {
3457   if (IS_TYPE_OR_DECL_P (t)
3458       /* We check for constants explicitly since they are not considered
3459          gimple invariants if they overflowed.  */
3460       || CONSTANT_CLASS_P (t)
3461       || is_gimple_min_invariant (t)
3462       || TREE_CODE (t) == SSA_NAME
3463       || t == error_mark_node)
3464     return true;
3465
3466   if (TREE_CODE (t) == CASE_LABEL_EXPR)
3467     return true;
3468
3469   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3470           /* We check for constants explicitly since they are not considered
3471              gimple invariants if they overflowed.  */
3472           && (CONSTANT_CLASS_P (TREE_OPERAND (t, 1))
3473               || is_gimple_min_invariant (TREE_OPERAND (t, 1))))
3474          || (TREE_CODE (t) == COMPONENT_REF
3475              || TREE_CODE (t) == REALPART_EXPR
3476              || TREE_CODE (t) == IMAGPART_EXPR))
3477     t = TREE_OPERAND (t, 0);
3478
3479   if (DECL_P (t))
3480     return true;
3481
3482   return false;
3483 }
3484
3485
3486 /* Called via walk_trees.  Verify tree sharing.  */
3487
3488 static tree
3489 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3490 {
3491   htab_t htab = (htab_t) data;
3492   void **slot;
3493
3494   if (tree_node_can_be_shared (*tp))
3495     {
3496       *walk_subtrees = false;
3497       return NULL;
3498     }
3499
3500   slot = htab_find_slot (htab, *tp, INSERT);
3501   if (*slot)
3502     return *slot;
3503   *slot = *tp;
3504
3505   return NULL;
3506 }
3507
3508
3509 /* Verify the GIMPLE statement chain.  */
3510
3511 void
3512 verify_stmts (void)
3513 {
3514   basic_block bb;
3515   block_stmt_iterator bsi;
3516   bool err = false;
3517   htab_t htab;
3518   tree addr;
3519
3520   timevar_push (TV_TREE_STMT_VERIFY);
3521   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3522
3523   FOR_EACH_BB (bb)
3524     {
3525       tree phi;
3526       int i;
3527
3528       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3529         {
3530           int phi_num_args = PHI_NUM_ARGS (phi);
3531
3532           for (i = 0; i < phi_num_args; i++)
3533             {
3534               tree t = PHI_ARG_DEF (phi, i);
3535               tree addr;
3536
3537               /* Addressable variables do have SSA_NAMEs but they
3538                  are not considered gimple values.  */
3539               if (TREE_CODE (t) != SSA_NAME
3540                   && TREE_CODE (t) != FUNCTION_DECL
3541                   && !is_gimple_val (t))
3542                 {
3543                   error ("PHI def is not a GIMPLE value");
3544                   debug_generic_stmt (phi);
3545                   debug_generic_stmt (t);
3546                   err |= true;
3547                 }
3548
3549               addr = walk_tree (&t, verify_expr, NULL, NULL);
3550               if (addr)
3551                 {
3552                   debug_generic_stmt (addr);
3553                   err |= true;
3554                 }
3555
3556               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3557               if (addr)
3558                 {
3559                   error ("Incorrect sharing of tree nodes");
3560                   debug_generic_stmt (phi);
3561                   debug_generic_stmt (addr);
3562                   err |= true;
3563                 }
3564             }
3565         }
3566
3567       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3568         {
3569           tree stmt = bsi_stmt (bsi);
3570           bsi_next (&bsi);
3571           err |= verify_stmt (stmt, bsi_end_p (bsi));
3572           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3573           if (addr)
3574             {
3575               error ("Incorrect sharing of tree nodes");
3576               debug_generic_stmt (stmt);
3577               debug_generic_stmt (addr);
3578               err |= true;
3579             }
3580         }
3581     }
3582
3583   if (err)
3584     internal_error ("verify_stmts failed.");
3585
3586   htab_delete (htab);
3587   timevar_pop (TV_TREE_STMT_VERIFY);
3588 }
3589
3590
3591 /* Verifies that the flow information is OK.  */
3592
3593 static int
3594 tree_verify_flow_info (void)
3595 {
3596   int err = 0;
3597   basic_block bb;
3598   block_stmt_iterator bsi;
3599   tree stmt;
3600   edge e;
3601   edge_iterator ei;
3602
3603   if (ENTRY_BLOCK_PTR->stmt_list)
3604     {
3605       error ("ENTRY_BLOCK has a statement list associated with it\n");
3606       err = 1;
3607     }
3608
3609   if (EXIT_BLOCK_PTR->stmt_list)
3610     {
3611       error ("EXIT_BLOCK has a statement list associated with it\n");
3612       err = 1;
3613     }
3614
3615   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
3616     if (e->flags & EDGE_FALLTHRU)
3617       {
3618         error ("Fallthru to exit from bb %d\n", e->src->index);
3619         err = 1;
3620       }
3621
3622   FOR_EACH_BB (bb)
3623     {
3624       bool found_ctrl_stmt = false;
3625
3626       stmt = NULL_TREE;
3627
3628       /* Skip labels on the start of basic block.  */
3629       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3630         {
3631           tree prev_stmt = stmt;
3632
3633           stmt = bsi_stmt (bsi);
3634
3635           if (TREE_CODE (stmt) != LABEL_EXPR)
3636             break;
3637
3638           if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3639             {
3640               error ("Nonlocal label %s is not first "
3641                      "in a sequence of labels in bb %d",
3642                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3643                      bb->index);
3644               err = 1;
3645             }
3646
3647           if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
3648             {
3649               error ("Label %s to block does not match in bb %d\n",
3650                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3651                      bb->index);
3652               err = 1;
3653             }
3654
3655           if (decl_function_context (LABEL_EXPR_LABEL (stmt))
3656               != current_function_decl)
3657             {
3658               error ("Label %s has incorrect context in bb %d\n",
3659                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3660                      bb->index);
3661               err = 1;
3662             }
3663         }
3664
3665       /* Verify that body of basic block BB is free of control flow.  */
3666       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3667         {
3668           tree stmt = bsi_stmt (bsi);
3669
3670           if (found_ctrl_stmt)
3671             {
3672               error ("Control flow in the middle of basic block %d\n",
3673                      bb->index);
3674               err = 1;
3675             }
3676
3677           if (stmt_ends_bb_p (stmt))
3678             found_ctrl_stmt = true;
3679
3680           if (TREE_CODE (stmt) == LABEL_EXPR)
3681             {
3682               error ("Label %s in the middle of basic block %d\n",
3683                      IDENTIFIER_POINTER (DECL_NAME (stmt)),
3684                      bb->index);
3685               err = 1;
3686             }
3687         }
3688       bsi = bsi_last (bb);
3689       if (bsi_end_p (bsi))
3690         continue;
3691
3692       stmt = bsi_stmt (bsi);
3693
3694       if (is_ctrl_stmt (stmt))
3695         {
3696           FOR_EACH_EDGE (e, ei, bb->succs)
3697             if (e->flags & EDGE_FALLTHRU)
3698               {
3699                 error ("Fallthru edge after a control statement in bb %d \n",
3700                        bb->index);
3701                 err = 1;
3702               }
3703         }
3704
3705       switch (TREE_CODE (stmt))
3706         {
3707         case COND_EXPR:
3708           {
3709             edge true_edge;
3710             edge false_edge;
3711             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3712                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3713               {
3714                 error ("Structured COND_EXPR at the end of bb %d\n", bb->index);
3715                 err = 1;
3716               }
3717
3718             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3719
3720             if (!true_edge || !false_edge
3721                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3722                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3723                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3724                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3725                 || EDGE_COUNT (bb->succs) >= 3)
3726               {
3727                 error ("Wrong outgoing edge flags at end of bb %d\n",
3728                        bb->index);
3729                 err = 1;
3730               }
3731
3732             if (!has_label_p (true_edge->dest,
3733                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3734               {
3735                 error ("%<then%> label does not match edge at end of bb %d\n",
3736                        bb->index);
3737                 err = 1;
3738               }
3739
3740             if (!has_label_p (false_edge->dest,
3741                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3742               {
3743                 error ("%<else%> label does not match edge at end of bb %d\n",
3744                        bb->index);
3745                 err = 1;
3746               }
3747           }
3748           break;
3749
3750         case GOTO_EXPR:
3751           if (simple_goto_p (stmt))
3752             {
3753               error ("Explicit goto at end of bb %d\n", bb->index);
3754               err = 1;
3755             }
3756           else
3757             {
3758               /* FIXME.  We should double check that the labels in the
3759                  destination blocks have their address taken.  */
3760               FOR_EACH_EDGE (e, ei, bb->succs)
3761                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3762                                  | EDGE_FALSE_VALUE))
3763                     || !(e->flags & EDGE_ABNORMAL))
3764                   {
3765                     error ("Wrong outgoing edge flags at end of bb %d\n",
3766                            bb->index);
3767                     err = 1;
3768                   }
3769             }
3770           break;
3771
3772         case RETURN_EXPR:
3773           if (EDGE_COUNT (bb->succs) != 1
3774               || (EDGE_SUCC (bb, 0)->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3775                                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3776             {
3777               error ("Wrong outgoing edge flags at end of bb %d\n", bb->index);
3778               err = 1;
3779             }
3780           if (EDGE_SUCC (bb, 0)->dest != EXIT_BLOCK_PTR)
3781             {
3782               error ("Return edge does not point to exit in bb %d\n",
3783                      bb->index);
3784               err = 1;
3785             }
3786           break;
3787
3788         case SWITCH_EXPR:
3789           {
3790             tree prev;
3791             edge e;
3792             size_t i, n;
3793             tree vec;
3794
3795             vec = SWITCH_LABELS (stmt);
3796             n = TREE_VEC_LENGTH (vec);
3797
3798             /* Mark all the destination basic blocks.  */
3799             for (i = 0; i < n; ++i)
3800               {
3801                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3802                 basic_block label_bb = label_to_block (lab);
3803
3804                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
3805                 label_bb->aux = (void *)1;
3806               }
3807
3808             /* Verify that the case labels are sorted.  */
3809             prev = TREE_VEC_ELT (vec, 0);
3810             for (i = 1; i < n - 1; ++i)
3811               {
3812                 tree c = TREE_VEC_ELT (vec, i);
3813                 if (! CASE_LOW (c))
3814                   {
3815                     error ("Found default case not at end of case vector");
3816                     err = 1;
3817                     continue;
3818                   }
3819                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
3820                   {
3821                     error ("Case labels not sorted:\n ");
3822                     print_generic_expr (stderr, prev, 0);
3823                     fprintf (stderr," is greater than ");
3824                     print_generic_expr (stderr, c, 0);
3825                     fprintf (stderr," but comes before it.\n");
3826                     err = 1;
3827                   }
3828                 prev = c;
3829               }
3830             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
3831               {
3832                 error ("No default case found at end of case vector");
3833                 err = 1;
3834               }
3835
3836             FOR_EACH_EDGE (e, ei, bb->succs)
3837               {
3838                 if (!e->dest->aux)
3839                   {
3840                     error ("Extra outgoing edge %d->%d\n",
3841                            bb->index, e->dest->index);
3842                     err = 1;
3843                   }
3844                 e->dest->aux = (void *)2;
3845                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3846                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3847                   {
3848                     error ("Wrong outgoing edge flags at end of bb %d\n",
3849                            bb->index);
3850                     err = 1;
3851                   }
3852               }
3853
3854             /* Check that we have all of them.  */
3855             for (i = 0; i < n; ++i)
3856               {
3857                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3858                 basic_block label_bb = label_to_block (lab);
3859
3860                 if (label_bb->aux != (void *)2)
3861                   {
3862                     error ("Missing edge %i->%i",
3863                            bb->index, label_bb->index);
3864                     err = 1;
3865                   }
3866               }
3867
3868             FOR_EACH_EDGE (e, ei, bb->succs)
3869               e->dest->aux = (void *)0;
3870           }
3871
3872         default: ;
3873         }
3874     }
3875
3876   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
3877     verify_dominators (CDI_DOMINATORS);
3878
3879   return err;
3880 }
3881
3882
3883 /* Updates phi nodes after creating a forwarder block joined
3884    by edge FALLTHRU.  */
3885
3886 static void
3887 tree_make_forwarder_block (edge fallthru)
3888 {
3889   edge e;
3890   edge_iterator ei;
3891   basic_block dummy, bb;
3892   tree phi, new_phi, var;
3893
3894   dummy = fallthru->src;
3895   bb = fallthru->dest;
3896
3897   if (EDGE_COUNT (bb->preds) == 1)
3898     return;
3899
3900   /* If we redirected a branch we must create new phi nodes at the
3901      start of BB.  */
3902   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
3903     {
3904       var = PHI_RESULT (phi);
3905       new_phi = create_phi_node (var, bb);
3906       SSA_NAME_DEF_STMT (var) = new_phi;
3907       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
3908       add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
3909     }
3910
3911   /* Ensure that the PHI node chain is in the same order.  */
3912   set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
3913
3914   /* Add the arguments we have stored on edges.  */
3915   FOR_EACH_EDGE (e, ei, bb->preds)
3916     {
3917       if (e == fallthru)
3918         continue;
3919
3920       flush_pending_stmts (e);
3921     }
3922 }
3923
3924
3925 /* Return true if basic block BB does nothing except pass control
3926    flow to another block and that we can safely insert a label at
3927    the start of the successor block.
3928
3929    As a precondition, we require that BB be not equal to
3930    ENTRY_BLOCK_PTR.  */
3931
3932 static bool
3933 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
3934 {
3935   block_stmt_iterator bsi;
3936
3937   /* BB must have a single outgoing edge.  */
3938   if (EDGE_COUNT (bb->succs) != 1
3939       /* If PHI_WANTED is false, BB must not have any PHI nodes.
3940          Otherwise, BB must have PHI nodes.  */
3941       || (phi_nodes (bb) != NULL_TREE) != phi_wanted
3942       /* BB may not be a predecessor of EXIT_BLOCK_PTR.  */
3943       || EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR
3944       /* Nor should this be an infinite loop.  */
3945       || EDGE_SUCC (bb, 0)->dest == bb
3946       /* BB may not have an abnormal outgoing edge.  */
3947       || (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL))
3948     return false;
3949
3950 #if ENABLE_CHECKING
3951   gcc_assert (bb != ENTRY_BLOCK_PTR);
3952 #endif
3953
3954   /* Now walk through the statements backward.  We can ignore labels,
3955      anything else means this is not a forwarder block.  */
3956   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3957     {
3958       tree stmt = bsi_stmt (bsi);
3959
3960       switch (TREE_CODE (stmt))
3961         {
3962         case LABEL_EXPR:
3963           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3964             return false;
3965           break;
3966
3967         default:
3968           return false;
3969         }
3970     }
3971
3972   if (find_edge (ENTRY_BLOCK_PTR, bb))
3973     return false;
3974
3975   return true;
3976 }
3977
3978 /* Return true if BB has at least one abnormal incoming edge.  */
3979
3980 static inline bool
3981 has_abnormal_incoming_edge_p (basic_block bb)
3982 {
3983   edge e;
3984   edge_iterator ei;
3985
3986   FOR_EACH_EDGE (e, ei, bb->preds)
3987     if (e->flags & EDGE_ABNORMAL)
3988       return true;
3989
3990   return false;
3991 }
3992
3993 /* Removes forwarder block BB.  Returns false if this failed.  If a new
3994    forwarder block is created due to redirection of edges, it is
3995    stored to worklist.  */
3996
3997 static bool
3998 remove_forwarder_block (basic_block bb, basic_block **worklist)
3999 {
4000   edge succ = EDGE_SUCC (bb, 0), e, s;
4001   basic_block dest = succ->dest;
4002   tree label;
4003   tree phi;
4004   edge_iterator ei;
4005   block_stmt_iterator bsi, bsi_to;
4006   bool seen_abnormal_edge = false;
4007
4008   /* We check for infinite loops already in tree_forwarder_block_p.
4009      However it may happen that the infinite loop is created
4010      afterwards due to removal of forwarders.  */
4011   if (dest == bb)
4012     return false;
4013
4014   /* If the destination block consists of a nonlocal label, do not merge
4015      it.  */
4016   label = first_stmt (dest);
4017   if (label
4018       && TREE_CODE (label) == LABEL_EXPR
4019       && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
4020     return false;
4021
4022   /* If there is an abnormal edge to basic block BB, but not into
4023      dest, problems might occur during removal of the phi node at out
4024      of ssa due to overlapping live ranges of registers.
4025
4026      If there is an abnormal edge in DEST, the problems would occur
4027      anyway since cleanup_dead_labels would then merge the labels for
4028      two different eh regions, and rest of exception handling code
4029      does not like it.
4030
4031      So if there is an abnormal edge to BB, proceed only if there is
4032      no abnormal edge to DEST and there are no phi nodes in DEST.  */
4033   if (has_abnormal_incoming_edge_p (bb))
4034     {
4035       seen_abnormal_edge = true;
4036
4037       if (has_abnormal_incoming_edge_p (dest)
4038           || phi_nodes (dest) != NULL_TREE)
4039         return false;
4040     }
4041
4042   /* If there are phi nodes in DEST, and some of the blocks that are
4043      predecessors of BB are also predecessors of DEST, check that the
4044      phi node arguments match.  */
4045   if (phi_nodes (dest))
4046     {
4047       FOR_EACH_EDGE (e, ei, bb->preds)
4048         {
4049           s = find_edge (e->src, dest);
4050           if (!s)
4051             continue;
4052
4053           if (!phi_alternatives_equal (dest, succ, s))
4054             return false;
4055         }
4056     }
4057
4058   /* Redirect the edges.  */
4059   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
4060     {
4061       if (e->flags & EDGE_ABNORMAL)
4062         {
4063           /* If there is an abnormal edge, redirect it anyway, and
4064              move the labels to the new block to make it legal.  */
4065           s = redirect_edge_succ_nodup (e, dest);
4066         }
4067       else
4068         s = redirect_edge_and_branch (e, dest);
4069
4070       if (s == e)
4071         {
4072           /* Create arguments for the phi nodes, since the edge was not
4073              here before.  */
4074           for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
4075             add_phi_arg (phi, PHI_ARG_DEF (phi, succ->dest_idx), s);
4076         }
4077       else
4078         {
4079           /* The source basic block might become a forwarder.  We know
4080              that it was not a forwarder before, since it used to have
4081              at least two outgoing edges, so we may just add it to
4082              worklist.  */
4083           if (tree_forwarder_block_p (s->src, false))
4084             *(*worklist)++ = s->src;
4085         }
4086     }
4087
4088   if (seen_abnormal_edge)
4089     {
4090       /* Move the labels to the new block, so that the redirection of
4091          the abnormal edges works.  */
4092
4093       bsi_to = bsi_start (dest);
4094       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
4095         {
4096           label = bsi_stmt (bsi);
4097           gcc_assert (TREE_CODE (label) == LABEL_EXPR);
4098           bsi_remove (&bsi);
4099           bsi_insert_before (&bsi_to, label, BSI_CONTINUE_LINKING);
4100         }
4101     }
4102
4103   /* Update the dominators.  */
4104   if (dom_info_available_p (CDI_DOMINATORS))
4105     {
4106       basic_block dom, dombb, domdest;
4107
4108       dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
4109       domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
4110       if (domdest == bb)
4111         {
4112           /* Shortcut to avoid calling (relatively expensive)
4113              nearest_common_dominator unless necessary.  */
4114           dom = dombb;
4115         }
4116       else
4117         dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
4118
4119       set_immediate_dominator (CDI_DOMINATORS, dest, dom);
4120     }
4121
4122   /* And kill the forwarder block.  */
4123   delete_basic_block (bb);
4124
4125   return true;
4126 }
4127
4128 /* Removes forwarder blocks.  */
4129
4130 static bool
4131 cleanup_forwarder_blocks (void)
4132 {
4133   basic_block bb;
4134   bool changed = false;
4135   basic_block *worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
4136   basic_block *current = worklist;
4137
4138   FOR_EACH_BB (bb)
4139     {
4140       if (tree_forwarder_block_p (bb, false))
4141         *current++ = bb;
4142     }
4143
4144   while (current != worklist)
4145     {
4146       bb = *--current;
4147       changed |= remove_forwarder_block (bb, &current);
4148     }
4149
4150   free (worklist);
4151   return changed;
4152 }
4153
4154 /* Merge the PHI nodes at BB into those at BB's sole successor.  */
4155
4156 static void
4157 remove_forwarder_block_with_phi (basic_block bb)
4158 {
4159   edge succ = EDGE_SUCC (bb, 0);
4160   basic_block dest = succ->dest;
4161   tree label;
4162   basic_block dombb, domdest, dom;
4163
4164   /* We check for infinite loops already in tree_forwarder_block_p.
4165      However it may happen that the infinite loop is created
4166      afterwards due to removal of forwarders.  */
4167   if (dest == bb)
4168     return;
4169
4170   /* If the destination block consists of a nonlocal label, do not
4171      merge it.  */
4172   label = first_stmt (dest);
4173   if (label
4174       && TREE_CODE (label) == LABEL_EXPR
4175       && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
4176     return;
4177
4178   /* Redirect each incoming edge to BB to DEST.  */
4179   while (EDGE_COUNT (bb->preds) > 0)
4180     {
4181       edge e = EDGE_PRED (bb, 0), s;
4182       tree phi;
4183
4184       s = find_edge (e->src, dest);
4185       if (s)
4186         {
4187           /* We already have an edge S from E->src to DEST.  If S and
4188              E->dest's sole successor edge have the same PHI arguments
4189              at DEST, redirect S to DEST.  */
4190           if (phi_alternatives_equal (dest, s, succ))
4191             {
4192               e = redirect_edge_and_branch (e, dest);
4193               PENDING_STMT (e) = NULL_TREE;
4194               continue;
4195             }
4196
4197           /* PHI arguments are different.  Create a forwarder block by
4198              splitting E so that we can merge PHI arguments on E to
4199              DEST.  */
4200           e = EDGE_SUCC (split_edge (e), 0);
4201         }
4202
4203       s = redirect_edge_and_branch (e, dest);
4204
4205       /* redirect_edge_and_branch must not create a new edge.  */
4206       gcc_assert (s == e);
4207
4208       /* Add to the PHI nodes at DEST each PHI argument removed at the
4209          destination of E.  */
4210       for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
4211         {
4212           tree def = PHI_ARG_DEF (phi, succ->dest_idx);
4213
4214           if (TREE_CODE (def) == SSA_NAME)
4215             {
4216               tree var;
4217
4218               /* If DEF is one of the results of PHI nodes removed during
4219                  redirection, replace it with the PHI argument that used
4220                  to be on E.  */
4221               for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
4222                 {
4223                   tree old_arg = TREE_PURPOSE (var);
4224                   tree new_arg = TREE_VALUE (var);
4225
4226                   if (def == old_arg)
4227                     {
4228                       def = new_arg;
4229                       break;
4230                     }
4231                 }
4232             }
4233
4234           add_phi_arg (phi, def, s);
4235         }
4236
4237       PENDING_STMT (e) = NULL;
4238     }
4239
4240   /* Update the dominators.  */
4241   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
4242   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
4243   if (domdest == bb)
4244     {
4245       /* Shortcut to avoid calling (relatively expensive)
4246          nearest_common_dominator unless necessary.  */
4247       dom = dombb;
4248     }
4249   else
4250     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
4251
4252   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
4253
4254   /* Remove BB since all of BB's incoming edges have been redirected
4255      to DEST.  */
4256   delete_basic_block (bb);
4257 }
4258
4259 /* This pass merges PHI nodes if one feeds into another.  For example,
4260    suppose we have the following:
4261
4262   goto <bb 9> (<L9>);
4263
4264 <L8>:;
4265   tem_17 = foo ();
4266
4267   # tem_6 = PHI <tem_17(8), tem_23(7)>;
4268 <L9>:;
4269
4270   # tem_3 = PHI <tem_6(9), tem_2(5)>;
4271 <L10>:;
4272
4273   Then we merge the first PHI node into the second one like so:
4274
4275   goto <bb 9> (<L10>);
4276
4277 <L8>:;
4278   tem_17 = foo ();
4279
4280   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
4281 <L10>:;
4282 */
4283
4284 static void
4285 merge_phi_nodes (void)
4286 {
4287   basic_block *worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
4288   basic_block *current = worklist;
4289   basic_block bb;
4290
4291   calculate_dominance_info (CDI_DOMINATORS);
4292
4293   /* Find all PHI nodes that we may be able to merge.  */
4294   FOR_EACH_BB (bb)
4295     {
4296       basic_block dest;
4297
4298       /* Look for a forwarder block with PHI nodes.  */
4299       if (!tree_forwarder_block_p (bb, true))
4300         continue;
4301
4302       dest = EDGE_SUCC (bb, 0)->dest;
4303
4304       /* We have to feed into another basic block with PHI
4305          nodes.  */
4306       if (!phi_nodes (dest)
4307           /* We don't want to deal with a basic block with
4308              abnormal edges.  */
4309           || has_abnormal_incoming_edge_p (bb))
4310         continue;
4311
4312       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
4313         {
4314           /* If BB does not dominate DEST, then the PHI nodes at
4315              DEST must be the only users of the results of the PHI
4316              nodes at BB.  */
4317           *current++ = bb;
4318         }
4319     }
4320
4321   /* Now let's drain WORKLIST.  */
4322   while (current != worklist)
4323     {
4324       bb = *--current;
4325       remove_forwarder_block_with_phi (bb);
4326     }
4327
4328   free (worklist);
4329 }
4330
4331 static bool
4332 gate_merge_phi (void)
4333 {
4334   return 1;
4335 }
4336
4337 struct tree_opt_pass pass_merge_phi = {
4338   "mergephi",                   /* name */
4339   gate_merge_phi,               /* gate */
4340   merge_phi_nodes,              /* execute */
4341   NULL,                         /* sub */
4342   NULL,                         /* next */
4343   0,                            /* static_pass_number */
4344   TV_TREE_MERGE_PHI,            /* tv_id */
4345   PROP_cfg | PROP_ssa,          /* properties_required */
4346   0,                            /* properties_provided */
4347   0,                            /* properties_destroyed */
4348   0,                            /* todo_flags_start */
4349   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
4350   | TODO_verify_ssa,
4351   0                             /* letter */
4352 };
4353
4354 /* Return a non-special label in the head of basic block BLOCK.
4355    Create one if it doesn't exist.  */
4356
4357 tree
4358 tree_block_label (basic_block bb)
4359 {
4360   block_stmt_iterator i, s = bsi_start (bb);
4361   bool first = true;
4362   tree label, stmt;
4363
4364   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
4365     {
4366       stmt = bsi_stmt (i);
4367       if (TREE_CODE (stmt) != LABEL_EXPR)
4368         break;
4369       label = LABEL_EXPR_LABEL (stmt);
4370       if (!DECL_NONLOCAL (label))
4371         {
4372           if (!first)
4373             bsi_move_before (&i, &s);
4374           return label;
4375         }
4376     }
4377
4378   label = create_artificial_label ();
4379   stmt = build1 (LABEL_EXPR, void_type_node, label);
4380   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
4381   return label;
4382 }
4383
4384
4385 /* Attempt to perform edge redirection by replacing a possibly complex
4386    jump instruction by a goto or by removing the jump completely.
4387    This can apply only if all edges now point to the same block.  The
4388    parameters and return values are equivalent to
4389    redirect_edge_and_branch.  */
4390
4391 static edge
4392 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4393 {
4394   basic_block src = e->src;
4395   block_stmt_iterator b;
4396   tree stmt;
4397
4398   /* We can replace or remove a complex jump only when we have exactly
4399      two edges.  */
4400   if (EDGE_COUNT (src->succs) != 2
4401       /* Verify that all targets will be TARGET.  Specifically, the
4402          edge that is not E must also go to TARGET.  */
4403       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4404     return NULL;
4405
4406   b = bsi_last (src);
4407   if (bsi_end_p (b))
4408     return NULL;
4409   stmt = bsi_stmt (b);
4410
4411   if (TREE_CODE (stmt) == COND_EXPR
4412       || TREE_CODE (stmt) == SWITCH_EXPR)
4413     {
4414       bsi_remove (&b);
4415       e = ssa_redirect_edge (e, target);
4416       e->flags = EDGE_FALLTHRU;
4417       return e;
4418     }
4419
4420   return NULL;
4421 }
4422
4423
4424 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4425    edge representing the redirected branch.  */
4426
4427 static edge
4428 tree_redirect_edge_and_branch (edge e, basic_block dest)
4429 {
4430   basic_block bb = e->src;
4431   block_stmt_iterator bsi;
4432   edge ret;
4433   tree label, stmt;
4434
4435   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4436     return NULL;
4437
4438   if (e->src != ENTRY_BLOCK_PTR
4439       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4440     return ret;
4441
4442   if (e->dest == dest)
4443     return NULL;
4444
4445   label = tree_block_label (dest);
4446
4447   bsi = bsi_last (bb);
4448   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4449
4450   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4451     {
4452     case COND_EXPR:
4453       stmt = (e->flags & EDGE_TRUE_VALUE
4454               ? COND_EXPR_THEN (stmt)
4455               : COND_EXPR_ELSE (stmt));
4456       GOTO_DESTINATION (stmt) = label;
4457       break;
4458
4459     case GOTO_EXPR:
4460       /* No non-abnormal edges should lead from a non-simple goto, and
4461          simple ones should be represented implicitly.  */
4462       gcc_unreachable ();
4463
4464     case SWITCH_EXPR:
4465       {
4466         tree cases = get_cases_for_edge (e, stmt);
4467
4468         /* If we have a list of cases associated with E, then use it
4469            as it's a lot faster than walking the entire case vector.  */
4470         if (cases)
4471           {
4472             edge e2 = find_edge (e->src, dest);
4473             tree last, first;
4474
4475             first = cases;
4476             while (cases)
4477               {
4478                 last = cases;
4479                 CASE_LABEL (cases) = label;
4480                 cases = TREE_CHAIN (cases);
4481               }
4482
4483             /* If there was already an edge in the CFG, then we need
4484                to move all the cases associated with E to E2.  */
4485             if (e2)
4486               {
4487                 tree cases2 = get_cases_for_edge (e2, stmt);
4488
4489                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4490                 TREE_CHAIN (cases2) = first;
4491               }
4492           }
4493         else
4494           {
4495             tree vec = SWITCH_LABELS (stmt);
4496             size_t i, n = TREE_VEC_LENGTH (vec);
4497
4498             for (i = 0; i < n; i++)
4499               {
4500                 tree elt = TREE_VEC_ELT (vec, i);
4501
4502                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4503                   CASE_LABEL (elt) = label;
4504               }
4505           }
4506
4507         break;
4508       }
4509
4510     case RETURN_EXPR:
4511       bsi_remove (&bsi);
4512       e->flags |= EDGE_FALLTHRU;
4513       break;
4514
4515     default:
4516       /* Otherwise it must be a fallthru edge, and we don't need to
4517          do anything besides redirecting it.  */
4518       gcc_assert (e->flags & EDGE_FALLTHRU);
4519       break;
4520     }
4521
4522   /* Update/insert PHI nodes as necessary.  */
4523
4524   /* Now update the edges in the CFG.  */
4525   e = ssa_redirect_edge (e, dest);
4526
4527   return e;
4528 }
4529
4530
4531 /* Simple wrapper, as we can always redirect fallthru edges.  */
4532
4533 static basic_block
4534 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4535 {
4536   e = tree_redirect_edge_and_branch (e, dest);
4537   gcc_assert (e);
4538
4539   return NULL;
4540 }
4541
4542
4543 /* Splits basic block BB after statement STMT (but at least after the
4544    labels).  If STMT is NULL, BB is split just after the labels.  */
4545
4546 static basic_block
4547 tree_split_block (basic_block bb, void *stmt)
4548 {
4549   block_stmt_iterator bsi, bsi_tgt;
4550   tree act;
4551   basic_block new_bb;
4552   edge e;
4553   edge_iterator ei;
4554
4555   new_bb = create_empty_bb (bb);
4556
4557   /* Redirect the outgoing edges.  */
4558   new_bb->succs = bb->succs;
4559   bb->succs = NULL;
4560   FOR_EACH_EDGE (e, ei, new_bb->succs)
4561     e->src = new_bb;
4562
4563   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4564     stmt = NULL;
4565
4566   /* Move everything from BSI to the new basic block.  */
4567   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4568     {
4569       act = bsi_stmt (bsi);
4570       if (TREE_CODE (act) == LABEL_EXPR)
4571         continue;
4572
4573       if (!stmt)
4574         break;
4575
4576       if (stmt == act)
4577         {
4578           bsi_next (&bsi);
4579           break;
4580         }
4581     }
4582
4583   bsi_tgt = bsi_start (new_bb);
4584   while (!bsi_end_p (bsi))
4585     {
4586       act = bsi_stmt (bsi);
4587       bsi_remove (&bsi);
4588       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
4589     }
4590
4591   return new_bb;
4592 }
4593
4594
4595 /* Moves basic block BB after block AFTER.  */
4596
4597 static bool
4598 tree_move_block_after (basic_block bb, basic_block after)
4599 {
4600   if (bb->prev_bb == after)
4601     return true;
4602
4603   unlink_block (bb);
4604   link_block (bb, after);
4605
4606   return true;
4607 }
4608
4609
4610 /* Return true if basic_block can be duplicated.  */
4611
4612 static bool
4613 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4614 {
4615   return true;
4616 }
4617
4618 /* Create a duplicate of the basic block BB.  NOTE: This does not
4619    preserve SSA form.  */
4620
4621 static basic_block
4622 tree_duplicate_bb (basic_block bb)
4623 {
4624   basic_block new_bb;
4625   block_stmt_iterator bsi, bsi_tgt;
4626   tree phi, val;
4627   ssa_op_iter op_iter;
4628
4629   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4630
4631   /* First copy the phi nodes.  We do not copy phi node arguments here,
4632      since the edges are not ready yet.  Keep the chain of phi nodes in
4633      the same order, so that we can add them later.  */
4634   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4635     {
4636       mark_for_rewrite (PHI_RESULT (phi));
4637       create_phi_node (PHI_RESULT (phi), new_bb);
4638     }
4639   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
4640
4641   bsi_tgt = bsi_start (new_bb);
4642   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4643     {
4644       tree stmt = bsi_stmt (bsi);
4645       tree copy;
4646
4647       if (TREE_CODE (stmt) == LABEL_EXPR)
4648         continue;
4649
4650       /* Record the definitions.  */
4651       get_stmt_operands (stmt);
4652
4653       FOR_EACH_SSA_TREE_OPERAND (val, stmt, op_iter, SSA_OP_ALL_DEFS)
4654         mark_for_rewrite (val);
4655
4656       copy = unshare_expr (stmt);
4657
4658       /* Copy also the virtual operands.  */
4659       get_stmt_ann (copy);
4660       copy_virtual_operands (copy, stmt);
4661
4662       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4663     }
4664
4665   return new_bb;
4666 }
4667
4668 /* Basic block BB_COPY was created by code duplication.  Add phi node
4669    arguments for edges going out of BB_COPY.  The blocks that were
4670    duplicated have rbi->duplicated set to one.  */
4671
4672 void
4673 add_phi_args_after_copy_bb (basic_block bb_copy)
4674 {
4675   basic_block bb, dest;
4676   edge e, e_copy;
4677   edge_iterator ei;
4678   tree phi, phi_copy, phi_next, def;
4679
4680   bb = bb_copy->rbi->original;
4681
4682   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
4683     {
4684       if (!phi_nodes (e_copy->dest))
4685         continue;
4686
4687       if (e_copy->dest->rbi->duplicated)
4688         dest = e_copy->dest->rbi->original;
4689       else
4690         dest = e_copy->dest;
4691
4692       e = find_edge (bb, dest);
4693       if (!e)
4694         {
4695           /* During loop unrolling the target of the latch edge is copied.
4696              In this case we are not looking for edge to dest, but to
4697              duplicated block whose original was dest.  */
4698           FOR_EACH_EDGE (e, ei, bb->succs)
4699             if (e->dest->rbi->duplicated
4700                 && e->dest->rbi->original == dest)
4701               break;
4702
4703           gcc_assert (e != NULL);
4704         }
4705
4706       for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
4707            phi;
4708            phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
4709         {
4710           phi_next = PHI_CHAIN (phi);
4711
4712           gcc_assert (PHI_RESULT (phi) == PHI_RESULT (phi_copy));
4713           def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4714           add_phi_arg (phi_copy, def, e_copy);
4715         }
4716     }
4717 }
4718
4719 /* Blocks in REGION_COPY array of length N_REGION were created by
4720    duplication of basic blocks.  Add phi node arguments for edges
4721    going from these blocks.  */
4722
4723 void
4724 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
4725 {
4726   unsigned i;
4727
4728   for (i = 0; i < n_region; i++)
4729     region_copy[i]->rbi->duplicated = 1;
4730
4731   for (i = 0; i < n_region; i++)
4732     add_phi_args_after_copy_bb (region_copy[i]);
4733
4734   for (i = 0; i < n_region; i++)
4735     region_copy[i]->rbi->duplicated = 0;
4736 }
4737
4738 /* Maps the old ssa name FROM_NAME to TO_NAME.  */
4739
4740 struct ssa_name_map_entry
4741 {
4742   tree from_name;
4743   tree to_name;
4744 };
4745
4746 /* Hash function for ssa_name_map_entry.  */
4747
4748 static hashval_t
4749 ssa_name_map_entry_hash (const void *entry)
4750 {
4751   const struct ssa_name_map_entry *en = entry;
4752   return SSA_NAME_VERSION (en->from_name);
4753 }
4754
4755 /* Equality function for ssa_name_map_entry.  */
4756
4757 static int
4758 ssa_name_map_entry_eq (const void *in_table, const void *ssa_name)
4759 {
4760   const struct ssa_name_map_entry *en = in_table;
4761
4762   return en->from_name == ssa_name;
4763 }
4764
4765 /* Allocate duplicates of ssa names in list DEFINITIONS and store the mapping
4766    to MAP.  */
4767
4768 void
4769 allocate_ssa_names (bitmap definitions, htab_t *map)
4770 {
4771   tree name;
4772   struct ssa_name_map_entry *entry;
4773   PTR *slot;
4774   unsigned ver;
4775   bitmap_iterator bi;
4776
4777   if (!*map)
4778     *map = htab_create (10, ssa_name_map_entry_hash,
4779                         ssa_name_map_entry_eq, free);
4780   EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
4781     {
4782       name = ssa_name (ver);
4783       slot = htab_find_slot_with_hash (*map, name, SSA_NAME_VERSION (name),
4784                                        INSERT);
4785       if (*slot)
4786         entry = *slot;
4787       else
4788         {
4789           entry = xmalloc (sizeof (struct ssa_name_map_entry));
4790           entry->from_name = name;
4791           *slot = entry;
4792         }
4793       entry->to_name = duplicate_ssa_name (name, SSA_NAME_DEF_STMT (name));
4794     }
4795 }
4796
4797 /* Rewrite the definition DEF in statement STMT to new ssa name as specified
4798    by the mapping MAP.  */
4799
4800 static void
4801 rewrite_to_new_ssa_names_def (def_operand_p def, tree stmt, htab_t map)
4802 {
4803   tree name = DEF_FROM_PTR (def);
4804   struct ssa_name_map_entry *entry;
4805
4806   gcc_assert (TREE_CODE (name) == SSA_NAME);
4807
4808   entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
4809   if (!entry)
4810     return;
4811
4812   SET_DEF (def, entry->to_name);
4813   SSA_NAME_DEF_STMT (entry->to_name) = stmt;
4814 }
4815
4816 /* Rewrite the USE to new ssa name as specified by the mapping MAP.  */
4817
4818 static void
4819 rewrite_to_new_ssa_names_use (use_operand_p use, htab_t map)
4820 {
4821   tree name = USE_FROM_PTR (use);
4822   struct ssa_name_map_entry *entry;
4823
4824   if (TREE_CODE (name) != SSA_NAME)
4825     return;
4826
4827   entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
4828   if (!entry)
4829     return;
4830
4831   SET_USE (use, entry->to_name);
4832 }
4833
4834 /* Rewrite the ssa names in basic block BB to new ones as specified by the
4835    mapping MAP.  */
4836
4837 void
4838 rewrite_to_new_ssa_names_bb (basic_block bb, htab_t map)
4839 {
4840   unsigned i;
4841   edge e;
4842   edge_iterator ei;
4843   tree phi, stmt;
4844   block_stmt_iterator bsi;
4845   use_optype uses;
4846   vuse_optype vuses;
4847   def_optype defs;
4848   v_may_def_optype v_may_defs;
4849   v_must_def_optype v_must_defs;
4850   stmt_ann_t ann;
4851
4852   FOR_EACH_EDGE (e, ei, bb->preds)
4853     if (e->flags & EDGE_ABNORMAL)
4854       break;
4855
4856   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4857     {
4858       rewrite_to_new_ssa_names_def (PHI_RESULT_PTR (phi), phi, map);
4859       if (e)
4860         SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
4861     }
4862
4863   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4864     {
4865       stmt = bsi_stmt (bsi);
4866       get_stmt_operands (stmt);
4867       ann = stmt_ann (stmt);
4868
4869       uses = USE_OPS (ann);
4870       for (i = 0; i < NUM_USES (uses); i++)
4871         rewrite_to_new_ssa_names_use (USE_OP_PTR (uses, i), map);
4872
4873       defs = DEF_OPS (ann);
4874       for (i = 0; i < NUM_DEFS (defs); i++)
4875         rewrite_to_new_ssa_names_def (DEF_OP_PTR (defs, i), stmt, map);
4876
4877       vuses = VUSE_OPS (ann);
4878       for (i = 0; i < NUM_VUSES (vuses); i++)
4879         rewrite_to_new_ssa_names_use (VUSE_OP_PTR (vuses, i), map);
4880
4881       v_may_defs = V_MAY_DEF_OPS (ann);
4882       for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
4883         {
4884           rewrite_to_new_ssa_names_use
4885                   (V_MAY_DEF_OP_PTR (v_may_defs, i), map);
4886           rewrite_to_new_ssa_names_def
4887                   (V_MAY_DEF_RESULT_PTR (v_may_defs, i), stmt, map);
4888         }
4889
4890       v_must_defs = V_MUST_DEF_OPS (ann);
4891       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
4892         {
4893           rewrite_to_new_ssa_names_def
4894             (V_MUST_DEF_RESULT_PTR (v_must_defs, i), stmt, map);
4895           rewrite_to_new_ssa_names_use
4896             (V_MUST_DEF_KILL_PTR (v_must_defs, i),  map);
4897         }
4898     }
4899
4900   FOR_EACH_EDGE (e, ei, bb->succs)
4901     for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
4902       {
4903         rewrite_to_new_ssa_names_use
4904                 (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e), map);
4905
4906         if (e->flags & EDGE_ABNORMAL)
4907           {
4908             tree op = PHI_ARG_DEF_FROM_EDGE (phi, e);
4909             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op) = 1;
4910           }
4911       }
4912 }
4913
4914 /* Rewrite the ssa names in N_REGION blocks REGION to the new ones as specified
4915    by the mapping MAP.  */
4916
4917 void
4918 rewrite_to_new_ssa_names (basic_block *region, unsigned n_region, htab_t map)
4919 {
4920   unsigned r;
4921
4922   for (r = 0; r < n_region; r++)
4923     rewrite_to_new_ssa_names_bb (region[r], map);
4924 }
4925
4926 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
4927    important exit edge EXIT.  By important we mean that no SSA name defined
4928    inside region is live over the other exit edges of the region.  All entry
4929    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
4930    to the duplicate of the region.  SSA form, dominance and loop information
4931    is updated.  The new basic blocks are stored to REGION_COPY in the same
4932    order as they had in REGION, provided that REGION_COPY is not NULL.
4933    The function returns false if it is unable to copy the region,
4934    true otherwise.  */
4935
4936 bool
4937 tree_duplicate_sese_region (edge entry, edge exit,
4938                             basic_block *region, unsigned n_region,
4939                             basic_block *region_copy)
4940 {
4941   unsigned i, n_doms, ver;
4942   bool free_region_copy = false, copying_header = false;
4943   struct loop *loop = entry->dest->loop_father;
4944   edge exit_copy;
4945   bitmap definitions;
4946   tree phi;
4947   basic_block *doms;
4948   htab_t ssa_name_map = NULL;
4949   edge redirected;
4950   bitmap_iterator bi;
4951
4952   if (!can_copy_bbs_p (region, n_region))
4953     return false;
4954
4955   /* Some sanity checking.  Note that we do not check for all possible
4956      missuses of the functions.  I.e. if you ask to copy something weird,
4957      it will work, but the state of structures probably will not be
4958      correct.  */
4959
4960   for (i = 0; i < n_region; i++)
4961     {
4962       /* We do not handle subloops, i.e. all the blocks must belong to the
4963          same loop.  */
4964       if (region[i]->loop_father != loop)
4965         return false;
4966
4967       if (region[i] != entry->dest
4968           && region[i] == loop->header)
4969         return false;
4970     }
4971
4972   loop->copy = loop;
4973
4974   /* In case the function is used for loop header copying (which is the primary
4975      use), ensure that EXIT and its copy will be new latch and entry edges.  */
4976   if (loop->header == entry->dest)
4977     {
4978       copying_header = true;
4979       loop->copy = loop->outer;
4980
4981       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
4982         return false;
4983
4984       for (i = 0; i < n_region; i++)
4985         if (region[i] != exit->src
4986             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
4987           return false;
4988     }
4989
4990   if (!region_copy)
4991     {
4992       region_copy = xmalloc (sizeof (basic_block) * n_region);
4993       free_region_copy = true;
4994     }
4995
4996   gcc_assert (!any_marked_for_rewrite_p ());
4997
4998   /* Record blocks outside the region that are duplicated by something
4999      inside.  */
5000   doms = xmalloc (sizeof (basic_block) * n_basic_blocks);
5001   n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
5002
5003   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
5004   definitions = marked_ssa_names ();
5005
5006   if (copying_header)
5007     {
5008       loop->header = exit->dest;
5009       loop->latch = exit->src;
5010     }
5011
5012   /* Redirect the entry and add the phi node arguments.  */
5013   redirected = redirect_edge_and_branch (entry, entry->dest->rbi->copy);
5014   gcc_assert (redirected != NULL);
5015   flush_pending_stmts (entry);
5016
5017   /* Concerning updating of dominators:  We must recount dominators
5018      for entry block and its copy.  Anything that is outside of the region, but
5019      was dominated by something inside needs recounting as well.  */
5020   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5021   doms[n_doms++] = entry->dest->rbi->original;
5022   iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
5023   free (doms);
5024
5025   /* Add the other phi node arguments.  */
5026   add_phi_args_after_copy (region_copy, n_region);
5027
5028   /* Add phi nodes for definitions at exit.  TODO -- once we have immediate
5029      uses, it should be possible to emit phi nodes just for definitions that
5030      are used outside region.  */
5031   EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
5032     {
5033       tree name = ssa_name (ver);
5034
5035       phi = create_phi_node (name, exit->dest);
5036       add_phi_arg (phi, name, exit);
5037       add_phi_arg (phi, name, exit_copy);
5038
5039       SSA_NAME_DEF_STMT (name) = phi;
5040     }
5041
5042   /* And create new definitions inside region and its copy.  TODO -- once we
5043      have immediate uses, it might be better to leave definitions in region
5044      unchanged, create new ssa names for phi nodes on exit, and rewrite
5045      the uses, to avoid changing the copied region.  */
5046   allocate_ssa_names (definitions, &ssa_name_map);
5047   rewrite_to_new_ssa_names (region, n_region, ssa_name_map);
5048   allocate_ssa_names (definitions, &ssa_name_map);
5049   rewrite_to_new_ssa_names (region_copy, n_region, ssa_name_map);
5050   htab_delete (ssa_name_map);
5051
5052   if (free_region_copy)
5053     free (region_copy);
5054
5055   unmark_all_for_rewrite ();
5056   BITMAP_XFREE (definitions);
5057
5058   return true;
5059 }
5060
5061 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
5062
5063 void
5064 dump_function_to_file (tree fn, FILE *file, int flags)
5065 {
5066   tree arg, vars, var;
5067   bool ignore_topmost_bind = false, any_var = false;
5068   basic_block bb;
5069   tree chain;
5070
5071   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
5072
5073   arg = DECL_ARGUMENTS (fn);
5074   while (arg)
5075     {
5076       print_generic_expr (file, arg, dump_flags);
5077       if (TREE_CHAIN (arg))
5078         fprintf (file, ", ");
5079       arg = TREE_CHAIN (arg);
5080     }
5081   fprintf (file, ")\n");
5082
5083   if (flags & TDF_RAW)
5084     {
5085       dump_node (fn, TDF_SLIM | flags, file);
5086       return;
5087     }
5088
5089   /* When GIMPLE is lowered, the variables are no longer available in
5090      BIND_EXPRs, so display them separately.  */
5091   if (cfun && cfun->unexpanded_var_list)
5092     {
5093       ignore_topmost_bind = true;
5094
5095       fprintf (file, "{\n");
5096       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
5097         {
5098           var = TREE_VALUE (vars);
5099
5100           print_generic_decl (file, var, flags);
5101           fprintf (file, "\n");
5102
5103           any_var = true;
5104         }
5105     }
5106
5107   if (basic_block_info)
5108     {
5109       /* Make a CFG based dump.  */
5110       check_bb_profile (ENTRY_BLOCK_PTR, file);
5111       if (!ignore_topmost_bind)
5112         fprintf (file, "{\n");
5113
5114       if (any_var && n_basic_blocks)
5115         fprintf (file, "\n");
5116
5117       FOR_EACH_BB (bb)
5118         dump_generic_bb (file, bb, 2, flags);
5119
5120       fprintf (file, "}\n");
5121       check_bb_profile (EXIT_BLOCK_PTR, file);
5122     }
5123   else
5124     {
5125       int indent;
5126
5127       /* Make a tree based dump.  */
5128       chain = DECL_SAVED_TREE (fn);
5129
5130       if (TREE_CODE (chain) == BIND_EXPR)
5131         {
5132           if (ignore_topmost_bind)
5133             {
5134               chain = BIND_EXPR_BODY (chain);
5135               indent = 2;
5136             }
5137           else
5138             indent = 0;
5139         }
5140       else
5141         {
5142           if (!ignore_topmost_bind)
5143             fprintf (file, "{\n");
5144           indent = 2;
5145         }
5146
5147       if (any_var)
5148         fprintf (file, "\n");
5149
5150       print_generic_stmt_indented (file, chain, flags, indent);
5151       if (ignore_topmost_bind)
5152         fprintf (file, "}\n");
5153     }
5154
5155   fprintf (file, "\n\n");
5156 }
5157
5158
5159 /* Pretty print of the loops intermediate representation.  */
5160 static void print_loop (FILE *, struct loop *, int);
5161 static void print_pred_bbs (FILE *, basic_block bb);
5162 static void print_succ_bbs (FILE *, basic_block bb);
5163
5164
5165 /* Print the predecessors indexes of edge E on FILE.  */
5166
5167 static void
5168 print_pred_bbs (FILE *file, basic_block bb)
5169 {
5170   edge e;
5171   edge_iterator ei;
5172
5173   FOR_EACH_EDGE (e, ei, bb->preds)
5174     fprintf (file, "bb_%d", e->src->index);
5175 }
5176
5177
5178 /* Print the successors indexes of edge E on FILE.  */
5179
5180 static void
5181 print_succ_bbs (FILE *file, basic_block bb)
5182 {
5183   edge e;
5184   edge_iterator ei;
5185
5186   FOR_EACH_EDGE (e, ei, bb->succs)
5187     fprintf (file, "bb_%d", e->src->index);
5188 }
5189
5190
5191 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
5192
5193 static void
5194 print_loop (FILE *file, struct loop *loop, int indent)
5195 {
5196   char *s_indent;
5197   basic_block bb;
5198
5199   if (loop == NULL)
5200     return;
5201
5202   s_indent = (char *) alloca ((size_t) indent + 1);
5203   memset ((void *) s_indent, ' ', (size_t) indent);
5204   s_indent[indent] = '\0';
5205
5206   /* Print the loop's header.  */
5207   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
5208
5209   /* Print the loop's body.  */
5210   fprintf (file, "%s{\n", s_indent);
5211   FOR_EACH_BB (bb)
5212     if (bb->loop_father == loop)
5213       {
5214         /* Print the basic_block's header.  */
5215         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
5216         print_pred_bbs (file, bb);
5217         fprintf (file, "}, succs = {");
5218         print_succ_bbs (file, bb);
5219         fprintf (file, "})\n");
5220
5221         /* Print the basic_block's body.  */
5222         fprintf (file, "%s  {\n", s_indent);
5223         tree_dump_bb (bb, file, indent + 4);
5224         fprintf (file, "%s  }\n", s_indent);
5225       }
5226
5227   print_loop (file, loop->inner, indent + 2);
5228   fprintf (file, "%s}\n", s_indent);
5229   print_loop (file, loop->next, indent);
5230 }
5231
5232
5233 /* Follow a CFG edge from the entry point of the program, and on entry
5234    of a loop, pretty print the loop structure on FILE.  */
5235
5236 void
5237 print_loop_ir (FILE *file)
5238 {
5239   basic_block bb;
5240
5241   bb = BASIC_BLOCK (0);
5242   if (bb && bb->loop_father)
5243     print_loop (file, bb->loop_father, 0);
5244 }
5245
5246
5247 /* Debugging loops structure at tree level.  */
5248
5249 void
5250 debug_loop_ir (void)
5251 {
5252   print_loop_ir (stderr);
5253 }
5254
5255
5256 /* Return true if BB ends with a call, possibly followed by some
5257    instructions that must stay with the call.  Return false,
5258    otherwise.  */
5259
5260 static bool
5261 tree_block_ends_with_call_p (basic_block bb)
5262 {
5263   block_stmt_iterator bsi = bsi_last (bb);
5264   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
5265 }
5266
5267
5268 /* Return true if BB ends with a conditional branch.  Return false,
5269    otherwise.  */
5270
5271 static bool
5272 tree_block_ends_with_condjump_p (basic_block bb)
5273 {
5274   tree stmt = tsi_stmt (bsi_last (bb).tsi);
5275   return (TREE_CODE (stmt) == COND_EXPR);
5276 }
5277
5278
5279 /* Return true if we need to add fake edge to exit at statement T.
5280    Helper function for tree_flow_call_edges_add.  */
5281
5282 static bool
5283 need_fake_edge_p (tree t)
5284 {
5285   tree call;
5286
5287   /* NORETURN and LONGJMP calls already have an edge to exit.
5288      CONST, PURE and ALWAYS_RETURN calls do not need one.
5289      We don't currently check for CONST and PURE here, although
5290      it would be a good idea, because those attributes are
5291      figured out from the RTL in mark_constant_function, and
5292      the counter incrementation code from -fprofile-arcs
5293      leads to different results from -fbranch-probabilities.  */
5294   call = get_call_expr_in (t);
5295   if (call
5296       && !(call_expr_flags (call) & (ECF_NORETURN | ECF_ALWAYS_RETURN)))
5297     return true;
5298
5299   if (TREE_CODE (t) == ASM_EXPR
5300        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
5301     return true;
5302
5303   return false;
5304 }
5305
5306
5307 /* Add fake edges to the function exit for any non constant and non
5308    noreturn calls, volatile inline assembly in the bitmap of blocks
5309    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
5310    the number of blocks that were split.
5311
5312    The goal is to expose cases in which entering a basic block does
5313    not imply that all subsequent instructions must be executed.  */
5314
5315 static int
5316 tree_flow_call_edges_add (sbitmap blocks)
5317 {
5318   int i;
5319   int blocks_split = 0;
5320   int last_bb = last_basic_block;
5321   bool check_last_block = false;
5322
5323   if (n_basic_blocks == 0)
5324     return 0;
5325
5326   if (! blocks)
5327     check_last_block = true;
5328   else
5329     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
5330
5331   /* In the last basic block, before epilogue generation, there will be
5332      a fallthru edge to EXIT.  Special care is required if the last insn
5333      of the last basic block is a call because make_edge folds duplicate
5334      edges, which would result in the fallthru edge also being marked
5335      fake, which would result in the fallthru edge being removed by
5336      remove_fake_edges, which would result in an invalid CFG.
5337
5338      Moreover, we can't elide the outgoing fake edge, since the block
5339      profiler needs to take this into account in order to solve the minimal
5340      spanning tree in the case that the call doesn't return.
5341
5342      Handle this by adding a dummy instruction in a new last basic block.  */
5343   if (check_last_block)
5344     {
5345       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
5346       block_stmt_iterator bsi = bsi_last (bb);
5347       tree t = NULL_TREE;
5348       if (!bsi_end_p (bsi))
5349         t = bsi_stmt (bsi);
5350
5351       if (need_fake_edge_p (t))
5352         {
5353           edge e;
5354
5355           e = find_edge (bb, EXIT_BLOCK_PTR);
5356           if (e)
5357             {
5358               bsi_insert_on_edge (e, build_empty_stmt ());
5359               bsi_commit_edge_inserts ();
5360             }
5361         }
5362     }
5363
5364   /* Now add fake edges to the function exit for any non constant
5365      calls since there is no way that we can determine if they will
5366      return or not...  */
5367   for (i = 0; i < last_bb; i++)
5368     {
5369       basic_block bb = BASIC_BLOCK (i);
5370       block_stmt_iterator bsi;
5371       tree stmt, last_stmt;
5372
5373       if (!bb)
5374         continue;
5375
5376       if (blocks && !TEST_BIT (blocks, i))
5377         continue;
5378
5379       bsi = bsi_last (bb);
5380       if (!bsi_end_p (bsi))
5381         {
5382           last_stmt = bsi_stmt (bsi);
5383           do
5384             {
5385               stmt = bsi_stmt (bsi);
5386               if (need_fake_edge_p (stmt))
5387                 {
5388                   edge e;
5389                   /* The handling above of the final block before the
5390                      epilogue should be enough to verify that there is
5391                      no edge to the exit block in CFG already.
5392                      Calling make_edge in such case would cause us to
5393                      mark that edge as fake and remove it later.  */
5394 #ifdef ENABLE_CHECKING
5395                   if (stmt == last_stmt)
5396                     {
5397                       e = find_edge (bb, EXIT_BLOCK_PTR);
5398                       gcc_assert (e == NULL);
5399                     }
5400 #endif
5401
5402                   /* Note that the following may create a new basic block
5403                      and renumber the existing basic blocks.  */
5404                   if (stmt != last_stmt)
5405                     {
5406                       e = split_block (bb, stmt);
5407                       if (e)
5408                         blocks_split++;
5409                     }
5410                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
5411                 }
5412               bsi_prev (&bsi);
5413             }
5414           while (!bsi_end_p (bsi));
5415         }
5416     }
5417
5418   if (blocks_split)
5419     verify_flow_info ();
5420
5421   return blocks_split;
5422 }
5423
5424 bool
5425 tree_purge_dead_eh_edges (basic_block bb)
5426 {
5427   bool changed = false;
5428   edge e;
5429   edge_iterator ei;
5430   tree stmt = last_stmt (bb);
5431
5432   if (stmt && tree_can_throw_internal (stmt))
5433     return false;
5434
5435   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
5436     {
5437       if (e->flags & EDGE_EH)
5438         {
5439           remove_edge (e);
5440           changed = true;
5441         }
5442       else
5443         ei_next (&ei);
5444     }
5445
5446   /* Removal of dead EH edges might change dominators of not
5447      just immediate successors.  E.g. when bb1 is changed so that
5448      it no longer can throw and bb1->bb3 and bb1->bb4 are dead
5449      eh edges purged by this function in:
5450            0
5451           / \
5452          v   v
5453          1-->2
5454         / \  |
5455        v   v |
5456        3-->4 |
5457         \    v
5458          --->5
5459              |
5460              -
5461      idom(bb5) must be recomputed.  For now just free the dominance
5462      info.  */
5463   if (changed)
5464     free_dominance_info (CDI_DOMINATORS);
5465
5466   return changed;
5467 }
5468
5469 bool
5470 tree_purge_all_dead_eh_edges (bitmap blocks)
5471 {
5472   bool changed = false;
5473   unsigned i;
5474   bitmap_iterator bi;
5475
5476   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
5477     {
5478       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
5479     }
5480
5481   return changed;
5482 }
5483
5484 /* This function is called whenever a new edge is created or
5485    redirected.  */
5486
5487 static void
5488 tree_execute_on_growing_pred (edge e)
5489 {
5490   basic_block bb = e->dest;
5491
5492   if (phi_nodes (bb))
5493     reserve_phi_args_for_new_edge (bb);
5494 }
5495
5496 /* This function is called immediately before edge E is removed from
5497    the edge vector E->dest->preds.  */
5498
5499 static void
5500 tree_execute_on_shrinking_pred (edge e)
5501 {
5502   if (phi_nodes (e->dest))
5503     remove_phi_args (e);
5504 }
5505
5506 struct cfg_hooks tree_cfg_hooks = {
5507   "tree",
5508   tree_verify_flow_info,
5509   tree_dump_bb,                 /* dump_bb  */
5510   create_bb,                    /* create_basic_block  */
5511   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
5512   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
5513   remove_bb,                    /* delete_basic_block  */
5514   tree_split_block,             /* split_block  */
5515   tree_move_block_after,        /* move_block_after  */
5516   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
5517   tree_merge_blocks,            /* merge_blocks  */
5518   tree_predict_edge,            /* predict_edge  */
5519   tree_predicted_by_p,          /* predicted_by_p  */
5520   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
5521   tree_duplicate_bb,            /* duplicate_block  */
5522   tree_split_edge,              /* split_edge  */
5523   tree_make_forwarder_block,    /* make_forward_block  */
5524   NULL,                         /* tidy_fallthru_edge  */
5525   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
5526   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
5527   tree_flow_call_edges_add,     /* flow_call_edges_add */
5528   tree_execute_on_growing_pred, /* execute_on_growing_pred */
5529   tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
5530 };
5531
5532
5533 /* Split all critical edges.  */
5534
5535 static void
5536 split_critical_edges (void)
5537 {
5538   basic_block bb;
5539   edge e;
5540   edge_iterator ei;
5541
5542   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
5543      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
5544      mappings around the calls to split_edge.  */
5545   start_recording_case_labels ();
5546   FOR_ALL_BB (bb)
5547     {
5548       FOR_EACH_EDGE (e, ei, bb->succs)
5549         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
5550           {
5551             split_edge (e);
5552           }
5553     }
5554   end_recording_case_labels ();
5555 }
5556
5557 struct tree_opt_pass pass_split_crit_edges =
5558 {
5559   "crited",                          /* name */
5560   NULL,                          /* gate */
5561   split_critical_edges,          /* execute */
5562   NULL,                          /* sub */
5563   NULL,                          /* next */
5564   0,                             /* static_pass_number */
5565   TV_TREE_SPLIT_EDGES,           /* tv_id */
5566   PROP_cfg,                      /* properties required */
5567   PROP_no_crit_edges,            /* properties_provided */
5568   0,                             /* properties_destroyed */
5569   0,                             /* todo_flags_start */
5570   TODO_dump_func,                /* todo_flags_finish */
5571   0                              /* letter */
5572 };
5573
5574 \f
5575 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
5576    a temporary, make sure and register it to be renamed if necessary,
5577    and finally return the temporary.  Put the statements to compute
5578    EXP before the current statement in BSI.  */
5579
5580 tree
5581 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
5582 {
5583   tree t, new_stmt, orig_stmt;
5584
5585   if (is_gimple_val (exp))
5586     return exp;
5587
5588   t = make_rename_temp (type, NULL);
5589   new_stmt = build (MODIFY_EXPR, type, t, exp);
5590
5591   orig_stmt = bsi_stmt (*bsi);
5592   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
5593   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
5594
5595   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
5596
5597   return t;
5598 }
5599
5600 /* Build a ternary operation and gimplify it.  Emit code before BSI.
5601    Return the gimple_val holding the result.  */
5602
5603 tree
5604 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
5605                  tree type, tree a, tree b, tree c)
5606 {
5607   tree ret;
5608
5609   ret = fold (build3 (code, type, a, b, c));
5610   STRIP_NOPS (ret);
5611
5612   return gimplify_val (bsi, type, ret);
5613 }
5614
5615 /* Build a binary operation and gimplify it.  Emit code before BSI.
5616    Return the gimple_val holding the result.  */
5617
5618 tree
5619 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
5620                  tree type, tree a, tree b)
5621 {
5622   tree ret;
5623
5624   ret = fold (build2 (code, type, a, b));
5625   STRIP_NOPS (ret);
5626
5627   return gimplify_val (bsi, type, ret);
5628 }
5629
5630 /* Build a unary operation and gimplify it.  Emit code before BSI.
5631    Return the gimple_val holding the result.  */
5632
5633 tree
5634 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
5635                  tree a)
5636 {
5637   tree ret;
5638
5639   ret = fold (build1 (code, type, a));
5640   STRIP_NOPS (ret);
5641
5642   return gimplify_val (bsi, type, ret);
5643 }
5644
5645
5646 \f
5647 /* Emit return warnings.  */
5648
5649 static void
5650 execute_warn_function_return (void)
5651 {
5652 #ifdef USE_MAPPED_LOCATION
5653   source_location location;
5654 #else
5655   location_t *locus;
5656 #endif
5657   tree last;
5658   edge e;
5659   edge_iterator ei;
5660
5661   if (warn_missing_noreturn
5662       && !TREE_THIS_VOLATILE (cfun->decl)
5663       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
5664       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
5665     warning ("%Jfunction might be possible candidate for "
5666              "attribute %<noreturn%>",
5667              cfun->decl);
5668
5669   /* If we have a path to EXIT, then we do return.  */
5670   if (TREE_THIS_VOLATILE (cfun->decl)
5671       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
5672     {
5673 #ifdef USE_MAPPED_LOCATION
5674       location = UNKNOWN_LOCATION;
5675 #else
5676       locus = NULL;
5677 #endif
5678       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5679         {
5680           last = last_stmt (e->src);
5681           if (TREE_CODE (last) == RETURN_EXPR
5682 #ifdef USE_MAPPED_LOCATION
5683               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
5684 #else
5685               && (locus = EXPR_LOCUS (last)) != NULL)
5686 #endif
5687             break;
5688         }
5689 #ifdef USE_MAPPED_LOCATION
5690       if (location == UNKNOWN_LOCATION)
5691         location = cfun->function_end_locus;
5692       warning ("%H%<noreturn%> function does return", &location);
5693 #else
5694       if (!locus)
5695         locus = &cfun->function_end_locus;
5696       warning ("%H%<noreturn%> function does return", locus);
5697 #endif
5698     }
5699
5700   /* If we see "return;" in some basic block, then we do reach the end
5701      without returning a value.  */
5702   else if (warn_return_type
5703            && !TREE_NO_WARNING (cfun->decl)
5704            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
5705            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
5706     {
5707       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5708         {
5709           tree last = last_stmt (e->src);
5710           if (TREE_CODE (last) == RETURN_EXPR
5711               && TREE_OPERAND (last, 0) == NULL)
5712             {
5713 #ifdef USE_MAPPED_LOCATION
5714               location = EXPR_LOCATION (last);
5715               if (location == UNKNOWN_LOCATION)
5716                   location = cfun->function_end_locus;
5717               warning ("%Hcontrol reaches end of non-void function", &location);
5718 #else
5719               locus = EXPR_LOCUS (last);
5720               if (!locus)
5721                 locus = &cfun->function_end_locus;
5722               warning ("%Hcontrol reaches end of non-void function", locus);
5723 #endif
5724               TREE_NO_WARNING (cfun->decl) = 1;
5725               break;
5726             }
5727         }
5728     }
5729 }
5730
5731
5732 /* Given a basic block B which ends with a conditional and has
5733    precisely two successors, determine which of the edges is taken if
5734    the conditional is true and which is taken if the conditional is
5735    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
5736
5737 void
5738 extract_true_false_edges_from_block (basic_block b,
5739                                      edge *true_edge,
5740                                      edge *false_edge)
5741 {
5742   edge e = EDGE_SUCC (b, 0);
5743
5744   if (e->flags & EDGE_TRUE_VALUE)
5745     {
5746       *true_edge = e;
5747       *false_edge = EDGE_SUCC (b, 1);
5748     }
5749   else
5750     {
5751       *false_edge = e;
5752       *true_edge = EDGE_SUCC (b, 1);
5753     }
5754 }
5755
5756 struct tree_opt_pass pass_warn_function_return =
5757 {
5758   NULL,                                 /* name */
5759   NULL,                                 /* gate */
5760   execute_warn_function_return,         /* execute */
5761   NULL,                                 /* sub */
5762   NULL,                                 /* next */
5763   0,                                    /* static_pass_number */
5764   0,                                    /* tv_id */
5765   PROP_cfg,                             /* properties_required */
5766   0,                                    /* properties_provided */
5767   0,                                    /* properties_destroyed */
5768   0,                                    /* todo_flags_start */
5769   0,                                    /* todo_flags_finish */
5770   0                                     /* letter */
5771 };
5772
5773 #include "gt-tree-cfg.h"