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