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           FOR_EACH_EDGE (e, ei, bb->succs)
2653             {
2654               if (e->dest != bb->next_bb)
2655                 continue;
2656
2657               if (e->flags & EDGE_TRUE_VALUE)
2658                 COND_EXPR_THEN (stmt) = build_empty_stmt ();
2659               else if (e->flags & EDGE_FALSE_VALUE)
2660                 COND_EXPR_ELSE (stmt) = build_empty_stmt ();
2661               else
2662                 gcc_unreachable ();
2663               e->flags |= EDGE_FALLTHRU;
2664             }
2665
2666           continue;
2667         }
2668
2669       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
2670         {
2671           /* Remove the RETURN_EXPR if we may fall though to the exit
2672              instead.  */
2673           gcc_assert (EDGE_COUNT (bb->succs) == 1);
2674           gcc_assert (EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR);
2675
2676           if (bb->next_bb == EXIT_BLOCK_PTR
2677               && !TREE_OPERAND (stmt, 0))
2678             {
2679               bsi_remove (&last);
2680               EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
2681             }
2682           continue;
2683         }
2684
2685       /* There can be no fallthru edge if the last statement is a control
2686          one.  */
2687       if (stmt && is_ctrl_stmt (stmt))
2688         continue;
2689
2690       /* Find a fallthru edge and emit the goto if necessary.  */
2691       FOR_EACH_EDGE (e, ei, bb->succs)
2692         if (e->flags & EDGE_FALLTHRU)
2693           break;
2694
2695       if (!e || e->dest == bb->next_bb)
2696         continue;
2697
2698       gcc_assert (e->dest != EXIT_BLOCK_PTR);
2699       label = tree_block_label (e->dest);
2700
2701       stmt = build1 (GOTO_EXPR, void_type_node, label);
2702 #ifdef USE_MAPPED_LOCATION
2703       SET_EXPR_LOCATION (stmt, e->goto_locus);
2704 #else
2705       SET_EXPR_LOCUS (stmt, e->goto_locus);
2706 #endif
2707       bsi_insert_after (&last, stmt, BSI_NEW_STMT);
2708       e->flags &= ~EDGE_FALLTHRU;
2709     }
2710 }
2711
2712 /* Remove block annotations and other datastructures.  */
2713
2714 void
2715 delete_tree_cfg_annotations (void)
2716 {
2717   basic_block bb;
2718   if (n_basic_blocks > 0)
2719     free_blocks_annotations ();
2720
2721   label_to_block_map = NULL;
2722   free_rbi_pool ();
2723   FOR_EACH_BB (bb)
2724     bb->rbi = NULL;
2725 }
2726
2727
2728 /* Return the first statement in basic block BB.  */
2729
2730 tree
2731 first_stmt (basic_block bb)
2732 {
2733   block_stmt_iterator i = bsi_start (bb);
2734   return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2735 }
2736
2737
2738 /* Return the last statement in basic block BB.  */
2739
2740 tree
2741 last_stmt (basic_block bb)
2742 {
2743   block_stmt_iterator b = bsi_last (bb);
2744   return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2745 }
2746
2747
2748 /* Return a pointer to the last statement in block BB.  */
2749
2750 tree *
2751 last_stmt_ptr (basic_block bb)
2752 {
2753   block_stmt_iterator last = bsi_last (bb);
2754   return !bsi_end_p (last) ? bsi_stmt_ptr (last) : NULL;
2755 }
2756
2757
2758 /* Return the last statement of an otherwise empty block.  Return NULL
2759    if the block is totally empty, or if it contains more than one
2760    statement.  */
2761
2762 tree
2763 last_and_only_stmt (basic_block bb)
2764 {
2765   block_stmt_iterator i = bsi_last (bb);
2766   tree last, prev;
2767
2768   if (bsi_end_p (i))
2769     return NULL_TREE;
2770
2771   last = bsi_stmt (i);
2772   bsi_prev (&i);
2773   if (bsi_end_p (i))
2774     return last;
2775
2776   /* Empty statements should no longer appear in the instruction stream.
2777      Everything that might have appeared before should be deleted by
2778      remove_useless_stmts, and the optimizers should just bsi_remove
2779      instead of smashing with build_empty_stmt.
2780
2781      Thus the only thing that should appear here in a block containing
2782      one executable statement is a label.  */
2783   prev = bsi_stmt (i);
2784   if (TREE_CODE (prev) == LABEL_EXPR)
2785     return last;
2786   else
2787     return NULL_TREE;
2788 }
2789
2790
2791 /* Mark BB as the basic block holding statement T.  */
2792
2793 void
2794 set_bb_for_stmt (tree t, basic_block bb)
2795 {
2796   if (TREE_CODE (t) == PHI_NODE)
2797     PHI_BB (t) = bb;
2798   else if (TREE_CODE (t) == STATEMENT_LIST)
2799     {
2800       tree_stmt_iterator i;
2801       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2802         set_bb_for_stmt (tsi_stmt (i), bb);
2803     }
2804   else
2805     {
2806       stmt_ann_t ann = get_stmt_ann (t);
2807       ann->bb = bb;
2808
2809       /* If the statement is a label, add the label to block-to-labels map
2810          so that we can speed up edge creation for GOTO_EXPRs.  */
2811       if (TREE_CODE (t) == LABEL_EXPR)
2812         {
2813           int uid;
2814
2815           t = LABEL_EXPR_LABEL (t);
2816           uid = LABEL_DECL_UID (t);
2817           if (uid == -1)
2818             {
2819               LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
2820               if (VARRAY_SIZE (label_to_block_map) <= (unsigned) uid)
2821                 VARRAY_GROW (label_to_block_map, 3 * uid / 2);
2822             }
2823           else
2824             /* We're moving an existing label.  Make sure that we've
2825                 removed it from the old block.  */
2826             gcc_assert (!bb || !VARRAY_BB (label_to_block_map, uid));
2827           VARRAY_BB (label_to_block_map, uid) = bb;
2828         }
2829     }
2830 }
2831
2832 /* Finds iterator for STMT.  */
2833
2834 extern block_stmt_iterator
2835 bsi_for_stmt (tree stmt)
2836 {
2837   block_stmt_iterator bsi;
2838
2839   for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2840     if (bsi_stmt (bsi) == stmt)
2841       return bsi;
2842
2843   gcc_unreachable ();
2844 }
2845
2846 /* Insert statement (or statement list) T before the statement
2847    pointed-to by iterator I.  M specifies how to update iterator I
2848    after insertion (see enum bsi_iterator_update).  */
2849
2850 void
2851 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2852 {
2853   set_bb_for_stmt (t, i->bb);
2854   tsi_link_before (&i->tsi, t, m);
2855   modify_stmt (t);
2856 }
2857
2858
2859 /* Insert statement (or statement list) T after the statement
2860    pointed-to by iterator I.  M specifies how to update iterator I
2861    after insertion (see enum bsi_iterator_update).  */
2862
2863 void
2864 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2865 {
2866   set_bb_for_stmt (t, i->bb);
2867   tsi_link_after (&i->tsi, t, m);
2868   modify_stmt (t);
2869 }
2870
2871
2872 /* Remove the statement pointed to by iterator I.  The iterator is updated
2873    to the next statement.  */
2874
2875 void
2876 bsi_remove (block_stmt_iterator *i)
2877 {
2878   tree t = bsi_stmt (*i);
2879   set_bb_for_stmt (t, NULL);
2880   tsi_delink (&i->tsi);
2881 }
2882
2883
2884 /* Move the statement at FROM so it comes right after the statement at TO.  */
2885
2886 void
2887 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2888 {
2889   tree stmt = bsi_stmt (*from);
2890   bsi_remove (from);
2891   bsi_insert_after (to, stmt, BSI_SAME_STMT);
2892 }
2893
2894
2895 /* Move the statement at FROM so it comes right before the statement at TO.  */
2896
2897 void
2898 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2899 {
2900   tree stmt = bsi_stmt (*from);
2901   bsi_remove (from);
2902   bsi_insert_before (to, stmt, BSI_SAME_STMT);
2903 }
2904
2905
2906 /* Move the statement at FROM to the end of basic block BB.  */
2907
2908 void
2909 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2910 {
2911   block_stmt_iterator last = bsi_last (bb);
2912
2913   /* Have to check bsi_end_p because it could be an empty block.  */
2914   if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2915     bsi_move_before (from, &last);
2916   else
2917     bsi_move_after (from, &last);
2918 }
2919
2920
2921 /* Replace the contents of the statement pointed to by iterator BSI
2922    with STMT.  If PRESERVE_EH_INFO is true, the exception handling
2923    information of the original statement is preserved.  */
2924
2925 void
2926 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool preserve_eh_info)
2927 {
2928   int eh_region;
2929   tree orig_stmt = bsi_stmt (*bsi);
2930
2931   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2932   set_bb_for_stmt (stmt, bsi->bb);
2933
2934   /* Preserve EH region information from the original statement, if
2935      requested by the caller.  */
2936   if (preserve_eh_info)
2937     {
2938       eh_region = lookup_stmt_eh_region (orig_stmt);
2939       if (eh_region >= 0)
2940         add_stmt_to_eh_region (stmt, eh_region);
2941     }
2942
2943   *bsi_stmt_ptr (*bsi) = stmt;
2944   modify_stmt (stmt);
2945 }
2946
2947
2948 /* Insert the statement pointed-to by BSI into edge E.  Every attempt
2949    is made to place the statement in an existing basic block, but
2950    sometimes that isn't possible.  When it isn't possible, the edge is
2951    split and the statement is added to the new block.
2952
2953    In all cases, the returned *BSI points to the correct location.  The
2954    return value is true if insertion should be done after the location,
2955    or false if it should be done before the location.  If new basic block
2956    has to be created, it is stored in *NEW_BB.  */
2957
2958 static bool
2959 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2960                            basic_block *new_bb)
2961 {
2962   basic_block dest, src;
2963   tree tmp;
2964
2965   dest = e->dest;
2966  restart:
2967
2968   /* If the destination has one predecessor which has no PHI nodes,
2969      insert there.  Except for the exit block.
2970
2971      The requirement for no PHI nodes could be relaxed.  Basically we
2972      would have to examine the PHIs to prove that none of them used
2973      the value set by the statement we want to insert on E.  That
2974      hardly seems worth the effort.  */
2975   if (EDGE_COUNT (dest->preds) == 1
2976       && ! phi_nodes (dest)
2977       && dest != EXIT_BLOCK_PTR)
2978     {
2979       *bsi = bsi_start (dest);
2980       if (bsi_end_p (*bsi))
2981         return true;
2982
2983       /* Make sure we insert after any leading labels.  */
2984       tmp = bsi_stmt (*bsi);
2985       while (TREE_CODE (tmp) == LABEL_EXPR)
2986         {
2987           bsi_next (bsi);
2988           if (bsi_end_p (*bsi))
2989             break;
2990           tmp = bsi_stmt (*bsi);
2991         }
2992
2993       if (bsi_end_p (*bsi))
2994         {
2995           *bsi = bsi_last (dest);
2996           return true;
2997         }
2998       else
2999         return false;
3000     }
3001
3002   /* If the source has one successor, the edge is not abnormal and
3003      the last statement does not end a basic block, insert there.
3004      Except for the entry block.  */
3005   src = e->src;
3006   if ((e->flags & EDGE_ABNORMAL) == 0
3007       && EDGE_COUNT (src->succs) == 1
3008       && src != ENTRY_BLOCK_PTR)
3009     {
3010       *bsi = bsi_last (src);
3011       if (bsi_end_p (*bsi))
3012         return true;
3013
3014       tmp = bsi_stmt (*bsi);
3015       if (!stmt_ends_bb_p (tmp))
3016         return true;
3017
3018       /* Insert code just before returning the value.  We may need to decompose
3019          the return in the case it contains non-trivial operand.  */
3020       if (TREE_CODE (tmp) == RETURN_EXPR)
3021         {
3022           tree op = TREE_OPERAND (tmp, 0);
3023           if (!is_gimple_val (op))
3024             {
3025               gcc_assert (TREE_CODE (op) == MODIFY_EXPR);
3026               bsi_insert_before (bsi, op, BSI_NEW_STMT);
3027               TREE_OPERAND (tmp, 0) = TREE_OPERAND (op, 0);
3028             }
3029           bsi_prev (bsi);
3030           return true;
3031         }
3032     }
3033
3034   /* Otherwise, create a new basic block, and split this edge.  */
3035   dest = split_edge (e);
3036   if (new_bb)
3037     *new_bb = dest;
3038   e = EDGE_PRED (dest, 0);
3039   goto restart;
3040 }
3041
3042
3043 /* This routine will commit all pending edge insertions, creating any new
3044    basic blocks which are necessary.  */
3045
3046 void
3047 bsi_commit_edge_inserts (void)
3048 {
3049   basic_block bb;
3050   edge e;
3051   edge_iterator ei;
3052
3053   bsi_commit_one_edge_insert (EDGE_SUCC (ENTRY_BLOCK_PTR, 0), NULL);
3054
3055   FOR_EACH_BB (bb)
3056     FOR_EACH_EDGE (e, ei, bb->succs)
3057       bsi_commit_one_edge_insert (e, NULL);
3058 }
3059
3060
3061 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
3062    to this block, otherwise set it to NULL.  */
3063
3064 void
3065 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
3066 {
3067   if (new_bb)
3068     *new_bb = NULL;
3069   if (PENDING_STMT (e))
3070     {
3071       block_stmt_iterator bsi;
3072       tree stmt = PENDING_STMT (e);
3073
3074       PENDING_STMT (e) = NULL_TREE;
3075
3076       if (tree_find_edge_insert_loc (e, &bsi, new_bb))
3077         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3078       else
3079         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3080     }
3081 }
3082
3083
3084 /* Add STMT to the pending list of edge E.  No actual insertion is
3085    made until a call to bsi_commit_edge_inserts () is made.  */
3086
3087 void
3088 bsi_insert_on_edge (edge e, tree stmt)
3089 {
3090   append_to_statement_list (stmt, &PENDING_STMT (e));
3091 }
3092
3093 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If new block has to
3094    be created, it is returned.  */
3095
3096 basic_block
3097 bsi_insert_on_edge_immediate (edge e, tree stmt)
3098 {
3099   block_stmt_iterator bsi;
3100   basic_block new_bb = NULL;
3101
3102   gcc_assert (!PENDING_STMT (e));
3103
3104   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3105     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3106   else
3107     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3108
3109   return new_bb;
3110 }
3111
3112 /*---------------------------------------------------------------------------
3113              Tree specific functions for CFG manipulation
3114 ---------------------------------------------------------------------------*/
3115
3116 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3117    Abort on abnormal edges.  */
3118
3119 static basic_block
3120 tree_split_edge (edge edge_in)
3121 {
3122   basic_block new_bb, after_bb, dest, src;
3123   edge new_edge, e;
3124   tree phi;
3125   int i, num_elem;
3126   edge_iterator ei;
3127
3128   /* Abnormal edges cannot be split.  */
3129   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3130
3131   src = edge_in->src;
3132   dest = edge_in->dest;
3133
3134   /* Place the new block in the block list.  Try to keep the new block
3135      near its "logical" location.  This is of most help to humans looking
3136      at debugging dumps.  */
3137   FOR_EACH_EDGE (e, ei, dest->preds)
3138     if (e->src->next_bb == dest)
3139       break;
3140   if (!e)
3141     after_bb = dest->prev_bb;
3142   else
3143     after_bb = edge_in->src;
3144
3145   new_bb = create_empty_bb (after_bb);
3146   new_bb->frequency = EDGE_FREQUENCY (edge_in);
3147   new_bb->count = edge_in->count;
3148   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3149   new_edge->probability = REG_BR_PROB_BASE;
3150   new_edge->count = edge_in->count;
3151
3152   /* Find all the PHI arguments on the original edge, and change them to
3153      the new edge.  Do it before redirection, so that the argument does not
3154      get removed.  */
3155   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
3156     {
3157       num_elem = PHI_NUM_ARGS (phi);
3158       for (i = 0; i < num_elem; i++)
3159         if (PHI_ARG_EDGE (phi, i) == edge_in)
3160           {
3161             PHI_ARG_EDGE (phi, i) = new_edge;
3162             break;
3163           }
3164     }
3165
3166   e = redirect_edge_and_branch (edge_in, new_bb);
3167   gcc_assert (e);
3168   gcc_assert (!PENDING_STMT (edge_in));
3169
3170   return new_bb;
3171 }
3172
3173
3174 /* Return true when BB has label LABEL in it.  */
3175
3176 static bool
3177 has_label_p (basic_block bb, tree label)
3178 {
3179   block_stmt_iterator bsi;
3180
3181   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3182     {
3183       tree stmt = bsi_stmt (bsi);
3184
3185       if (TREE_CODE (stmt) != LABEL_EXPR)
3186         return false;
3187       if (LABEL_EXPR_LABEL (stmt) == label)
3188         return true;
3189     }
3190   return false;
3191 }
3192
3193
3194 /* Callback for walk_tree, check that all elements with address taken are
3195    properly noticed as such.  */
3196
3197 static tree
3198 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3199 {
3200   tree t = *tp, x;
3201
3202   if (TYPE_P (t))
3203     *walk_subtrees = 0;
3204
3205   /* Check operand N for being valid GIMPLE and give error MSG if not.
3206      We check for constants explicitly since they are not considered
3207      gimple invariants if they overflowed.  */
3208 #define CHECK_OP(N, MSG) \
3209   do { if (!CONSTANT_CLASS_P (TREE_OPERAND (t, N))              \
3210          && !is_gimple_val (TREE_OPERAND (t, N)))               \
3211        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3212
3213   switch (TREE_CODE (t))
3214     {
3215     case SSA_NAME:
3216       if (SSA_NAME_IN_FREE_LIST (t))
3217         {
3218           error ("SSA name in freelist but still referenced");
3219           return *tp;
3220         }
3221       break;
3222
3223     case MODIFY_EXPR:
3224       x = TREE_OPERAND (t, 0);
3225       if (TREE_CODE (x) == BIT_FIELD_REF
3226           && is_gimple_reg (TREE_OPERAND (x, 0)))
3227         {
3228           error ("GIMPLE register modified with BIT_FIELD_REF");
3229           return t;
3230         }
3231       break;
3232
3233     case ADDR_EXPR:
3234       /* Skip any references (they will be checked when we recurse down the
3235          tree) and ensure that any variable used as a prefix is marked
3236          addressable.  */
3237       for (x = TREE_OPERAND (t, 0);
3238            (handled_component_p (x)
3239             || TREE_CODE (x) == REALPART_EXPR
3240             || TREE_CODE (x) == IMAGPART_EXPR);
3241            x = TREE_OPERAND (x, 0))
3242         ;
3243
3244       if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3245         return NULL;
3246       if (!TREE_ADDRESSABLE (x))
3247         {
3248           error ("address taken, but ADDRESSABLE bit not set");
3249           return x;
3250         }
3251       break;
3252
3253     case COND_EXPR:
3254       x = COND_EXPR_COND (t);
3255       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3256         {
3257           error ("non-boolean used in condition");
3258           return x;
3259         }
3260       break;
3261
3262     case NOP_EXPR:
3263     case CONVERT_EXPR:
3264     case FIX_TRUNC_EXPR:
3265     case FIX_CEIL_EXPR:
3266     case FIX_FLOOR_EXPR:
3267     case FIX_ROUND_EXPR:
3268     case FLOAT_EXPR:
3269     case NEGATE_EXPR:
3270     case ABS_EXPR:
3271     case BIT_NOT_EXPR:
3272     case NON_LVALUE_EXPR:
3273     case TRUTH_NOT_EXPR:
3274       CHECK_OP (0, "Invalid operand to unary operator");
3275       break;
3276
3277     case REALPART_EXPR:
3278     case IMAGPART_EXPR:
3279     case COMPONENT_REF:
3280     case ARRAY_REF:
3281     case ARRAY_RANGE_REF:
3282     case BIT_FIELD_REF:
3283     case VIEW_CONVERT_EXPR:
3284       /* We have a nest of references.  Verify that each of the operands
3285          that determine where to reference is either a constant or a variable,
3286          verify that the base is valid, and then show we've already checked
3287          the subtrees.  */
3288       while (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR
3289              || handled_component_p (t))
3290         {
3291           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3292             CHECK_OP (2, "Invalid COMPONENT_REF offset operator");
3293           else if (TREE_CODE (t) == ARRAY_REF
3294                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3295             {
3296               CHECK_OP (1, "Invalid array index.");
3297               if (TREE_OPERAND (t, 2))
3298                 CHECK_OP (2, "Invalid array lower bound.");
3299               if (TREE_OPERAND (t, 3))
3300                 CHECK_OP (3, "Invalid array stride.");
3301             }
3302           else if (TREE_CODE (t) == BIT_FIELD_REF)
3303             {
3304               CHECK_OP (1, "Invalid operand to BIT_FIELD_REF");
3305               CHECK_OP (2, "Invalid operand to BIT_FIELD_REF");
3306             }
3307
3308           t = TREE_OPERAND (t, 0);
3309         }
3310
3311       if (!CONSTANT_CLASS_P (t) && !is_gimple_lvalue (t))
3312         {
3313           error ("Invalid reference prefix.");
3314           return t;
3315         }
3316       *walk_subtrees = 0;
3317       break;
3318
3319     case LT_EXPR:
3320     case LE_EXPR:
3321     case GT_EXPR:
3322     case GE_EXPR:
3323     case EQ_EXPR:
3324     case NE_EXPR:
3325     case UNORDERED_EXPR:
3326     case ORDERED_EXPR:
3327     case UNLT_EXPR:
3328     case UNLE_EXPR:
3329     case UNGT_EXPR:
3330     case UNGE_EXPR:
3331     case UNEQ_EXPR:
3332     case LTGT_EXPR:
3333     case PLUS_EXPR:
3334     case MINUS_EXPR:
3335     case MULT_EXPR:
3336     case TRUNC_DIV_EXPR:
3337     case CEIL_DIV_EXPR:
3338     case FLOOR_DIV_EXPR:
3339     case ROUND_DIV_EXPR:
3340     case TRUNC_MOD_EXPR:
3341     case CEIL_MOD_EXPR:
3342     case FLOOR_MOD_EXPR:
3343     case ROUND_MOD_EXPR:
3344     case RDIV_EXPR:
3345     case EXACT_DIV_EXPR:
3346     case MIN_EXPR:
3347     case MAX_EXPR:
3348     case LSHIFT_EXPR:
3349     case RSHIFT_EXPR:
3350     case LROTATE_EXPR:
3351     case RROTATE_EXPR:
3352     case BIT_IOR_EXPR:
3353     case BIT_XOR_EXPR:
3354     case BIT_AND_EXPR:
3355       CHECK_OP (0, "Invalid operand to binary operator");
3356       CHECK_OP (1, "Invalid operand to binary operator");
3357       break;
3358
3359     default:
3360       break;
3361     }
3362   return NULL;
3363
3364 #undef CHECK_OP
3365 }
3366
3367
3368 /* Verify STMT, return true if STMT is not in GIMPLE form.
3369    TODO: Implement type checking.  */
3370
3371 static bool
3372 verify_stmt (tree stmt, bool last_in_block)
3373 {
3374   tree addr;
3375
3376   if (!is_gimple_stmt (stmt))
3377     {
3378       error ("Is not a valid GIMPLE statement.");
3379       goto fail;
3380     }
3381
3382   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3383   if (addr)
3384     {
3385       debug_generic_stmt (addr);
3386       return true;
3387     }
3388
3389   /* If the statement is marked as part of an EH region, then it is
3390      expected that the statement could throw.  Verify that when we
3391      have optimizations that simplify statements such that we prove
3392      that they cannot throw, that we update other data structures
3393      to match.  */
3394   if (lookup_stmt_eh_region (stmt) >= 0)
3395     {
3396       if (!tree_could_throw_p (stmt))
3397         {
3398           error ("Statement marked for throw, but doesn%'t.");
3399           goto fail;
3400         }
3401       if (!last_in_block && tree_can_throw_internal (stmt))
3402         {
3403           error ("Statement marked for throw in middle of block.");
3404           goto fail;
3405         }
3406     }
3407
3408   return false;
3409
3410  fail:
3411   debug_generic_stmt (stmt);
3412   return true;
3413 }
3414
3415
3416 /* Return true when the T can be shared.  */
3417
3418 static bool
3419 tree_node_can_be_shared (tree t)
3420 {
3421   if (IS_TYPE_OR_DECL_P (t)
3422       /* We check for constants explicitly since they are not considered
3423          gimple invariants if they overflowed.  */
3424       || CONSTANT_CLASS_P (t)
3425       || is_gimple_min_invariant (t)
3426       || TREE_CODE (t) == SSA_NAME)
3427     return true;
3428
3429   if (TREE_CODE (t) == CASE_LABEL_EXPR)
3430     return true;
3431
3432   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3433           /* We check for constants explicitly since they are not considered
3434              gimple invariants if they overflowed.  */
3435           && (CONSTANT_CLASS_P (TREE_OPERAND (t, 1))
3436               || is_gimple_min_invariant (TREE_OPERAND (t, 1))))
3437          || (TREE_CODE (t) == COMPONENT_REF
3438              || TREE_CODE (t) == REALPART_EXPR
3439              || TREE_CODE (t) == IMAGPART_EXPR))
3440     t = TREE_OPERAND (t, 0);
3441
3442   if (DECL_P (t))
3443     return true;
3444
3445   return false;
3446 }
3447
3448
3449 /* Called via walk_trees.  Verify tree sharing.  */
3450
3451 static tree
3452 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3453 {
3454   htab_t htab = (htab_t) data;
3455   void **slot;
3456
3457   if (tree_node_can_be_shared (*tp))
3458     {
3459       *walk_subtrees = false;
3460       return NULL;
3461     }
3462
3463   slot = htab_find_slot (htab, *tp, INSERT);
3464   if (*slot)
3465     return *slot;
3466   *slot = *tp;
3467
3468   return NULL;
3469 }
3470
3471
3472 /* Verify the GIMPLE statement chain.  */
3473
3474 void
3475 verify_stmts (void)
3476 {
3477   basic_block bb;
3478   block_stmt_iterator bsi;
3479   bool err = false;
3480   htab_t htab;
3481   tree addr;
3482
3483   timevar_push (TV_TREE_STMT_VERIFY);
3484   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3485
3486   FOR_EACH_BB (bb)
3487     {
3488       tree phi;
3489       int i;
3490
3491       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3492         {
3493           int phi_num_args = PHI_NUM_ARGS (phi);
3494
3495           for (i = 0; i < phi_num_args; i++)
3496             {
3497               tree t = PHI_ARG_DEF (phi, i);
3498               tree addr;
3499
3500               /* Addressable variables do have SSA_NAMEs but they
3501                  are not considered gimple values.  */
3502               if (TREE_CODE (t) != SSA_NAME
3503                   && TREE_CODE (t) != FUNCTION_DECL
3504                   && !is_gimple_val (t))
3505                 {
3506                   error ("PHI def is not a GIMPLE value");
3507                   debug_generic_stmt (phi);
3508                   debug_generic_stmt (t);
3509                   err |= true;
3510                 }
3511
3512               addr = walk_tree (&t, verify_expr, NULL, NULL);
3513               if (addr)
3514                 {
3515                   debug_generic_stmt (addr);
3516                   err |= true;
3517                 }
3518
3519               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3520               if (addr)
3521                 {
3522                   error ("Incorrect sharing of tree nodes");
3523                   debug_generic_stmt (phi);
3524                   debug_generic_stmt (addr);
3525                   err |= true;
3526                 }
3527             }
3528         }
3529
3530       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3531         {
3532           tree stmt = bsi_stmt (bsi);
3533           bsi_next (&bsi);
3534           err |= verify_stmt (stmt, bsi_end_p (bsi));
3535           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3536           if (addr)
3537             {
3538               error ("Incorrect sharing of tree nodes");
3539               debug_generic_stmt (stmt);
3540               debug_generic_stmt (addr);
3541               err |= true;
3542             }
3543         }
3544     }
3545
3546   if (err)
3547     internal_error ("verify_stmts failed.");
3548
3549   htab_delete (htab);
3550   timevar_pop (TV_TREE_STMT_VERIFY);
3551 }
3552
3553
3554 /* Verifies that the flow information is OK.  */
3555
3556 static int
3557 tree_verify_flow_info (void)
3558 {
3559   int err = 0;
3560   basic_block bb;
3561   block_stmt_iterator bsi;
3562   tree stmt;
3563   edge e;
3564   edge_iterator ei;
3565
3566   if (ENTRY_BLOCK_PTR->stmt_list)
3567     {
3568       error ("ENTRY_BLOCK has a statement list associated with it\n");
3569       err = 1;
3570     }
3571
3572   if (EXIT_BLOCK_PTR->stmt_list)
3573     {
3574       error ("EXIT_BLOCK has a statement list associated with it\n");
3575       err = 1;
3576     }
3577
3578   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
3579     if (e->flags & EDGE_FALLTHRU)
3580       {
3581         error ("Fallthru to exit from bb %d\n", e->src->index);
3582         err = 1;
3583       }
3584
3585   FOR_EACH_BB (bb)
3586     {
3587       bool found_ctrl_stmt = false;
3588
3589       /* Skip labels on the start of basic block.  */
3590       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3591         {
3592           if (TREE_CODE (bsi_stmt (bsi)) != LABEL_EXPR)
3593             break;
3594
3595           if (label_to_block (LABEL_EXPR_LABEL (bsi_stmt (bsi))) != bb)
3596             {
3597               tree stmt = bsi_stmt (bsi);
3598               error ("Label %s to block does not match in bb %d\n",
3599                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3600                      bb->index);
3601               err = 1;
3602             }
3603
3604           if (decl_function_context (LABEL_EXPR_LABEL (bsi_stmt (bsi)))
3605               != current_function_decl)
3606             {
3607               tree stmt = bsi_stmt (bsi);
3608               error ("Label %s has incorrect context in bb %d\n",
3609                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3610                      bb->index);
3611               err = 1;
3612             }
3613         }
3614
3615       /* Verify that body of basic block BB is free of control flow.  */
3616       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3617         {
3618           tree stmt = bsi_stmt (bsi);
3619
3620           if (found_ctrl_stmt)
3621             {
3622               error ("Control flow in the middle of basic block %d\n",
3623                      bb->index);
3624               err = 1;
3625             }
3626
3627           if (stmt_ends_bb_p (stmt))
3628             found_ctrl_stmt = true;
3629
3630           if (TREE_CODE (stmt) == LABEL_EXPR)
3631             {
3632               error ("Label %s in the middle of basic block %d\n",
3633                      IDENTIFIER_POINTER (DECL_NAME (stmt)),
3634                      bb->index);
3635               err = 1;
3636             }
3637         }
3638       bsi = bsi_last (bb);
3639       if (bsi_end_p (bsi))
3640         continue;
3641
3642       stmt = bsi_stmt (bsi);
3643
3644       if (is_ctrl_stmt (stmt))
3645         {
3646           FOR_EACH_EDGE (e, ei, bb->succs)
3647             if (e->flags & EDGE_FALLTHRU)
3648               {
3649                 error ("Fallthru edge after a control statement in bb %d \n",
3650                        bb->index);
3651                 err = 1;
3652               }
3653         }
3654
3655       switch (TREE_CODE (stmt))
3656         {
3657         case COND_EXPR:
3658           {
3659             edge true_edge;
3660             edge false_edge;
3661             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3662                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3663               {
3664                 error ("Structured COND_EXPR at the end of bb %d\n", bb->index);
3665                 err = 1;
3666               }
3667
3668             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3669
3670             if (!true_edge || !false_edge
3671                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3672                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3673                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3674                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3675                 || EDGE_COUNT (bb->succs) >= 3)
3676               {
3677                 error ("Wrong outgoing edge flags at end of bb %d\n",
3678                        bb->index);
3679                 err = 1;
3680               }
3681
3682             if (!has_label_p (true_edge->dest,
3683                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3684               {
3685                 error ("%<then%> label does not match edge at end of bb %d\n",
3686                        bb->index);
3687                 err = 1;
3688               }
3689
3690             if (!has_label_p (false_edge->dest,
3691                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3692               {
3693                 error ("%<else%> label does not match edge at end of bb %d\n",
3694                        bb->index);
3695                 err = 1;
3696               }
3697           }
3698           break;
3699
3700         case GOTO_EXPR:
3701           if (simple_goto_p (stmt))
3702             {
3703               error ("Explicit goto at end of bb %d\n", bb->index);
3704               err = 1;
3705             }
3706           else
3707             {
3708               /* FIXME.  We should double check that the labels in the
3709                  destination blocks have their address taken.  */
3710               FOR_EACH_EDGE (e, ei, bb->succs)
3711                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3712                                  | EDGE_FALSE_VALUE))
3713                     || !(e->flags & EDGE_ABNORMAL))
3714                   {
3715                     error ("Wrong outgoing edge flags at end of bb %d\n",
3716                            bb->index);
3717                     err = 1;
3718                   }
3719             }
3720           break;
3721
3722         case RETURN_EXPR:
3723           if (EDGE_COUNT (bb->succs) != 1
3724               || (EDGE_SUCC (bb, 0)->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3725                                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3726             {
3727               error ("Wrong outgoing edge flags at end of bb %d\n", bb->index);
3728               err = 1;
3729             }
3730           if (EDGE_SUCC (bb, 0)->dest != EXIT_BLOCK_PTR)
3731             {
3732               error ("Return edge does not point to exit in bb %d\n",
3733                      bb->index);
3734               err = 1;
3735             }
3736           break;
3737
3738         case SWITCH_EXPR:
3739           {
3740             tree prev;
3741             edge e;
3742             size_t i, n;
3743             tree vec;
3744
3745             vec = SWITCH_LABELS (stmt);
3746             n = TREE_VEC_LENGTH (vec);
3747
3748             /* Mark all the destination basic blocks.  */
3749             for (i = 0; i < n; ++i)
3750               {
3751                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3752                 basic_block label_bb = label_to_block (lab);
3753
3754                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
3755                 label_bb->aux = (void *)1;
3756               }
3757
3758             /* Verify that the case labels are sorted.  */
3759             prev = TREE_VEC_ELT (vec, 0);
3760             for (i = 1; i < n - 1; ++i)
3761               {
3762                 tree c = TREE_VEC_ELT (vec, i);
3763                 if (! CASE_LOW (c))
3764                   {
3765                     error ("Found default case not at end of case vector");
3766                     err = 1;
3767                     continue;
3768                   }
3769                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
3770                   {
3771                     error ("Case labels not sorted:\n ");
3772                     print_generic_expr (stderr, prev, 0);
3773                     fprintf (stderr," is greater than ");
3774                     print_generic_expr (stderr, c, 0);
3775                     fprintf (stderr," but comes before it.\n");
3776                     err = 1;
3777                   }
3778                 prev = c;
3779               }
3780             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
3781               {
3782                 error ("No default case found at end of case vector");
3783                 err = 1;
3784               }
3785
3786             FOR_EACH_EDGE (e, ei, bb->succs)
3787               {
3788                 if (!e->dest->aux)
3789                   {
3790                     error ("Extra outgoing edge %d->%d\n",
3791                            bb->index, e->dest->index);
3792                     err = 1;
3793                   }
3794                 e->dest->aux = (void *)2;
3795                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3796                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3797                   {
3798                     error ("Wrong outgoing edge flags at end of bb %d\n",
3799                            bb->index);
3800                     err = 1;
3801                   }
3802               }
3803
3804             /* Check that we have all of them.  */
3805             for (i = 0; i < n; ++i)
3806               {
3807                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3808                 basic_block label_bb = label_to_block (lab);
3809
3810                 if (label_bb->aux != (void *)2)
3811                   {
3812                     error ("Missing edge %i->%i\n",
3813                            bb->index, label_bb->index);
3814                     err = 1;
3815                   }
3816               }
3817
3818             FOR_EACH_EDGE (e, ei, bb->succs)
3819               e->dest->aux = (void *)0;
3820           }
3821
3822         default: ;
3823         }
3824     }
3825
3826   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
3827     verify_dominators (CDI_DOMINATORS);
3828
3829   return err;
3830 }
3831
3832
3833 /* Updates phi nodes after creating a forwarder block joined
3834    by edge FALLTHRU.  */
3835
3836 static void
3837 tree_make_forwarder_block (edge fallthru)
3838 {
3839   edge e;
3840   edge_iterator ei;
3841   basic_block dummy, bb;
3842   tree phi, new_phi, var;
3843
3844   dummy = fallthru->src;
3845   bb = fallthru->dest;
3846
3847   if (EDGE_COUNT (bb->preds) == 1)
3848     return;
3849
3850   /* If we redirected a branch we must create new phi nodes at the
3851      start of BB.  */
3852   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
3853     {
3854       var = PHI_RESULT (phi);
3855       new_phi = create_phi_node (var, bb);
3856       SSA_NAME_DEF_STMT (var) = new_phi;
3857       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
3858       add_phi_arg (&new_phi, PHI_RESULT (phi), fallthru);
3859     }
3860
3861   /* Ensure that the PHI node chain is in the same order.  */
3862   set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
3863
3864   /* Add the arguments we have stored on edges.  */
3865   FOR_EACH_EDGE (e, ei, bb->preds)
3866     {
3867       if (e == fallthru)
3868         continue;
3869
3870       flush_pending_stmts (e);
3871     }
3872 }
3873
3874
3875 /* Return true if basic block BB does nothing except pass control
3876    flow to another block and that we can safely insert a label at
3877    the start of the successor block.
3878
3879    As a precondition, we require that BB be not equal to
3880    ENTRY_BLOCK_PTR.  */
3881
3882 static bool
3883 tree_forwarder_block_p (basic_block bb)
3884 {
3885   block_stmt_iterator bsi;
3886   edge e;
3887   edge_iterator ei;
3888
3889   /* BB must have a single outgoing edge.  */
3890   if (EDGE_COUNT (bb->succs) != 1
3891       /* BB can not have any PHI nodes.  This could potentially be
3892          relaxed early in compilation if we re-rewrote the variables
3893          appearing in any PHI nodes in forwarder blocks.  */
3894       || phi_nodes (bb)
3895       /* BB may not be a predecessor of EXIT_BLOCK_PTR.  */
3896       || EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR
3897       /* BB may not have an abnormal outgoing edge.  */
3898       || (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL))
3899     return false;
3900
3901 #if ENABLE_CHECKING
3902   gcc_assert (bb != ENTRY_BLOCK_PTR);
3903 #endif
3904
3905   /* Successors of the entry block are not forwarders.  */
3906   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
3907     if (e->dest == bb)
3908       return false;
3909
3910   /* Now walk through the statements.  We can ignore labels, anything else
3911      means this is not a forwarder block.  */
3912   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3913     {
3914       tree stmt = bsi_stmt (bsi);
3915
3916       switch (TREE_CODE (stmt))
3917         {
3918         case LABEL_EXPR:
3919           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3920             return false;
3921           break;
3922
3923         default:
3924           return false;
3925         }
3926     }
3927
3928   return true;
3929 }
3930
3931 /* Thread jumps from BB.  */
3932
3933 static bool
3934 thread_jumps_from_bb (basic_block bb)
3935 {
3936   edge_iterator ei;
3937   edge e;
3938   bool retval = false;
3939
3940   /* Examine each of our block's successors to see if it is
3941      forwardable.  */
3942   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3943     {
3944       int freq;
3945       gcov_type count;
3946       edge last, old;
3947       basic_block dest, tmp, curr, old_dest;
3948       tree phi;
3949       int arg;
3950
3951       /* If the edge is abnormal or its destination is not
3952          forwardable, then there's nothing to do.  */
3953       if ((e->flags & EDGE_ABNORMAL)
3954           || !bb_ann (e->dest)->forwardable)
3955         {
3956           ei_next (&ei);
3957           continue;
3958         }
3959
3960       /* Now walk through as many forwarder blocks as possible to find
3961          the ultimate destination we want to thread our jump to.  */
3962       last = EDGE_SUCC (e->dest, 0);
3963       bb_ann (e->dest)->forwardable = 0;
3964       for (dest = EDGE_SUCC (e->dest, 0)->dest;
3965            bb_ann (dest)->forwardable;
3966            last = EDGE_SUCC (dest, 0),
3967              dest = EDGE_SUCC (dest, 0)->dest)
3968         bb_ann (dest)->forwardable = 0;
3969
3970       /* Reset the forwardable marks to 1.  */
3971       for (tmp = e->dest;
3972            tmp != dest;
3973            tmp = EDGE_SUCC (tmp, 0)->dest)
3974         bb_ann (tmp)->forwardable = 1;
3975
3976       if (dest == e->dest)
3977         {
3978           ei_next (&ei);
3979           continue;
3980         }
3981
3982       old = find_edge (bb, dest);
3983       if (old)
3984         {
3985           /* If there already is an edge, check whether the values in
3986              phi nodes differ.  */
3987           if (!phi_alternatives_equal (dest, last, old))
3988             {
3989               /* The previous block is forwarder.  Redirect our jump
3990                  to that target instead since we know it has no PHI
3991                  nodes that will need updating.  */
3992               dest = last->src;
3993
3994               /* That might mean that no forwarding at all is
3995                  possible.  */
3996               if (dest == e->dest)
3997                 {
3998                   ei_next (&ei);
3999                   continue;
4000                 }
4001
4002               old = find_edge (bb, dest);
4003             }
4004         }
4005
4006       /* Perform the redirection.  */
4007       retval = true;
4008       count = e->count;
4009       freq = EDGE_FREQUENCY (e);
4010       old_dest = e->dest;
4011       e = redirect_edge_and_branch (e, dest);
4012
4013       /* Update the profile.  */
4014       if (profile_status != PROFILE_ABSENT)
4015         for (curr = old_dest;
4016              curr != dest;
4017              curr = EDGE_SUCC (curr, 0)->dest)
4018           {
4019             curr->frequency -= freq;
4020             if (curr->frequency < 0)
4021               curr->frequency = 0;
4022             curr->count -= count;
4023             if (curr->count < 0)
4024               curr->count = 0;
4025             EDGE_SUCC (curr, 0)->count -= count;
4026             if (EDGE_SUCC (curr, 0)->count < 0)
4027               EDGE_SUCC (curr, 0)->count = 0;
4028           }
4029
4030       if (!old)
4031         {
4032           /* Update PHI nodes.  We know that the new argument should
4033              have the same value as the argument associated with LAST.
4034              Otherwise we would have changed our target block
4035              above.  */
4036           for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
4037             {
4038               arg = phi_arg_from_edge (phi, last);
4039               gcc_assert (arg >= 0);
4040               add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
4041             }
4042         }
4043
4044       /* Remove the unreachable blocks (observe that if all blocks
4045          were reachable before, only those in the path we threaded
4046          over and did not have any predecessor outside of the path
4047          become unreachable).  */
4048       for (; old_dest != dest; old_dest = tmp)
4049         {
4050           tmp = EDGE_SUCC (old_dest, 0)->dest;
4051
4052           if (EDGE_COUNT (old_dest->preds) > 0)
4053             break;
4054
4055           delete_basic_block (old_dest);
4056         }
4057
4058       /* Update the dominators.  */
4059       if (dom_info_available_p (CDI_DOMINATORS))
4060         {
4061           /* If the dominator of the destination was in the
4062              path, set its dominator to the start of the
4063              redirected edge.  */
4064           if (get_immediate_dominator (CDI_DOMINATORS, old_dest) == NULL)
4065             set_immediate_dominator (CDI_DOMINATORS, old_dest, bb);
4066
4067           /* Now proceed like if we forwarded just over one edge at a
4068              time.  Algorithm for forwarding edge S --> A over
4069              edge A --> B then is
4070
4071              if (idom (B) == A
4072                  && !dominated_by (S, B))
4073                idom (B) = idom (A);
4074              recount_idom (A);  */
4075
4076           for (; old_dest != dest; old_dest = tmp)
4077             {
4078               basic_block dom;
4079
4080               tmp = EDGE_SUCC (old_dest, 0)->dest;
4081
4082               if (get_immediate_dominator (CDI_DOMINATORS, tmp) == old_dest
4083                   && !dominated_by_p (CDI_DOMINATORS, bb, tmp))
4084                 {
4085                   dom = get_immediate_dominator (CDI_DOMINATORS, old_dest);
4086                   set_immediate_dominator (CDI_DOMINATORS, tmp, dom);
4087                 }
4088
4089               dom = recount_dominator (CDI_DOMINATORS, old_dest);
4090               set_immediate_dominator (CDI_DOMINATORS, old_dest, dom);
4091             }
4092         }
4093     }
4094
4095   return retval;
4096 }
4097
4098
4099 /* Thread jumps over empty statements.
4100
4101    This code should _not_ thread over obviously equivalent conditions
4102    as that requires nontrivial updates to the SSA graph.
4103
4104    As a precondition, we require that all basic blocks be reachable.
4105    That is, there should be no opportunities left for
4106    delete_unreachable_blocks.  */
4107
4108 static bool
4109 thread_jumps (void)
4110 {
4111   basic_block bb;
4112   bool retval = false;
4113   basic_block *worklist = xmalloc (sizeof (basic_block) * last_basic_block);
4114   basic_block *current = worklist;
4115
4116   FOR_EACH_BB (bb)
4117     {
4118       bb_ann (bb)->forwardable = tree_forwarder_block_p (bb);
4119       bb->flags &= ~BB_VISITED;
4120     }
4121
4122   /* We pretend to have ENTRY_BLOCK_PTR in WORKLIST.  This way,
4123      ENTRY_BLOCK_PTR will never be entered into WORKLIST.  */
4124   ENTRY_BLOCK_PTR->flags |= BB_VISITED;
4125
4126   /* Initialize WORKLIST by putting non-forwarder blocks that
4127      immediately precede forwarder blocks because those are the ones
4128      that we know we can thread jumps from.  We use BB_VISITED to
4129      indicate whether a given basic block is in WORKLIST or not,
4130      thereby avoiding duplicates in WORKLIST.  */
4131   FOR_EACH_BB (bb)
4132     {
4133       edge_iterator ei;
4134       edge e;
4135
4136       /* We are not interested in finding non-forwarder blocks
4137          directly.  We want to find non-forwarder blocks as
4138          predecessors of a forwarder block.  */
4139       if (!bb_ann (bb)->forwardable)
4140         continue;
4141
4142       /* Now we know BB is a forwarder block.  Visit each of its
4143          incoming edges and add to WORKLIST all non-forwarder blocks
4144          among BB's predecessors.  */
4145       FOR_EACH_EDGE (e, ei, bb->preds)
4146         {
4147           /* We don't want to put a duplicate into WORKLIST.  */
4148           if ((e->src->flags & BB_VISITED) == 0
4149               /* We are not interested in threading jumps from a forwarder
4150                  block.  */
4151               && !bb_ann (e->src)->forwardable)
4152             {
4153               e->src->flags |= BB_VISITED;
4154               *current++ = e->src;
4155             }
4156         }
4157     }
4158
4159   /* Now let's drain WORKLIST.  */
4160   while (worklist != current)
4161     {
4162       bb = *--current;
4163
4164       /* BB is no longer in WORKLIST, so clear BB_VISITED.  */
4165       bb->flags &= ~BB_VISITED;
4166
4167       if (thread_jumps_from_bb (bb))
4168         {
4169           retval = true;
4170
4171           if (tree_forwarder_block_p (bb))
4172             {
4173               edge_iterator ej;
4174               edge f;
4175
4176               bb_ann (bb)->forwardable = true;
4177
4178               /* Attempts to thread through BB may have been blocked
4179                  because BB was not a forwarder block before.  Now
4180                  that BB is a forwarder block, we should revisit BB's
4181                  predecessors.  */
4182               FOR_EACH_EDGE (f, ej, bb->preds)
4183                 {
4184                   /* We don't want to put a duplicate into WORKLIST.  */
4185                   if ((f->src->flags & BB_VISITED) == 0
4186                       /* We are not interested in threading jumps from a
4187                          forwarder block.  */
4188                       && !bb_ann (f->src)->forwardable)
4189                     {
4190                       f->src->flags |= BB_VISITED;
4191                       *current++ = f->src;
4192                     }
4193                 }
4194             }
4195         }
4196     }
4197
4198   ENTRY_BLOCK_PTR->flags &= ~BB_VISITED;
4199
4200   free (worklist);
4201
4202   return retval;
4203 }
4204
4205
4206 /* Return a non-special label in the head of basic block BLOCK.
4207    Create one if it doesn't exist.  */
4208
4209 tree
4210 tree_block_label (basic_block bb)
4211 {
4212   block_stmt_iterator i, s = bsi_start (bb);
4213   bool first = true;
4214   tree label, stmt;
4215
4216   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
4217     {
4218       stmt = bsi_stmt (i);
4219       if (TREE_CODE (stmt) != LABEL_EXPR)
4220         break;
4221       label = LABEL_EXPR_LABEL (stmt);
4222       if (!DECL_NONLOCAL (label))
4223         {
4224           if (!first)
4225             bsi_move_before (&i, &s);
4226           return label;
4227         }
4228     }
4229
4230   label = create_artificial_label ();
4231   stmt = build1 (LABEL_EXPR, void_type_node, label);
4232   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
4233   return label;
4234 }
4235
4236
4237 /* Attempt to perform edge redirection by replacing a possibly complex
4238    jump instruction by a goto or by removing the jump completely.
4239    This can apply only if all edges now point to the same block.  The
4240    parameters and return values are equivalent to
4241    redirect_edge_and_branch.  */
4242
4243 static edge
4244 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4245 {
4246   basic_block src = e->src;
4247   edge tmp;
4248   block_stmt_iterator b;
4249   tree stmt;
4250   edge_iterator ei;
4251
4252   /* Verify that all targets will be TARGET.  */
4253   FOR_EACH_EDGE (tmp, ei, src->succs)
4254     if (tmp->dest != target && tmp != e)
4255       break;
4256
4257   if (tmp)
4258     return NULL;
4259
4260   b = bsi_last (src);
4261   if (bsi_end_p (b))
4262     return NULL;
4263   stmt = bsi_stmt (b);
4264
4265   if (TREE_CODE (stmt) == COND_EXPR
4266       || TREE_CODE (stmt) == SWITCH_EXPR)
4267     {
4268       bsi_remove (&b);
4269       e = ssa_redirect_edge (e, target);
4270       e->flags = EDGE_FALLTHRU;
4271       return e;
4272     }
4273
4274   return NULL;
4275 }
4276
4277
4278 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4279    edge representing the redirected branch.  */
4280
4281 static edge
4282 tree_redirect_edge_and_branch (edge e, basic_block dest)
4283 {
4284   basic_block bb = e->src;
4285   block_stmt_iterator bsi;
4286   edge ret;
4287   tree label, stmt;
4288
4289   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4290     return NULL;
4291
4292   if (e->src != ENTRY_BLOCK_PTR
4293       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4294     return ret;
4295
4296   if (e->dest == dest)
4297     return NULL;
4298
4299   label = tree_block_label (dest);
4300
4301   bsi = bsi_last (bb);
4302   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4303
4304   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4305     {
4306     case COND_EXPR:
4307       stmt = (e->flags & EDGE_TRUE_VALUE
4308               ? COND_EXPR_THEN (stmt)
4309               : COND_EXPR_ELSE (stmt));
4310       GOTO_DESTINATION (stmt) = label;
4311       break;
4312
4313     case GOTO_EXPR:
4314       /* No non-abnormal edges should lead from a non-simple goto, and
4315          simple ones should be represented implicitly.  */
4316       gcc_unreachable ();
4317
4318     case SWITCH_EXPR:
4319       {
4320         tree cases = get_cases_for_edge (e, stmt);
4321         edge e2 = find_edge (e->src, dest);
4322
4323         /* If we have a list of cases associated with E, then use it
4324            as it's a lot faster than walking the entire case vector.  */
4325         if (cases)
4326           {
4327             tree last, first;
4328
4329             first = cases;
4330             while (cases)
4331               {
4332                 last = cases;
4333                 CASE_LABEL (cases) = label;
4334                 cases = TREE_CHAIN (cases);
4335               }
4336
4337             /* If there was already an edge in the CFG, then we need
4338                to move all the cases associated with E to E2.  */
4339             if (e2)
4340               {
4341                 tree cases2 = get_cases_for_edge (e2, stmt);
4342
4343                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4344                 TREE_CHAIN (cases2) = first;
4345               }
4346           }
4347         else
4348           {
4349             tree vec = SWITCH_LABELS (stmt);
4350             size_t i, n = TREE_VEC_LENGTH (vec);
4351
4352             for (i = 0; i < n; i++)
4353               {
4354                 tree elt = TREE_VEC_ELT (vec, i);
4355
4356                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4357                   CASE_LABEL (elt) = label;
4358               }
4359           }
4360
4361         break;
4362       }
4363
4364     case RETURN_EXPR:
4365       bsi_remove (&bsi);
4366       e->flags |= EDGE_FALLTHRU;
4367       break;
4368
4369     default:
4370       /* Otherwise it must be a fallthru edge, and we don't need to
4371          do anything besides redirecting it.  */
4372       gcc_assert (e->flags & EDGE_FALLTHRU);
4373       break;
4374     }
4375
4376   /* Update/insert PHI nodes as necessary.  */
4377
4378   /* Now update the edges in the CFG.  */
4379   e = ssa_redirect_edge (e, dest);
4380
4381   return e;
4382 }
4383
4384
4385 /* Simple wrapper, as we can always redirect fallthru edges.  */
4386
4387 static basic_block
4388 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4389 {
4390   e = tree_redirect_edge_and_branch (e, dest);
4391   gcc_assert (e);
4392
4393   return NULL;
4394 }
4395
4396
4397 /* Splits basic block BB after statement STMT (but at least after the
4398    labels).  If STMT is NULL, BB is split just after the labels.  */
4399
4400 static basic_block
4401 tree_split_block (basic_block bb, void *stmt)
4402 {
4403   block_stmt_iterator bsi, bsi_tgt;
4404   tree act;
4405   basic_block new_bb;
4406   edge e;
4407   edge_iterator ei;
4408
4409   new_bb = create_empty_bb (bb);
4410
4411   /* Redirect the outgoing edges.  */
4412   new_bb->succs = bb->succs;
4413   bb->succs = NULL;
4414   FOR_EACH_EDGE (e, ei, new_bb->succs)
4415     e->src = new_bb;
4416
4417   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4418     stmt = NULL;
4419
4420   /* Move everything from BSI to the new basic block.  */
4421   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4422     {
4423       act = bsi_stmt (bsi);
4424       if (TREE_CODE (act) == LABEL_EXPR)
4425         continue;
4426
4427       if (!stmt)
4428         break;
4429
4430       if (stmt == act)
4431         {
4432           bsi_next (&bsi);
4433           break;
4434         }
4435     }
4436
4437   bsi_tgt = bsi_start (new_bb);
4438   while (!bsi_end_p (bsi))
4439     {
4440       act = bsi_stmt (bsi);
4441       bsi_remove (&bsi);
4442       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
4443     }
4444
4445   return new_bb;
4446 }
4447
4448
4449 /* Moves basic block BB after block AFTER.  */
4450
4451 static bool
4452 tree_move_block_after (basic_block bb, basic_block after)
4453 {
4454   if (bb->prev_bb == after)
4455     return true;
4456
4457   unlink_block (bb);
4458   link_block (bb, after);
4459
4460   return true;
4461 }
4462
4463
4464 /* Return true if basic_block can be duplicated.  */
4465
4466 static bool
4467 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4468 {
4469   return true;
4470 }
4471
4472 /* Create a duplicate of the basic block BB.  NOTE: This does not
4473    preserve SSA form.  */
4474
4475 static basic_block
4476 tree_duplicate_bb (basic_block bb)
4477 {
4478   basic_block new_bb;
4479   block_stmt_iterator bsi, bsi_tgt;
4480   tree phi, val;
4481   ssa_op_iter op_iter;
4482
4483   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4484
4485   /* First copy the phi nodes.  We do not copy phi node arguments here,
4486      since the edges are not ready yet.  Keep the chain of phi nodes in
4487      the same order, so that we can add them later.  */
4488   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4489     {
4490       mark_for_rewrite (PHI_RESULT (phi));
4491       create_phi_node (PHI_RESULT (phi), new_bb);
4492     }
4493   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
4494
4495   bsi_tgt = bsi_start (new_bb);
4496   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4497     {
4498       tree stmt = bsi_stmt (bsi);
4499       tree copy;
4500
4501       if (TREE_CODE (stmt) == LABEL_EXPR)
4502         continue;
4503
4504       /* Record the definitions.  */
4505       get_stmt_operands (stmt);
4506
4507       FOR_EACH_SSA_TREE_OPERAND (val, stmt, op_iter, SSA_OP_ALL_DEFS)
4508         mark_for_rewrite (val);
4509
4510       copy = unshare_expr (stmt);
4511
4512       /* Copy also the virtual operands.  */
4513       get_stmt_ann (copy);
4514       copy_virtual_operands (copy, stmt);
4515
4516       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4517     }
4518
4519   return new_bb;
4520 }
4521
4522 /* Basic block BB_COPY was created by code duplication.  Add phi node
4523    arguments for edges going out of BB_COPY.  The blocks that were
4524    duplicated have rbi->duplicated set to one.  */
4525
4526 void
4527 add_phi_args_after_copy_bb (basic_block bb_copy)
4528 {
4529   basic_block bb, dest;
4530   edge e, e_copy;
4531   edge_iterator ei;
4532   tree phi, phi_copy, phi_next, def;
4533
4534   bb = bb_copy->rbi->original;
4535
4536   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
4537     {
4538       if (!phi_nodes (e_copy->dest))
4539         continue;
4540
4541       if (e_copy->dest->rbi->duplicated)
4542         dest = e_copy->dest->rbi->original;
4543       else
4544         dest = e_copy->dest;
4545
4546       e = find_edge (bb, dest);
4547       if (!e)
4548         {
4549           /* During loop unrolling the target of the latch edge is copied.
4550              In this case we are not looking for edge to dest, but to
4551              duplicated block whose original was dest.  */
4552           FOR_EACH_EDGE (e, ei, bb->succs)
4553             if (e->dest->rbi->duplicated
4554                 && e->dest->rbi->original == dest)
4555               break;
4556
4557           gcc_assert (e != NULL);
4558         }
4559
4560       for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
4561            phi;
4562            phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
4563         {
4564           phi_next = PHI_CHAIN (phi);
4565
4566           gcc_assert (PHI_RESULT (phi) == PHI_RESULT (phi_copy));
4567           def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4568           add_phi_arg (&phi_copy, def, e_copy);
4569         }
4570     }
4571 }
4572
4573 /* Blocks in REGION_COPY array of length N_REGION were created by
4574    duplication of basic blocks.  Add phi node arguments for edges
4575    going from these blocks.  */
4576
4577 void
4578 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
4579 {
4580   unsigned i;
4581
4582   for (i = 0; i < n_region; i++)
4583     region_copy[i]->rbi->duplicated = 1;
4584
4585   for (i = 0; i < n_region; i++)
4586     add_phi_args_after_copy_bb (region_copy[i]);
4587
4588   for (i = 0; i < n_region; i++)
4589     region_copy[i]->rbi->duplicated = 0;
4590 }
4591
4592 /* Maps the old ssa name FROM_NAME to TO_NAME.  */
4593
4594 struct ssa_name_map_entry
4595 {
4596   tree from_name;
4597   tree to_name;
4598 };
4599
4600 /* Hash function for ssa_name_map_entry.  */
4601
4602 static hashval_t
4603 ssa_name_map_entry_hash (const void *entry)
4604 {
4605   const struct ssa_name_map_entry *en = entry;
4606   return SSA_NAME_VERSION (en->from_name);
4607 }
4608
4609 /* Equality function for ssa_name_map_entry.  */
4610
4611 static int
4612 ssa_name_map_entry_eq (const void *in_table, const void *ssa_name)
4613 {
4614   const struct ssa_name_map_entry *en = in_table;
4615
4616   return en->from_name == ssa_name;
4617 }
4618
4619 /* Allocate duplicates of ssa names in list DEFINITIONS and store the mapping
4620    to MAP.  */
4621
4622 void
4623 allocate_ssa_names (bitmap definitions, htab_t *map)
4624 {
4625   tree name;
4626   struct ssa_name_map_entry *entry;
4627   PTR *slot;
4628   unsigned ver;
4629   bitmap_iterator bi;
4630
4631   if (!*map)
4632     *map = htab_create (10, ssa_name_map_entry_hash,
4633                         ssa_name_map_entry_eq, free);
4634   EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
4635     {
4636       name = ssa_name (ver);
4637       slot = htab_find_slot_with_hash (*map, name, SSA_NAME_VERSION (name),
4638                                        INSERT);
4639       if (*slot)
4640         entry = *slot;
4641       else
4642         {
4643           entry = xmalloc (sizeof (struct ssa_name_map_entry));
4644           entry->from_name = name;
4645           *slot = entry;
4646         }
4647       entry->to_name = duplicate_ssa_name (name, SSA_NAME_DEF_STMT (name));
4648     }
4649 }
4650
4651 /* Rewrite the definition DEF in statement STMT to new ssa name as specified
4652    by the mapping MAP.  */
4653
4654 static void
4655 rewrite_to_new_ssa_names_def (def_operand_p def, tree stmt, htab_t map)
4656 {
4657   tree name = DEF_FROM_PTR (def);
4658   struct ssa_name_map_entry *entry;
4659
4660   gcc_assert (TREE_CODE (name) == SSA_NAME);
4661
4662   entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
4663   if (!entry)
4664     return;
4665
4666   SET_DEF (def, entry->to_name);
4667   SSA_NAME_DEF_STMT (entry->to_name) = stmt;
4668 }
4669
4670 /* Rewrite the USE to new ssa name as specified by the mapping MAP.  */
4671
4672 static void
4673 rewrite_to_new_ssa_names_use (use_operand_p use, htab_t map)
4674 {
4675   tree name = USE_FROM_PTR (use);
4676   struct ssa_name_map_entry *entry;
4677
4678   if (TREE_CODE (name) != SSA_NAME)
4679     return;
4680
4681   entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
4682   if (!entry)
4683     return;
4684
4685   SET_USE (use, entry->to_name);
4686 }
4687
4688 /* Rewrite the ssa names in basic block BB to new ones as specified by the
4689    mapping MAP.  */
4690
4691 void
4692 rewrite_to_new_ssa_names_bb (basic_block bb, htab_t map)
4693 {
4694   unsigned i;
4695   edge e;
4696   edge_iterator ei;
4697   tree phi, stmt;
4698   block_stmt_iterator bsi;
4699   use_optype uses;
4700   vuse_optype vuses;
4701   def_optype defs;
4702   v_may_def_optype v_may_defs;
4703   v_must_def_optype v_must_defs;
4704   stmt_ann_t ann;
4705
4706   FOR_EACH_EDGE (e, ei, bb->preds)
4707     if (e->flags & EDGE_ABNORMAL)
4708       break;
4709
4710   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4711     {
4712       rewrite_to_new_ssa_names_def (PHI_RESULT_PTR (phi), phi, map);
4713       if (e)
4714         SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
4715     }
4716
4717   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4718     {
4719       stmt = bsi_stmt (bsi);
4720       get_stmt_operands (stmt);
4721       ann = stmt_ann (stmt);
4722
4723       uses = USE_OPS (ann);
4724       for (i = 0; i < NUM_USES (uses); i++)
4725         rewrite_to_new_ssa_names_use (USE_OP_PTR (uses, i), map);
4726
4727       defs = DEF_OPS (ann);
4728       for (i = 0; i < NUM_DEFS (defs); i++)
4729         rewrite_to_new_ssa_names_def (DEF_OP_PTR (defs, i), stmt, map);
4730
4731       vuses = VUSE_OPS (ann);
4732       for (i = 0; i < NUM_VUSES (vuses); i++)
4733         rewrite_to_new_ssa_names_use (VUSE_OP_PTR (vuses, i), map);
4734
4735       v_may_defs = V_MAY_DEF_OPS (ann);
4736       for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
4737         {
4738           rewrite_to_new_ssa_names_use
4739                   (V_MAY_DEF_OP_PTR (v_may_defs, i), map);
4740           rewrite_to_new_ssa_names_def
4741                   (V_MAY_DEF_RESULT_PTR (v_may_defs, i), stmt, map);
4742         }
4743
4744       v_must_defs = V_MUST_DEF_OPS (ann);
4745       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
4746         {
4747           rewrite_to_new_ssa_names_def
4748             (V_MUST_DEF_RESULT_PTR (v_must_defs, i), stmt, map);
4749           rewrite_to_new_ssa_names_use
4750             (V_MUST_DEF_KILL_PTR (v_must_defs, i),  map);
4751         }
4752     }
4753
4754   FOR_EACH_EDGE (e, ei, bb->succs)
4755     for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
4756       {
4757         rewrite_to_new_ssa_names_use
4758                 (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e), map);
4759
4760         if (e->flags & EDGE_ABNORMAL)
4761           {
4762             tree op = PHI_ARG_DEF_FROM_EDGE (phi, e);
4763             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op) = 1;
4764           }
4765       }
4766 }
4767
4768 /* Rewrite the ssa names in N_REGION blocks REGION to the new ones as specified
4769    by the mapping MAP.  */
4770
4771 void
4772 rewrite_to_new_ssa_names (basic_block *region, unsigned n_region, htab_t map)
4773 {
4774   unsigned r;
4775
4776   for (r = 0; r < n_region; r++)
4777     rewrite_to_new_ssa_names_bb (region[r], map);
4778 }
4779
4780 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
4781    important exit edge EXIT.  By important we mean that no SSA name defined
4782    inside region is live over the other exit edges of the region.  All entry
4783    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
4784    to the duplicate of the region.  SSA form, dominance and loop information
4785    is updated.  The new basic blocks are stored to REGION_COPY in the same
4786    order as they had in REGION, provided that REGION_COPY is not NULL.
4787    The function returns false if it is unable to copy the region,
4788    true otherwise.  */
4789
4790 bool
4791 tree_duplicate_sese_region (edge entry, edge exit,
4792                             basic_block *region, unsigned n_region,
4793                             basic_block *region_copy)
4794 {
4795   unsigned i, n_doms, ver;
4796   bool free_region_copy = false, copying_header = false;
4797   struct loop *loop = entry->dest->loop_father;
4798   edge exit_copy;
4799   bitmap definitions;
4800   tree phi;
4801   basic_block *doms;
4802   htab_t ssa_name_map = NULL;
4803   edge redirected;
4804   bitmap_iterator bi;
4805
4806   if (!can_copy_bbs_p (region, n_region))
4807     return false;
4808
4809   /* Some sanity checking.  Note that we do not check for all possible
4810      missuses of the functions.  I.e. if you ask to copy something weird,
4811      it will work, but the state of structures probably will not be
4812      correct.  */
4813
4814   for (i = 0; i < n_region; i++)
4815     {
4816       /* We do not handle subloops, i.e. all the blocks must belong to the
4817          same loop.  */
4818       if (region[i]->loop_father != loop)
4819         return false;
4820
4821       if (region[i] != entry->dest
4822           && region[i] == loop->header)
4823         return false;
4824     }
4825
4826   loop->copy = loop;
4827
4828   /* In case the function is used for loop header copying (which is the primary
4829      use), ensure that EXIT and its copy will be new latch and entry edges.  */
4830   if (loop->header == entry->dest)
4831     {
4832       copying_header = true;
4833       loop->copy = loop->outer;
4834
4835       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
4836         return false;
4837
4838       for (i = 0; i < n_region; i++)
4839         if (region[i] != exit->src
4840             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
4841           return false;
4842     }
4843
4844   if (!region_copy)
4845     {
4846       region_copy = xmalloc (sizeof (basic_block) * n_region);
4847       free_region_copy = true;
4848     }
4849
4850   gcc_assert (!any_marked_for_rewrite_p ());
4851
4852   /* Record blocks outside the region that are duplicated by something
4853      inside.  */
4854   doms = xmalloc (sizeof (basic_block) * n_basic_blocks);
4855   n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
4856
4857   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
4858   definitions = marked_ssa_names ();
4859
4860   if (copying_header)
4861     {
4862       loop->header = exit->dest;
4863       loop->latch = exit->src;
4864     }
4865
4866   /* Redirect the entry and add the phi node arguments.  */
4867   redirected = redirect_edge_and_branch (entry, entry->dest->rbi->copy);
4868   gcc_assert (redirected != NULL);
4869   flush_pending_stmts (entry);
4870
4871   /* Concerning updating of dominators:  We must recount dominators
4872      for entry block and its copy.  Anything that is outside of the region, but
4873      was dominated by something inside needs recounting as well.  */
4874   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
4875   doms[n_doms++] = entry->dest->rbi->original;
4876   iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
4877   free (doms);
4878
4879   /* Add the other phi node arguments.  */
4880   add_phi_args_after_copy (region_copy, n_region);
4881
4882   /* Add phi nodes for definitions at exit.  TODO -- once we have immediate
4883      uses, it should be possible to emit phi nodes just for definitions that
4884      are used outside region.  */
4885   EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
4886     {
4887       tree name = ssa_name (ver);
4888
4889       phi = create_phi_node (name, exit->dest);
4890       add_phi_arg (&phi, name, exit);
4891       add_phi_arg (&phi, name, exit_copy);
4892
4893       SSA_NAME_DEF_STMT (name) = phi;
4894     }
4895
4896   /* And create new definitions inside region and its copy.  TODO -- once we
4897      have immediate uses, it might be better to leave definitions in region
4898      unchanged, create new ssa names for phi nodes on exit, and rewrite
4899      the uses, to avoid changing the copied region.  */
4900   allocate_ssa_names (definitions, &ssa_name_map);
4901   rewrite_to_new_ssa_names (region, n_region, ssa_name_map);
4902   allocate_ssa_names (definitions, &ssa_name_map);
4903   rewrite_to_new_ssa_names (region_copy, n_region, ssa_name_map);
4904   htab_delete (ssa_name_map);
4905
4906   if (free_region_copy)
4907     free (region_copy);
4908
4909   unmark_all_for_rewrite ();
4910   BITMAP_XFREE (definitions);
4911
4912   return true;
4913 }
4914
4915 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4916
4917 void
4918 dump_function_to_file (tree fn, FILE *file, int flags)
4919 {
4920   tree arg, vars, var;
4921   bool ignore_topmost_bind = false, any_var = false;
4922   basic_block bb;
4923   tree chain;
4924
4925   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4926
4927   arg = DECL_ARGUMENTS (fn);
4928   while (arg)
4929     {
4930       print_generic_expr (file, arg, dump_flags);
4931       if (TREE_CHAIN (arg))
4932         fprintf (file, ", ");
4933       arg = TREE_CHAIN (arg);
4934     }
4935   fprintf (file, ")\n");
4936
4937   if (flags & TDF_RAW)
4938     {
4939       dump_node (fn, TDF_SLIM | flags, file);
4940       return;
4941     }
4942
4943   /* When GIMPLE is lowered, the variables are no longer available in
4944      BIND_EXPRs, so display them separately.  */
4945   if (cfun && cfun->unexpanded_var_list)
4946     {
4947       ignore_topmost_bind = true;
4948
4949       fprintf (file, "{\n");
4950       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
4951         {
4952           var = TREE_VALUE (vars);
4953
4954           print_generic_decl (file, var, flags);
4955           fprintf (file, "\n");
4956
4957           any_var = true;
4958         }
4959     }
4960
4961   if (basic_block_info)
4962     {
4963       /* Make a CFG based dump.  */
4964       check_bb_profile (ENTRY_BLOCK_PTR, file);
4965       if (!ignore_topmost_bind)
4966         fprintf (file, "{\n");
4967
4968       if (any_var && n_basic_blocks)
4969         fprintf (file, "\n");
4970
4971       FOR_EACH_BB (bb)
4972         dump_generic_bb (file, bb, 2, flags);
4973
4974       fprintf (file, "}\n");
4975       check_bb_profile (EXIT_BLOCK_PTR, file);
4976     }
4977   else
4978     {
4979       int indent;
4980
4981       /* Make a tree based dump.  */
4982       chain = DECL_SAVED_TREE (fn);
4983
4984       if (TREE_CODE (chain) == BIND_EXPR)
4985         {
4986           if (ignore_topmost_bind)
4987             {
4988               chain = BIND_EXPR_BODY (chain);
4989               indent = 2;
4990             }
4991           else
4992             indent = 0;
4993         }
4994       else
4995         {
4996           if (!ignore_topmost_bind)
4997             fprintf (file, "{\n");
4998           indent = 2;
4999         }
5000
5001       if (any_var)
5002         fprintf (file, "\n");
5003
5004       print_generic_stmt_indented (file, chain, flags, indent);
5005       if (ignore_topmost_bind)
5006         fprintf (file, "}\n");
5007     }
5008
5009   fprintf (file, "\n\n");
5010 }
5011
5012
5013 /* Pretty print of the loops intermediate representation.  */
5014 static void print_loop (FILE *, struct loop *, int);
5015 static void print_pred_bbs (FILE *, basic_block bb);
5016 static void print_succ_bbs (FILE *, basic_block bb);
5017
5018
5019 /* Print the predecessors indexes of edge E on FILE.  */
5020
5021 static void
5022 print_pred_bbs (FILE *file, basic_block bb)
5023 {
5024   edge e;
5025   edge_iterator ei;
5026
5027   FOR_EACH_EDGE (e, ei, bb->preds)
5028     fprintf (file, "bb_%d", e->src->index);
5029 }
5030
5031
5032 /* Print the successors indexes of edge E on FILE.  */
5033
5034 static void
5035 print_succ_bbs (FILE *file, basic_block bb)
5036 {
5037   edge e;
5038   edge_iterator ei;
5039
5040   FOR_EACH_EDGE (e, ei, bb->succs)
5041     fprintf (file, "bb_%d", e->src->index);
5042 }
5043
5044
5045 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
5046
5047 static void
5048 print_loop (FILE *file, struct loop *loop, int indent)
5049 {
5050   char *s_indent;
5051   basic_block bb;
5052
5053   if (loop == NULL)
5054     return;
5055
5056   s_indent = (char *) alloca ((size_t) indent + 1);
5057   memset ((void *) s_indent, ' ', (size_t) indent);
5058   s_indent[indent] = '\0';
5059
5060   /* Print the loop's header.  */
5061   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
5062
5063   /* Print the loop's body.  */
5064   fprintf (file, "%s{\n", s_indent);
5065   FOR_EACH_BB (bb)
5066     if (bb->loop_father == loop)
5067       {
5068         /* Print the basic_block's header.  */
5069         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
5070         print_pred_bbs (file, bb);
5071         fprintf (file, "}, succs = {");
5072         print_succ_bbs (file, bb);
5073         fprintf (file, "})\n");
5074
5075         /* Print the basic_block's body.  */
5076         fprintf (file, "%s  {\n", s_indent);
5077         tree_dump_bb (bb, file, indent + 4);
5078         fprintf (file, "%s  }\n", s_indent);
5079       }
5080
5081   print_loop (file, loop->inner, indent + 2);
5082   fprintf (file, "%s}\n", s_indent);
5083   print_loop (file, loop->next, indent);
5084 }
5085
5086
5087 /* Follow a CFG edge from the entry point of the program, and on entry
5088    of a loop, pretty print the loop structure on FILE.  */
5089
5090 void
5091 print_loop_ir (FILE *file)
5092 {
5093   basic_block bb;
5094
5095   bb = BASIC_BLOCK (0);
5096   if (bb && bb->loop_father)
5097     print_loop (file, bb->loop_father, 0);
5098 }
5099
5100
5101 /* Debugging loops structure at tree level.  */
5102
5103 void
5104 debug_loop_ir (void)
5105 {
5106   print_loop_ir (stderr);
5107 }
5108
5109
5110 /* Return true if BB ends with a call, possibly followed by some
5111    instructions that must stay with the call.  Return false,
5112    otherwise.  */
5113
5114 static bool
5115 tree_block_ends_with_call_p (basic_block bb)
5116 {
5117   block_stmt_iterator bsi = bsi_last (bb);
5118   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
5119 }
5120
5121
5122 /* Return true if BB ends with a conditional branch.  Return false,
5123    otherwise.  */
5124
5125 static bool
5126 tree_block_ends_with_condjump_p (basic_block bb)
5127 {
5128   tree stmt = tsi_stmt (bsi_last (bb).tsi);
5129   return (TREE_CODE (stmt) == COND_EXPR);
5130 }
5131
5132
5133 /* Return true if we need to add fake edge to exit at statement T.
5134    Helper function for tree_flow_call_edges_add.  */
5135
5136 static bool
5137 need_fake_edge_p (tree t)
5138 {
5139   tree call;
5140
5141   /* NORETURN and LONGJMP calls already have an edge to exit.
5142      CONST, PURE and ALWAYS_RETURN calls do not need one.
5143      We don't currently check for CONST and PURE here, although
5144      it would be a good idea, because those attributes are
5145      figured out from the RTL in mark_constant_function, and
5146      the counter incrementation code from -fprofile-arcs
5147      leads to different results from -fbranch-probabilities.  */
5148   call = get_call_expr_in (t);
5149   if (call
5150       && !(call_expr_flags (call) &
5151            (ECF_NORETURN | ECF_LONGJMP | ECF_ALWAYS_RETURN)))
5152     return true;
5153
5154   if (TREE_CODE (t) == ASM_EXPR
5155        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
5156     return true;
5157
5158   return false;
5159 }
5160
5161
5162 /* Add fake edges to the function exit for any non constant and non
5163    noreturn calls, volatile inline assembly in the bitmap of blocks
5164    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
5165    the number of blocks that were split.
5166
5167    The goal is to expose cases in which entering a basic block does
5168    not imply that all subsequent instructions must be executed.  */
5169
5170 static int
5171 tree_flow_call_edges_add (sbitmap blocks)
5172 {
5173   int i;
5174   int blocks_split = 0;
5175   int last_bb = last_basic_block;
5176   bool check_last_block = false;
5177
5178   if (n_basic_blocks == 0)
5179     return 0;
5180
5181   if (! blocks)
5182     check_last_block = true;
5183   else
5184     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
5185
5186   /* In the last basic block, before epilogue generation, there will be
5187      a fallthru edge to EXIT.  Special care is required if the last insn
5188      of the last basic block is a call because make_edge folds duplicate
5189      edges, which would result in the fallthru edge also being marked
5190      fake, which would result in the fallthru edge being removed by
5191      remove_fake_edges, which would result in an invalid CFG.
5192
5193      Moreover, we can't elide the outgoing fake edge, since the block
5194      profiler needs to take this into account in order to solve the minimal
5195      spanning tree in the case that the call doesn't return.
5196
5197      Handle this by adding a dummy instruction in a new last basic block.  */
5198   if (check_last_block)
5199     {
5200       edge_iterator ei;
5201       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
5202       block_stmt_iterator bsi = bsi_last (bb);
5203       tree t = NULL_TREE;
5204       if (!bsi_end_p (bsi))
5205         t = bsi_stmt (bsi);
5206
5207       if (need_fake_edge_p (t))
5208         {
5209           edge e;
5210
5211           FOR_EACH_EDGE (e, ei, bb->succs)
5212             if (e->dest == EXIT_BLOCK_PTR)
5213               {
5214                 bsi_insert_on_edge (e, build_empty_stmt ());
5215                 bsi_commit_edge_inserts ();
5216                 break;
5217               }
5218         }
5219     }
5220
5221   /* Now add fake edges to the function exit for any non constant
5222      calls since there is no way that we can determine if they will
5223      return or not...  */
5224   for (i = 0; i < last_bb; i++)
5225     {
5226       basic_block bb = BASIC_BLOCK (i);
5227       block_stmt_iterator bsi;
5228       tree stmt, last_stmt;
5229
5230       if (!bb)
5231         continue;
5232
5233       if (blocks && !TEST_BIT (blocks, i))
5234         continue;
5235
5236       bsi = bsi_last (bb);
5237       if (!bsi_end_p (bsi))
5238         {
5239           last_stmt = bsi_stmt (bsi);
5240           do
5241             {
5242               stmt = bsi_stmt (bsi);
5243               if (need_fake_edge_p (stmt))
5244                 {
5245                   edge e;
5246                   /* The handling above of the final block before the
5247                      epilogue should be enough to verify that there is
5248                      no edge to the exit block in CFG already.
5249                      Calling make_edge in such case would cause us to
5250                      mark that edge as fake and remove it later.  */
5251 #ifdef ENABLE_CHECKING
5252                   if (stmt == last_stmt)
5253                     {
5254                       edge_iterator ei;
5255                       FOR_EACH_EDGE (e, ei, bb->succs)
5256                         gcc_assert (e->dest != EXIT_BLOCK_PTR);
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 };
5365
5366
5367 /* Split all critical edges.  */
5368
5369 static void
5370 split_critical_edges (void)
5371 {
5372   basic_block bb;
5373   edge e;
5374   edge_iterator ei;
5375
5376   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
5377      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
5378      mappings around the calls to split_edge.  */
5379   start_recording_case_labels ();
5380   FOR_ALL_BB (bb)
5381     {
5382       FOR_EACH_EDGE (e, ei, bb->succs)
5383         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
5384           {
5385             split_edge (e);
5386           }
5387     }
5388   end_recording_case_labels ();
5389 }
5390
5391 struct tree_opt_pass pass_split_crit_edges =
5392 {
5393   "crited",                          /* name */
5394   NULL,                          /* gate */
5395   split_critical_edges,          /* execute */
5396   NULL,                          /* sub */
5397   NULL,                          /* next */
5398   0,                             /* static_pass_number */
5399   TV_TREE_SPLIT_EDGES,           /* tv_id */
5400   PROP_cfg,                      /* properties required */
5401   PROP_no_crit_edges,            /* properties_provided */
5402   0,                             /* properties_destroyed */
5403   0,                             /* todo_flags_start */
5404   TODO_dump_func,                /* todo_flags_finish */
5405   0                              /* letter */
5406 };
5407
5408 \f
5409 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
5410    a temporary, make sure and register it to be renamed if necessary,
5411    and finally return the temporary.  Put the statements to compute
5412    EXP before the current statement in BSI.  */
5413
5414 tree
5415 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
5416 {
5417   tree t, new_stmt, orig_stmt;
5418
5419   if (is_gimple_val (exp))
5420     return exp;
5421
5422   t = make_rename_temp (type, NULL);
5423   new_stmt = build (MODIFY_EXPR, type, t, exp);
5424
5425   orig_stmt = bsi_stmt (*bsi);
5426   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
5427   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
5428
5429   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
5430
5431   return t;
5432 }
5433
5434 /* Build a ternary operation and gimplify it.  Emit code before BSI.
5435    Return the gimple_val holding the result.  */
5436
5437 tree
5438 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
5439                  tree type, tree a, tree b, tree c)
5440 {
5441   tree ret;
5442
5443   ret = fold (build3 (code, type, a, b, c));
5444   STRIP_NOPS (ret);
5445
5446   return gimplify_val (bsi, type, ret);
5447 }
5448
5449 /* Build a binary operation and gimplify it.  Emit code before BSI.
5450    Return the gimple_val holding the result.  */
5451
5452 tree
5453 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
5454                  tree type, tree a, tree b)
5455 {
5456   tree ret;
5457
5458   ret = fold (build2 (code, type, a, b));
5459   STRIP_NOPS (ret);
5460
5461   return gimplify_val (bsi, type, ret);
5462 }
5463
5464 /* Build a unary operation and gimplify it.  Emit code before BSI.
5465    Return the gimple_val holding the result.  */
5466
5467 tree
5468 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
5469                  tree a)
5470 {
5471   tree ret;
5472
5473   ret = fold (build1 (code, type, a));
5474   STRIP_NOPS (ret);
5475
5476   return gimplify_val (bsi, type, ret);
5477 }
5478
5479
5480 \f
5481 /* Emit return warnings.  */
5482
5483 static void
5484 execute_warn_function_return (void)
5485 {
5486 #ifdef USE_MAPPED_LOCATION
5487   source_location location;
5488 #else
5489   location_t *locus;
5490 #endif
5491   tree last;
5492   edge e;
5493   edge_iterator ei;
5494
5495   if (warn_missing_noreturn
5496       && !TREE_THIS_VOLATILE (cfun->decl)
5497       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
5498       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
5499     warning ("%Jfunction might be possible candidate for "
5500              "attribute %<noreturn%>",
5501              cfun->decl);
5502
5503   /* If we have a path to EXIT, then we do return.  */
5504   if (TREE_THIS_VOLATILE (cfun->decl)
5505       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
5506     {
5507 #ifdef USE_MAPPED_LOCATION
5508       location = UNKNOWN_LOCATION;
5509 #else
5510       locus = NULL;
5511 #endif
5512       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5513         {
5514           last = last_stmt (e->src);
5515           if (TREE_CODE (last) == RETURN_EXPR
5516 #ifdef USE_MAPPED_LOCATION
5517               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
5518 #else
5519               && (locus = EXPR_LOCUS (last)) != NULL)
5520 #endif
5521             break;
5522         }
5523 #ifdef USE_MAPPED_LOCATION
5524       if (location == UNKNOWN_LOCATION)
5525         location = cfun->function_end_locus;
5526       warning ("%H%<noreturn%> function does return", &location);
5527 #else
5528       if (!locus)
5529         locus = &cfun->function_end_locus;
5530       warning ("%H%<noreturn%> function does return", locus);
5531 #endif
5532     }
5533
5534   /* If we see "return;" in some basic block, then we do reach the end
5535      without returning a value.  */
5536   else if (warn_return_type
5537            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
5538            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
5539     {
5540       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5541         {
5542           tree last = last_stmt (e->src);
5543           if (TREE_CODE (last) == RETURN_EXPR
5544               && TREE_OPERAND (last, 0) == NULL)
5545             {
5546 #ifdef USE_MAPPED_LOCATION
5547               location = EXPR_LOCATION (last);
5548               if (location == UNKNOWN_LOCATION)
5549                   location = cfun->function_end_locus;
5550               warning ("%Hcontrol reaches end of non-void function", &location);
5551 #else
5552               locus = EXPR_LOCUS (last);
5553               if (!locus)
5554                 locus = &cfun->function_end_locus;
5555               warning ("%Hcontrol reaches end of non-void function", locus);
5556 #endif
5557               break;
5558             }
5559         }
5560     }
5561 }
5562
5563
5564 /* Given a basic block B which ends with a conditional and has
5565    precisely two successors, determine which of the edges is taken if
5566    the conditional is true and which is taken if the conditional is
5567    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
5568
5569 void
5570 extract_true_false_edges_from_block (basic_block b,
5571                                      edge *true_edge,
5572                                      edge *false_edge)
5573 {
5574   edge e = EDGE_SUCC (b, 0);
5575
5576   if (e->flags & EDGE_TRUE_VALUE)
5577     {
5578       *true_edge = e;
5579       *false_edge = EDGE_SUCC (b, 1);
5580     }
5581   else
5582     {
5583       *false_edge = e;
5584       *true_edge = EDGE_SUCC (b, 1);
5585     }
5586 }
5587
5588 struct tree_opt_pass pass_warn_function_return =
5589 {
5590   NULL,                                 /* name */
5591   NULL,                                 /* gate */
5592   execute_warn_function_return,         /* execute */
5593   NULL,                                 /* sub */
5594   NULL,                                 /* next */
5595   0,                                    /* static_pass_number */
5596   0,                                    /* tv_id */
5597   PROP_cfg,                             /* properties_required */
5598   0,                                    /* properties_provided */
5599   0,                                    /* properties_destroyed */
5600   0,                                    /* todo_flags_start */
5601   0,                                    /* todo_flags_finish */
5602   0                                     /* letter */
5603 };
5604
5605 #include "gt-tree-cfg.h"