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