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