gcc/tree-cfg.c

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