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