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 | ECF_LONGJMP))
 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     ssa_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               ssa_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 | ECF_LONGJMP))
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\n",
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   if (find_edge (ENTRY_BLOCK_PTR, bb))
3911     return false;
3912
3913   /* Now walk through the statements.  We can ignore labels, anything else
3914      means this is not a forwarder block.  */
3915   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3916     {
3917       tree stmt = bsi_stmt (bsi);
3918
3919       switch (TREE_CODE (stmt))
3920         {
3921         case LABEL_EXPR:
3922           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3923             return false;
3924           break;
3925
3926         default:
3927           return false;
3928         }
3929     }
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   edge tmp;
4251   block_stmt_iterator b;
4252   tree stmt;
4253   edge_iterator ei;
4254
4255   /* Verify that all targets will be TARGET.  */
4256   FOR_EACH_EDGE (tmp, ei, src->succs)
4257     if (tmp->dest != target && tmp != e)
4258       break;
4259
4260   if (tmp)
4261     return NULL;
4262
4263   b = bsi_last (src);
4264   if (bsi_end_p (b))
4265     return NULL;
4266   stmt = bsi_stmt (b);
4267
4268   if (TREE_CODE (stmt) == COND_EXPR
4269       || TREE_CODE (stmt) == SWITCH_EXPR)
4270     {
4271       bsi_remove (&b);
4272       e = ssa_redirect_edge (e, target);
4273       e->flags = EDGE_FALLTHRU;
4274       return e;
4275     }
4276
4277   return NULL;
4278 }
4279
4280
4281 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4282    edge representing the redirected branch.  */
4283
4284 static edge
4285 tree_redirect_edge_and_branch (edge e, basic_block dest)
4286 {
4287   basic_block bb = e->src;
4288   block_stmt_iterator bsi;
4289   edge ret;
4290   tree label, stmt;
4291
4292   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4293     return NULL;
4294
4295   if (e->src != ENTRY_BLOCK_PTR
4296       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4297     return ret;
4298
4299   if (e->dest == dest)
4300     return NULL;
4301
4302   label = tree_block_label (dest);
4303
4304   bsi = bsi_last (bb);
4305   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4306
4307   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4308     {
4309     case COND_EXPR:
4310       stmt = (e->flags & EDGE_TRUE_VALUE
4311               ? COND_EXPR_THEN (stmt)
4312               : COND_EXPR_ELSE (stmt));
4313       GOTO_DESTINATION (stmt) = label;
4314       break;
4315
4316     case GOTO_EXPR:
4317       /* No non-abnormal edges should lead from a non-simple goto, and
4318          simple ones should be represented implicitly.  */
4319       gcc_unreachable ();
4320
4321     case SWITCH_EXPR:
4322       {
4323         tree cases = get_cases_for_edge (e, stmt);
4324         edge e2 = find_edge (e->src, dest);
4325
4326         /* If we have a list of cases associated with E, then use it
4327            as it's a lot faster than walking the entire case vector.  */
4328         if (cases)
4329           {
4330             tree last, first;
4331
4332             first = cases;
4333             while (cases)
4334               {
4335                 last = cases;
4336                 CASE_LABEL (cases) = label;
4337                 cases = TREE_CHAIN (cases);
4338               }
4339
4340             /* If there was already an edge in the CFG, then we need
4341                to move all the cases associated with E to E2.  */
4342             if (e2)
4343               {
4344                 tree cases2 = get_cases_for_edge (e2, stmt);
4345
4346                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4347                 TREE_CHAIN (cases2) = first;
4348               }
4349           }
4350         else
4351           {
4352             tree vec = SWITCH_LABELS (stmt);
4353             size_t i, n = TREE_VEC_LENGTH (vec);
4354
4355             for (i = 0; i < n; i++)
4356               {
4357                 tree elt = TREE_VEC_ELT (vec, i);
4358
4359                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4360                   CASE_LABEL (elt) = label;
4361               }
4362           }
4363
4364         break;
4365       }
4366
4367     case RETURN_EXPR:
4368       bsi_remove (&bsi);
4369       e->flags |= EDGE_FALLTHRU;
4370       break;
4371
4372     default:
4373       /* Otherwise it must be a fallthru edge, and we don't need to
4374          do anything besides redirecting it.  */
4375       gcc_assert (e->flags & EDGE_FALLTHRU);
4376       break;
4377     }
4378
4379   /* Update/insert PHI nodes as necessary.  */
4380
4381   /* Now update the edges in the CFG.  */
4382   e = ssa_redirect_edge (e, dest);
4383
4384   return e;
4385 }
4386
4387
4388 /* Simple wrapper, as we can always redirect fallthru edges.  */
4389
4390 static basic_block
4391 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4392 {
4393   e = tree_redirect_edge_and_branch (e, dest);
4394   gcc_assert (e);
4395
4396   return NULL;
4397 }
4398
4399
4400 /* Splits basic block BB after statement STMT (but at least after the
4401    labels).  If STMT is NULL, BB is split just after the labels.  */
4402
4403 static basic_block
4404 tree_split_block (basic_block bb, void *stmt)
4405 {
4406   block_stmt_iterator bsi, bsi_tgt;
4407   tree act;
4408   basic_block new_bb;
4409   edge e;
4410   edge_iterator ei;
4411
4412   new_bb = create_empty_bb (bb);
4413
4414   /* Redirect the outgoing edges.  */
4415   new_bb->succs = bb->succs;
4416   bb->succs = NULL;
4417   FOR_EACH_EDGE (e, ei, new_bb->succs)
4418     e->src = new_bb;
4419
4420   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4421     stmt = NULL;
4422
4423   /* Move everything from BSI to the new basic block.  */
4424   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4425     {
4426       act = bsi_stmt (bsi);
4427       if (TREE_CODE (act) == LABEL_EXPR)
4428         continue;
4429
4430       if (!stmt)
4431         break;
4432
4433       if (stmt == act)
4434         {
4435           bsi_next (&bsi);
4436           break;
4437         }
4438     }
4439
4440   bsi_tgt = bsi_start (new_bb);
4441   while (!bsi_end_p (bsi))
4442     {
4443       act = bsi_stmt (bsi);
4444       bsi_remove (&bsi);
4445       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
4446     }
4447
4448   return new_bb;
4449 }
4450
4451
4452 /* Moves basic block BB after block AFTER.  */
4453
4454 static bool
4455 tree_move_block_after (basic_block bb, basic_block after)
4456 {
4457   if (bb->prev_bb == after)
4458     return true;
4459
4460   unlink_block (bb);
4461   link_block (bb, after);
4462
4463   return true;
4464 }
4465
4466
4467 /* Return true if basic_block can be duplicated.  */
4468
4469 static bool
4470 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4471 {
4472   return true;
4473 }
4474
4475 /* Create a duplicate of the basic block BB.  NOTE: This does not
4476    preserve SSA form.  */
4477
4478 static basic_block
4479 tree_duplicate_bb (basic_block bb)
4480 {
4481   basic_block new_bb;
4482   block_stmt_iterator bsi, bsi_tgt;
4483   tree phi, val;
4484   ssa_op_iter op_iter;
4485
4486   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4487
4488   /* First copy the phi nodes.  We do not copy phi node arguments here,
4489      since the edges are not ready yet.  Keep the chain of phi nodes in
4490      the same order, so that we can add them later.  */
4491   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4492     {
4493       mark_for_rewrite (PHI_RESULT (phi));
4494       create_phi_node (PHI_RESULT (phi), new_bb);
4495     }
4496   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
4497
4498   bsi_tgt = bsi_start (new_bb);
4499   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4500     {
4501       tree stmt = bsi_stmt (bsi);
4502       tree copy;
4503
4504       if (TREE_CODE (stmt) == LABEL_EXPR)
4505         continue;
4506
4507       /* Record the definitions.  */
4508       get_stmt_operands (stmt);
4509
4510       FOR_EACH_SSA_TREE_OPERAND (val, stmt, op_iter, SSA_OP_ALL_DEFS)
4511         mark_for_rewrite (val);
4512
4513       copy = unshare_expr (stmt);
4514
4515       /* Copy also the virtual operands.  */
4516       get_stmt_ann (copy);
4517       copy_virtual_operands (copy, stmt);
4518
4519       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4520     }
4521
4522   return new_bb;
4523 }
4524
4525 /* Basic block BB_COPY was created by code duplication.  Add phi node
4526    arguments for edges going out of BB_COPY.  The blocks that were
4527    duplicated have rbi->duplicated set to one.  */
4528
4529 void
4530 add_phi_args_after_copy_bb (basic_block bb_copy)
4531 {
4532   basic_block bb, dest;
4533   edge e, e_copy;
4534   edge_iterator ei;
4535   tree phi, phi_copy, phi_next, def;
4536
4537   bb = bb_copy->rbi->original;
4538
4539   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
4540     {
4541       if (!phi_nodes (e_copy->dest))
4542         continue;
4543
4544       if (e_copy->dest->rbi->duplicated)
4545         dest = e_copy->dest->rbi->original;
4546       else
4547         dest = e_copy->dest;
4548
4549       e = find_edge (bb, dest);
4550       if (!e)
4551         {
4552           /* During loop unrolling the target of the latch edge is copied.
4553              In this case we are not looking for edge to dest, but to
4554              duplicated block whose original was dest.  */
4555           FOR_EACH_EDGE (e, ei, bb->succs)
4556             if (e->dest->rbi->duplicated
4557                 && e->dest->rbi->original == dest)
4558               break;
4559
4560           gcc_assert (e != NULL);
4561         }
4562
4563       for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
4564            phi;
4565            phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
4566         {
4567           phi_next = PHI_CHAIN (phi);
4568
4569           gcc_assert (PHI_RESULT (phi) == PHI_RESULT (phi_copy));
4570           def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4571           add_phi_arg (&phi_copy, def, e_copy);
4572         }
4573     }
4574 }
4575
4576 /* Blocks in REGION_COPY array of length N_REGION were created by
4577    duplication of basic blocks.  Add phi node arguments for edges
4578    going from these blocks.  */
4579
4580 void
4581 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
4582 {
4583   unsigned i;
4584
4585   for (i = 0; i < n_region; i++)
4586     region_copy[i]->rbi->duplicated = 1;
4587
4588   for (i = 0; i < n_region; i++)
4589     add_phi_args_after_copy_bb (region_copy[i]);
4590
4591   for (i = 0; i < n_region; i++)
4592     region_copy[i]->rbi->duplicated = 0;
4593 }
4594
4595 /* Maps the old ssa name FROM_NAME to TO_NAME.  */
4596
4597 struct ssa_name_map_entry
4598 {
4599   tree from_name;
4600   tree to_name;
4601 };
4602
4603 /* Hash function for ssa_name_map_entry.  */
4604
4605 static hashval_t
4606 ssa_name_map_entry_hash (const void *entry)
4607 {
4608   const struct ssa_name_map_entry *en = entry;
4609   return SSA_NAME_VERSION (en->from_name);
4610 }
4611
4612 /* Equality function for ssa_name_map_entry.  */
4613
4614 static int
4615 ssa_name_map_entry_eq (const void *in_table, const void *ssa_name)
4616 {
4617   const struct ssa_name_map_entry *en = in_table;
4618
4619   return en->from_name == ssa_name;
4620 }
4621
4622 /* Allocate duplicates of ssa names in list DEFINITIONS and store the mapping
4623    to MAP.  */
4624
4625 void
4626 allocate_ssa_names (bitmap definitions, htab_t *map)
4627 {
4628   tree name;
4629   struct ssa_name_map_entry *entry;
4630   PTR *slot;
4631   unsigned ver;
4632   bitmap_iterator bi;
4633
4634   if (!*map)
4635     *map = htab_create (10, ssa_name_map_entry_hash,
4636                         ssa_name_map_entry_eq, free);
4637   EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
4638     {
4639       name = ssa_name (ver);
4640       slot = htab_find_slot_with_hash (*map, name, SSA_NAME_VERSION (name),
4641                                        INSERT);
4642       if (*slot)
4643         entry = *slot;
4644       else
4645         {
4646           entry = xmalloc (sizeof (struct ssa_name_map_entry));
4647           entry->from_name = name;
4648           *slot = entry;
4649         }
4650       entry->to_name = duplicate_ssa_name (name, SSA_NAME_DEF_STMT (name));
4651     }
4652 }
4653
4654 /* Rewrite the definition DEF in statement STMT to new ssa name as specified
4655    by the mapping MAP.  */
4656
4657 static void
4658 rewrite_to_new_ssa_names_def (def_operand_p def, tree stmt, htab_t map)
4659 {
4660   tree name = DEF_FROM_PTR (def);
4661   struct ssa_name_map_entry *entry;
4662
4663   gcc_assert (TREE_CODE (name) == SSA_NAME);
4664
4665   entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
4666   if (!entry)
4667     return;
4668
4669   SET_DEF (def, entry->to_name);
4670   SSA_NAME_DEF_STMT (entry->to_name) = stmt;
4671 }
4672
4673 /* Rewrite the USE to new ssa name as specified by the mapping MAP.  */
4674
4675 static void
4676 rewrite_to_new_ssa_names_use (use_operand_p use, htab_t map)
4677 {
4678   tree name = USE_FROM_PTR (use);
4679   struct ssa_name_map_entry *entry;
4680
4681   if (TREE_CODE (name) != SSA_NAME)
4682     return;
4683
4684   entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
4685   if (!entry)
4686     return;
4687
4688   SET_USE (use, entry->to_name);
4689 }
4690
4691 /* Rewrite the ssa names in basic block BB to new ones as specified by the
4692    mapping MAP.  */
4693
4694 void
4695 rewrite_to_new_ssa_names_bb (basic_block bb, htab_t map)
4696 {
4697   unsigned i;
4698   edge e;
4699   edge_iterator ei;
4700   tree phi, stmt;
4701   block_stmt_iterator bsi;
4702   use_optype uses;
4703   vuse_optype vuses;
4704   def_optype defs;
4705   v_may_def_optype v_may_defs;
4706   v_must_def_optype v_must_defs;
4707   stmt_ann_t ann;
4708
4709   FOR_EACH_EDGE (e, ei, bb->preds)
4710     if (e->flags & EDGE_ABNORMAL)
4711       break;
4712
4713   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4714     {
4715       rewrite_to_new_ssa_names_def (PHI_RESULT_PTR (phi), phi, map);
4716       if (e)
4717         SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
4718     }
4719
4720   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4721     {
4722       stmt = bsi_stmt (bsi);
4723       get_stmt_operands (stmt);
4724       ann = stmt_ann (stmt);
4725
4726       uses = USE_OPS (ann);
4727       for (i = 0; i < NUM_USES (uses); i++)
4728         rewrite_to_new_ssa_names_use (USE_OP_PTR (uses, i), map);
4729
4730       defs = DEF_OPS (ann);
4731       for (i = 0; i < NUM_DEFS (defs); i++)
4732         rewrite_to_new_ssa_names_def (DEF_OP_PTR (defs, i), stmt, map);
4733
4734       vuses = VUSE_OPS (ann);
4735       for (i = 0; i < NUM_VUSES (vuses); i++)
4736         rewrite_to_new_ssa_names_use (VUSE_OP_PTR (vuses, i), map);
4737
4738       v_may_defs = V_MAY_DEF_OPS (ann);
4739       for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
4740         {
4741           rewrite_to_new_ssa_names_use
4742                   (V_MAY_DEF_OP_PTR (v_may_defs, i), map);
4743           rewrite_to_new_ssa_names_def
4744                   (V_MAY_DEF_RESULT_PTR (v_may_defs, i), stmt, map);
4745         }
4746
4747       v_must_defs = V_MUST_DEF_OPS (ann);
4748       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
4749         {
4750           rewrite_to_new_ssa_names_def
4751             (V_MUST_DEF_RESULT_PTR (v_must_defs, i), stmt, map);
4752           rewrite_to_new_ssa_names_use
4753             (V_MUST_DEF_KILL_PTR (v_must_defs, i),  map);
4754         }
4755     }
4756
4757   FOR_EACH_EDGE (e, ei, bb->succs)
4758     for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
4759       {
4760         rewrite_to_new_ssa_names_use
4761                 (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e), map);
4762
4763         if (e->flags & EDGE_ABNORMAL)
4764           {
4765             tree op = PHI_ARG_DEF_FROM_EDGE (phi, e);
4766             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op) = 1;
4767           }
4768       }
4769 }
4770
4771 /* Rewrite the ssa names in N_REGION blocks REGION to the new ones as specified
4772    by the mapping MAP.  */
4773
4774 void
4775 rewrite_to_new_ssa_names (basic_block *region, unsigned n_region, htab_t map)
4776 {
4777   unsigned r;
4778
4779   for (r = 0; r < n_region; r++)
4780     rewrite_to_new_ssa_names_bb (region[r], map);
4781 }
4782
4783 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
4784    important exit edge EXIT.  By important we mean that no SSA name defined
4785    inside region is live over the other exit edges of the region.  All entry
4786    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
4787    to the duplicate of the region.  SSA form, dominance and loop information
4788    is updated.  The new basic blocks are stored to REGION_COPY in the same
4789    order as they had in REGION, provided that REGION_COPY is not NULL.
4790    The function returns false if it is unable to copy the region,
4791    true otherwise.  */
4792
4793 bool
4794 tree_duplicate_sese_region (edge entry, edge exit,
4795                             basic_block *region, unsigned n_region,
4796                             basic_block *region_copy)
4797 {
4798   unsigned i, n_doms, ver;
4799   bool free_region_copy = false, copying_header = false;
4800   struct loop *loop = entry->dest->loop_father;
4801   edge exit_copy;
4802   bitmap definitions;
4803   tree phi;
4804   basic_block *doms;
4805   htab_t ssa_name_map = NULL;
4806   edge redirected;
4807   bitmap_iterator bi;
4808
4809   if (!can_copy_bbs_p (region, n_region))
4810     return false;
4811
4812   /* Some sanity checking.  Note that we do not check for all possible
4813      missuses of the functions.  I.e. if you ask to copy something weird,
4814      it will work, but the state of structures probably will not be
4815      correct.  */
4816
4817   for (i = 0; i < n_region; i++)
4818     {
4819       /* We do not handle subloops, i.e. all the blocks must belong to the
4820          same loop.  */
4821       if (region[i]->loop_father != loop)
4822         return false;
4823
4824       if (region[i] != entry->dest
4825           && region[i] == loop->header)
4826         return false;
4827     }
4828
4829   loop->copy = loop;
4830
4831   /* In case the function is used for loop header copying (which is the primary
4832      use), ensure that EXIT and its copy will be new latch and entry edges.  */
4833   if (loop->header == entry->dest)
4834     {
4835       copying_header = true;
4836       loop->copy = loop->outer;
4837
4838       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
4839         return false;
4840
4841       for (i = 0; i < n_region; i++)
4842         if (region[i] != exit->src
4843             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
4844           return false;
4845     }
4846
4847   if (!region_copy)
4848     {
4849       region_copy = xmalloc (sizeof (basic_block) * n_region);
4850       free_region_copy = true;
4851     }
4852
4853   gcc_assert (!any_marked_for_rewrite_p ());
4854
4855   /* Record blocks outside the region that are duplicated by something
4856      inside.  */
4857   doms = xmalloc (sizeof (basic_block) * n_basic_blocks);
4858   n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
4859
4860   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
4861   definitions = marked_ssa_names ();
4862
4863   if (copying_header)
4864     {
4865       loop->header = exit->dest;
4866       loop->latch = exit->src;
4867     }
4868
4869   /* Redirect the entry and add the phi node arguments.  */
4870   redirected = redirect_edge_and_branch (entry, entry->dest->rbi->copy);
4871   gcc_assert (redirected != NULL);
4872   flush_pending_stmts (entry);
4873
4874   /* Concerning updating of dominators:  We must recount dominators
4875      for entry block and its copy.  Anything that is outside of the region, but
4876      was dominated by something inside needs recounting as well.  */
4877   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
4878   doms[n_doms++] = entry->dest->rbi->original;
4879   iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
4880   free (doms);
4881
4882   /* Add the other phi node arguments.  */
4883   add_phi_args_after_copy (region_copy, n_region);
4884
4885   /* Add phi nodes for definitions at exit.  TODO -- once we have immediate
4886      uses, it should be possible to emit phi nodes just for definitions that
4887      are used outside region.  */
4888   EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
4889     {
4890       tree name = ssa_name (ver);
4891
4892       phi = create_phi_node (name, exit->dest);
4893       add_phi_arg (&phi, name, exit);
4894       add_phi_arg (&phi, name, exit_copy);
4895
4896       SSA_NAME_DEF_STMT (name) = phi;
4897     }
4898
4899   /* And create new definitions inside region and its copy.  TODO -- once we
4900      have immediate uses, it might be better to leave definitions in region
4901      unchanged, create new ssa names for phi nodes on exit, and rewrite
4902      the uses, to avoid changing the copied region.  */
4903   allocate_ssa_names (definitions, &ssa_name_map);
4904   rewrite_to_new_ssa_names (region, n_region, ssa_name_map);
4905   allocate_ssa_names (definitions, &ssa_name_map);
4906   rewrite_to_new_ssa_names (region_copy, n_region, ssa_name_map);
4907   htab_delete (ssa_name_map);
4908
4909   if (free_region_copy)
4910     free (region_copy);
4911
4912   unmark_all_for_rewrite ();
4913   BITMAP_XFREE (definitions);
4914
4915   return true;
4916 }
4917
4918 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4919
4920 void
4921 dump_function_to_file (tree fn, FILE *file, int flags)
4922 {
4923   tree arg, vars, var;
4924   bool ignore_topmost_bind = false, any_var = false;
4925   basic_block bb;
4926   tree chain;
4927
4928   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4929
4930   arg = DECL_ARGUMENTS (fn);
4931   while (arg)
4932     {
4933       print_generic_expr (file, arg, dump_flags);
4934       if (TREE_CHAIN (arg))
4935         fprintf (file, ", ");
4936       arg = TREE_CHAIN (arg);
4937     }
4938   fprintf (file, ")\n");
4939
4940   if (flags & TDF_RAW)
4941     {
4942       dump_node (fn, TDF_SLIM | flags, file);
4943       return;
4944     }
4945
4946   /* When GIMPLE is lowered, the variables are no longer available in
4947      BIND_EXPRs, so display them separately.  */
4948   if (cfun && cfun->unexpanded_var_list)
4949     {
4950       ignore_topmost_bind = true;
4951
4952       fprintf (file, "{\n");
4953       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
4954         {
4955           var = TREE_VALUE (vars);
4956
4957           print_generic_decl (file, var, flags);
4958           fprintf (file, "\n");
4959
4960           any_var = true;
4961         }
4962     }
4963
4964   if (basic_block_info)
4965     {
4966       /* Make a CFG based dump.  */
4967       check_bb_profile (ENTRY_BLOCK_PTR, file);
4968       if (!ignore_topmost_bind)
4969         fprintf (file, "{\n");
4970
4971       if (any_var && n_basic_blocks)
4972         fprintf (file, "\n");
4973
4974       FOR_EACH_BB (bb)
4975         dump_generic_bb (file, bb, 2, flags);
4976
4977       fprintf (file, "}\n");
4978       check_bb_profile (EXIT_BLOCK_PTR, file);
4979     }
4980   else
4981     {
4982       int indent;
4983
4984       /* Make a tree based dump.  */
4985       chain = DECL_SAVED_TREE (fn);
4986
4987       if (TREE_CODE (chain) == BIND_EXPR)
4988         {
4989           if (ignore_topmost_bind)
4990             {
4991               chain = BIND_EXPR_BODY (chain);
4992               indent = 2;
4993             }
4994           else
4995             indent = 0;
4996         }
4997       else
4998         {
4999           if (!ignore_topmost_bind)
5000             fprintf (file, "{\n");
5001           indent = 2;
5002         }
5003
5004       if (any_var)
5005         fprintf (file, "\n");
5006
5007       print_generic_stmt_indented (file, chain, flags, indent);
5008       if (ignore_topmost_bind)
5009         fprintf (file, "}\n");
5010     }
5011
5012   fprintf (file, "\n\n");
5013 }
5014
5015
5016 /* Pretty print of the loops intermediate representation.  */
5017 static void print_loop (FILE *, struct loop *, int);
5018 static void print_pred_bbs (FILE *, basic_block bb);
5019 static void print_succ_bbs (FILE *, basic_block bb);
5020
5021
5022 /* Print the predecessors indexes of edge E on FILE.  */
5023
5024 static void
5025 print_pred_bbs (FILE *file, basic_block bb)
5026 {
5027   edge e;
5028   edge_iterator ei;
5029
5030   FOR_EACH_EDGE (e, ei, bb->preds)
5031     fprintf (file, "bb_%d", e->src->index);
5032 }
5033
5034
5035 /* Print the successors indexes of edge E on FILE.  */
5036
5037 static void
5038 print_succ_bbs (FILE *file, basic_block bb)
5039 {
5040   edge e;
5041   edge_iterator ei;
5042
5043   FOR_EACH_EDGE (e, ei, bb->succs)
5044     fprintf (file, "bb_%d", e->src->index);
5045 }
5046
5047
5048 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
5049
5050 static void
5051 print_loop (FILE *file, struct loop *loop, int indent)
5052 {
5053   char *s_indent;
5054   basic_block bb;
5055
5056   if (loop == NULL)
5057     return;
5058
5059   s_indent = (char *) alloca ((size_t) indent + 1);
5060   memset ((void *) s_indent, ' ', (size_t) indent);
5061   s_indent[indent] = '\0';
5062
5063   /* Print the loop's header.  */
5064   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
5065
5066   /* Print the loop's body.  */
5067   fprintf (file, "%s{\n", s_indent);
5068   FOR_EACH_BB (bb)
5069     if (bb->loop_father == loop)
5070       {
5071         /* Print the basic_block's header.  */
5072         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
5073         print_pred_bbs (file, bb);
5074         fprintf (file, "}, succs = {");
5075         print_succ_bbs (file, bb);
5076         fprintf (file, "})\n");
5077
5078         /* Print the basic_block's body.  */
5079         fprintf (file, "%s  {\n", s_indent);
5080         tree_dump_bb (bb, file, indent + 4);
5081         fprintf (file, "%s  }\n", s_indent);
5082       }
5083
5084   print_loop (file, loop->inner, indent + 2);
5085   fprintf (file, "%s}\n", s_indent);
5086   print_loop (file, loop->next, indent);
5087 }
5088
5089
5090 /* Follow a CFG edge from the entry point of the program, and on entry
5091    of a loop, pretty print the loop structure on FILE.  */
5092
5093 void
5094 print_loop_ir (FILE *file)
5095 {
5096   basic_block bb;
5097
5098   bb = BASIC_BLOCK (0);
5099   if (bb && bb->loop_father)
5100     print_loop (file, bb->loop_father, 0);
5101 }
5102
5103
5104 /* Debugging loops structure at tree level.  */
5105
5106 void
5107 debug_loop_ir (void)
5108 {
5109   print_loop_ir (stderr);
5110 }
5111
5112
5113 /* Return true if BB ends with a call, possibly followed by some
5114    instructions that must stay with the call.  Return false,
5115    otherwise.  */
5116
5117 static bool
5118 tree_block_ends_with_call_p (basic_block bb)
5119 {
5120   block_stmt_iterator bsi = bsi_last (bb);
5121   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
5122 }
5123
5124
5125 /* Return true if BB ends with a conditional branch.  Return false,
5126    otherwise.  */
5127
5128 static bool
5129 tree_block_ends_with_condjump_p (basic_block bb)
5130 {
5131   tree stmt = tsi_stmt (bsi_last (bb).tsi);
5132   return (TREE_CODE (stmt) == COND_EXPR);
5133 }
5134
5135
5136 /* Return true if we need to add fake edge to exit at statement T.
5137    Helper function for tree_flow_call_edges_add.  */
5138
5139 static bool
5140 need_fake_edge_p (tree t)
5141 {
5142   tree call;
5143
5144   /* NORETURN and LONGJMP calls already have an edge to exit.
5145      CONST, PURE and ALWAYS_RETURN calls do not need one.
5146      We don't currently check for CONST and PURE here, although
5147      it would be a good idea, because those attributes are
5148      figured out from the RTL in mark_constant_function, and
5149      the counter incrementation code from -fprofile-arcs
5150      leads to different results from -fbranch-probabilities.  */
5151   call = get_call_expr_in (t);
5152   if (call
5153       && !(call_expr_flags (call) &
5154            (ECF_NORETURN | ECF_LONGJMP | ECF_ALWAYS_RETURN)))
5155     return true;
5156
5157   if (TREE_CODE (t) == ASM_EXPR
5158        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
5159     return true;
5160
5161   return false;
5162 }
5163
5164
5165 /* Add fake edges to the function exit for any non constant and non
5166    noreturn calls, volatile inline assembly in the bitmap of blocks
5167    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
5168    the number of blocks that were split.
5169
5170    The goal is to expose cases in which entering a basic block does
5171    not imply that all subsequent instructions must be executed.  */
5172
5173 static int
5174 tree_flow_call_edges_add (sbitmap blocks)
5175 {
5176   int i;
5177   int blocks_split = 0;
5178   int last_bb = last_basic_block;
5179   bool check_last_block = false;
5180
5181   if (n_basic_blocks == 0)
5182     return 0;
5183
5184   if (! blocks)
5185     check_last_block = true;
5186   else
5187     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
5188
5189   /* In the last basic block, before epilogue generation, there will be
5190      a fallthru edge to EXIT.  Special care is required if the last insn
5191      of the last basic block is a call because make_edge folds duplicate
5192      edges, which would result in the fallthru edge also being marked
5193      fake, which would result in the fallthru edge being removed by
5194      remove_fake_edges, which would result in an invalid CFG.
5195
5196      Moreover, we can't elide the outgoing fake edge, since the block
5197      profiler needs to take this into account in order to solve the minimal
5198      spanning tree in the case that the call doesn't return.
5199
5200      Handle this by adding a dummy instruction in a new last basic block.  */
5201   if (check_last_block)
5202     {
5203       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
5204       block_stmt_iterator bsi = bsi_last (bb);
5205       tree t = NULL_TREE;
5206       if (!bsi_end_p (bsi))
5207         t = bsi_stmt (bsi);
5208
5209       if (need_fake_edge_p (t))
5210         {
5211           edge e;
5212
5213           e = find_edge (bb, EXIT_BLOCK_PTR);
5214           if (e)
5215             {
5216               bsi_insert_on_edge (e, build_empty_stmt ());
5217               bsi_commit_edge_inserts ();
5218             }
5219         }
5220     }
5221
5222   /* Now add fake edges to the function exit for any non constant
5223      calls since there is no way that we can determine if they will
5224      return or not...  */
5225   for (i = 0; i < last_bb; i++)
5226     {
5227       basic_block bb = BASIC_BLOCK (i);
5228       block_stmt_iterator bsi;
5229       tree stmt, last_stmt;
5230
5231       if (!bb)
5232         continue;
5233
5234       if (blocks && !TEST_BIT (blocks, i))
5235         continue;
5236
5237       bsi = bsi_last (bb);
5238       if (!bsi_end_p (bsi))
5239         {
5240           last_stmt = bsi_stmt (bsi);
5241           do
5242             {
5243               stmt = bsi_stmt (bsi);
5244               if (need_fake_edge_p (stmt))
5245                 {
5246                   edge e;
5247                   /* The handling above of the final block before the
5248                      epilogue should be enough to verify that there is
5249                      no edge to the exit block in CFG already.
5250                      Calling make_edge in such case would cause us to
5251                      mark that edge as fake and remove it later.  */
5252 #ifdef ENABLE_CHECKING
5253                   if (stmt == last_stmt)
5254                     {
5255                       e = find_edge (bb, EXIT_BLOCK_PTR);
5256                       gcc_assert (e == NULL);
5257                     }
5258 #endif
5259
5260                   /* Note that the following may create a new basic block
5261                      and renumber the existing basic blocks.  */
5262                   if (stmt != last_stmt)
5263                     {
5264                       e = split_block (bb, stmt);
5265                       if (e)
5266                         blocks_split++;
5267                     }
5268                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
5269                 }
5270               bsi_prev (&bsi);
5271             }
5272           while (!bsi_end_p (bsi));
5273         }
5274     }
5275
5276   if (blocks_split)
5277     verify_flow_info ();
5278
5279   return blocks_split;
5280 }
5281
5282 bool
5283 tree_purge_dead_eh_edges (basic_block bb)
5284 {
5285   bool changed = false;
5286   edge e;
5287   edge_iterator ei;
5288   tree stmt = last_stmt (bb);
5289
5290   if (stmt && tree_can_throw_internal (stmt))
5291     return false;
5292
5293   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
5294     {
5295       if (e->flags & EDGE_EH)
5296         {
5297           ssa_remove_edge (e);
5298           changed = true;
5299         }
5300       else
5301         ei_next (&ei);
5302     }
5303
5304   /* Removal of dead EH edges might change dominators of not
5305      just immediate successors.  E.g. when bb1 is changed so that
5306      it no longer can throw and bb1->bb3 and bb1->bb4 are dead
5307      eh edges purged by this function in:
5308            0
5309           / \
5310          v   v
5311          1-->2
5312         / \  |
5313        v   v |
5314        3-->4 |
5315         \    v
5316          --->5
5317              |
5318              -
5319      idom(bb5) must be recomputed.  For now just free the dominance
5320      info.  */
5321   if (changed)
5322     free_dominance_info (CDI_DOMINATORS);
5323
5324   return changed;
5325 }
5326
5327 bool
5328 tree_purge_all_dead_eh_edges (bitmap blocks)
5329 {
5330   bool changed = false;
5331   unsigned i;
5332   bitmap_iterator bi;
5333
5334   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
5335     {
5336       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
5337     }
5338
5339   return changed;
5340 }
5341
5342 struct cfg_hooks tree_cfg_hooks = {
5343   "tree",
5344   tree_verify_flow_info,
5345   tree_dump_bb,                 /* dump_bb  */
5346   create_bb,                    /* create_basic_block  */
5347   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
5348   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
5349   remove_bb,                    /* delete_basic_block  */
5350   tree_split_block,             /* split_block  */
5351   tree_move_block_after,        /* move_block_after  */
5352   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
5353   tree_merge_blocks,            /* merge_blocks  */
5354   tree_predict_edge,            /* predict_edge  */
5355   tree_predicted_by_p,          /* predicted_by_p  */
5356   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
5357   tree_duplicate_bb,            /* duplicate_block  */
5358   tree_split_edge,              /* split_edge  */
5359   tree_make_forwarder_block,    /* make_forward_block  */
5360   NULL,                         /* tidy_fallthru_edge  */
5361   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
5362   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
5363   tree_flow_call_edges_add,     /* flow_call_edges_add */
5364   NULL, /* execute_on_growing_pred */
5365   NULL, /* execute_on_shrinking_pred */
5366 };
5367
5368
5369 /* Split all critical edges.  */
5370
5371 static void
5372 split_critical_edges (void)
5373 {
5374   basic_block bb;
5375   edge e;
5376   edge_iterator ei;
5377
5378   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
5379      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
5380      mappings around the calls to split_edge.  */
5381   start_recording_case_labels ();
5382   FOR_ALL_BB (bb)
5383     {
5384       FOR_EACH_EDGE (e, ei, bb->succs)
5385         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
5386           {
5387             split_edge (e);
5388           }
5389     }
5390   end_recording_case_labels ();
5391 }
5392
5393 struct tree_opt_pass pass_split_crit_edges =
5394 {
5395   "crited",                          /* name */
5396   NULL,                          /* gate */
5397   split_critical_edges,          /* execute */
5398   NULL,                          /* sub */
5399   NULL,                          /* next */
5400   0,                             /* static_pass_number */
5401   TV_TREE_SPLIT_EDGES,           /* tv_id */
5402   PROP_cfg,                      /* properties required */
5403   PROP_no_crit_edges,            /* properties_provided */
5404   0,                             /* properties_destroyed */
5405   0,                             /* todo_flags_start */
5406   TODO_dump_func,                /* todo_flags_finish */
5407   0                              /* letter */
5408 };
5409
5410 \f
5411 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
5412    a temporary, make sure and register it to be renamed if necessary,
5413    and finally return the temporary.  Put the statements to compute
5414    EXP before the current statement in BSI.  */
5415
5416 tree
5417 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
5418 {
5419   tree t, new_stmt, orig_stmt;
5420
5421   if (is_gimple_val (exp))
5422     return exp;
5423
5424   t = make_rename_temp (type, NULL);
5425   new_stmt = build (MODIFY_EXPR, type, t, exp);
5426
5427   orig_stmt = bsi_stmt (*bsi);
5428   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
5429   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
5430
5431   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
5432
5433   return t;
5434 }
5435
5436 /* Build a ternary operation and gimplify it.  Emit code before BSI.
5437    Return the gimple_val holding the result.  */
5438
5439 tree
5440 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
5441                  tree type, tree a, tree b, tree c)
5442 {
5443   tree ret;
5444
5445   ret = fold (build3 (code, type, a, b, c));
5446   STRIP_NOPS (ret);
5447
5448   return gimplify_val (bsi, type, ret);
5449 }
5450
5451 /* Build a binary operation and gimplify it.  Emit code before BSI.
5452    Return the gimple_val holding the result.  */
5453
5454 tree
5455 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
5456                  tree type, tree a, tree b)
5457 {
5458   tree ret;
5459
5460   ret = fold (build2 (code, type, a, b));
5461   STRIP_NOPS (ret);
5462
5463   return gimplify_val (bsi, type, ret);
5464 }
5465
5466 /* Build a unary operation and gimplify it.  Emit code before BSI.
5467    Return the gimple_val holding the result.  */
5468
5469 tree
5470 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
5471                  tree a)
5472 {
5473   tree ret;
5474
5475   ret = fold (build1 (code, type, a));
5476   STRIP_NOPS (ret);
5477
5478   return gimplify_val (bsi, type, ret);
5479 }
5480
5481
5482 \f
5483 /* Emit return warnings.  */
5484
5485 static void
5486 execute_warn_function_return (void)
5487 {
5488 #ifdef USE_MAPPED_LOCATION
5489   source_location location;
5490 #else
5491   location_t *locus;
5492 #endif
5493   tree last;
5494   edge e;
5495   edge_iterator ei;
5496
5497   if (warn_missing_noreturn
5498       && !TREE_THIS_VOLATILE (cfun->decl)
5499       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
5500       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
5501     warning ("%Jfunction might be possible candidate for "
5502              "attribute %<noreturn%>",
5503              cfun->decl);
5504
5505   /* If we have a path to EXIT, then we do return.  */
5506   if (TREE_THIS_VOLATILE (cfun->decl)
5507       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
5508     {
5509 #ifdef USE_MAPPED_LOCATION
5510       location = UNKNOWN_LOCATION;
5511 #else
5512       locus = NULL;
5513 #endif
5514       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5515         {
5516           last = last_stmt (e->src);
5517           if (TREE_CODE (last) == RETURN_EXPR
5518 #ifdef USE_MAPPED_LOCATION
5519               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
5520 #else
5521               && (locus = EXPR_LOCUS (last)) != NULL)
5522 #endif
5523             break;
5524         }
5525 #ifdef USE_MAPPED_LOCATION
5526       if (location == UNKNOWN_LOCATION)
5527         location = cfun->function_end_locus;
5528       warning ("%H%<noreturn%> function does return", &location);
5529 #else
5530       if (!locus)
5531         locus = &cfun->function_end_locus;
5532       warning ("%H%<noreturn%> function does return", locus);
5533 #endif
5534     }
5535
5536   /* If we see "return;" in some basic block, then we do reach the end
5537      without returning a value.  */
5538   else if (warn_return_type
5539            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
5540            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
5541     {
5542       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5543         {
5544           tree last = last_stmt (e->src);
5545           if (TREE_CODE (last) == RETURN_EXPR
5546               && TREE_OPERAND (last, 0) == NULL)
5547             {
5548 #ifdef USE_MAPPED_LOCATION
5549               location = EXPR_LOCATION (last);
5550               if (location == UNKNOWN_LOCATION)
5551                   location = cfun->function_end_locus;
5552               warning ("%Hcontrol reaches end of non-void function", &location);
5553 #else
5554               locus = EXPR_LOCUS (last);
5555               if (!locus)
5556                 locus = &cfun->function_end_locus;
5557               warning ("%Hcontrol reaches end of non-void function", locus);
5558 #endif
5559               break;
5560             }
5561         }
5562     }
5563 }
5564
5565
5566 /* Given a basic block B which ends with a conditional and has
5567    precisely two successors, determine which of the edges is taken if
5568    the conditional is true and which is taken if the conditional is
5569    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
5570
5571 void
5572 extract_true_false_edges_from_block (basic_block b,
5573                                      edge *true_edge,
5574                                      edge *false_edge)
5575 {
5576   edge e = EDGE_SUCC (b, 0);
5577
5578   if (e->flags & EDGE_TRUE_VALUE)
5579     {
5580       *true_edge = e;
5581       *false_edge = EDGE_SUCC (b, 1);
5582     }
5583   else
5584     {
5585       *false_edge = e;
5586       *true_edge = EDGE_SUCC (b, 1);
5587     }
5588 }
5589
5590 struct tree_opt_pass pass_warn_function_return =
5591 {
5592   NULL,                                 /* name */
5593   NULL,                                 /* gate */
5594   execute_warn_function_return,         /* execute */
5595   NULL,                                 /* sub */
5596   NULL,                                 /* next */
5597   0,                                    /* static_pass_number */
5598   0,                                    /* tv_id */
5599   PROP_cfg,                             /* properties_required */
5600   0,                                    /* properties_provided */
5601   0,                                    /* properties_destroyed */
5602   0,                                    /* todo_flags_start */
5603   0,                                    /* todo_flags_finish */
5604   0                                     /* letter */
5605 };
5606
5607 #include "gt-tree-cfg.h"