gcc/tree-cfg.c

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