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