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