gcc/tree-cfg.c

   1 /* Control flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
   3    2010, 2011, 2012  Free Software Foundation, Inc.
   4    Contributed by Diego Novillo <dnovillo@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "tm_p.h"
  28 #include "basic-block.h"
  29 #include "flags.h"
  30 #include "function.h"
  31 #include "ggc.h"
  32 #include "gimple-pretty-print.h"
  33 #include "tree-flow.h"
  34 #include "tree-dump.h"
  35 #include "tree-pass.h"
  36 #include "diagnostic-core.h"
  37 #include "except.h"
  38 #include "cfgloop.h"
  39 #include "tree-ssa-propagate.h"
  40 #include "value-prof.h"
  41 #include "pointer-set.h"
  42 #include "tree-inline.h"
  43
  44 /* This file contains functions for building the Control Flow Graph (CFG)
  45    for a function tree.  */
  46
  47 /* Local declarations.  */
  48
  49 /* Initial capacity for the basic block array.  */
  50 static const int initial_cfg_capacity = 20;
  51
  52 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
  53    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
  54    via their CASE_CHAIN field, which we clear after we're done with the
  55    hash table to prevent problems with duplication of GIMPLE_SWITCHes.
  56
  57    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
  58    update the case vector in response to edge redirections.
  59
  60    Right now this table is set up and torn down at key points in the
  61    compilation process.  It would be nice if we could make the table
  62    more persistent.  The key is getting notification of changes to
  63    the CFG (particularly edge removal, creation and redirection).  */
  64
  65 static struct pointer_map_t *edge_to_cases;
  66
  67 /* If we record edge_to_cases, this bitmap will hold indexes
  68    of basic blocks that end in a GIMPLE_SWITCH which we touched
  69    due to edge manipulations.  */
  70
  71 static bitmap touched_switch_bbs;
  72
  73 /* CFG statistics.  */
  74 struct cfg_stats_d
  75 {
  76   long num_merged_labels;
  77 };
  78
  79 static struct cfg_stats_d cfg_stats;
  80
  81 /* Nonzero if we found a computed goto while building basic blocks.  */
  82 static bool found_computed_goto;
  83
  84 /* Hash table to store last discriminator assigned for each locus.  */
  85 struct locus_discrim_map
  86 {
  87   location_t locus;
  88   int discriminator;
  89 };
  90 static htab_t discriminator_per_locus;
  91
  92 /* Basic blocks and flowgraphs.  */
  93 static void make_blocks (gimple_seq);
  94 static void factor_computed_gotos (void);
  95
  96 /* Edges.  */
  97 static void make_edges (void);
  98 static void make_cond_expr_edges (basic_block);
  99 static void make_gimple_switch_edges (basic_block);
 100 static void make_goto_expr_edges (basic_block);
 101 static void make_gimple_asm_edges (basic_block);
 102 static unsigned int locus_map_hash (const void *);
 103 static int locus_map_eq (const void *, const void *);
 104 static void assign_discriminator (location_t, basic_block);
 105 static edge gimple_redirect_edge_and_branch (edge, basic_block);
 106 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block);
 107 static unsigned int split_critical_edges (void);
 108
 109 /* Various helpers.  */
 110 static inline bool stmt_starts_bb_p (gimple, gimple);
 111 static int gimple_verify_flow_info (void);
 112 static void gimple_make_forwarder_block (edge);
 113 static void gimple_cfg2vcg (FILE *);
 114 static gimple first_non_label_stmt (basic_block);
 115 static bool verify_gimple_transaction (gimple);
 116
 117 /* Flowgraph optimization and cleanup.  */
 118 static void gimple_merge_blocks (basic_block, basic_block);
 119 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
 120 static void remove_bb (basic_block);
 121 static edge find_taken_edge_computed_goto (basic_block, tree);
 122 static edge find_taken_edge_cond_expr (basic_block, tree);
 123 static edge find_taken_edge_switch_expr (basic_block, tree);
 124 static tree find_case_label_for_value (gimple, tree);
 125
 126 void
 127 init_empty_tree_cfg_for_function (struct function *fn)
 128 {
 129   /* Initialize the basic block array.  */
 130   init_flow (fn);
 131   profile_status_for_function (fn) = PROFILE_ABSENT;
 132   n_basic_blocks_for_function (fn) = NUM_FIXED_BLOCKS;
 133   last_basic_block_for_function (fn) = NUM_FIXED_BLOCKS;
 134   basic_block_info_for_function (fn)
 135     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 136   VEC_safe_grow_cleared (basic_block, gc,
 137                          basic_block_info_for_function (fn),
 138                          initial_cfg_capacity);
 139
 140   /* Build a mapping of labels to their associated blocks.  */
 141   label_to_block_map_for_function (fn)
 142     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 143   VEC_safe_grow_cleared (basic_block, gc,
 144                          label_to_block_map_for_function (fn),
 145                          initial_cfg_capacity);
 146
 147   SET_BASIC_BLOCK_FOR_FUNCTION (fn, ENTRY_BLOCK,
 148                                 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn));
 149   SET_BASIC_BLOCK_FOR_FUNCTION (fn, EXIT_BLOCK,
 150                    EXIT_BLOCK_PTR_FOR_FUNCTION (fn));
 151
 152   ENTRY_BLOCK_PTR_FOR_FUNCTION (fn)->next_bb
 153     = EXIT_BLOCK_PTR_FOR_FUNCTION (fn);
 154   EXIT_BLOCK_PTR_FOR_FUNCTION (fn)->prev_bb
 155     = ENTRY_BLOCK_PTR_FOR_FUNCTION (fn);
 156 }
 157
 158 void
 159 init_empty_tree_cfg (void)
 160 {
 161   init_empty_tree_cfg_for_function (cfun);
 162 }
 163
 164 /*---------------------------------------------------------------------------
 165                               Create basic blocks
 166 ---------------------------------------------------------------------------*/
 167
 168 /* Entry point to the CFG builder for trees.  SEQ is the sequence of
 169    statements to be added to the flowgraph.  */
 170
 171 static void
 172 build_gimple_cfg (gimple_seq seq)
 173 {
 174   /* Register specific gimple functions.  */
 175   gimple_register_cfg_hooks ();
 176
 177   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
 178
 179   init_empty_tree_cfg ();
 180
 181   found_computed_goto = 0;
 182   make_blocks (seq);
 183
 184   /* Computed gotos are hell to deal with, especially if there are
 185      lots of them with a large number of destinations.  So we factor
 186      them to a common computed goto location before we build the
 187      edge list.  After we convert back to normal form, we will un-factor
 188      the computed gotos since factoring introduces an unwanted jump.  */
 189   if (found_computed_goto)
 190     factor_computed_gotos ();
 191
 192   /* Make sure there is always at least one block, even if it's empty.  */
 193   if (n_basic_blocks == NUM_FIXED_BLOCKS)
 194     create_empty_bb (ENTRY_BLOCK_PTR);
 195
 196   /* Adjust the size of the array.  */
 197   if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
 198     VEC_safe_grow_cleared (basic_block, gc, basic_block_info, n_basic_blocks);
 199
 200   /* To speed up statement iterator walks, we first purge dead labels.  */
 201   cleanup_dead_labels ();
 202
 203   /* Group case nodes to reduce the number of edges.
 204      We do this after cleaning up dead labels because otherwise we miss
 205      a lot of obvious case merging opportunities.  */
 206   group_case_labels ();
 207
 208   /* Create the edges of the flowgraph.  */
 209   discriminator_per_locus = htab_create (13, locus_map_hash, locus_map_eq,
 210                                          free);
 211   make_edges ();
 212   cleanup_dead_labels ();
 213   htab_delete (discriminator_per_locus);
 214
 215   /* Debugging dumps.  */
 216
 217   /* Write the flowgraph to a VCG file.  */
 218   {
 219     int local_dump_flags;
 220     FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
 221     if (vcg_file)
 222       {
 223         gimple_cfg2vcg (vcg_file);
 224         dump_end (TDI_vcg, vcg_file);
 225       }
 226   }
 227 }
 228
 229 static unsigned int
 230 execute_build_cfg (void)
 231 {
 232   gimple_seq body = gimple_body (current_function_decl);
 233
 234   build_gimple_cfg (body);
 235   gimple_set_body (current_function_decl, NULL);
 236   if (dump_file && (dump_flags & TDF_DETAILS))
 237     {
 238       fprintf (dump_file, "Scope blocks:\n");
 239       dump_scope_blocks (dump_file, dump_flags);
 240     }
 241   return 0;
 242 }
 243
 244 struct gimple_opt_pass pass_build_cfg =
 245 {
 246  {
 247   GIMPLE_PASS,
 248   "cfg",                                /* name */
 249   NULL,                                 /* gate */
 250   execute_build_cfg,                    /* execute */
 251   NULL,                                 /* sub */
 252   NULL,                                 /* next */
 253   0,                                    /* static_pass_number */
 254   TV_TREE_CFG,                          /* tv_id */
 255   PROP_gimple_leh,                      /* properties_required */
 256   PROP_cfg,                             /* properties_provided */
 257   0,                                    /* properties_destroyed */
 258   0,                                    /* todo_flags_start */
 259   TODO_verify_stmts | TODO_cleanup_cfg  /* todo_flags_finish */
 260  }
 261 };
 262
 263
 264 /* Return true if T is a computed goto.  */
 265
 266 static bool
 267 computed_goto_p (gimple t)
 268 {
 269   return (gimple_code (t) == GIMPLE_GOTO
 270           && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
 271 }
 272
 273
 274 /* Search the CFG for any computed gotos.  If found, factor them to a
 275    common computed goto site.  Also record the location of that site so
 276    that we can un-factor the gotos after we have converted back to
 277    normal form.  */
 278
 279 static void
 280 factor_computed_gotos (void)
 281 {
 282   basic_block bb;
 283   tree factored_label_decl = NULL;
 284   tree var = NULL;
 285   gimple factored_computed_goto_label = NULL;
 286   gimple factored_computed_goto = NULL;
 287
 288   /* We know there are one or more computed gotos in this function.
 289      Examine the last statement in each basic block to see if the block
 290      ends with a computed goto.  */
 291
 292   FOR_EACH_BB (bb)
 293     {
 294       gimple_stmt_iterator gsi = gsi_last_bb (bb);
 295       gimple last;
 296
 297       if (gsi_end_p (gsi))
 298         continue;
 299
 300       last = gsi_stmt (gsi);
 301
 302       /* Ignore the computed goto we create when we factor the original
 303          computed gotos.  */
 304       if (last == factored_computed_goto)
 305         continue;
 306
 307       /* If the last statement is a computed goto, factor it.  */
 308       if (computed_goto_p (last))
 309         {
 310           gimple assignment;
 311
 312           /* The first time we find a computed goto we need to create
 313              the factored goto block and the variable each original
 314              computed goto will use for their goto destination.  */
 315           if (!factored_computed_goto)
 316             {
 317               basic_block new_bb = create_empty_bb (bb);
 318               gimple_stmt_iterator new_gsi = gsi_start_bb (new_bb);
 319
 320               /* Create the destination of the factored goto.  Each original
 321                  computed goto will put its desired destination into this
 322                  variable and jump to the label we create immediately
 323                  below.  */
 324               var = create_tmp_var (ptr_type_node, "gotovar");
 325
 326               /* Build a label for the new block which will contain the
 327                  factored computed goto.  */
 328               factored_label_decl = create_artificial_label (UNKNOWN_LOCATION);
 329               factored_computed_goto_label
 330                 = gimple_build_label (factored_label_decl);
 331               gsi_insert_after (&new_gsi, factored_computed_goto_label,
 332                                 GSI_NEW_STMT);
 333
 334               /* Build our new computed goto.  */
 335               factored_computed_goto = gimple_build_goto (var);
 336               gsi_insert_after (&new_gsi, factored_computed_goto, GSI_NEW_STMT);
 337             }
 338
 339           /* Copy the original computed goto's destination into VAR.  */
 340           assignment = gimple_build_assign (var, gimple_goto_dest (last));
 341           gsi_insert_before (&gsi, assignment, GSI_SAME_STMT);
 342
 343           /* And re-vector the computed goto to the new destination.  */
 344           gimple_goto_set_dest (last, factored_label_decl);
 345         }
 346     }
 347 }
 348
 349
 350 /* Build a flowgraph for the sequence of stmts SEQ.  */
 351
 352 static void
 353 make_blocks (gimple_seq seq)
 354 {
 355   gimple_stmt_iterator i = gsi_start (seq);
 356   gimple stmt = NULL;
 357   bool start_new_block = true;
 358   bool first_stmt_of_seq = true;
 359   basic_block bb = ENTRY_BLOCK_PTR;
 360
 361   while (!gsi_end_p (i))
 362     {
 363       gimple prev_stmt;
 364
 365       prev_stmt = stmt;
 366       stmt = gsi_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_seq)
 374             gsi_split_seq_before (&i, &seq);
 375           bb = create_basic_block (seq, 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       gimple_set_bb (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         {
 390           /* If the stmt can make abnormal goto use a new temporary
 391              for the assignment to the LHS.  This makes sure the old value
 392              of the LHS is available on the abnormal edge.  Otherwise
 393              we will end up with overlapping life-ranges for abnormal
 394              SSA names.  */
 395           if (gimple_has_lhs (stmt)
 396               && stmt_can_make_abnormal_goto (stmt)
 397               && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt))))
 398             {
 399               tree lhs = gimple_get_lhs (stmt);
 400               tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
 401               gimple s = gimple_build_assign (lhs, tmp);
 402               gimple_set_location (s, gimple_location (stmt));
 403               gimple_set_block (s, gimple_block (stmt));
 404               gimple_set_lhs (stmt, tmp);
 405               if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE
 406                   || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE)
 407                 DECL_GIMPLE_REG_P (tmp) = 1;
 408               gsi_insert_after (&i, s, GSI_SAME_STMT);
 409             }
 410           start_new_block = true;
 411         }
 412
 413       gsi_next (&i);
 414       first_stmt_of_seq = false;
 415     }
 416 }
 417
 418
 419 /* Create and return a new empty basic block after bb AFTER.  */
 420
 421 static basic_block
 422 create_bb (void *h, void *e, basic_block after)
 423 {
 424   basic_block bb;
 425
 426   gcc_assert (!e);
 427
 428   /* Create and initialize a new basic block.  Since alloc_block uses
 429      GC allocation that clears memory to allocate a basic block, we do
 430      not have to clear the newly allocated basic block here.  */
 431   bb = alloc_block ();
 432
 433   bb->index = last_basic_block;
 434   bb->flags = BB_NEW;
 435   set_bb_seq (bb, h ? (gimple_seq) h : NULL);
 436
 437   /* Add the new block to the linked list of blocks.  */
 438   link_block (bb, after);
 439
 440   /* Grow the basic block array if needed.  */
 441   if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
 442     {
 443       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
 444       VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
 445     }
 446
 447   /* Add the newly created block to the array.  */
 448   SET_BASIC_BLOCK (last_basic_block, bb);
 449
 450   n_basic_blocks++;
 451   last_basic_block++;
 452
 453   return bb;
 454 }
 455
 456
 457 /*---------------------------------------------------------------------------
 458                                  Edge creation
 459 ---------------------------------------------------------------------------*/
 460
 461 /* Fold COND_EXPR_COND of each COND_EXPR.  */
 462
 463 void
 464 fold_cond_expr_cond (void)
 465 {
 466   basic_block bb;
 467
 468   FOR_EACH_BB (bb)
 469     {
 470       gimple stmt = last_stmt (bb);
 471
 472       if (stmt && gimple_code (stmt) == GIMPLE_COND)
 473         {
 474           location_t loc = gimple_location (stmt);
 475           tree cond;
 476           bool zerop, onep;
 477
 478           fold_defer_overflow_warnings ();
 479           cond = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node,
 480                               gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 481           if (cond)
 482             {
 483               zerop = integer_zerop (cond);
 484               onep = integer_onep (cond);
 485             }
 486           else
 487             zerop = onep = false;
 488
 489           fold_undefer_overflow_warnings (zerop || onep,
 490                                           stmt,
 491                                           WARN_STRICT_OVERFLOW_CONDITIONAL);
 492           if (zerop)
 493             gimple_cond_make_false (stmt);
 494           else if (onep)
 495             gimple_cond_make_true (stmt);
 496         }
 497     }
 498 }
 499
 500 /* Join all the blocks in the flowgraph.  */
 501
 502 static void
 503 make_edges (void)
 504 {
 505   basic_block bb;
 506   struct omp_region *cur_region = NULL;
 507
 508   /* Create an edge from entry to the first block with executable
 509      statements in it.  */
 510   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
 511
 512   /* Traverse the basic block array placing edges.  */
 513   FOR_EACH_BB (bb)
 514     {
 515       gimple last = last_stmt (bb);
 516       bool fallthru;
 517
 518       if (last)
 519         {
 520           enum gimple_code code = gimple_code (last);
 521           switch (code)
 522             {
 523             case GIMPLE_GOTO:
 524               make_goto_expr_edges (bb);
 525               fallthru = false;
 526               break;
 527             case GIMPLE_RETURN:
 528               make_edge (bb, EXIT_BLOCK_PTR, 0);
 529               fallthru = false;
 530               break;
 531             case GIMPLE_COND:
 532               make_cond_expr_edges (bb);
 533               fallthru = false;
 534               break;
 535             case GIMPLE_SWITCH:
 536               make_gimple_switch_edges (bb);
 537               fallthru = false;
 538               break;
 539             case GIMPLE_RESX:
 540               make_eh_edges (last);
 541               fallthru = false;
 542               break;
 543             case GIMPLE_EH_DISPATCH:
 544               fallthru = make_eh_dispatch_edges (last);
 545               break;
 546
 547             case GIMPLE_CALL:
 548               /* If this function receives a nonlocal goto, then we need to
 549                  make edges from this call site to all the nonlocal goto
 550                  handlers.  */
 551               if (stmt_can_make_abnormal_goto (last))
 552                 make_abnormal_goto_edges (bb, true);
 553
 554               /* If this statement has reachable exception handlers, then
 555                  create abnormal edges to them.  */
 556               make_eh_edges (last);
 557
 558               /* BUILTIN_RETURN is really a return statement.  */
 559               if (gimple_call_builtin_p (last, BUILT_IN_RETURN))
 560                 make_edge (bb, EXIT_BLOCK_PTR, 0), fallthru = false;
 561               /* Some calls are known not to return.  */
 562               else
 563                 fallthru = !(gimple_call_flags (last) & ECF_NORETURN);
 564               break;
 565
 566             case GIMPLE_ASSIGN:
 567                /* A GIMPLE_ASSIGN may throw internally and thus be considered
 568                   control-altering. */
 569               if (is_ctrl_altering_stmt (last))
 570                 make_eh_edges (last);
 571               fallthru = true;
 572               break;
 573
 574             case GIMPLE_ASM:
 575               make_gimple_asm_edges (bb);
 576               fallthru = true;
 577               break;
 578
 579             case GIMPLE_OMP_PARALLEL:
 580             case GIMPLE_OMP_TASK:
 581             case GIMPLE_OMP_FOR:
 582             case GIMPLE_OMP_SINGLE:
 583             case GIMPLE_OMP_MASTER:
 584             case GIMPLE_OMP_ORDERED:
 585             case GIMPLE_OMP_CRITICAL:
 586             case GIMPLE_OMP_SECTION:
 587               cur_region = new_omp_region (bb, code, cur_region);
 588               fallthru = true;
 589               break;
 590
 591             case GIMPLE_OMP_SECTIONS:
 592               cur_region = new_omp_region (bb, code, cur_region);
 593               fallthru = true;
 594               break;
 595
 596             case GIMPLE_OMP_SECTIONS_SWITCH:
 597               fallthru = false;
 598               break;
 599
 600             case GIMPLE_OMP_ATOMIC_LOAD:
 601             case GIMPLE_OMP_ATOMIC_STORE:
 602                fallthru = true;
 603                break;
 604
 605             case GIMPLE_OMP_RETURN:
 606               /* In the case of a GIMPLE_OMP_SECTION, the edge will go
 607                  somewhere other than the next block.  This will be
 608                  created later.  */
 609               cur_region->exit = bb;
 610               fallthru = cur_region->type != GIMPLE_OMP_SECTION;
 611               cur_region = cur_region->outer;
 612               break;
 613
 614             case GIMPLE_OMP_CONTINUE:
 615               cur_region->cont = bb;
 616               switch (cur_region->type)
 617                 {
 618                 case GIMPLE_OMP_FOR:
 619                   /* Mark all GIMPLE_OMP_FOR and GIMPLE_OMP_CONTINUE
 620                      succs edges as abnormal to prevent splitting
 621                      them.  */
 622                   single_succ_edge (cur_region->entry)->flags |= EDGE_ABNORMAL;
 623                   /* Make the loopback edge.  */
 624                   make_edge (bb, single_succ (cur_region->entry),
 625                              EDGE_ABNORMAL);
 626
 627                   /* Create an edge from GIMPLE_OMP_FOR to exit, which
 628                      corresponds to the case that the body of the loop
 629                      is not executed at all.  */
 630                   make_edge (cur_region->entry, bb->next_bb, EDGE_ABNORMAL);
 631                   make_edge (bb, bb->next_bb, EDGE_FALLTHRU | EDGE_ABNORMAL);
 632                   fallthru = false;
 633                   break;
 634
 635                 case GIMPLE_OMP_SECTIONS:
 636                   /* Wire up the edges into and out of the nested sections.  */
 637                   {
 638                     basic_block switch_bb = single_succ (cur_region->entry);
 639
 640                     struct omp_region *i;
 641                     for (i = cur_region->inner; i ; i = i->next)
 642                       {
 643                         gcc_assert (i->type == GIMPLE_OMP_SECTION);
 644                         make_edge (switch_bb, i->entry, 0);
 645                         make_edge (i->exit, bb, EDGE_FALLTHRU);
 646                       }
 647
 648                     /* Make the loopback edge to the block with
 649                        GIMPLE_OMP_SECTIONS_SWITCH.  */
 650                     make_edge (bb, switch_bb, 0);
 651
 652                     /* Make the edge from the switch to exit.  */
 653                     make_edge (switch_bb, bb->next_bb, 0);
 654                     fallthru = false;
 655                   }
 656                   break;
 657
 658                 default:
 659                   gcc_unreachable ();
 660                 }
 661               break;
 662
 663             case GIMPLE_TRANSACTION:
 664               {
 665                 tree abort_label = gimple_transaction_label (last);
 666                 if (abort_label)
 667                   make_edge (bb, label_to_block (abort_label), 0);
 668                 fallthru = true;
 669               }
 670               break;
 671
 672             default:
 673               gcc_assert (!stmt_ends_bb_p (last));
 674               fallthru = true;
 675             }
 676         }
 677       else
 678         fallthru = true;
 679
 680       if (fallthru)
 681         {
 682           make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 683           if (last)
 684             assign_discriminator (gimple_location (last), bb->next_bb);
 685         }
 686     }
 687
 688   if (root_omp_region)
 689     free_omp_regions ();
 690
 691   /* Fold COND_EXPR_COND of each COND_EXPR.  */
 692   fold_cond_expr_cond ();
 693 }
 694
 695 /* Trivial hash function for a location_t.  ITEM is a pointer to
 696    a hash table entry that maps a location_t to a discriminator.  */
 697
 698 static unsigned int
 699 locus_map_hash (const void *item)
 700 {
 701   return ((const struct locus_discrim_map *) item)->locus;
 702 }
 703
 704 /* Equality function for the locus-to-discriminator map.  VA and VB
 705    point to the two hash table entries to compare.  */
 706
 707 static int
 708 locus_map_eq (const void *va, const void *vb)
 709 {
 710   const struct locus_discrim_map *a = (const struct locus_discrim_map *) va;
 711   const struct locus_discrim_map *b = (const struct locus_discrim_map *) vb;
 712   return a->locus == b->locus;
 713 }
 714
 715 /* Find the next available discriminator value for LOCUS.  The
 716    discriminator distinguishes among several basic blocks that
 717    share a common locus, allowing for more accurate sample-based
 718    profiling.  */
 719
 720 static int
 721 next_discriminator_for_locus (location_t locus)
 722 {
 723   struct locus_discrim_map item;
 724   struct locus_discrim_map **slot;
 725
 726   item.locus = locus;
 727   item.discriminator = 0;
 728   slot = (struct locus_discrim_map **)
 729       htab_find_slot_with_hash (discriminator_per_locus, (void *) &item,
 730                                 (hashval_t) locus, INSERT);
 731   gcc_assert (slot);
 732   if (*slot == HTAB_EMPTY_ENTRY)
 733     {
 734       *slot = XNEW (struct locus_discrim_map);
 735       gcc_assert (*slot);
 736       (*slot)->locus = locus;
 737       (*slot)->discriminator = 0;
 738     }
 739   (*slot)->discriminator++;
 740   return (*slot)->discriminator;
 741 }
 742
 743 /* Return TRUE if LOCUS1 and LOCUS2 refer to the same source line.  */
 744
 745 static bool
 746 same_line_p (location_t locus1, location_t locus2)
 747 {
 748   expanded_location from, to;
 749
 750   if (locus1 == locus2)
 751     return true;
 752
 753   from = expand_location (locus1);
 754   to = expand_location (locus2);
 755
 756   if (from.line != to.line)
 757     return false;
 758   if (from.file == to.file)
 759     return true;
 760   return (from.file != NULL
 761           && to.file != NULL
 762           && filename_cmp (from.file, to.file) == 0);
 763 }
 764
 765 /* Assign a unique discriminator value to block BB if it begins at the same
 766    LOCUS as its predecessor block.  */
 767
 768 static void
 769 assign_discriminator (location_t locus, basic_block bb)
 770 {
 771   gimple first_in_to_bb, last_in_to_bb;
 772
 773   if (locus == 0 || bb->discriminator != 0)
 774     return;
 775
 776   first_in_to_bb = first_non_label_stmt (bb);
 777   last_in_to_bb = last_stmt (bb);
 778   if ((first_in_to_bb && same_line_p (locus, gimple_location (first_in_to_bb)))
 779       || (last_in_to_bb && same_line_p (locus, gimple_location (last_in_to_bb))))
 780     bb->discriminator = next_discriminator_for_locus (locus);
 781 }
 782
 783 /* Create the edges for a GIMPLE_COND starting at block BB.  */
 784
 785 static void
 786 make_cond_expr_edges (basic_block bb)
 787 {
 788   gimple entry = last_stmt (bb);
 789   gimple then_stmt, else_stmt;
 790   basic_block then_bb, else_bb;
 791   tree then_label, else_label;
 792   edge e;
 793   location_t entry_locus;
 794
 795   gcc_assert (entry);
 796   gcc_assert (gimple_code (entry) == GIMPLE_COND);
 797
 798   entry_locus = gimple_location (entry);
 799
 800   /* Entry basic blocks for each component.  */
 801   then_label = gimple_cond_true_label (entry);
 802   else_label = gimple_cond_false_label (entry);
 803   then_bb = label_to_block (then_label);
 804   else_bb = label_to_block (else_label);
 805   then_stmt = first_stmt (then_bb);
 806   else_stmt = first_stmt (else_bb);
 807
 808   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
 809   assign_discriminator (entry_locus, then_bb);
 810   e->goto_locus = gimple_location (then_stmt);
 811   if (e->goto_locus)
 812     e->goto_block = gimple_block (then_stmt);
 813   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
 814   if (e)
 815     {
 816       assign_discriminator (entry_locus, else_bb);
 817       e->goto_locus = gimple_location (else_stmt);
 818       if (e->goto_locus)
 819         e->goto_block = gimple_block (else_stmt);
 820     }
 821
 822   /* We do not need the labels anymore.  */
 823   gimple_cond_set_true_label (entry, NULL_TREE);
 824   gimple_cond_set_false_label (entry, NULL_TREE);
 825 }
 826
 827
 828 /* Called for each element in the hash table (P) as we delete the
 829    edge to cases hash table.
 830
 831    Clear all the TREE_CHAINs to prevent problems with copying of
 832    SWITCH_EXPRs and structure sharing rules, then free the hash table
 833    element.  */
 834
 835 static bool
 836 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
 837                        void *data ATTRIBUTE_UNUSED)
 838 {
 839   tree t, next;
 840
 841   for (t = (tree) *value; t; t = next)
 842     {
 843       next = CASE_CHAIN (t);
 844       CASE_CHAIN (t) = NULL;
 845     }
 846
 847   *value = NULL;
 848   return true;
 849 }
 850
 851 /* Start recording information mapping edges to case labels.  */
 852
 853 void
 854 start_recording_case_labels (void)
 855 {
 856   gcc_assert (edge_to_cases == NULL);
 857   edge_to_cases = pointer_map_create ();
 858   touched_switch_bbs = BITMAP_ALLOC (NULL);
 859 }
 860
 861 /* Return nonzero if we are recording information for case labels.  */
 862
 863 static bool
 864 recording_case_labels_p (void)
 865 {
 866   return (edge_to_cases != NULL);
 867 }
 868
 869 /* Stop recording information mapping edges to case labels and
 870    remove any information we have recorded.  */
 871 void
 872 end_recording_case_labels (void)
 873 {
 874   bitmap_iterator bi;
 875   unsigned i;
 876   pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
 877   pointer_map_destroy (edge_to_cases);
 878   edge_to_cases = NULL;
 879   EXECUTE_IF_SET_IN_BITMAP (touched_switch_bbs, 0, i, bi)
 880     {
 881       basic_block bb = BASIC_BLOCK (i);
 882       if (bb)
 883         {
 884           gimple stmt = last_stmt (bb);
 885           if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
 886             group_case_labels_stmt (stmt);
 887         }
 888     }
 889   BITMAP_FREE (touched_switch_bbs);
 890 }
 891
 892 /* If we are inside a {start,end}_recording_cases block, then return
 893    a chain of CASE_LABEL_EXPRs from T which reference E.
 894
 895    Otherwise return NULL.  */
 896
 897 static tree
 898 get_cases_for_edge (edge e, gimple t)
 899 {
 900   void **slot;
 901   size_t i, n;
 902
 903   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
 904      chains available.  Return NULL so the caller can detect this case.  */
 905   if (!recording_case_labels_p ())
 906     return NULL;
 907
 908   slot = pointer_map_contains (edge_to_cases, e);
 909   if (slot)
 910     return (tree) *slot;
 911
 912   /* If we did not find E in the hash table, then this must be the first
 913      time we have been queried for information about E & T.  Add all the
 914      elements from T to the hash table then perform the query again.  */
 915
 916   n = gimple_switch_num_labels (t);
 917   for (i = 0; i < n; i++)
 918     {
 919       tree elt = gimple_switch_label (t, i);
 920       tree lab = CASE_LABEL (elt);
 921       basic_block label_bb = label_to_block (lab);
 922       edge this_edge = find_edge (e->src, label_bb);
 923
 924       /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
 925          a new chain.  */
 926       slot = pointer_map_insert (edge_to_cases, this_edge);
 927       CASE_CHAIN (elt) = (tree) *slot;
 928       *slot = elt;
 929     }
 930
 931   return (tree) *pointer_map_contains (edge_to_cases, e);
 932 }
 933
 934 /* Create the edges for a GIMPLE_SWITCH starting at block BB.  */
 935
 936 static void
 937 make_gimple_switch_edges (basic_block bb)
 938 {
 939   gimple entry = last_stmt (bb);
 940   location_t entry_locus;
 941   size_t i, n;
 942
 943   entry_locus = gimple_location (entry);
 944
 945   n = gimple_switch_num_labels (entry);
 946
 947   for (i = 0; i < n; ++i)
 948     {
 949       tree lab = CASE_LABEL (gimple_switch_label (entry, i));
 950       basic_block label_bb = label_to_block (lab);
 951       make_edge (bb, label_bb, 0);
 952       assign_discriminator (entry_locus, label_bb);
 953     }
 954 }
 955
 956
 957 /* Return the basic block holding label DEST.  */
 958
 959 basic_block
 960 label_to_block_fn (struct function *ifun, tree dest)
 961 {
 962   int uid = LABEL_DECL_UID (dest);
 963
 964   /* We would die hard when faced by an undefined label.  Emit a label to
 965      the very first basic block.  This will hopefully make even the dataflow
 966      and undefined variable warnings quite right.  */
 967   if (seen_error () && uid < 0)
 968     {
 969       gimple_stmt_iterator gsi = gsi_start_bb (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 970       gimple stmt;
 971
 972       stmt = gimple_build_label (dest);
 973       gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 974       uid = LABEL_DECL_UID (dest);
 975     }
 976   if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
 977       <= (unsigned int) uid)
 978     return NULL;
 979   return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
 980 }
 981
 982 /* Create edges for an abnormal goto statement at block BB.  If FOR_CALL
 983    is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR.  */
 984
 985 void
 986 make_abnormal_goto_edges (basic_block bb, bool for_call)
 987 {
 988   basic_block target_bb;
 989   gimple_stmt_iterator gsi;
 990
 991   FOR_EACH_BB (target_bb)
 992     for (gsi = gsi_start_bb (target_bb); !gsi_end_p (gsi); gsi_next (&gsi))
 993       {
 994         gimple label_stmt = gsi_stmt (gsi);
 995         tree target;
 996
 997         if (gimple_code (label_stmt) != GIMPLE_LABEL)
 998           break;
 999
1000         target = gimple_label_label (label_stmt);
1001
1002         /* Make an edge to every label block that has been marked as a
1003            potential target for a computed goto or a non-local goto.  */
1004         if ((FORCED_LABEL (target) && !for_call)
1005             || (DECL_NONLOCAL (target) && for_call))
1006           {
1007             make_edge (bb, target_bb, EDGE_ABNORMAL);
1008             break;
1009           }
1010       }
1011 }
1012
1013 /* Create edges for a goto statement at block BB.  */
1014
1015 static void
1016 make_goto_expr_edges (basic_block bb)
1017 {
1018   gimple_stmt_iterator last = gsi_last_bb (bb);
1019   gimple goto_t = gsi_stmt (last);
1020
1021   /* A simple GOTO creates normal edges.  */
1022   if (simple_goto_p (goto_t))
1023     {
1024       tree dest = gimple_goto_dest (goto_t);
1025       basic_block label_bb = label_to_block (dest);
1026       edge e = make_edge (bb, label_bb, EDGE_FALLTHRU);
1027       e->goto_locus = gimple_location (goto_t);
1028       assign_discriminator (e->goto_locus, label_bb);
1029       if (e->goto_locus)
1030         e->goto_block = gimple_block (goto_t);
1031       gsi_remove (&last, true);
1032       return;
1033     }
1034
1035   /* A computed GOTO creates abnormal edges.  */
1036   make_abnormal_goto_edges (bb, false);
1037 }
1038
1039 /* Create edges for an asm statement with labels at block BB.  */
1040
1041 static void
1042 make_gimple_asm_edges (basic_block bb)
1043 {
1044   gimple stmt = last_stmt (bb);
1045   location_t stmt_loc = gimple_location (stmt);
1046   int i, n = gimple_asm_nlabels (stmt);
1047
1048   for (i = 0; i < n; ++i)
1049     {
1050       tree label = TREE_VALUE (gimple_asm_label_op (stmt, i));
1051       basic_block label_bb = label_to_block (label);
1052       make_edge (bb, label_bb, 0);
1053       assign_discriminator (stmt_loc, label_bb);
1054     }
1055 }
1056
1057 /*---------------------------------------------------------------------------
1058                                Flowgraph analysis
1059 ---------------------------------------------------------------------------*/
1060
1061 /* Cleanup useless labels in basic blocks.  This is something we wish
1062    to do early because it allows us to group case labels before creating
1063    the edges for the CFG, and it speeds up block statement iterators in
1064    all passes later on.
1065    We rerun this pass after CFG is created, to get rid of the labels that
1066    are no longer referenced.  After then we do not run it any more, since
1067    (almost) no new labels should be created.  */
1068
1069 /* A map from basic block index to the leading label of that block.  */
1070 static struct label_record
1071 {
1072   /* The label.  */
1073   tree label;
1074
1075   /* True if the label is referenced from somewhere.  */
1076   bool used;
1077 } *label_for_bb;
1078
1079 /* Given LABEL return the first label in the same basic block.  */
1080
1081 static tree
1082 main_block_label (tree label)
1083 {
1084   basic_block bb = label_to_block (label);
1085   tree main_label = label_for_bb[bb->index].label;
1086
1087   /* label_to_block possibly inserted undefined label into the chain.  */
1088   if (!main_label)
1089     {
1090       label_for_bb[bb->index].label = label;
1091       main_label = label;
1092     }
1093
1094   label_for_bb[bb->index].used = true;
1095   return main_label;
1096 }
1097
1098 /* Clean up redundant labels within the exception tree.  */
1099
1100 static void
1101 cleanup_dead_labels_eh (void)
1102 {
1103   eh_landing_pad lp;
1104   eh_region r;
1105   tree lab;
1106   int i;
1107
1108   if (cfun->eh == NULL)
1109     return;
1110
1111   for (i = 1; VEC_iterate (eh_landing_pad, cfun->eh->lp_array, i, lp); ++i)
1112     if (lp && lp->post_landing_pad)
1113       {
1114         lab = main_block_label (lp->post_landing_pad);
1115         if (lab != lp->post_landing_pad)
1116           {
1117             EH_LANDING_PAD_NR (lp->post_landing_pad) = 0;
1118             EH_LANDING_PAD_NR (lab) = lp->index;
1119           }
1120       }
1121
1122   FOR_ALL_EH_REGION (r)
1123     switch (r->type)
1124       {
1125       case ERT_CLEANUP:
1126       case ERT_MUST_NOT_THROW:
1127         break;
1128
1129       case ERT_TRY:
1130         {
1131           eh_catch c;
1132           for (c = r->u.eh_try.first_catch; c ; c = c->next_catch)
1133             {
1134               lab = c->label;
1135               if (lab)
1136                 c->label = main_block_label (lab);
1137             }
1138         }
1139         break;
1140
1141       case ERT_ALLOWED_EXCEPTIONS:
1142         lab = r->u.allowed.label;
1143         if (lab)
1144           r->u.allowed.label = main_block_label (lab);
1145         break;
1146       }
1147 }
1148
1149
1150 /* Cleanup redundant labels.  This is a three-step process:
1151      1) Find the leading label for each block.
1152      2) Redirect all references to labels to the leading labels.
1153      3) Cleanup all useless labels.  */
1154
1155 void
1156 cleanup_dead_labels (void)
1157 {
1158   basic_block bb;
1159   label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
1160
1161   /* Find a suitable label for each block.  We use the first user-defined
1162      label if there is one, or otherwise just the first label we see.  */
1163   FOR_EACH_BB (bb)
1164     {
1165       gimple_stmt_iterator i;
1166
1167       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
1168         {
1169           tree label;
1170           gimple stmt = gsi_stmt (i);
1171
1172           if (gimple_code (stmt) != GIMPLE_LABEL)
1173             break;
1174
1175           label = gimple_label_label (stmt);
1176
1177           /* If we have not yet seen a label for the current block,
1178              remember this one and see if there are more labels.  */
1179           if (!label_for_bb[bb->index].label)
1180             {
1181               label_for_bb[bb->index].label = label;
1182               continue;
1183             }
1184
1185           /* If we did see a label for the current block already, but it
1186              is an artificially created label, replace it if the current
1187              label is a user defined label.  */
1188           if (!DECL_ARTIFICIAL (label)
1189               && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
1190             {
1191               label_for_bb[bb->index].label = label;
1192               break;
1193             }
1194         }
1195     }
1196
1197   /* Now redirect all jumps/branches to the selected label.
1198      First do so for each block ending in a control statement.  */
1199   FOR_EACH_BB (bb)
1200     {
1201       gimple stmt = last_stmt (bb);
1202       tree label, new_label;
1203
1204       if (!stmt)
1205         continue;
1206
1207       switch (gimple_code (stmt))
1208         {
1209         case GIMPLE_COND:
1210           label = gimple_cond_true_label (stmt);
1211           if (label)
1212             {
1213               new_label = main_block_label (label);
1214               if (new_label != label)
1215                 gimple_cond_set_true_label (stmt, new_label);
1216             }
1217
1218           label = gimple_cond_false_label (stmt);
1219           if (label)
1220             {
1221               new_label = main_block_label (label);
1222               if (new_label != label)
1223                 gimple_cond_set_false_label (stmt, new_label);
1224             }
1225           break;
1226
1227         case GIMPLE_SWITCH:
1228           {
1229             size_t i, n = gimple_switch_num_labels (stmt);
1230
1231             /* Replace all destination labels.  */
1232             for (i = 0; i < n; ++i)
1233               {
1234                 tree case_label = gimple_switch_label (stmt, i);
1235                 label = CASE_LABEL (case_label);
1236                 new_label = main_block_label (label);
1237                 if (new_label != label)
1238                   CASE_LABEL (case_label) = new_label;
1239               }
1240             break;
1241           }
1242
1243         case GIMPLE_ASM:
1244           {
1245             int i, n = gimple_asm_nlabels (stmt);
1246
1247             for (i = 0; i < n; ++i)
1248               {
1249                 tree cons = gimple_asm_label_op (stmt, i);
1250                 tree label = main_block_label (TREE_VALUE (cons));
1251                 TREE_VALUE (cons) = label;
1252               }
1253             break;
1254           }
1255
1256         /* We have to handle gotos until they're removed, and we don't
1257            remove them until after we've created the CFG edges.  */
1258         case GIMPLE_GOTO:
1259           if (!computed_goto_p (stmt))
1260             {
1261               label = gimple_goto_dest (stmt);
1262               new_label = main_block_label (label);
1263               if (new_label != label)
1264                 gimple_goto_set_dest (stmt, new_label);
1265             }
1266           break;
1267
1268         case GIMPLE_TRANSACTION:
1269           {
1270             tree label = gimple_transaction_label (stmt);
1271             if (label)
1272               {
1273                 tree new_label = main_block_label (label);
1274                 if (new_label != label)
1275                   gimple_transaction_set_label (stmt, new_label);
1276               }
1277           }
1278           break;
1279
1280         default:
1281           break;
1282       }
1283     }
1284
1285   /* Do the same for the exception region tree labels.  */
1286   cleanup_dead_labels_eh ();
1287
1288   /* Finally, purge dead labels.  All user-defined labels and labels that
1289      can be the target of non-local gotos and labels which have their
1290      address taken are preserved.  */
1291   FOR_EACH_BB (bb)
1292     {
1293       gimple_stmt_iterator i;
1294       tree label_for_this_bb = label_for_bb[bb->index].label;
1295
1296       if (!label_for_this_bb)
1297         continue;
1298
1299       /* If the main label of the block is unused, we may still remove it.  */
1300       if (!label_for_bb[bb->index].used)
1301         label_for_this_bb = NULL;
1302
1303       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1304         {
1305           tree label;
1306           gimple stmt = gsi_stmt (i);
1307
1308           if (gimple_code (stmt) != GIMPLE_LABEL)
1309             break;
1310
1311           label = gimple_label_label (stmt);
1312
1313           if (label == label_for_this_bb
1314               || !DECL_ARTIFICIAL (label)
1315               || DECL_NONLOCAL (label)
1316               || FORCED_LABEL (label))
1317             gsi_next (&i);
1318           else
1319             gsi_remove (&i, true);
1320         }
1321     }
1322
1323   free (label_for_bb);
1324 }
1325
1326 /* Scan the sorted vector of cases in STMT (a GIMPLE_SWITCH) and combine
1327    the ones jumping to the same label.
1328    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1329
1330 void
1331 group_case_labels_stmt (gimple stmt)
1332 {
1333   int old_size = gimple_switch_num_labels (stmt);
1334   int i, j, new_size = old_size;
1335   tree default_case = NULL_TREE;
1336   tree default_label = NULL_TREE;
1337   bool has_default;
1338
1339   /* The default label is always the first case in a switch
1340      statement after gimplification if it was not optimized
1341      away */
1342   if (!CASE_LOW (gimple_switch_default_label (stmt))
1343       && !CASE_HIGH (gimple_switch_default_label (stmt)))
1344     {
1345       default_case = gimple_switch_default_label (stmt);
1346       default_label = CASE_LABEL (default_case);
1347       has_default = true;
1348     }
1349   else
1350     has_default = false;
1351
1352   /* Look for possible opportunities to merge cases.  */
1353   if (has_default)
1354     i = 1;
1355   else
1356     i = 0;
1357   while (i < old_size)
1358     {
1359       tree base_case, base_label, base_high;
1360       base_case = gimple_switch_label (stmt, i);
1361
1362       gcc_assert (base_case);
1363       base_label = CASE_LABEL (base_case);
1364
1365       /* Discard cases that have the same destination as the
1366          default case.  */
1367       if (base_label == default_label)
1368         {
1369           gimple_switch_set_label (stmt, i, NULL_TREE);
1370           i++;
1371           new_size--;
1372           continue;
1373         }
1374
1375       base_high = CASE_HIGH (base_case)
1376           ? CASE_HIGH (base_case)
1377           : CASE_LOW (base_case);
1378       i++;
1379
1380       /* Try to merge case labels.  Break out when we reach the end
1381          of the label vector or when we cannot merge the next case
1382          label with the current one.  */
1383       while (i < old_size)
1384         {
1385           tree merge_case = gimple_switch_label (stmt, i);
1386           tree merge_label = CASE_LABEL (merge_case);
1387           double_int bhp1 = double_int_add (tree_to_double_int (base_high),
1388                                             double_int_one);
1389
1390           /* Merge the cases if they jump to the same place,
1391              and their ranges are consecutive.  */
1392           if (merge_label == base_label
1393               && double_int_equal_p (tree_to_double_int (CASE_LOW (merge_case)),
1394                                      bhp1))
1395             {
1396               base_high = CASE_HIGH (merge_case) ?
1397                   CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1398               CASE_HIGH (base_case) = base_high;
1399               gimple_switch_set_label (stmt, i, NULL_TREE);
1400               new_size--;
1401               i++;
1402             }
1403           else
1404             break;
1405         }
1406     }
1407
1408   /* Compress the case labels in the label vector, and adjust the
1409      length of the vector.  */
1410   for (i = 0, j = 0; i < new_size; i++)
1411     {
1412       while (! gimple_switch_label (stmt, j))
1413         j++;
1414       gimple_switch_set_label (stmt, i,
1415                                gimple_switch_label (stmt, j++));
1416     }
1417
1418   gcc_assert (new_size <= old_size);
1419   gimple_switch_set_num_labels (stmt, new_size);
1420 }
1421
1422 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
1423    and scan the sorted vector of cases.  Combine the ones jumping to the
1424    same label.  */
1425
1426 void
1427 group_case_labels (void)
1428 {
1429   basic_block bb;
1430
1431   FOR_EACH_BB (bb)
1432     {
1433       gimple stmt = last_stmt (bb);
1434       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1435         group_case_labels_stmt (stmt);
1436     }
1437 }
1438
1439 /* Checks whether we can merge block B into block A.  */
1440
1441 static bool
1442 gimple_can_merge_blocks_p (basic_block a, basic_block b)
1443 {
1444   gimple stmt;
1445   gimple_stmt_iterator gsi;
1446   gimple_seq phis;
1447
1448   if (!single_succ_p (a))
1449     return false;
1450
1451   if (single_succ_edge (a)->flags & EDGE_COMPLEX)
1452     return false;
1453
1454   if (single_succ (a) != b)
1455     return false;
1456
1457   if (!single_pred_p (b))
1458     return false;
1459
1460   if (b == EXIT_BLOCK_PTR)
1461     return false;
1462
1463   /* If A ends by a statement causing exceptions or something similar, we
1464      cannot merge the blocks.  */
1465   stmt = last_stmt (a);
1466   if (stmt && stmt_ends_bb_p (stmt))
1467     return false;
1468
1469   /* Do not allow a block with only a non-local label to be merged.  */
1470   if (stmt
1471       && gimple_code (stmt) == GIMPLE_LABEL
1472       && DECL_NONLOCAL (gimple_label_label (stmt)))
1473     return false;
1474
1475   /* Examine the labels at the beginning of B.  */
1476   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
1477     {
1478       tree lab;
1479       stmt = gsi_stmt (gsi);
1480       if (gimple_code (stmt) != GIMPLE_LABEL)
1481         break;
1482       lab = gimple_label_label (stmt);
1483
1484       /* Do not remove user forced labels or for -O0 any user labels.  */
1485       if (!DECL_ARTIFICIAL (lab) && (!optimize || FORCED_LABEL (lab)))
1486         return false;
1487     }
1488
1489   /* Protect the loop latches.  */
1490   if (current_loops && b->loop_father->latch == b)
1491     return false;
1492
1493   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1494      is not up-to-date and a name-mapping is registered, we cannot eliminate
1495      any phis.  Symbols marked for renaming are never a problem though.  */
1496   phis = phi_nodes (b);
1497   if (!gimple_seq_empty_p (phis)
1498       && name_mappings_registered_p ())
1499     return false;
1500
1501   /* When not optimizing, don't merge if we'd lose goto_locus.  */
1502   if (!optimize
1503       && single_succ_edge (a)->goto_locus != UNKNOWN_LOCATION)
1504     {
1505       location_t goto_locus = single_succ_edge (a)->goto_locus;
1506       gimple_stmt_iterator prev, next;
1507       prev = gsi_last_nondebug_bb (a);
1508       next = gsi_after_labels (b);
1509       if (!gsi_end_p (next) && is_gimple_debug (gsi_stmt (next)))
1510         gsi_next_nondebug (&next);
1511       if ((gsi_end_p (prev)
1512            || gimple_location (gsi_stmt (prev)) != goto_locus)
1513           && (gsi_end_p (next)
1514               || gimple_location (gsi_stmt (next)) != goto_locus))
1515         return false;
1516     }
1517
1518   return true;
1519 }
1520
1521 /* Return true if the var whose chain of uses starts at PTR has no
1522    nondebug uses.  */
1523 bool
1524 has_zero_uses_1 (const ssa_use_operand_t *head)
1525 {
1526   const ssa_use_operand_t *ptr;
1527
1528   for (ptr = head->next; ptr != head; ptr = ptr->next)
1529     if (!is_gimple_debug (USE_STMT (ptr)))
1530       return false;
1531
1532   return true;
1533 }
1534
1535 /* Return true if the var whose chain of uses starts at PTR has a
1536    single nondebug use.  Set USE_P and STMT to that single nondebug
1537    use, if so, or to NULL otherwise.  */
1538 bool
1539 single_imm_use_1 (const ssa_use_operand_t *head,
1540                   use_operand_p *use_p, gimple *stmt)
1541 {
1542   ssa_use_operand_t *ptr, *single_use = 0;
1543
1544   for (ptr = head->next; ptr != head; ptr = ptr->next)
1545     if (!is_gimple_debug (USE_STMT (ptr)))
1546       {
1547         if (single_use)
1548           {
1549             single_use = NULL;
1550             break;
1551           }
1552         single_use = ptr;
1553       }
1554
1555   if (use_p)
1556     *use_p = single_use;
1557
1558   if (stmt)
1559     *stmt = single_use ? single_use->loc.stmt : NULL;
1560
1561   return !!single_use;
1562 }
1563
1564 /* Replaces all uses of NAME by VAL.  */
1565
1566 void
1567 replace_uses_by (tree name, tree val)
1568 {
1569   imm_use_iterator imm_iter;
1570   use_operand_p use;
1571   gimple stmt;
1572   edge e;
1573
1574   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1575     {
1576       FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1577         {
1578           replace_exp (use, val);
1579
1580           if (gimple_code (stmt) == GIMPLE_PHI)
1581             {
1582               e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use));
1583               if (e->flags & EDGE_ABNORMAL)
1584                 {
1585                   /* This can only occur for virtual operands, since
1586                      for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1587                      would prevent replacement.  */
1588                   gcc_checking_assert (!is_gimple_reg (name));
1589                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1590                 }
1591             }
1592         }
1593
1594       if (gimple_code (stmt) != GIMPLE_PHI)
1595         {
1596           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1597           gimple orig_stmt = stmt;
1598           size_t i;
1599
1600           /* Mark the block if we changed the last stmt in it.  */
1601           if (cfgcleanup_altered_bbs
1602               && stmt_ends_bb_p (stmt))
1603             bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1604
1605           /* FIXME.  It shouldn't be required to keep TREE_CONSTANT
1606              on ADDR_EXPRs up-to-date on GIMPLE.  Propagation will
1607              only change sth from non-invariant to invariant, and only
1608              when propagating constants.  */
1609           if (is_gimple_min_invariant (val))
1610             for (i = 0; i < gimple_num_ops (stmt); i++)
1611               {
1612                 tree op = gimple_op (stmt, i);
1613                 /* Operands may be empty here.  For example, the labels
1614                    of a GIMPLE_COND are nulled out following the creation
1615                    of the corresponding CFG edges.  */
1616                 if (op && TREE_CODE (op) == ADDR_EXPR)
1617                   recompute_tree_invariant_for_addr_expr (op);
1618               }
1619
1620           if (fold_stmt (&gsi))
1621             stmt = gsi_stmt (gsi);
1622
1623           if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
1624             gimple_purge_dead_eh_edges (gimple_bb (stmt));
1625
1626           update_stmt (stmt);
1627         }
1628     }
1629
1630   gcc_checking_assert (has_zero_uses (name));
1631
1632   /* Also update the trees stored in loop structures.  */
1633   if (current_loops)
1634     {
1635       struct loop *loop;
1636       loop_iterator li;
1637
1638       FOR_EACH_LOOP (li, loop, 0)
1639         {
1640           substitute_in_loop_info (loop, name, val);
1641         }
1642     }
1643 }
1644
1645 /* Merge block B into block A.  */
1646
1647 static void
1648 gimple_merge_blocks (basic_block a, basic_block b)
1649 {
1650   gimple_stmt_iterator last, gsi, psi;
1651
1652   if (dump_file)
1653     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1654
1655   /* Remove all single-valued PHI nodes from block B of the form
1656      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1657   gsi = gsi_last_bb (a);
1658   for (psi = gsi_start_phis (b); !gsi_end_p (psi); )
1659     {
1660       gimple phi = gsi_stmt (psi);
1661       tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1662       gimple copy;
1663       bool may_replace_uses = !is_gimple_reg (def)
1664                               || may_propagate_copy (def, use);
1665
1666       /* In case we maintain loop closed ssa form, do not propagate arguments
1667          of loop exit phi nodes.  */
1668       if (current_loops
1669           && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1670           && is_gimple_reg (def)
1671           && TREE_CODE (use) == SSA_NAME
1672           && a->loop_father != b->loop_father)
1673         may_replace_uses = false;
1674
1675       if (!may_replace_uses)
1676         {
1677           gcc_assert (is_gimple_reg (def));
1678
1679           /* Note that just emitting the copies is fine -- there is no problem
1680              with ordering of phi nodes.  This is because A is the single
1681              predecessor of B, therefore results of the phi nodes cannot
1682              appear as arguments of the phi nodes.  */
1683           copy = gimple_build_assign (def, use);
1684           gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1685           remove_phi_node (&psi, false);
1686         }
1687       else
1688         {
1689           /* If we deal with a PHI for virtual operands, we can simply
1690              propagate these without fussing with folding or updating
1691              the stmt.  */
1692           if (!is_gimple_reg (def))
1693             {
1694               imm_use_iterator iter;
1695               use_operand_p use_p;
1696               gimple stmt;
1697
1698               FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1699                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1700                   SET_USE (use_p, use);
1701
1702               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
1703                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use) = 1;
1704             }
1705           else
1706             replace_uses_by (def, use);
1707
1708           remove_phi_node (&psi, true);
1709         }
1710     }
1711
1712   /* Ensure that B follows A.  */
1713   move_block_after (b, a);
1714
1715   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1716   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1717
1718   /* Remove labels from B and set gimple_bb to A for other statements.  */
1719   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1720     {
1721       gimple stmt = gsi_stmt (gsi);
1722       if (gimple_code (stmt) == GIMPLE_LABEL)
1723         {
1724           tree label = gimple_label_label (stmt);
1725           int lp_nr;
1726
1727           gsi_remove (&gsi, false);
1728
1729           /* Now that we can thread computed gotos, we might have
1730              a situation where we have a forced label in block B
1731              However, the label at the start of block B might still be
1732              used in other ways (think about the runtime checking for
1733              Fortran assigned gotos).  So we can not just delete the
1734              label.  Instead we move the label to the start of block A.  */
1735           if (FORCED_LABEL (label))
1736             {
1737               gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1738               gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT);
1739             }
1740           /* Other user labels keep around in a form of a debug stmt.  */
1741           else if (!DECL_ARTIFICIAL (label) && MAY_HAVE_DEBUG_STMTS)
1742             {
1743               gimple dbg = gimple_build_debug_bind (label,
1744                                                     integer_zero_node,
1745                                                     stmt);
1746               gimple_debug_bind_reset_value (dbg);
1747               gsi_insert_before (&gsi, dbg, GSI_SAME_STMT);
1748             }
1749
1750           lp_nr = EH_LANDING_PAD_NR (label);
1751           if (lp_nr)
1752             {
1753               eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1754               lp->post_landing_pad = NULL;
1755             }
1756         }
1757       else
1758         {
1759           gimple_set_bb (stmt, a);
1760           gsi_next (&gsi);
1761         }
1762     }
1763
1764   /* Merge the sequences.  */
1765   last = gsi_last_bb (a);
1766   gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1767   set_bb_seq (b, NULL);
1768
1769   if (cfgcleanup_altered_bbs)
1770     bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1771 }
1772
1773
1774 /* Return the one of two successors of BB that is not reachable by a
1775    complex edge, if there is one.  Else, return BB.  We use
1776    this in optimizations that use post-dominators for their heuristics,
1777    to catch the cases in C++ where function calls are involved.  */
1778
1779 basic_block
1780 single_noncomplex_succ (basic_block bb)
1781 {
1782   edge e0, e1;
1783   if (EDGE_COUNT (bb->succs) != 2)
1784     return bb;
1785
1786   e0 = EDGE_SUCC (bb, 0);
1787   e1 = EDGE_SUCC (bb, 1);
1788   if (e0->flags & EDGE_COMPLEX)
1789     return e1->dest;
1790   if (e1->flags & EDGE_COMPLEX)
1791     return e0->dest;
1792
1793   return bb;
1794 }
1795
1796 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1797
1798 void
1799 notice_special_calls (gimple call)
1800 {
1801   int flags = gimple_call_flags (call);
1802
1803   if (flags & ECF_MAY_BE_ALLOCA)
1804     cfun->calls_alloca = true;
1805   if (flags & ECF_RETURNS_TWICE)
1806     cfun->calls_setjmp = true;
1807 }
1808
1809
1810 /* Clear flags set by notice_special_calls.  Used by dead code removal
1811    to update the flags.  */
1812
1813 void
1814 clear_special_calls (void)
1815 {
1816   cfun->calls_alloca = false;
1817   cfun->calls_setjmp = false;
1818 }
1819
1820 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1821
1822 static void
1823 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1824 {
1825   /* Since this block is no longer reachable, we can just delete all
1826      of its PHI nodes.  */
1827   remove_phi_nodes (bb);
1828
1829   /* Remove edges to BB's successors.  */
1830   while (EDGE_COUNT (bb->succs) > 0)
1831     remove_edge (EDGE_SUCC (bb, 0));
1832 }
1833
1834
1835 /* Remove statements of basic block BB.  */
1836
1837 static void
1838 remove_bb (basic_block bb)
1839 {
1840   gimple_stmt_iterator i;
1841
1842   if (dump_file)
1843     {
1844       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1845       if (dump_flags & TDF_DETAILS)
1846         {
1847           dump_bb (dump_file, bb, 0, 0);
1848           fprintf (dump_file, "\n");
1849         }
1850     }
1851
1852   if (current_loops)
1853     {
1854       struct loop *loop = bb->loop_father;
1855
1856       /* If a loop gets removed, clean up the information associated
1857          with it.  */
1858       if (loop->latch == bb
1859           || loop->header == bb)
1860         free_numbers_of_iterations_estimates_loop (loop);
1861     }
1862
1863   /* Remove all the instructions in the block.  */
1864   if (bb_seq (bb) != NULL)
1865     {
1866       /* Walk backwards so as to get a chance to substitute all
1867          released DEFs into debug stmts.  See
1868          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
1869          details.  */
1870       for (i = gsi_last_bb (bb); !gsi_end_p (i);)
1871         {
1872           gimple stmt = gsi_stmt (i);
1873           if (gimple_code (stmt) == GIMPLE_LABEL
1874               && (FORCED_LABEL (gimple_label_label (stmt))
1875                   || DECL_NONLOCAL (gimple_label_label (stmt))))
1876             {
1877               basic_block new_bb;
1878               gimple_stmt_iterator new_gsi;
1879
1880               /* A non-reachable non-local label may still be referenced.
1881                  But it no longer needs to carry the extra semantics of
1882                  non-locality.  */
1883               if (DECL_NONLOCAL (gimple_label_label (stmt)))
1884                 {
1885                   DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
1886                   FORCED_LABEL (gimple_label_label (stmt)) = 1;
1887                 }
1888
1889               new_bb = bb->prev_bb;
1890               new_gsi = gsi_start_bb (new_bb);
1891               gsi_remove (&i, false);
1892               gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
1893             }
1894           else
1895             {
1896               /* Release SSA definitions if we are in SSA.  Note that we
1897                  may be called when not in SSA.  For example,
1898                  final_cleanup calls this function via
1899                  cleanup_tree_cfg.  */
1900               if (gimple_in_ssa_p (cfun))
1901                 release_defs (stmt);
1902
1903               gsi_remove (&i, true);
1904             }
1905
1906           if (gsi_end_p (i))
1907             i = gsi_last_bb (bb);
1908           else
1909             gsi_prev (&i);
1910         }
1911     }
1912
1913   remove_phi_nodes_and_edges_for_unreachable_block (bb);
1914   bb->il.gimple.seq = NULL;
1915   bb->il.gimple.phi_nodes = NULL;
1916 }
1917
1918
1919 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
1920    predicate VAL, return the edge that will be taken out of the block.
1921    If VAL does not match a unique edge, NULL is returned.  */
1922
1923 edge
1924 find_taken_edge (basic_block bb, tree val)
1925 {
1926   gimple stmt;
1927
1928   stmt = last_stmt (bb);
1929
1930   gcc_assert (stmt);
1931   gcc_assert (is_ctrl_stmt (stmt));
1932
1933   if (val == NULL)
1934     return NULL;
1935
1936   if (!is_gimple_min_invariant (val))
1937     return NULL;
1938
1939   if (gimple_code (stmt) == GIMPLE_COND)
1940     return find_taken_edge_cond_expr (bb, val);
1941
1942   if (gimple_code (stmt) == GIMPLE_SWITCH)
1943     return find_taken_edge_switch_expr (bb, val);
1944
1945   if (computed_goto_p (stmt))
1946     {
1947       /* Only optimize if the argument is a label, if the argument is
1948          not a label then we can not construct a proper CFG.
1949
1950          It may be the case that we only need to allow the LABEL_REF to
1951          appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
1952          appear inside a LABEL_EXPR just to be safe.  */
1953       if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
1954           && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
1955         return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
1956       return NULL;
1957     }
1958
1959   gcc_unreachable ();
1960 }
1961
1962 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
1963    statement, determine which of the outgoing edges will be taken out of the
1964    block.  Return NULL if either edge may be taken.  */
1965
1966 static edge
1967 find_taken_edge_computed_goto (basic_block bb, tree val)
1968 {
1969   basic_block dest;
1970   edge e = NULL;
1971
1972   dest = label_to_block (val);
1973   if (dest)
1974     {
1975       e = find_edge (bb, dest);
1976       gcc_assert (e != NULL);
1977     }
1978
1979   return e;
1980 }
1981
1982 /* Given a constant value VAL and the entry block BB to a COND_EXPR
1983    statement, determine which of the two edges will be taken out of the
1984    block.  Return NULL if either edge may be taken.  */
1985
1986 static edge
1987 find_taken_edge_cond_expr (basic_block bb, tree val)
1988 {
1989   edge true_edge, false_edge;
1990
1991   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1992
1993   gcc_assert (TREE_CODE (val) == INTEGER_CST);
1994   return (integer_zerop (val) ? false_edge : true_edge);
1995 }
1996
1997 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
1998    statement, determine which edge will be taken out of the block.  Return
1999    NULL if any edge may be taken.  */
2000
2001 static edge
2002 find_taken_edge_switch_expr (basic_block bb, tree val)
2003 {
2004   basic_block dest_bb;
2005   edge e;
2006   gimple switch_stmt;
2007   tree taken_case;
2008
2009   switch_stmt = last_stmt (bb);
2010   taken_case = find_case_label_for_value (switch_stmt, val);
2011   dest_bb = label_to_block (CASE_LABEL (taken_case));
2012
2013   e = find_edge (bb, dest_bb);
2014   gcc_assert (e);
2015   return e;
2016 }
2017
2018
2019 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
2020    We can make optimal use here of the fact that the case labels are
2021    sorted: We can do a binary search for a case matching VAL.  */
2022
2023 static tree
2024 find_case_label_for_value (gimple switch_stmt, tree val)
2025 {
2026   size_t low, high, n = gimple_switch_num_labels (switch_stmt);
2027   tree default_case = gimple_switch_default_label (switch_stmt);
2028
2029   for (low = 0, high = n; high - low > 1; )
2030     {
2031       size_t i = (high + low) / 2;
2032       tree t = gimple_switch_label (switch_stmt, i);
2033       int cmp;
2034
2035       /* Cache the result of comparing CASE_LOW and val.  */
2036       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2037
2038       if (cmp > 0)
2039         high = i;
2040       else
2041         low = i;
2042
2043       if (CASE_HIGH (t) == NULL)
2044         {
2045           /* A singe-valued case label.  */
2046           if (cmp == 0)
2047             return t;
2048         }
2049       else
2050         {
2051           /* A case range.  We can only handle integer ranges.  */
2052           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2053             return t;
2054         }
2055     }
2056
2057   return default_case;
2058 }
2059
2060
2061 /* Dump a basic block on stderr.  */
2062
2063 void
2064 gimple_debug_bb (basic_block bb)
2065 {
2066   dump_bb (stderr, bb, 0, TDF_VOPS|TDF_MEMSYMS);
2067 }
2068
2069
2070 /* Dump basic block with index N on stderr.  */
2071
2072 basic_block
2073 gimple_debug_bb_n (int n)
2074 {
2075   gimple_debug_bb (BASIC_BLOCK (n));
2076   return BASIC_BLOCK (n);
2077 }
2078
2079
2080 /* Dump the CFG on stderr.
2081
2082    FLAGS are the same used by the tree dumping functions
2083    (see TDF_* in tree-pass.h).  */
2084
2085 void
2086 gimple_debug_cfg (int flags)
2087 {
2088   gimple_dump_cfg (stderr, flags);
2089 }
2090
2091
2092 /* Dump the program showing basic block boundaries on the given FILE.
2093
2094    FLAGS are the same used by the tree dumping functions (see TDF_* in
2095    tree.h).  */
2096
2097 void
2098 gimple_dump_cfg (FILE *file, int flags)
2099 {
2100   if (flags & TDF_DETAILS)
2101     {
2102       dump_function_header (file, current_function_decl, flags);
2103       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2104                n_basic_blocks, n_edges, last_basic_block);
2105
2106       brief_dump_cfg (file);
2107       fprintf (file, "\n");
2108     }
2109
2110   if (flags & TDF_STATS)
2111     dump_cfg_stats (file);
2112
2113   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2114 }
2115
2116
2117 /* Dump CFG statistics on FILE.  */
2118
2119 void
2120 dump_cfg_stats (FILE *file)
2121 {
2122   static long max_num_merged_labels = 0;
2123   unsigned long size, total = 0;
2124   long num_edges;
2125   basic_block bb;
2126   const char * const fmt_str   = "%-30s%-13s%12s\n";
2127   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2128   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2129   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2130   const char *funcname = current_function_name ();
2131
2132   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2133
2134   fprintf (file, "---------------------------------------------------------\n");
2135   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2136   fprintf (file, fmt_str, "", "  instances  ", "used ");
2137   fprintf (file, "---------------------------------------------------------\n");
2138
2139   size = n_basic_blocks * sizeof (struct basic_block_def);
2140   total += size;
2141   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2142            SCALE (size), LABEL (size));
2143
2144   num_edges = 0;
2145   FOR_EACH_BB (bb)
2146     num_edges += EDGE_COUNT (bb->succs);
2147   size = num_edges * sizeof (struct edge_def);
2148   total += size;
2149   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2150
2151   fprintf (file, "---------------------------------------------------------\n");
2152   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2153            LABEL (total));
2154   fprintf (file, "---------------------------------------------------------\n");
2155   fprintf (file, "\n");
2156
2157   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2158     max_num_merged_labels = cfg_stats.num_merged_labels;
2159
2160   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2161            cfg_stats.num_merged_labels, max_num_merged_labels);
2162
2163   fprintf (file, "\n");
2164 }
2165
2166
2167 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2168    linked in the final executable.  */
2169
2170 DEBUG_FUNCTION void
2171 debug_cfg_stats (void)
2172 {
2173   dump_cfg_stats (stderr);
2174 }
2175
2176
2177 /* Dump the flowgraph to a .vcg FILE.  */
2178
2179 static void
2180 gimple_cfg2vcg (FILE *file)
2181 {
2182   edge e;
2183   edge_iterator ei;
2184   basic_block bb;
2185   const char *funcname = current_function_name ();
2186
2187   /* Write the file header.  */
2188   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2189   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2190   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2191
2192   /* Write blocks and edges.  */
2193   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2194     {
2195       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2196                e->dest->index);
2197
2198       if (e->flags & EDGE_FAKE)
2199         fprintf (file, " linestyle: dotted priority: 10");
2200       else
2201         fprintf (file, " linestyle: solid priority: 100");
2202
2203       fprintf (file, " }\n");
2204     }
2205   fputc ('\n', file);
2206
2207   FOR_EACH_BB (bb)
2208     {
2209       enum gimple_code head_code, end_code;
2210       const char *head_name, *end_name;
2211       int head_line = 0;
2212       int end_line = 0;
2213       gimple first = first_stmt (bb);
2214       gimple last = last_stmt (bb);
2215
2216       if (first)
2217         {
2218           head_code = gimple_code (first);
2219           head_name = gimple_code_name[head_code];
2220           head_line = get_lineno (first);
2221         }
2222       else
2223         head_name = "no-statement";
2224
2225       if (last)
2226         {
2227           end_code = gimple_code (last);
2228           end_name = gimple_code_name[end_code];
2229           end_line = get_lineno (last);
2230         }
2231       else
2232         end_name = "no-statement";
2233
2234       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2235                bb->index, bb->index, head_name, head_line, end_name,
2236                end_line);
2237
2238       FOR_EACH_EDGE (e, ei, bb->succs)
2239         {
2240           if (e->dest == EXIT_BLOCK_PTR)
2241             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2242           else
2243             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2244
2245           if (e->flags & EDGE_FAKE)
2246             fprintf (file, " priority: 10 linestyle: dotted");
2247           else
2248             fprintf (file, " priority: 100 linestyle: solid");
2249
2250           fprintf (file, " }\n");
2251         }
2252
2253       if (bb->next_bb != EXIT_BLOCK_PTR)
2254         fputc ('\n', file);
2255     }
2256
2257   fputs ("}\n\n", file);
2258 }
2259
2260
2261
2262 /*---------------------------------------------------------------------------
2263                              Miscellaneous helpers
2264 ---------------------------------------------------------------------------*/
2265
2266 /* Return true if T, a GIMPLE_CALL, can make an abnormal transfer of control
2267    flow.  Transfers of control flow associated with EH are excluded.  */
2268
2269 static bool
2270 call_can_make_abnormal_goto (gimple t)
2271 {
2272   /* If the function has no non-local labels, then a call cannot make an
2273      abnormal transfer of control.  */
2274   if (!cfun->has_nonlocal_label)
2275    return false;
2276
2277   /* Likewise if the call has no side effects.  */
2278   if (!gimple_has_side_effects (t))
2279     return false;
2280
2281   /* Likewise if the called function is leaf.  */
2282   if (gimple_call_flags (t) & ECF_LEAF)
2283     return false;
2284
2285   return true;
2286 }
2287
2288
2289 /* Return true if T can make an abnormal transfer of control flow.
2290    Transfers of control flow associated with EH are excluded.  */
2291
2292 bool
2293 stmt_can_make_abnormal_goto (gimple t)
2294 {
2295   if (computed_goto_p (t))
2296     return true;
2297   if (is_gimple_call (t))
2298     return call_can_make_abnormal_goto (t);
2299   return false;
2300 }
2301
2302
2303 /* Return true if T represents a stmt that always transfers control.  */
2304
2305 bool
2306 is_ctrl_stmt (gimple t)
2307 {
2308   switch (gimple_code (t))
2309     {
2310     case GIMPLE_COND:
2311     case GIMPLE_SWITCH:
2312     case GIMPLE_GOTO:
2313     case GIMPLE_RETURN:
2314     case GIMPLE_RESX:
2315       return true;
2316     default:
2317       return false;
2318     }
2319 }
2320
2321
2322 /* Return true if T is a statement that may alter the flow of control
2323    (e.g., a call to a non-returning function).  */
2324
2325 bool
2326 is_ctrl_altering_stmt (gimple t)
2327 {
2328   gcc_assert (t);
2329
2330   switch (gimple_code (t))
2331     {
2332     case GIMPLE_CALL:
2333       {
2334         int flags = gimple_call_flags (t);
2335
2336         /* A call alters control flow if it can make an abnormal goto.  */
2337         if (call_can_make_abnormal_goto (t))
2338           return true;
2339
2340         /* A call also alters control flow if it does not return.  */
2341         if (flags & ECF_NORETURN)
2342           return true;
2343
2344         /* TM ending statements have backedges out of the transaction.
2345            Return true so we split the basic block containing them.
2346            Note that the TM_BUILTIN test is merely an optimization.  */
2347         if ((flags & ECF_TM_BUILTIN)
2348             && is_tm_ending_fndecl (gimple_call_fndecl (t)))
2349           return true;
2350
2351         /* BUILT_IN_RETURN call is same as return statement.  */
2352         if (gimple_call_builtin_p (t, BUILT_IN_RETURN))
2353           return true;
2354       }
2355       break;
2356
2357     case GIMPLE_EH_DISPATCH:
2358       /* EH_DISPATCH branches to the individual catch handlers at
2359          this level of a try or allowed-exceptions region.  It can
2360          fallthru to the next statement as well.  */
2361       return true;
2362
2363     case GIMPLE_ASM:
2364       if (gimple_asm_nlabels (t) > 0)
2365         return true;
2366       break;
2367
2368     CASE_GIMPLE_OMP:
2369       /* OpenMP directives alter control flow.  */
2370       return true;
2371
2372     case GIMPLE_TRANSACTION:
2373       /* A transaction start alters control flow.  */
2374       return true;
2375
2376     default:
2377       break;
2378     }
2379
2380   /* If a statement can throw, it alters control flow.  */
2381   return stmt_can_throw_internal (t);
2382 }
2383
2384
2385 /* Return true if T is a simple local goto.  */
2386
2387 bool
2388 simple_goto_p (gimple t)
2389 {
2390   return (gimple_code (t) == GIMPLE_GOTO
2391           && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2392 }
2393
2394
2395 /* Return true if STMT should start a new basic block.  PREV_STMT is
2396    the statement preceding STMT.  It is used when STMT is a label or a
2397    case label.  Labels should only start a new basic block if their
2398    previous statement wasn't a label.  Otherwise, sequence of labels
2399    would generate unnecessary basic blocks that only contain a single
2400    label.  */
2401
2402 static inline bool
2403 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2404 {
2405   if (stmt == NULL)
2406     return false;
2407
2408   /* Labels start a new basic block only if the preceding statement
2409      wasn't a label of the same type.  This prevents the creation of
2410      consecutive blocks that have nothing but a single label.  */
2411   if (gimple_code (stmt) == GIMPLE_LABEL)
2412     {
2413       /* Nonlocal and computed GOTO targets always start a new block.  */
2414       if (DECL_NONLOCAL (gimple_label_label (stmt))
2415           || FORCED_LABEL (gimple_label_label (stmt)))
2416         return true;
2417
2418       if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2419         {
2420           if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2421             return true;
2422
2423           cfg_stats.num_merged_labels++;
2424           return false;
2425         }
2426       else
2427         return true;
2428     }
2429
2430   return false;
2431 }
2432
2433
2434 /* Return true if T should end a basic block.  */
2435
2436 bool
2437 stmt_ends_bb_p (gimple t)
2438 {
2439   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2440 }
2441
2442 /* Remove block annotations and other data structures.  */
2443
2444 void
2445 delete_tree_cfg_annotations (void)
2446 {
2447   label_to_block_map = NULL;
2448 }
2449
2450
2451 /* Return the first statement in basic block BB.  */
2452
2453 gimple
2454 first_stmt (basic_block bb)
2455 {
2456   gimple_stmt_iterator i = gsi_start_bb (bb);
2457   gimple stmt = NULL;
2458
2459   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2460     {
2461       gsi_next (&i);
2462       stmt = NULL;
2463     }
2464   return stmt;
2465 }
2466
2467 /* Return the first non-label statement in basic block BB.  */
2468
2469 static gimple
2470 first_non_label_stmt (basic_block bb)
2471 {
2472   gimple_stmt_iterator i = gsi_start_bb (bb);
2473   while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2474     gsi_next (&i);
2475   return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2476 }
2477
2478 /* Return the last statement in basic block BB.  */
2479
2480 gimple
2481 last_stmt (basic_block bb)
2482 {
2483   gimple_stmt_iterator i = gsi_last_bb (bb);
2484   gimple stmt = NULL;
2485
2486   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2487     {
2488       gsi_prev (&i);
2489       stmt = NULL;
2490     }
2491   return stmt;
2492 }
2493
2494 /* Return the last statement of an otherwise empty block.  Return NULL
2495    if the block is totally empty, or if it contains more than one
2496    statement.  */
2497
2498 gimple
2499 last_and_only_stmt (basic_block bb)
2500 {
2501   gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
2502   gimple last, prev;
2503
2504   if (gsi_end_p (i))
2505     return NULL;
2506
2507   last = gsi_stmt (i);
2508   gsi_prev_nondebug (&i);
2509   if (gsi_end_p (i))
2510     return last;
2511
2512   /* Empty statements should no longer appear in the instruction stream.
2513      Everything that might have appeared before should be deleted by
2514      remove_useless_stmts, and the optimizers should just gsi_remove
2515      instead of smashing with build_empty_stmt.
2516
2517      Thus the only thing that should appear here in a block containing
2518      one executable statement is a label.  */
2519   prev = gsi_stmt (i);
2520   if (gimple_code (prev) == GIMPLE_LABEL)
2521     return last;
2522   else
2523     return NULL;
2524 }
2525
2526 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
2527
2528 static void
2529 reinstall_phi_args (edge new_edge, edge old_edge)
2530 {
2531   edge_var_map_vector v;
2532   edge_var_map *vm;
2533   int i;
2534   gimple_stmt_iterator phis;
2535
2536   v = redirect_edge_var_map_vector (old_edge);
2537   if (!v)
2538     return;
2539
2540   for (i = 0, phis = gsi_start_phis (new_edge->dest);
2541        VEC_iterate (edge_var_map, v, i, vm) && !gsi_end_p (phis);
2542        i++, gsi_next (&phis))
2543     {
2544       gimple phi = gsi_stmt (phis);
2545       tree result = redirect_edge_var_map_result (vm);
2546       tree arg = redirect_edge_var_map_def (vm);
2547
2548       gcc_assert (result == gimple_phi_result (phi));
2549
2550       add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
2551     }
2552
2553   redirect_edge_var_map_clear (old_edge);
2554 }
2555
2556 /* Returns the basic block after which the new basic block created
2557    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
2558    near its "logical" location.  This is of most help to humans looking
2559    at debugging dumps.  */
2560
2561 static basic_block
2562 split_edge_bb_loc (edge edge_in)
2563 {
2564   basic_block dest = edge_in->dest;
2565   basic_block dest_prev = dest->prev_bb;
2566
2567   if (dest_prev)
2568     {
2569       edge e = find_edge (dest_prev, dest);
2570       if (e && !(e->flags & EDGE_COMPLEX))
2571         return edge_in->src;
2572     }
2573   return dest_prev;
2574 }
2575
2576 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
2577    Abort on abnormal edges.  */
2578
2579 static basic_block
2580 gimple_split_edge (edge edge_in)
2581 {
2582   basic_block new_bb, after_bb, dest;
2583   edge new_edge, e;
2584
2585   /* Abnormal edges cannot be split.  */
2586   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2587
2588   dest = edge_in->dest;
2589
2590   after_bb = split_edge_bb_loc (edge_in);
2591
2592   new_bb = create_empty_bb (after_bb);
2593   new_bb->frequency = EDGE_FREQUENCY (edge_in);
2594   new_bb->count = edge_in->count;
2595   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2596   new_edge->probability = REG_BR_PROB_BASE;
2597   new_edge->count = edge_in->count;
2598
2599   e = redirect_edge_and_branch (edge_in, new_bb);
2600   gcc_assert (e == edge_in);
2601   reinstall_phi_args (new_edge, e);
2602
2603   return new_bb;
2604 }
2605
2606
2607 /* Verify properties of the address expression T with base object BASE.  */
2608
2609 static tree
2610 verify_address (tree t, tree base)
2611 {
2612   bool old_constant;
2613   bool old_side_effects;
2614   bool new_constant;
2615   bool new_side_effects;
2616
2617   old_constant = TREE_CONSTANT (t);
2618   old_side_effects = TREE_SIDE_EFFECTS (t);
2619
2620   recompute_tree_invariant_for_addr_expr (t);
2621   new_side_effects = TREE_SIDE_EFFECTS (t);
2622   new_constant = TREE_CONSTANT (t);
2623
2624   if (old_constant != new_constant)
2625     {
2626       error ("constant not recomputed when ADDR_EXPR changed");
2627       return t;
2628     }
2629   if (old_side_effects != new_side_effects)
2630     {
2631       error ("side effects not recomputed when ADDR_EXPR changed");
2632       return t;
2633     }
2634
2635   if (!(TREE_CODE (base) == VAR_DECL
2636         || TREE_CODE (base) == PARM_DECL
2637         || TREE_CODE (base) == RESULT_DECL))
2638     return NULL_TREE;
2639
2640   if (DECL_GIMPLE_REG_P (base))
2641     {
2642       error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2643       return base;
2644     }
2645
2646   return NULL_TREE;
2647 }
2648
2649 /* Callback for walk_tree, check that all elements with address taken are
2650    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
2651    inside a PHI node.  */
2652
2653 static tree
2654 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2655 {
2656   tree t = *tp, x;
2657
2658   if (TYPE_P (t))
2659     *walk_subtrees = 0;
2660
2661   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
2662 #define CHECK_OP(N, MSG) \
2663   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
2664        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2665
2666   switch (TREE_CODE (t))
2667     {
2668     case SSA_NAME:
2669       if (SSA_NAME_IN_FREE_LIST (t))
2670         {
2671           error ("SSA name in freelist but still referenced");
2672           return *tp;
2673         }
2674       break;
2675
2676     case INDIRECT_REF:
2677       error ("INDIRECT_REF in gimple IL");
2678       return t;
2679
2680     case MEM_REF:
2681       x = TREE_OPERAND (t, 0);
2682       if (!POINTER_TYPE_P (TREE_TYPE (x))
2683           || !is_gimple_mem_ref_addr (x))
2684         {
2685           error ("invalid first operand of MEM_REF");
2686           return x;
2687         }
2688       if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST
2689           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1))))
2690         {
2691           error ("invalid offset operand of MEM_REF");
2692           return TREE_OPERAND (t, 1);
2693         }
2694       if (TREE_CODE (x) == ADDR_EXPR
2695           && (x = verify_address (x, TREE_OPERAND (x, 0))))
2696         return x;
2697       *walk_subtrees = 0;
2698       break;
2699
2700     case ASSERT_EXPR:
2701       x = fold (ASSERT_EXPR_COND (t));
2702       if (x == boolean_false_node)
2703         {
2704           error ("ASSERT_EXPR with an always-false condition");
2705           return *tp;
2706         }
2707       break;
2708
2709     case MODIFY_EXPR:
2710       error ("MODIFY_EXPR not expected while having tuples");
2711       return *tp;
2712
2713     case ADDR_EXPR:
2714       {
2715         tree tem;
2716
2717         gcc_assert (is_gimple_address (t));
2718
2719         /* Skip any references (they will be checked when we recurse down the
2720            tree) and ensure that any variable used as a prefix is marked
2721            addressable.  */
2722         for (x = TREE_OPERAND (t, 0);
2723              handled_component_p (x);
2724              x = TREE_OPERAND (x, 0))
2725           ;
2726
2727         if ((tem = verify_address (t, x)))
2728           return tem;
2729
2730         if (!(TREE_CODE (x) == VAR_DECL
2731               || TREE_CODE (x) == PARM_DECL
2732               || TREE_CODE (x) == RESULT_DECL))
2733           return NULL;
2734
2735         if (!TREE_ADDRESSABLE (x))
2736           {
2737             error ("address taken, but ADDRESSABLE bit not set");
2738             return x;
2739           }
2740
2741         break;
2742       }
2743
2744     case COND_EXPR:
2745       x = COND_EXPR_COND (t);
2746       if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2747         {
2748           error ("non-integral used in condition");
2749           return x;
2750         }
2751       if (!is_gimple_condexpr (x))
2752         {
2753           error ("invalid conditional operand");
2754           return x;
2755         }
2756       break;
2757
2758     case NON_LVALUE_EXPR:
2759     case TRUTH_NOT_EXPR:
2760       gcc_unreachable ();
2761
2762     CASE_CONVERT:
2763     case FIX_TRUNC_EXPR:
2764     case FLOAT_EXPR:
2765     case NEGATE_EXPR:
2766     case ABS_EXPR:
2767     case BIT_NOT_EXPR:
2768       CHECK_OP (0, "invalid operand to unary operator");
2769       break;
2770
2771     case REALPART_EXPR:
2772     case IMAGPART_EXPR:
2773     case COMPONENT_REF:
2774     case ARRAY_REF:
2775     case ARRAY_RANGE_REF:
2776     case BIT_FIELD_REF:
2777     case VIEW_CONVERT_EXPR:
2778       /* We have a nest of references.  Verify that each of the operands
2779          that determine where to reference is either a constant or a variable,
2780          verify that the base is valid, and then show we've already checked
2781          the subtrees.  */
2782       while (handled_component_p (t))
2783         {
2784           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2785             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2786           else if (TREE_CODE (t) == ARRAY_REF
2787                    || TREE_CODE (t) == ARRAY_RANGE_REF)
2788             {
2789               CHECK_OP (1, "invalid array index");
2790               if (TREE_OPERAND (t, 2))
2791                 CHECK_OP (2, "invalid array lower bound");
2792               if (TREE_OPERAND (t, 3))
2793                 CHECK_OP (3, "invalid array stride");
2794             }
2795           else if (TREE_CODE (t) == BIT_FIELD_REF)
2796             {
2797               if (!host_integerp (TREE_OPERAND (t, 1), 1)
2798                   || !host_integerp (TREE_OPERAND (t, 2), 1))
2799                 {
2800                   error ("invalid position or size operand to BIT_FIELD_REF");
2801                   return t;
2802                 }
2803               if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2804                   && (TYPE_PRECISION (TREE_TYPE (t))
2805                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2806                 {
2807                   error ("integral result type precision does not match "
2808                          "field size of BIT_FIELD_REF");
2809                   return t;
2810                 }
2811               else if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2812                        && !AGGREGATE_TYPE_P (TREE_TYPE (t))
2813                        && TYPE_MODE (TREE_TYPE (t)) != BLKmode
2814                        && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2815                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2816                 {
2817                   error ("mode precision of non-integral result does not "
2818                          "match field size of BIT_FIELD_REF");
2819                   return t;
2820                 }
2821             }
2822
2823           t = TREE_OPERAND (t, 0);
2824         }
2825
2826       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2827         {
2828           error ("invalid reference prefix");
2829           return t;
2830         }
2831       *walk_subtrees = 0;
2832       break;
2833     case PLUS_EXPR:
2834     case MINUS_EXPR:
2835       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2836          POINTER_PLUS_EXPR. */
2837       if (POINTER_TYPE_P (TREE_TYPE (t)))
2838         {
2839           error ("invalid operand to plus/minus, type is a pointer");
2840           return t;
2841         }
2842       CHECK_OP (0, "invalid operand to binary operator");
2843       CHECK_OP (1, "invalid operand to binary operator");
2844       break;
2845
2846     case POINTER_PLUS_EXPR:
2847       /* Check to make sure the first operand is a pointer or reference type. */
2848       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
2849         {
2850           error ("invalid operand to pointer plus, first operand is not a pointer");
2851           return t;
2852         }
2853       /* Check to make sure the second operand is a ptrofftype.  */
2854       if (!ptrofftype_p (TREE_TYPE (TREE_OPERAND (t, 1))))
2855         {
2856           error ("invalid operand to pointer plus, second operand is not an "
2857                  "integer type of appropriate width");
2858           return t;
2859         }
2860       /* FALLTHROUGH */
2861     case LT_EXPR:
2862     case LE_EXPR:
2863     case GT_EXPR:
2864     case GE_EXPR:
2865     case EQ_EXPR:
2866     case NE_EXPR:
2867     case UNORDERED_EXPR:
2868     case ORDERED_EXPR:
2869     case UNLT_EXPR:
2870     case UNLE_EXPR:
2871     case UNGT_EXPR:
2872     case UNGE_EXPR:
2873     case UNEQ_EXPR:
2874     case LTGT_EXPR:
2875     case MULT_EXPR:
2876     case TRUNC_DIV_EXPR:
2877     case CEIL_DIV_EXPR:
2878     case FLOOR_DIV_EXPR:
2879     case ROUND_DIV_EXPR:
2880     case TRUNC_MOD_EXPR:
2881     case CEIL_MOD_EXPR:
2882     case FLOOR_MOD_EXPR:
2883     case ROUND_MOD_EXPR:
2884     case RDIV_EXPR:
2885     case EXACT_DIV_EXPR:
2886     case MIN_EXPR:
2887     case MAX_EXPR:
2888     case LSHIFT_EXPR:
2889     case RSHIFT_EXPR:
2890     case LROTATE_EXPR:
2891     case RROTATE_EXPR:
2892     case BIT_IOR_EXPR:
2893     case BIT_XOR_EXPR:
2894     case BIT_AND_EXPR:
2895       CHECK_OP (0, "invalid operand to binary operator");
2896       CHECK_OP (1, "invalid operand to binary operator");
2897       break;
2898
2899     case CONSTRUCTOR:
2900       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2901         *walk_subtrees = 0;
2902       break;
2903
2904     case CASE_LABEL_EXPR:
2905       if (CASE_CHAIN (t))
2906         {
2907           error ("invalid CASE_CHAIN");
2908           return t;
2909         }
2910       break;
2911
2912     default:
2913       break;
2914     }
2915   return NULL;
2916
2917 #undef CHECK_OP
2918 }
2919
2920
2921 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
2922    Returns true if there is an error, otherwise false.  */
2923
2924 static bool
2925 verify_types_in_gimple_min_lval (tree expr)
2926 {
2927   tree op;
2928
2929   if (is_gimple_id (expr))
2930     return false;
2931
2932   if (TREE_CODE (expr) != TARGET_MEM_REF
2933       && TREE_CODE (expr) != MEM_REF)
2934     {
2935       error ("invalid expression for min lvalue");
2936       return true;
2937     }
2938
2939   /* TARGET_MEM_REFs are strange beasts.  */
2940   if (TREE_CODE (expr) == TARGET_MEM_REF)
2941     return false;
2942
2943   op = TREE_OPERAND (expr, 0);
2944   if (!is_gimple_val (op))
2945     {
2946       error ("invalid operand in indirect reference");
2947       debug_generic_stmt (op);
2948       return true;
2949     }
2950   /* Memory references now generally can involve a value conversion.  */
2951
2952   return false;
2953 }
2954
2955 /* Verify if EXPR is a valid GIMPLE reference expression.  If
2956    REQUIRE_LVALUE is true verifies it is an lvalue.  Returns true
2957    if there is an error, otherwise false.  */
2958
2959 static bool
2960 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
2961 {
2962   while (handled_component_p (expr))
2963     {
2964       tree op = TREE_OPERAND (expr, 0);
2965
2966       if (TREE_CODE (expr) == ARRAY_REF
2967           || TREE_CODE (expr) == ARRAY_RANGE_REF)
2968         {
2969           if (!is_gimple_val (TREE_OPERAND (expr, 1))
2970               || (TREE_OPERAND (expr, 2)
2971                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
2972               || (TREE_OPERAND (expr, 3)
2973                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
2974             {
2975               error ("invalid operands to array reference");
2976               debug_generic_stmt (expr);
2977               return true;
2978             }
2979         }
2980
2981       /* Verify if the reference array element types are compatible.  */
2982       if (TREE_CODE (expr) == ARRAY_REF
2983           && !useless_type_conversion_p (TREE_TYPE (expr),
2984                                          TREE_TYPE (TREE_TYPE (op))))
2985         {
2986           error ("type mismatch in array reference");
2987           debug_generic_stmt (TREE_TYPE (expr));
2988           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2989           return true;
2990         }
2991       if (TREE_CODE (expr) == ARRAY_RANGE_REF
2992           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
2993                                          TREE_TYPE (TREE_TYPE (op))))
2994         {
2995           error ("type mismatch in array range reference");
2996           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
2997           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2998           return true;
2999         }
3000
3001       if ((TREE_CODE (expr) == REALPART_EXPR
3002            || TREE_CODE (expr) == IMAGPART_EXPR)
3003           && !useless_type_conversion_p (TREE_TYPE (expr),
3004                                          TREE_TYPE (TREE_TYPE (op))))
3005         {
3006           error ("type mismatch in real/imagpart reference");
3007           debug_generic_stmt (TREE_TYPE (expr));
3008           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3009           return true;
3010         }
3011
3012       if (TREE_CODE (expr) == COMPONENT_REF
3013           && !useless_type_conversion_p (TREE_TYPE (expr),
3014                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
3015         {
3016           error ("type mismatch in component reference");
3017           debug_generic_stmt (TREE_TYPE (expr));
3018           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3019           return true;
3020         }
3021
3022       if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
3023         {
3024           /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check
3025              that their operand is not an SSA name or an invariant when
3026              requiring an lvalue (this usually means there is a SRA or IPA-SRA
3027              bug).  Otherwise there is nothing to verify, gross mismatches at
3028              most invoke undefined behavior.  */
3029           if (require_lvalue
3030               && (TREE_CODE (op) == SSA_NAME
3031                   || is_gimple_min_invariant (op)))
3032             {
3033               error ("conversion of an SSA_NAME on the left hand side");
3034               debug_generic_stmt (expr);
3035               return true;
3036             }
3037           else if (TREE_CODE (op) == SSA_NAME
3038                    && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op)))
3039             {
3040               error ("conversion of register to a different size");
3041               debug_generic_stmt (expr);
3042               return true;
3043             }
3044           else if (!handled_component_p (op))
3045             return false;
3046         }
3047
3048       expr = op;
3049     }
3050
3051   if (TREE_CODE (expr) == MEM_REF)
3052     {
3053       if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0)))
3054         {
3055           error ("invalid address operand in MEM_REF");
3056           debug_generic_stmt (expr);
3057           return true;
3058         }
3059       if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST
3060           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
3061         {
3062           error ("invalid offset operand in MEM_REF");
3063           debug_generic_stmt (expr);
3064           return true;
3065         }
3066     }
3067   else if (TREE_CODE (expr) == TARGET_MEM_REF)
3068     {
3069       if (!TMR_BASE (expr)
3070           || !is_gimple_mem_ref_addr (TMR_BASE (expr)))
3071         {
3072           error ("invalid address operand in TARGET_MEM_REF");
3073           return true;
3074         }
3075       if (!TMR_OFFSET (expr)
3076           || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST
3077           || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr))))
3078         {
3079           error ("invalid offset operand in TARGET_MEM_REF");
3080           debug_generic_stmt (expr);
3081           return true;
3082         }
3083     }
3084
3085   return ((require_lvalue || !is_gimple_min_invariant (expr))
3086           && verify_types_in_gimple_min_lval (expr));
3087 }
3088
3089 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3090    list of pointer-to types that is trivially convertible to DEST.  */
3091
3092 static bool
3093 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3094 {
3095   tree src;
3096
3097   if (!TYPE_POINTER_TO (src_obj))
3098     return true;
3099
3100   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3101     if (useless_type_conversion_p (dest, src))
3102       return true;
3103
3104   return false;
3105 }
3106
3107 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3108    from TYPE2 can be handled by FIXED_CONVERT_EXPR.  */
3109
3110 static bool
3111 valid_fixed_convert_types_p (tree type1, tree type2)
3112 {
3113   return (FIXED_POINT_TYPE_P (type1)
3114           && (INTEGRAL_TYPE_P (type2)
3115               || SCALAR_FLOAT_TYPE_P (type2)
3116               || FIXED_POINT_TYPE_P (type2)));
3117 }
3118
3119 /* Verify the contents of a GIMPLE_CALL STMT.  Returns true when there
3120    is a problem, otherwise false.  */
3121
3122 static bool
3123 verify_gimple_call (gimple stmt)
3124 {
3125   tree fn = gimple_call_fn (stmt);
3126   tree fntype, fndecl;
3127   unsigned i;
3128
3129   if (gimple_call_internal_p (stmt))
3130     {
3131       if (fn)
3132         {
3133           error ("gimple call has two targets");
3134           debug_generic_stmt (fn);
3135           return true;
3136         }
3137     }
3138   else
3139     {
3140       if (!fn)
3141         {
3142           error ("gimple call has no target");
3143           return true;
3144         }
3145     }
3146
3147   if (fn && !is_gimple_call_addr (fn))
3148     {
3149       error ("invalid function in gimple call");
3150       debug_generic_stmt (fn);
3151       return true;
3152     }
3153
3154   if (fn
3155       && (!POINTER_TYPE_P (TREE_TYPE (fn))
3156           || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3157               && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE)))
3158     {
3159       error ("non-function in gimple call");
3160       return true;
3161     }
3162
3163    fndecl = gimple_call_fndecl (stmt);
3164    if (fndecl
3165        && TREE_CODE (fndecl) == FUNCTION_DECL
3166        && DECL_LOOPING_CONST_OR_PURE_P (fndecl)
3167        && !DECL_PURE_P (fndecl)
3168        && !TREE_READONLY (fndecl))
3169      {
3170        error ("invalid pure const state for function");
3171        return true;
3172      }
3173
3174   if (gimple_call_lhs (stmt)
3175       && (!is_gimple_lvalue (gimple_call_lhs (stmt))
3176           || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true)))
3177     {
3178       error ("invalid LHS in gimple call");
3179       return true;
3180     }
3181
3182   if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt))
3183     {
3184       error ("LHS in noreturn call");
3185       return true;
3186     }
3187
3188   fntype = gimple_call_fntype (stmt);
3189   if (fntype
3190       && gimple_call_lhs (stmt)
3191       && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3192                                      TREE_TYPE (fntype))
3193       /* ???  At least C++ misses conversions at assignments from
3194          void * call results.
3195          ???  Java is completely off.  Especially with functions
3196          returning java.lang.Object.
3197          For now simply allow arbitrary pointer type conversions.  */
3198       && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3199            && POINTER_TYPE_P (TREE_TYPE (fntype))))
3200     {
3201       error ("invalid conversion in gimple call");
3202       debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3203       debug_generic_stmt (TREE_TYPE (fntype));
3204       return true;
3205     }
3206
3207   if (gimple_call_chain (stmt)
3208       && !is_gimple_val (gimple_call_chain (stmt)))
3209     {
3210       error ("invalid static chain in gimple call");
3211       debug_generic_stmt (gimple_call_chain (stmt));
3212       return true;
3213     }
3214
3215   /* If there is a static chain argument, this should not be an indirect
3216      call, and the decl should have DECL_STATIC_CHAIN set.  */
3217   if (gimple_call_chain (stmt))
3218     {
3219       if (!gimple_call_fndecl (stmt))
3220         {
3221           error ("static chain in indirect gimple call");
3222           return true;
3223         }
3224       fn = TREE_OPERAND (fn, 0);
3225
3226       if (!DECL_STATIC_CHAIN (fn))
3227         {
3228           error ("static chain with function that doesn%'t use one");
3229           return true;
3230         }
3231     }
3232
3233   /* ???  The C frontend passes unpromoted arguments in case it
3234      didn't see a function declaration before the call.  So for now
3235      leave the call arguments mostly unverified.  Once we gimplify
3236      unit-at-a-time we have a chance to fix this.  */
3237
3238   for (i = 0; i < gimple_call_num_args (stmt); ++i)
3239     {
3240       tree arg = gimple_call_arg (stmt, i);
3241       if ((is_gimple_reg_type (TREE_TYPE (arg))
3242            && !is_gimple_val (arg))
3243           || (!is_gimple_reg_type (TREE_TYPE (arg))
3244               && !is_gimple_lvalue (arg)))
3245         {
3246           error ("invalid argument to gimple call");
3247           debug_generic_expr (arg);
3248           return true;
3249         }
3250     }
3251
3252   return false;
3253 }
3254
3255 /* Verifies the gimple comparison with the result type TYPE and
3256    the operands OP0 and OP1.  */
3257
3258 static bool
3259 verify_gimple_comparison (tree type, tree op0, tree op1)
3260 {
3261   tree op0_type = TREE_TYPE (op0);
3262   tree op1_type = TREE_TYPE (op1);
3263
3264   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3265     {
3266       error ("invalid operands in gimple comparison");
3267       return true;
3268     }
3269
3270   /* For comparisons we do not have the operations type as the
3271      effective type the comparison is carried out in.  Instead
3272      we require that either the first operand is trivially
3273      convertible into the second, or the other way around.
3274      Because we special-case pointers to void we allow
3275      comparisons of pointers with the same mode as well.  */
3276   if (!useless_type_conversion_p (op0_type, op1_type)
3277       && !useless_type_conversion_p (op1_type, op0_type)
3278       && (!POINTER_TYPE_P (op0_type)
3279           || !POINTER_TYPE_P (op1_type)
3280           || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3281     {
3282       error ("mismatching comparison operand types");
3283       debug_generic_expr (op0_type);
3284       debug_generic_expr (op1_type);
3285       return true;
3286     }
3287
3288   /* The resulting type of a comparison may be an effective boolean type.  */
3289   if (INTEGRAL_TYPE_P (type)
3290       && (TREE_CODE (type) == BOOLEAN_TYPE
3291           || TYPE_PRECISION (type) == 1))
3292     ;
3293   /* Or an integer vector type with the same size and element count
3294      as the comparison operand types.  */
3295   else if (TREE_CODE (type) == VECTOR_TYPE
3296            && TREE_CODE (TREE_TYPE (type)) == INTEGER_TYPE)
3297     {
3298       if (TREE_CODE (op0_type) != VECTOR_TYPE
3299           || TREE_CODE (op1_type) != VECTOR_TYPE)
3300         {
3301           error ("non-vector operands in vector comparison");
3302           debug_generic_expr (op0_type);
3303           debug_generic_expr (op1_type);
3304           return true;
3305         }
3306
3307       if (TYPE_VECTOR_SUBPARTS (type) != TYPE_VECTOR_SUBPARTS (op0_type)
3308           || (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (type)))
3309               != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0_type)))))
3310         {
3311           error ("invalid vector comparison resulting type");
3312           debug_generic_expr (type);
3313           return true;
3314         }
3315     }
3316   else
3317     {
3318       error ("bogus comparison result type");
3319       debug_generic_expr (type);
3320       return true;
3321     }
3322
3323   return false;
3324 }
3325
3326 /* Verify a gimple assignment statement STMT with an unary rhs.
3327    Returns true if anything is wrong.  */
3328
3329 static bool
3330 verify_gimple_assign_unary (gimple stmt)
3331 {
3332   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3333   tree lhs = gimple_assign_lhs (stmt);
3334   tree lhs_type = TREE_TYPE (lhs);
3335   tree rhs1 = gimple_assign_rhs1 (stmt);
3336   tree rhs1_type = TREE_TYPE (rhs1);
3337
3338   if (!is_gimple_reg (lhs))
3339     {
3340       error ("non-register as LHS of unary operation");
3341       return true;
3342     }
3343
3344   if (!is_gimple_val (rhs1))
3345     {
3346       error ("invalid operand in unary operation");
3347       return true;
3348     }
3349
3350   /* First handle conversions.  */
3351   switch (rhs_code)
3352     {
3353     CASE_CONVERT:
3354       {
3355         /* Allow conversions from pointer type to integral type only if
3356            there is no sign or zero extension involved.
3357            For targets were the precision of ptrofftype doesn't match that
3358            of pointers we need to allow arbitrary conversions to ptrofftype.  */
3359         if ((POINTER_TYPE_P (lhs_type)
3360              && INTEGRAL_TYPE_P (rhs1_type))
3361             || (POINTER_TYPE_P (rhs1_type)
3362                 && INTEGRAL_TYPE_P (lhs_type)
3363                 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3364                     || ptrofftype_p (sizetype))))
3365           return false;
3366
3367         /* Allow conversion from integral to offset type and vice versa.  */
3368         if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3369              && INTEGRAL_TYPE_P (rhs1_type))
3370             || (INTEGRAL_TYPE_P (lhs_type)
3371                 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3372           return false;
3373
3374         /* Otherwise assert we are converting between types of the
3375            same kind.  */
3376         if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3377           {
3378             error ("invalid types in nop conversion");
3379             debug_generic_expr (lhs_type);
3380             debug_generic_expr (rhs1_type);
3381             return true;
3382           }
3383
3384         return false;
3385       }
3386
3387     case ADDR_SPACE_CONVERT_EXPR:
3388       {
3389         if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3390             || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3391                 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3392           {
3393             error ("invalid types in address space conversion");
3394             debug_generic_expr (lhs_type);
3395             debug_generic_expr (rhs1_type);
3396             return true;
3397           }
3398
3399         return false;
3400       }
3401
3402     case FIXED_CONVERT_EXPR:
3403       {
3404         if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3405             && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3406           {
3407             error ("invalid types in fixed-point conversion");
3408             debug_generic_expr (lhs_type);
3409             debug_generic_expr (rhs1_type);
3410             return true;
3411           }
3412
3413         return false;
3414       }
3415
3416     case FLOAT_EXPR:
3417       {
3418         if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3419             && (!VECTOR_INTEGER_TYPE_P (rhs1_type)
3420                 || !VECTOR_FLOAT_TYPE_P(lhs_type)))
3421           {
3422             error ("invalid types in conversion to floating point");
3423             debug_generic_expr (lhs_type);
3424             debug_generic_expr (rhs1_type);
3425             return true;
3426           }
3427
3428         return false;
3429       }
3430
3431     case FIX_TRUNC_EXPR:
3432       {
3433         if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3434             && (!VECTOR_INTEGER_TYPE_P (lhs_type)
3435                 || !VECTOR_FLOAT_TYPE_P(rhs1_type)))
3436           {
3437             error ("invalid types in conversion to integer");
3438             debug_generic_expr (lhs_type);
3439             debug_generic_expr (rhs1_type);
3440             return true;
3441           }
3442
3443         return false;
3444       }
3445
3446     case VEC_UNPACK_HI_EXPR:
3447     case VEC_UNPACK_LO_EXPR:
3448     case REDUC_MAX_EXPR:
3449     case REDUC_MIN_EXPR:
3450     case REDUC_PLUS_EXPR:
3451     case VEC_UNPACK_FLOAT_HI_EXPR:
3452     case VEC_UNPACK_FLOAT_LO_EXPR:
3453       /* FIXME.  */
3454       return false;
3455
3456     case NEGATE_EXPR:
3457     case ABS_EXPR:
3458     case BIT_NOT_EXPR:
3459     case PAREN_EXPR:
3460     case NON_LVALUE_EXPR:
3461     case CONJ_EXPR:
3462       break;
3463
3464     default:
3465       gcc_unreachable ();
3466     }
3467
3468   /* For the remaining codes assert there is no conversion involved.  */
3469   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3470     {
3471       error ("non-trivial conversion in unary operation");
3472       debug_generic_expr (lhs_type);
3473       debug_generic_expr (rhs1_type);
3474       return true;
3475     }
3476
3477   return false;
3478 }
3479
3480 /* Verify a gimple assignment statement STMT with a binary rhs.
3481    Returns true if anything is wrong.  */
3482
3483 static bool
3484 verify_gimple_assign_binary (gimple stmt)
3485 {
3486   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3487   tree lhs = gimple_assign_lhs (stmt);
3488   tree lhs_type = TREE_TYPE (lhs);
3489   tree rhs1 = gimple_assign_rhs1 (stmt);
3490   tree rhs1_type = TREE_TYPE (rhs1);
3491   tree rhs2 = gimple_assign_rhs2 (stmt);
3492   tree rhs2_type = TREE_TYPE (rhs2);
3493
3494   if (!is_gimple_reg (lhs))
3495     {
3496       error ("non-register as LHS of binary operation");
3497       return true;
3498     }
3499
3500   if (!is_gimple_val (rhs1)
3501       || !is_gimple_val (rhs2))
3502     {
3503       error ("invalid operands in binary operation");
3504       return true;
3505     }
3506
3507   /* First handle operations that involve different types.  */
3508   switch (rhs_code)
3509     {
3510     case COMPLEX_EXPR:
3511       {
3512         if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3513             || !(INTEGRAL_TYPE_P (rhs1_type)
3514                  || SCALAR_FLOAT_TYPE_P (rhs1_type))
3515             || !(INTEGRAL_TYPE_P (rhs2_type)
3516                  || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3517           {
3518             error ("type mismatch in complex expression");
3519             debug_generic_expr (lhs_type);
3520             debug_generic_expr (rhs1_type);
3521             debug_generic_expr (rhs2_type);
3522             return true;
3523           }
3524
3525         return false;
3526       }
3527
3528     case LSHIFT_EXPR:
3529     case RSHIFT_EXPR:
3530     case LROTATE_EXPR:
3531     case RROTATE_EXPR:
3532       {
3533         /* Shifts and rotates are ok on integral types, fixed point
3534            types and integer vector types.  */
3535         if ((!INTEGRAL_TYPE_P (rhs1_type)
3536              && !FIXED_POINT_TYPE_P (rhs1_type)
3537              && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3538                   && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3539             || (!INTEGRAL_TYPE_P (rhs2_type)
3540                 /* Vector shifts of vectors are also ok.  */
3541                 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3542                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3543                      && TREE_CODE (rhs2_type) == VECTOR_TYPE
3544                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3545             || !useless_type_conversion_p (lhs_type, rhs1_type))
3546           {
3547             error ("type mismatch in shift expression");
3548             debug_generic_expr (lhs_type);
3549             debug_generic_expr (rhs1_type);
3550             debug_generic_expr (rhs2_type);
3551             return true;
3552           }
3553
3554         return false;
3555       }
3556
3557     case VEC_LSHIFT_EXPR:
3558     case VEC_RSHIFT_EXPR:
3559       {
3560         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3561             || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3562                  || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3563                  || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3564                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3565             || (!INTEGRAL_TYPE_P (rhs2_type)
3566                 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3567                     || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3568             || !useless_type_conversion_p (lhs_type, rhs1_type))
3569           {
3570             error ("type mismatch in vector shift expression");
3571             debug_generic_expr (lhs_type);
3572             debug_generic_expr (rhs1_type);
3573             debug_generic_expr (rhs2_type);
3574             return true;
3575           }
3576         /* For shifting a vector of non-integral components we
3577            only allow shifting by a constant multiple of the element size.  */
3578         if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3579             && (TREE_CODE (rhs2) != INTEGER_CST
3580                 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3581                                            TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3582           {
3583             error ("non-element sized vector shift of floating point vector");
3584             return true;
3585           }
3586
3587         return false;
3588       }
3589
3590     case WIDEN_LSHIFT_EXPR:
3591       {
3592         if (!INTEGRAL_TYPE_P (lhs_type)
3593             || !INTEGRAL_TYPE_P (rhs1_type)
3594             || TREE_CODE (rhs2) != INTEGER_CST
3595             || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)))
3596           {
3597             error ("type mismatch in widening vector shift expression");
3598             debug_generic_expr (lhs_type);
3599             debug_generic_expr (rhs1_type);
3600             debug_generic_expr (rhs2_type);
3601             return true;
3602           }
3603
3604         return false;
3605       }
3606
3607     case VEC_WIDEN_LSHIFT_HI_EXPR:
3608     case VEC_WIDEN_LSHIFT_LO_EXPR:
3609       {
3610         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3611             || TREE_CODE (lhs_type) != VECTOR_TYPE
3612             || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3613             || !INTEGRAL_TYPE_P (TREE_TYPE (lhs_type))
3614             || TREE_CODE (rhs2) != INTEGER_CST
3615             || (2 * TYPE_PRECISION (TREE_TYPE (rhs1_type))
3616                 > TYPE_PRECISION (TREE_TYPE (lhs_type))))
3617           {
3618             error ("type mismatch in widening vector shift expression");
3619             debug_generic_expr (lhs_type);
3620             debug_generic_expr (rhs1_type);
3621             debug_generic_expr (rhs2_type);
3622             return true;
3623           }
3624
3625         return false;
3626       }
3627
3628     case PLUS_EXPR:
3629     case MINUS_EXPR:
3630       {
3631         /* We use regular PLUS_EXPR and MINUS_EXPR for vectors.
3632            ???  This just makes the checker happy and may not be what is
3633            intended.  */
3634         if (TREE_CODE (lhs_type) == VECTOR_TYPE
3635             && POINTER_TYPE_P (TREE_TYPE (lhs_type)))
3636           {
3637             if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3638                 || TREE_CODE (rhs2_type) != VECTOR_TYPE)
3639               {
3640                 error ("invalid non-vector operands to vector valued plus");
3641                 return true;
3642               }
3643             lhs_type = TREE_TYPE (lhs_type);
3644             rhs1_type = TREE_TYPE (rhs1_type);
3645             rhs2_type = TREE_TYPE (rhs2_type);
3646             /* PLUS_EXPR is commutative, so we might end up canonicalizing
3647                the pointer to 2nd place.  */
3648             if (POINTER_TYPE_P (rhs2_type))
3649               {
3650                 tree tem = rhs1_type;
3651                 rhs1_type = rhs2_type;
3652                 rhs2_type = tem;
3653               }
3654             goto do_pointer_plus_expr_check;
3655           }
3656         if (POINTER_TYPE_P (lhs_type)
3657             || POINTER_TYPE_P (rhs1_type)
3658             || POINTER_TYPE_P (rhs2_type))
3659           {
3660             error ("invalid (pointer) operands to plus/minus");
3661             return true;
3662           }
3663
3664         /* Continue with generic binary expression handling.  */
3665         break;
3666       }
3667
3668     case POINTER_PLUS_EXPR:
3669       {
3670 do_pointer_plus_expr_check:
3671         if (!POINTER_TYPE_P (rhs1_type)
3672             || !useless_type_conversion_p (lhs_type, rhs1_type)
3673             || !ptrofftype_p (rhs2_type))
3674           {
3675             error ("type mismatch in pointer plus expression");
3676             debug_generic_stmt (lhs_type);
3677             debug_generic_stmt (rhs1_type);
3678             debug_generic_stmt (rhs2_type);
3679             return true;
3680           }
3681
3682         return false;
3683       }
3684
3685     case TRUTH_ANDIF_EXPR:
3686     case TRUTH_ORIF_EXPR:
3687     case TRUTH_AND_EXPR:
3688     case TRUTH_OR_EXPR:
3689     case TRUTH_XOR_EXPR:
3690
3691       gcc_unreachable ();
3692
3693     case LT_EXPR:
3694     case LE_EXPR:
3695     case GT_EXPR:
3696     case GE_EXPR:
3697     case EQ_EXPR:
3698     case NE_EXPR:
3699     case UNORDERED_EXPR:
3700     case ORDERED_EXPR:
3701     case UNLT_EXPR:
3702     case UNLE_EXPR:
3703     case UNGT_EXPR:
3704     case UNGE_EXPR:
3705     case UNEQ_EXPR:
3706     case LTGT_EXPR:
3707       /* Comparisons are also binary, but the result type is not
3708          connected to the operand types.  */
3709       return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3710
3711     case WIDEN_MULT_EXPR:
3712       if (TREE_CODE (lhs_type) != INTEGER_TYPE)
3713         return true;
3714       return ((2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type))
3715               || (TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type)));
3716
3717     case WIDEN_SUM_EXPR:
3718     case VEC_WIDEN_MULT_HI_EXPR:
3719     case VEC_WIDEN_MULT_LO_EXPR:
3720     case VEC_WIDEN_MULT_EVEN_EXPR:
3721     case VEC_WIDEN_MULT_ODD_EXPR:
3722     case VEC_PACK_TRUNC_EXPR:
3723     case VEC_PACK_SAT_EXPR:
3724     case VEC_PACK_FIX_TRUNC_EXPR:
3725       /* FIXME.  */
3726       return false;
3727
3728     case MULT_EXPR:
3729     case MULT_HIGHPART_EXPR:
3730     case TRUNC_DIV_EXPR:
3731     case CEIL_DIV_EXPR:
3732     case FLOOR_DIV_EXPR:
3733     case ROUND_DIV_EXPR:
3734     case TRUNC_MOD_EXPR:
3735     case CEIL_MOD_EXPR:
3736     case FLOOR_MOD_EXPR:
3737     case ROUND_MOD_EXPR:
3738     case RDIV_EXPR:
3739     case EXACT_DIV_EXPR:
3740     case MIN_EXPR:
3741     case MAX_EXPR:
3742     case BIT_IOR_EXPR:
3743     case BIT_XOR_EXPR:
3744     case BIT_AND_EXPR:
3745       /* Continue with generic binary expression handling.  */
3746       break;
3747
3748     default:
3749       gcc_unreachable ();
3750     }
3751
3752   if (!useless_type_conversion_p (lhs_type, rhs1_type)
3753       || !useless_type_conversion_p (lhs_type, rhs2_type))
3754     {
3755       error ("type mismatch in binary expression");
3756       debug_generic_stmt (lhs_type);
3757       debug_generic_stmt (rhs1_type);
3758       debug_generic_stmt (rhs2_type);
3759       return true;
3760     }
3761
3762   return false;
3763 }
3764
3765 /* Verify a gimple assignment statement STMT with a ternary rhs.
3766    Returns true if anything is wrong.  */
3767
3768 static bool
3769 verify_gimple_assign_ternary (gimple stmt)
3770 {
3771   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3772   tree lhs = gimple_assign_lhs (stmt);
3773   tree lhs_type = TREE_TYPE (lhs);
3774   tree rhs1 = gimple_assign_rhs1 (stmt);
3775   tree rhs1_type = TREE_TYPE (rhs1);
3776   tree rhs2 = gimple_assign_rhs2 (stmt);
3777   tree rhs2_type = TREE_TYPE (rhs2);
3778   tree rhs3 = gimple_assign_rhs3 (stmt);
3779   tree rhs3_type = TREE_TYPE (rhs3);
3780
3781   if (!is_gimple_reg (lhs))
3782     {
3783       error ("non-register as LHS of ternary operation");
3784       return true;
3785     }
3786
3787   if (((rhs_code == VEC_COND_EXPR || rhs_code == COND_EXPR)
3788        ? !is_gimple_condexpr (rhs1) : !is_gimple_val (rhs1))
3789       || !is_gimple_val (rhs2)
3790       || !is_gimple_val (rhs3))
3791     {
3792       error ("invalid operands in ternary operation");
3793       return true;
3794     }
3795
3796   /* First handle operations that involve different types.  */
3797   switch (rhs_code)
3798     {
3799     case WIDEN_MULT_PLUS_EXPR:
3800     case WIDEN_MULT_MINUS_EXPR:
3801       if ((!INTEGRAL_TYPE_P (rhs1_type)
3802            && !FIXED_POINT_TYPE_P (rhs1_type))
3803           || !useless_type_conversion_p (rhs1_type, rhs2_type)
3804           || !useless_type_conversion_p (lhs_type, rhs3_type)
3805           || 2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)
3806           || TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type))
3807         {
3808           error ("type mismatch in widening multiply-accumulate expression");
3809           debug_generic_expr (lhs_type);
3810           debug_generic_expr (rhs1_type);
3811           debug_generic_expr (rhs2_type);
3812           debug_generic_expr (rhs3_type);
3813           return true;
3814         }
3815       break;
3816
3817     case FMA_EXPR:
3818       if (!useless_type_conversion_p (lhs_type, rhs1_type)
3819           || !useless_type_conversion_p (lhs_type, rhs2_type)
3820           || !useless_type_conversion_p (lhs_type, rhs3_type))
3821         {
3822           error ("type mismatch in fused multiply-add expression");
3823           debug_generic_expr (lhs_type);
3824           debug_generic_expr (rhs1_type);
3825           debug_generic_expr (rhs2_type);
3826           debug_generic_expr (rhs3_type);
3827           return true;
3828         }
3829       break;
3830
3831     case COND_EXPR:
3832     case VEC_COND_EXPR:
3833       if (!useless_type_conversion_p (lhs_type, rhs2_type)
3834           || !useless_type_conversion_p (lhs_type, rhs3_type))
3835         {
3836           error ("type mismatch in conditional expression");
3837           debug_generic_expr (lhs_type);
3838           debug_generic_expr (rhs2_type);
3839           debug_generic_expr (rhs3_type);
3840           return true;
3841         }
3842       break;
3843
3844     case VEC_PERM_EXPR:
3845       if (!useless_type_conversion_p (lhs_type, rhs1_type)
3846           || !useless_type_conversion_p (lhs_type, rhs2_type))
3847         {
3848           error ("type mismatch in vector permute expression");
3849           debug_generic_expr (lhs_type);
3850           debug_generic_expr (rhs1_type);
3851           debug_generic_expr (rhs2_type);
3852           debug_generic_expr (rhs3_type);
3853           return true;
3854         }
3855
3856       if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3857           || TREE_CODE (rhs2_type) != VECTOR_TYPE
3858           || TREE_CODE (rhs3_type) != VECTOR_TYPE)
3859         {
3860           error ("vector types expected in vector permute expression");
3861           debug_generic_expr (lhs_type);
3862           debug_generic_expr (rhs1_type);
3863           debug_generic_expr (rhs2_type);
3864           debug_generic_expr (rhs3_type);
3865           return true;
3866         }
3867
3868       if (TYPE_VECTOR_SUBPARTS (rhs1_type) != TYPE_VECTOR_SUBPARTS (rhs2_type)
3869           || TYPE_VECTOR_SUBPARTS (rhs2_type)
3870              != TYPE_VECTOR_SUBPARTS (rhs3_type)
3871           || TYPE_VECTOR_SUBPARTS (rhs3_type)
3872              != TYPE_VECTOR_SUBPARTS (lhs_type))
3873         {
3874           error ("vectors with different element number found "
3875                  "in vector permute expression");
3876           debug_generic_expr (lhs_type);
3877           debug_generic_expr (rhs1_type);
3878           debug_generic_expr (rhs2_type);
3879           debug_generic_expr (rhs3_type);
3880           return true;
3881         }
3882
3883       if (TREE_CODE (TREE_TYPE (rhs3_type)) != INTEGER_TYPE
3884           || GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs3_type)))
3885              != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1_type))))
3886         {
3887           error ("invalid mask type in vector permute expression");
3888           debug_generic_expr (lhs_type);
3889           debug_generic_expr (rhs1_type);
3890           debug_generic_expr (rhs2_type);
3891           debug_generic_expr (rhs3_type);
3892           return true;
3893         }
3894
3895       return false;
3896
3897     case DOT_PROD_EXPR:
3898     case REALIGN_LOAD_EXPR:
3899       /* FIXME.  */
3900       return false;
3901
3902     default:
3903       gcc_unreachable ();
3904     }
3905   return false;
3906 }
3907
3908 /* Verify a gimple assignment statement STMT with a single rhs.
3909    Returns true if anything is wrong.  */
3910
3911 static bool
3912 verify_gimple_assign_single (gimple stmt)
3913 {
3914   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3915   tree lhs = gimple_assign_lhs (stmt);
3916   tree lhs_type = TREE_TYPE (lhs);
3917   tree rhs1 = gimple_assign_rhs1 (stmt);
3918   tree rhs1_type = TREE_TYPE (rhs1);
3919   bool res = false;
3920
3921   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3922     {
3923       error ("non-trivial conversion at assignment");
3924       debug_generic_expr (lhs_type);
3925       debug_generic_expr (rhs1_type);
3926       return true;
3927     }
3928
3929   if (handled_component_p (lhs))
3930     res |= verify_types_in_gimple_reference (lhs, true);
3931
3932   /* Special codes we cannot handle via their class.  */
3933   switch (rhs_code)
3934     {
3935     case ADDR_EXPR:
3936       {
3937         tree op = TREE_OPERAND (rhs1, 0);
3938         if (!is_gimple_addressable (op))
3939           {
3940             error ("invalid operand in unary expression");
3941             return true;
3942           }
3943
3944         /* Technically there is no longer a need for matching types, but
3945            gimple hygiene asks for this check.  In LTO we can end up
3946            combining incompatible units and thus end up with addresses
3947            of globals that change their type to a common one.  */
3948         if (!in_lto_p
3949             && !types_compatible_p (TREE_TYPE (op),
3950                                     TREE_TYPE (TREE_TYPE (rhs1)))
3951             && !one_pointer_to_useless_type_conversion_p (TREE_TYPE (rhs1),
3952                                                           TREE_TYPE (op)))
3953           {
3954             error ("type mismatch in address expression");
3955             debug_generic_stmt (TREE_TYPE (rhs1));
3956             debug_generic_stmt (TREE_TYPE (op));
3957             return true;
3958           }
3959
3960         return verify_types_in_gimple_reference (op, true);
3961       }
3962
3963     /* tcc_reference  */
3964     case INDIRECT_REF:
3965       error ("INDIRECT_REF in gimple IL");
3966       return true;
3967
3968     case COMPONENT_REF:
3969     case BIT_FIELD_REF:
3970     case ARRAY_REF:
3971     case ARRAY_RANGE_REF:
3972     case VIEW_CONVERT_EXPR:
3973     case REALPART_EXPR:
3974     case IMAGPART_EXPR:
3975     case TARGET_MEM_REF:
3976     case MEM_REF:
3977       if (!is_gimple_reg (lhs)
3978           && is_gimple_reg_type (TREE_TYPE (lhs)))
3979         {
3980           error ("invalid rhs for gimple memory store");
3981           debug_generic_stmt (lhs);
3982           debug_generic_stmt (rhs1);
3983           return true;
3984         }
3985       return res || verify_types_in_gimple_reference (rhs1, false);
3986
3987     /* tcc_constant  */
3988     case SSA_NAME:
3989     case INTEGER_CST:
3990     case REAL_CST:
3991     case FIXED_CST:
3992     case COMPLEX_CST:
3993     case VECTOR_CST:
3994     case STRING_CST:
3995       return res;
3996
3997     /* tcc_declaration  */
3998     case CONST_DECL:
3999       return res;
4000     case VAR_DECL:
4001     case PARM_DECL:
4002       if (!is_gimple_reg (lhs)
4003           && !is_gimple_reg (rhs1)
4004           && is_gimple_reg_type (TREE_TYPE (lhs)))
4005         {
4006           error ("invalid rhs for gimple memory store");
4007           debug_generic_stmt (lhs);
4008           debug_generic_stmt (rhs1);
4009           return true;
4010         }
4011       return res;
4012
4013     case CONSTRUCTOR:
4014     case OBJ_TYPE_REF:
4015     case ASSERT_EXPR:
4016     case WITH_SIZE_EXPR:
4017       /* FIXME.  */
4018       return res;
4019
4020     default:;
4021     }
4022
4023   return res;
4024 }
4025
4026 /* Verify the contents of a GIMPLE_ASSIGN STMT.  Returns true when there
4027    is a problem, otherwise false.  */
4028
4029 static bool
4030 verify_gimple_assign (gimple stmt)
4031 {
4032   switch (gimple_assign_rhs_class (stmt))
4033     {
4034     case GIMPLE_SINGLE_RHS:
4035       return verify_gimple_assign_single (stmt);
4036
4037     case GIMPLE_UNARY_RHS:
4038       return verify_gimple_assign_unary (stmt);
4039
4040     case GIMPLE_BINARY_RHS:
4041       return verify_gimple_assign_binary (stmt);
4042
4043     case GIMPLE_TERNARY_RHS:
4044       return verify_gimple_assign_ternary (stmt);
4045
4046     default:
4047       gcc_unreachable ();
4048     }
4049 }
4050
4051 /* Verify the contents of a GIMPLE_RETURN STMT.  Returns true when there
4052    is a problem, otherwise false.  */
4053
4054 static bool
4055 verify_gimple_return (gimple stmt)
4056 {
4057   tree op = gimple_return_retval (stmt);
4058   tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
4059
4060   /* We cannot test for present return values as we do not fix up missing
4061      return values from the original source.  */
4062   if (op == NULL)
4063     return false;
4064
4065   if (!is_gimple_val (op)
4066       && TREE_CODE (op) != RESULT_DECL)
4067     {
4068       error ("invalid operand in return statement");
4069       debug_generic_stmt (op);
4070       return true;
4071     }
4072
4073   if ((TREE_CODE (op) == RESULT_DECL
4074        && DECL_BY_REFERENCE (op))
4075       || (TREE_CODE (op) == SSA_NAME
4076           && TREE_CODE (SSA_NAME_VAR (op)) == RESULT_DECL
4077           && DECL_BY_REFERENCE (SSA_NAME_VAR (op))))
4078     op = TREE_TYPE (op);
4079
4080   if (!useless_type_conversion_p (restype, TREE_TYPE (op)))
4081     {
4082       error ("invalid conversion in return statement");
4083       debug_generic_stmt (restype);
4084       debug_generic_stmt (TREE_TYPE (op));
4085       return true;
4086     }
4087
4088   return false;
4089 }
4090
4091
4092 /* Verify the contents of a GIMPLE_GOTO STMT.  Returns true when there
4093    is a problem, otherwise false.  */
4094
4095 static bool
4096 verify_gimple_goto (gimple stmt)
4097 {
4098   tree dest = gimple_goto_dest (stmt);
4099
4100   /* ???  We have two canonical forms of direct goto destinations, a
4101      bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL.  */
4102   if (TREE_CODE (dest) != LABEL_DECL
4103       && (!is_gimple_val (dest)
4104           || !POINTER_TYPE_P (TREE_TYPE (dest))))
4105     {
4106       error ("goto destination is neither a label nor a pointer");
4107       return true;
4108     }
4109
4110   return false;
4111 }
4112
4113 /* Verify the contents of a GIMPLE_SWITCH STMT.  Returns true when there
4114    is a problem, otherwise false.  */
4115
4116 static bool
4117 verify_gimple_switch (gimple stmt)
4118 {
4119   unsigned int i, n;
4120   tree elt, prev_upper_bound = NULL_TREE;
4121   tree index_type, elt_type = NULL_TREE;
4122
4123   if (!is_gimple_val (gimple_switch_index (stmt)))
4124     {
4125       error ("invalid operand to switch statement");
4126       debug_generic_stmt (gimple_switch_index (stmt));
4127       return true;
4128     }
4129
4130   index_type = TREE_TYPE (gimple_switch_index (stmt));
4131   if (! INTEGRAL_TYPE_P (index_type))
4132     {
4133       error ("non-integral type switch statement");
4134       debug_generic_expr (index_type);
4135       return true;
4136     }
4137
4138   elt = gimple_switch_default_label (stmt);
4139   if (CASE_LOW (elt) != NULL_TREE || CASE_HIGH (elt) != NULL_TREE)
4140     {
4141       error ("invalid default case label in switch statement");
4142       debug_generic_expr (elt);
4143       return true;
4144     }
4145
4146   n = gimple_switch_num_labels (stmt);
4147   for (i = 1; i < n; i++)
4148     {
4149       elt = gimple_switch_label (stmt, i);
4150
4151       if (! CASE_LOW (elt))
4152         {
4153           error ("invalid case label in switch statement");
4154           debug_generic_expr (elt);
4155           return true;
4156         }
4157       if (CASE_HIGH (elt)
4158           && ! tree_int_cst_lt (CASE_LOW (elt), CASE_HIGH (elt)))
4159         {
4160           error ("invalid case range in switch statement");
4161           debug_generic_expr (elt);
4162           return true;
4163         }
4164
4165       if (elt_type)
4166         {
4167           if (TREE_TYPE (CASE_LOW (elt)) != elt_type
4168               || (CASE_HIGH (elt) && TREE_TYPE (CASE_HIGH (elt)) != elt_type))
4169             {
4170               error ("type mismatch for case label in switch statement");
4171               debug_generic_expr (elt);
4172               return true;
4173             }
4174         }
4175       else
4176         {
4177           elt_type = TREE_TYPE (CASE_LOW (elt));
4178           if (TYPE_PRECISION (index_type) < TYPE_PRECISION (elt_type))
4179             {
4180               error ("type precision mismatch in switch statement");
4181               return true;
4182             }
4183         }
4184
4185       if (prev_upper_bound)
4186         {
4187           if (! tree_int_cst_lt (prev_upper_bound, CASE_LOW (elt)))
4188             {
4189               error ("case labels not sorted in switch statement");
4190               return true;
4191             }
4192         }
4193
4194       prev_upper_bound = CASE_HIGH (elt);
4195       if (! prev_upper_bound)
4196         prev_upper_bound = CASE_LOW (elt);
4197     }
4198
4199   return false;
4200 }
4201
4202 /* Verify a gimple debug statement STMT.
4203    Returns true if anything is wrong.  */
4204
4205 static bool
4206 verify_gimple_debug (gimple stmt ATTRIBUTE_UNUSED)
4207 {
4208   /* There isn't much that could be wrong in a gimple debug stmt.  A
4209      gimple debug bind stmt, for example, maps a tree, that's usually
4210      a VAR_DECL or a PARM_DECL, but that could also be some scalarized
4211      component or member of an aggregate type, to another tree, that
4212      can be an arbitrary expression.  These stmts expand into debug
4213      insns, and are converted to debug notes by var-tracking.c.  */
4214   return false;
4215 }
4216
4217 /* Verify a gimple label statement STMT.
4218    Returns true if anything is wrong.  */
4219
4220 static bool
4221 verify_gimple_label (gimple stmt)
4222 {
4223   tree decl = gimple_label_label (stmt);
4224   int uid;
4225   bool err = false;
4226
4227   if (TREE_CODE (decl) != LABEL_DECL)
4228     return true;
4229
4230   uid = LABEL_DECL_UID (decl);
4231   if (cfun->cfg
4232       && (uid == -1
4233           || VEC_index (basic_block,
4234                         label_to_block_map, uid) != gimple_bb (stmt)))
4235     {
4236       error ("incorrect entry in label_to_block_map");
4237       err |= true;
4238     }
4239
4240   uid = EH_LANDING_PAD_NR (decl);
4241   if (uid)
4242     {
4243       eh_landing_pad lp = get_eh_landing_pad_from_number (uid);
4244       if (decl != lp->post_landing_pad)
4245         {
4246           error ("incorrect setting of landing pad number");
4247           err |= true;
4248         }
4249     }
4250
4251   return err;
4252 }
4253
4254 /* Verify the GIMPLE statement STMT.  Returns true if there is an
4255    error, otherwise false.  */
4256
4257 static bool
4258 verify_gimple_stmt (gimple stmt)
4259 {
4260   switch (gimple_code (stmt))
4261     {
4262     case GIMPLE_ASSIGN:
4263       return verify_gimple_assign (stmt);
4264
4265     case GIMPLE_LABEL:
4266       return verify_gimple_label (stmt);
4267
4268     case GIMPLE_CALL:
4269       return verify_gimple_call (stmt);
4270
4271     case GIMPLE_COND:
4272       if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
4273         {
4274           error ("invalid comparison code in gimple cond");
4275           return true;
4276         }
4277       if (!(!gimple_cond_true_label (stmt)
4278             || TREE_CODE (gimple_cond_true_label (stmt)) == LABEL_DECL)
4279           || !(!gimple_cond_false_label (stmt)
4280                || TREE_CODE (gimple_cond_false_label (stmt)) == LABEL_DECL))
4281         {
4282           error ("invalid labels in gimple cond");
4283           return true;
4284         }
4285
4286       return verify_gimple_comparison (boolean_type_node,
4287                                        gimple_cond_lhs (stmt),
4288                                        gimple_cond_rhs (stmt));
4289
4290     case GIMPLE_GOTO:
4291       return verify_gimple_goto (stmt);
4292
4293     case GIMPLE_SWITCH:
4294       return verify_gimple_switch (stmt);
4295
4296     case GIMPLE_RETURN:
4297       return verify_gimple_return (stmt);
4298
4299     case GIMPLE_ASM:
4300       return false;
4301
4302     case GIMPLE_TRANSACTION:
4303       return verify_gimple_transaction (stmt);
4304
4305     /* Tuples that do not have tree operands.  */
4306     case GIMPLE_NOP:
4307     case GIMPLE_PREDICT:
4308     case GIMPLE_RESX:
4309     case GIMPLE_EH_DISPATCH:
4310     case GIMPLE_EH_MUST_NOT_THROW:
4311       return false;
4312
4313     CASE_GIMPLE_OMP:
4314       /* OpenMP directives are validated by the FE and never operated
4315          on by the optimizers.  Furthermore, GIMPLE_OMP_FOR may contain
4316          non-gimple expressions when the main index variable has had
4317          its address taken.  This does not affect the loop itself
4318          because the header of an GIMPLE_OMP_FOR is merely used to determine
4319          how to setup the parallel iteration.  */
4320       return false;
4321
4322     case GIMPLE_DEBUG:
4323       return verify_gimple_debug (stmt);
4324
4325     default:
4326       gcc_unreachable ();
4327     }
4328 }
4329
4330 /* Verify the contents of a GIMPLE_PHI.  Returns true if there is a problem,
4331    and false otherwise.  */
4332
4333 static bool
4334 verify_gimple_phi (gimple phi)
4335 {
4336   bool err = false;
4337   unsigned i;
4338   tree phi_result = gimple_phi_result (phi);
4339   bool virtual_p;
4340
4341   if (!phi_result)
4342     {
4343       error ("invalid PHI result");
4344       return true;
4345     }
4346
4347   virtual_p = !is_gimple_reg (phi_result);
4348   if (TREE_CODE (phi_result) != SSA_NAME
4349       || (virtual_p
4350           && SSA_NAME_VAR (phi_result) != gimple_vop (cfun)))
4351     {
4352       error ("invalid PHI result");
4353       err = true;
4354     }
4355
4356   for (i = 0; i < gimple_phi_num_args (phi); i++)
4357     {
4358       tree t = gimple_phi_arg_def (phi, i);
4359
4360       if (!t)
4361         {
4362           error ("missing PHI def");
4363           err |= true;
4364           continue;
4365         }
4366       /* Addressable variables do have SSA_NAMEs but they
4367          are not considered gimple values.  */
4368       else if ((TREE_CODE (t) == SSA_NAME
4369                 && virtual_p != !is_gimple_reg (t))
4370                || (virtual_p
4371                    && (TREE_CODE (t) != SSA_NAME
4372                        || SSA_NAME_VAR (t) != gimple_vop (cfun)))
4373                || (!virtual_p
4374                    && !is_gimple_val (t)))
4375         {
4376           error ("invalid PHI argument");
4377           debug_generic_expr (t);
4378           err |= true;
4379         }
4380 #ifdef ENABLE_TYPES_CHECKING
4381       if (!useless_type_conversion_p (TREE_TYPE (phi_result), TREE_TYPE (t)))
4382         {
4383           error ("incompatible types in PHI argument %u", i);
4384           debug_generic_stmt (TREE_TYPE (phi_result));
4385           debug_generic_stmt (TREE_TYPE (t));
4386           err |= true;
4387         }
4388 #endif
4389     }
4390
4391   return err;
4392 }
4393
4394 /* Verify the GIMPLE statements inside the sequence STMTS.  */
4395
4396 static bool
4397 verify_gimple_in_seq_2 (gimple_seq stmts)
4398 {
4399   gimple_stmt_iterator ittr;
4400   bool err = false;
4401
4402   for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
4403     {
4404       gimple stmt = gsi_stmt (ittr);
4405
4406       switch (gimple_code (stmt))
4407         {
4408         case GIMPLE_BIND:
4409           err |= verify_gimple_in_seq_2 (gimple_bind_body (stmt));
4410           break;
4411
4412         case GIMPLE_TRY:
4413           err |= verify_gimple_in_seq_2 (gimple_try_eval (stmt));
4414           err |= verify_gimple_in_seq_2 (gimple_try_cleanup (stmt));
4415           break;
4416
4417         case GIMPLE_EH_FILTER:
4418           err |= verify_gimple_in_seq_2 (gimple_eh_filter_failure (stmt));
4419           break;
4420
4421         case GIMPLE_EH_ELSE:
4422           err |= verify_gimple_in_seq_2 (gimple_eh_else_n_body (stmt));
4423           err |= verify_gimple_in_seq_2 (gimple_eh_else_e_body (stmt));
4424           break;
4425
4426         case GIMPLE_CATCH:
4427           err |= verify_gimple_in_seq_2 (gimple_catch_handler (stmt));
4428           break;
4429
4430         case GIMPLE_TRANSACTION:
4431           err |= verify_gimple_transaction (stmt);
4432           break;
4433
4434         default:
4435           {
4436             bool err2 = verify_gimple_stmt (stmt);
4437             if (err2)
4438               debug_gimple_stmt (stmt);
4439             err |= err2;
4440           }
4441         }
4442     }
4443
4444   return err;
4445 }
4446
4447 /* Verify the contents of a GIMPLE_TRANSACTION.  Returns true if there
4448    is a problem, otherwise false.  */
4449
4450 static bool
4451 verify_gimple_transaction (gimple stmt)
4452 {
4453   tree lab = gimple_transaction_label (stmt);
4454   if (lab != NULL && TREE_CODE (lab) != LABEL_DECL)
4455     return true;
4456   return verify_gimple_in_seq_2 (gimple_transaction_body (stmt));
4457 }
4458
4459
4460 /* Verify the GIMPLE statements inside the statement list STMTS.  */
4461
4462 DEBUG_FUNCTION void
4463 verify_gimple_in_seq (gimple_seq stmts)
4464 {
4465   timevar_push (TV_TREE_STMT_VERIFY);
4466   if (verify_gimple_in_seq_2 (stmts))
4467     internal_error ("verify_gimple failed");
4468   timevar_pop (TV_TREE_STMT_VERIFY);
4469 }
4470
4471 /* Return true when the T can be shared.  */
4472
4473 bool
4474 tree_node_can_be_shared (tree t)
4475 {
4476   if (IS_TYPE_OR_DECL_P (t)
4477       || is_gimple_min_invariant (t)
4478       || TREE_CODE (t) == SSA_NAME
4479       || t == error_mark_node
4480       || TREE_CODE (t) == IDENTIFIER_NODE)
4481     return true;
4482
4483   if (TREE_CODE (t) == CASE_LABEL_EXPR)
4484     return true;
4485
4486   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4487            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4488          || TREE_CODE (t) == COMPONENT_REF
4489          || TREE_CODE (t) == REALPART_EXPR
4490          || TREE_CODE (t) == IMAGPART_EXPR)
4491     t = TREE_OPERAND (t, 0);
4492
4493   if (DECL_P (t))
4494     return true;
4495
4496   return false;
4497 }
4498
4499 /* Called via walk_gimple_stmt.  Verify tree sharing.  */
4500
4501 static tree
4502 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4503 {
4504   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4505   struct pointer_set_t *visited = (struct pointer_set_t *) wi->info;
4506
4507   if (tree_node_can_be_shared (*tp))
4508     {
4509       *walk_subtrees = false;
4510       return NULL;
4511     }
4512
4513   if (pointer_set_insert (visited, *tp))
4514     return *tp;
4515
4516   return NULL;
4517 }
4518
4519 static bool eh_error_found;
4520 static int
4521 verify_eh_throw_stmt_node (void **slot, void *data)
4522 {
4523   struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4524   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4525
4526   if (!pointer_set_contains (visited, node->stmt))
4527     {
4528       error ("dead STMT in EH table");
4529       debug_gimple_stmt (node->stmt);
4530       eh_error_found = true;
4531     }
4532   return 1;
4533 }
4534
4535 /* Verify the GIMPLE statements in the CFG of FN.  */
4536
4537 DEBUG_FUNCTION void
4538 verify_gimple_in_cfg (struct function *fn)
4539 {
4540   basic_block bb;
4541   bool err = false;
4542   struct pointer_set_t *visited, *visited_stmts;
4543
4544   timevar_push (TV_TREE_STMT_VERIFY);
4545   visited = pointer_set_create ();
4546   visited_stmts = pointer_set_create ();
4547
4548   FOR_EACH_BB_FN (bb, fn)
4549     {
4550       gimple_stmt_iterator gsi;
4551
4552       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4553         {
4554           gimple phi = gsi_stmt (gsi);
4555           bool err2 = false;
4556           unsigned i;
4557
4558           pointer_set_insert (visited_stmts, phi);
4559
4560           if (gimple_bb (phi) != bb)
4561             {
4562               error ("gimple_bb (phi) is set to a wrong basic block");
4563               err2 = true;
4564             }
4565
4566           err2 |= verify_gimple_phi (phi);
4567
4568           for (i = 0; i < gimple_phi_num_args (phi); i++)
4569             {
4570               tree arg = gimple_phi_arg_def (phi, i);
4571               tree addr = walk_tree (&arg, verify_node_sharing, visited, NULL);
4572               if (addr)
4573                 {
4574                   error ("incorrect sharing of tree nodes");
4575                   debug_generic_expr (addr);
4576                   err2 |= true;
4577                 }
4578             }
4579
4580           if (err2)
4581             debug_gimple_stmt (phi);
4582           err |= err2;
4583         }
4584
4585       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4586         {
4587           gimple stmt = gsi_stmt (gsi);
4588           bool err2 = false;
4589           struct walk_stmt_info wi;
4590           tree addr;
4591           int lp_nr;
4592
4593           pointer_set_insert (visited_stmts, stmt);
4594
4595           if (gimple_bb (stmt) != bb)
4596             {
4597               error ("gimple_bb (stmt) is set to a wrong basic block");
4598               err2 = true;
4599             }
4600
4601           err2 |= verify_gimple_stmt (stmt);
4602
4603           memset (&wi, 0, sizeof (wi));
4604           wi.info = (void *) visited;
4605           addr = walk_gimple_op (stmt, verify_node_sharing, &wi);
4606           if (addr)
4607             {
4608               error ("incorrect sharing of tree nodes");
4609               debug_generic_expr (addr);
4610               err2 |= true;
4611             }
4612
4613           /* ???  Instead of not checking these stmts at all the walker
4614              should know its context via wi.  */
4615           if (!is_gimple_debug (stmt)
4616               && !is_gimple_omp (stmt))
4617             {
4618               memset (&wi, 0, sizeof (wi));
4619               addr = walk_gimple_op (stmt, verify_expr, &wi);
4620               if (addr)
4621                 {
4622                   debug_generic_expr (addr);
4623                   inform (gimple_location (stmt), "in statement");
4624                   err2 |= true;
4625                 }
4626             }
4627
4628           /* If the statement is marked as part of an EH region, then it is
4629              expected that the statement could throw.  Verify that when we
4630              have optimizations that simplify statements such that we prove
4631              that they cannot throw, that we update other data structures
4632              to match.  */
4633           lp_nr = lookup_stmt_eh_lp (stmt);
4634           if (lp_nr != 0)
4635             {
4636               if (!stmt_could_throw_p (stmt))
4637                 {
4638                   error ("statement marked for throw, but doesn%'t");
4639                   err2 |= true;
4640                 }
4641               else if (lp_nr > 0
4642                        && !gsi_one_before_end_p (gsi)
4643                        && stmt_can_throw_internal (stmt))
4644                 {
4645                   error ("statement marked for throw in middle of block");
4646                   err2 |= true;
4647                 }
4648             }
4649
4650           if (err2)
4651             debug_gimple_stmt (stmt);
4652           err |= err2;
4653         }
4654     }
4655
4656   eh_error_found = false;
4657   if (get_eh_throw_stmt_table (cfun))
4658     htab_traverse (get_eh_throw_stmt_table (cfun),
4659                    verify_eh_throw_stmt_node,
4660                    visited_stmts);
4661
4662   if (err || eh_error_found)
4663     internal_error ("verify_gimple failed");
4664
4665   pointer_set_destroy (visited);
4666   pointer_set_destroy (visited_stmts);
4667   verify_histograms ();
4668   timevar_pop (TV_TREE_STMT_VERIFY);
4669 }
4670
4671
4672 /* Verifies that the flow information is OK.  */
4673
4674 static int
4675 gimple_verify_flow_info (void)
4676 {
4677   int err = 0;
4678   basic_block bb;
4679   gimple_stmt_iterator gsi;
4680   gimple stmt;
4681   edge e;
4682   edge_iterator ei;
4683
4684   if (ENTRY_BLOCK_PTR->il.gimple.seq || ENTRY_BLOCK_PTR->il.gimple.phi_nodes)
4685     {
4686       error ("ENTRY_BLOCK has IL associated with it");
4687       err = 1;
4688     }
4689
4690   if (EXIT_BLOCK_PTR->il.gimple.seq || EXIT_BLOCK_PTR->il.gimple.phi_nodes)
4691     {
4692       error ("EXIT_BLOCK has IL associated with it");
4693       err = 1;
4694     }
4695
4696   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4697     if (e->flags & EDGE_FALLTHRU)
4698       {
4699         error ("fallthru to exit from bb %d", e->src->index);
4700         err = 1;
4701       }
4702
4703   FOR_EACH_BB (bb)
4704     {
4705       bool found_ctrl_stmt = false;
4706
4707       stmt = NULL;
4708
4709       /* Skip labels on the start of basic block.  */
4710       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4711         {
4712           tree label;
4713           gimple prev_stmt = stmt;
4714
4715           stmt = gsi_stmt (gsi);
4716
4717           if (gimple_code (stmt) != GIMPLE_LABEL)
4718             break;
4719
4720           label = gimple_label_label (stmt);
4721           if (prev_stmt && DECL_NONLOCAL (label))
4722             {
4723               error ("nonlocal label ");
4724               print_generic_expr (stderr, label, 0);
4725               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4726                        bb->index);
4727               err = 1;
4728             }
4729
4730           if (prev_stmt && EH_LANDING_PAD_NR (label) != 0)
4731             {
4732               error ("EH landing pad label ");
4733               print_generic_expr (stderr, label, 0);
4734               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4735                        bb->index);
4736               err = 1;
4737             }
4738
4739           if (label_to_block (label) != bb)
4740             {
4741               error ("label ");
4742               print_generic_expr (stderr, label, 0);
4743               fprintf (stderr, " to block does not match in bb %d",
4744                        bb->index);
4745               err = 1;
4746             }
4747
4748           if (decl_function_context (label) != current_function_decl)
4749             {
4750               error ("label ");
4751               print_generic_expr (stderr, label, 0);
4752               fprintf (stderr, " has incorrect context in bb %d",
4753                        bb->index);
4754               err = 1;
4755             }
4756         }
4757
4758       /* Verify that body of basic block BB is free of control flow.  */
4759       for (; !gsi_end_p (gsi); gsi_next (&gsi))
4760         {
4761           gimple stmt = gsi_stmt (gsi);
4762
4763           if (found_ctrl_stmt)
4764             {
4765               error ("control flow in the middle of basic block %d",
4766                      bb->index);
4767               err = 1;
4768             }
4769
4770           if (stmt_ends_bb_p (stmt))
4771             found_ctrl_stmt = true;
4772
4773           if (gimple_code (stmt) == GIMPLE_LABEL)
4774             {
4775               error ("label ");
4776               print_generic_expr (stderr, gimple_label_label (stmt), 0);
4777               fprintf (stderr, " in the middle of basic block %d", bb->index);
4778               err = 1;
4779             }
4780         }
4781
4782       gsi = gsi_last_bb (bb);
4783       if (gsi_end_p (gsi))
4784         continue;
4785
4786       stmt = gsi_stmt (gsi);
4787
4788       if (gimple_code (stmt) == GIMPLE_LABEL)
4789         continue;
4790
4791       err |= verify_eh_edges (stmt);
4792
4793       if (is_ctrl_stmt (stmt))
4794         {
4795           FOR_EACH_EDGE (e, ei, bb->succs)
4796             if (e->flags & EDGE_FALLTHRU)
4797               {
4798                 error ("fallthru edge after a control statement in bb %d",
4799                        bb->index);
4800                 err = 1;
4801               }
4802         }
4803
4804       if (gimple_code (stmt) != GIMPLE_COND)
4805         {
4806           /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4807              after anything else but if statement.  */
4808           FOR_EACH_EDGE (e, ei, bb->succs)
4809             if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4810               {
4811                 error ("true/false edge after a non-GIMPLE_COND in bb %d",
4812                        bb->index);
4813                 err = 1;
4814               }
4815         }
4816
4817       switch (gimple_code (stmt))
4818         {
4819         case GIMPLE_COND:
4820           {
4821             edge true_edge;
4822             edge false_edge;
4823
4824             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4825
4826             if (!true_edge
4827                 || !false_edge
4828                 || !(true_edge->flags & EDGE_TRUE_VALUE)
4829                 || !(false_edge->flags & EDGE_FALSE_VALUE)
4830                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4831                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4832                 || EDGE_COUNT (bb->succs) >= 3)
4833               {
4834                 error ("wrong outgoing edge flags at end of bb %d",
4835                        bb->index);
4836                 err = 1;
4837               }
4838           }
4839           break;
4840
4841         case GIMPLE_GOTO:
4842           if (simple_goto_p (stmt))
4843             {
4844               error ("explicit goto at end of bb %d", bb->index);
4845               err = 1;
4846             }
4847           else
4848             {
4849               /* FIXME.  We should double check that the labels in the
4850                  destination blocks have their address taken.  */
4851               FOR_EACH_EDGE (e, ei, bb->succs)
4852                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4853                                  | EDGE_FALSE_VALUE))
4854                     || !(e->flags & EDGE_ABNORMAL))
4855                   {
4856                     error ("wrong outgoing edge flags at end of bb %d",
4857                            bb->index);
4858                     err = 1;
4859                   }
4860             }
4861           break;
4862
4863         case GIMPLE_CALL:
4864           if (!gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
4865             break;
4866           /* ... fallthru ... */
4867         case GIMPLE_RETURN:
4868           if (!single_succ_p (bb)
4869               || (single_succ_edge (bb)->flags
4870                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
4871                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4872             {
4873               error ("wrong outgoing edge flags at end of bb %d", bb->index);
4874               err = 1;
4875             }
4876           if (single_succ (bb) != EXIT_BLOCK_PTR)
4877             {
4878               error ("return edge does not point to exit in bb %d",
4879                      bb->index);
4880               err = 1;
4881             }
4882           break;
4883
4884         case GIMPLE_SWITCH:
4885           {
4886             tree prev;
4887             edge e;
4888             size_t i, n;
4889
4890             n = gimple_switch_num_labels (stmt);
4891
4892             /* Mark all the destination basic blocks.  */
4893             for (i = 0; i < n; ++i)
4894               {
4895                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4896                 basic_block label_bb = label_to_block (lab);
4897                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4898                 label_bb->aux = (void *)1;
4899               }
4900
4901             /* Verify that the case labels are sorted.  */
4902             prev = gimple_switch_label (stmt, 0);
4903             for (i = 1; i < n; ++i)
4904               {
4905                 tree c = gimple_switch_label (stmt, i);
4906                 if (!CASE_LOW (c))
4907                   {
4908                     error ("found default case not at the start of "
4909                            "case vector");
4910                     err = 1;
4911                     continue;
4912                   }
4913                 if (CASE_LOW (prev)
4914                     && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4915                   {
4916                     error ("case labels not sorted: ");
4917                     print_generic_expr (stderr, prev, 0);
4918                     fprintf (stderr," is greater than ");
4919                     print_generic_expr (stderr, c, 0);
4920                     fprintf (stderr," but comes before it.\n");
4921                     err = 1;
4922                   }
4923                 prev = c;
4924               }
4925             /* VRP will remove the default case if it can prove it will
4926                never be executed.  So do not verify there always exists
4927                a default case here.  */
4928
4929             FOR_EACH_EDGE (e, ei, bb->succs)
4930               {
4931                 if (!e->dest->aux)
4932                   {
4933                     error ("extra outgoing edge %d->%d",
4934                            bb->index, e->dest->index);
4935                     err = 1;
4936                   }
4937
4938                 e->dest->aux = (void *)2;
4939                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
4940                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4941                   {
4942                     error ("wrong outgoing edge flags at end of bb %d",
4943                            bb->index);
4944                     err = 1;
4945                   }
4946               }
4947
4948             /* Check that we have all of them.  */
4949             for (i = 0; i < n; ++i)
4950               {
4951                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4952                 basic_block label_bb = label_to_block (lab);
4953
4954                 if (label_bb->aux != (void *)2)
4955                   {
4956                     error ("missing edge %i->%i", bb->index, label_bb->index);
4957                     err = 1;
4958                   }
4959               }
4960
4961             FOR_EACH_EDGE (e, ei, bb->succs)
4962               e->dest->aux = (void *)0;
4963           }
4964           break;
4965
4966         case GIMPLE_EH_DISPATCH:
4967           err |= verify_eh_dispatch_edge (stmt);
4968           break;
4969
4970         default:
4971           break;
4972         }
4973     }
4974
4975   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
4976     verify_dominators (CDI_DOMINATORS);
4977
4978   return err;
4979 }
4980
4981
4982 /* Updates phi nodes after creating a forwarder block joined
4983    by edge FALLTHRU.  */
4984
4985 static void
4986 gimple_make_forwarder_block (edge fallthru)
4987 {
4988   edge e;
4989   edge_iterator ei;
4990   basic_block dummy, bb;
4991   tree var;
4992   gimple_stmt_iterator gsi;
4993
4994   dummy = fallthru->src;
4995   bb = fallthru->dest;
4996
4997   if (single_pred_p (bb))
4998     return;
4999
5000   /* If we redirected a branch we must create new PHI nodes at the
5001      start of BB.  */
5002   for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
5003     {
5004       gimple phi, new_phi;
5005
5006       phi = gsi_stmt (gsi);
5007       var = gimple_phi_result (phi);
5008       new_phi = create_phi_node (var, bb);
5009       SSA_NAME_DEF_STMT (var) = new_phi;
5010       gimple_phi_set_result (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
5011       add_phi_arg (new_phi, gimple_phi_result (phi), fallthru,
5012                    UNKNOWN_LOCATION);
5013     }
5014
5015   /* Add the arguments we have stored on edges.  */
5016   FOR_EACH_EDGE (e, ei, bb->preds)
5017     {
5018       if (e == fallthru)
5019         continue;
5020
5021       flush_pending_stmts (e);
5022     }
5023 }
5024
5025
5026 /* Return a non-special label in the head of basic block BLOCK.
5027    Create one if it doesn't exist.  */
5028
5029 tree
5030 gimple_block_label (basic_block bb)
5031 {
5032   gimple_stmt_iterator i, s = gsi_start_bb (bb);
5033   bool first = true;
5034   tree label;
5035   gimple stmt;
5036
5037   for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
5038     {
5039       stmt = gsi_stmt (i);
5040       if (gimple_code (stmt) != GIMPLE_LABEL)
5041         break;
5042       label = gimple_label_label (stmt);
5043       if (!DECL_NONLOCAL (label))
5044         {
5045           if (!first)
5046             gsi_move_before (&i, &s);
5047           return label;
5048         }
5049     }
5050
5051   label = create_artificial_label (UNKNOWN_LOCATION);
5052   stmt = gimple_build_label (label);
5053   gsi_insert_before (&s, stmt, GSI_NEW_STMT);
5054   return label;
5055 }
5056
5057
5058 /* Attempt to perform edge redirection by replacing a possibly complex
5059    jump instruction by a goto or by removing the jump completely.
5060    This can apply only if all edges now point to the same block.  The
5061    parameters and return values are equivalent to
5062    redirect_edge_and_branch.  */
5063
5064 static edge
5065 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
5066 {
5067   basic_block src = e->src;
5068   gimple_stmt_iterator i;
5069   gimple stmt;
5070
5071   /* We can replace or remove a complex jump only when we have exactly
5072      two edges.  */
5073   if (EDGE_COUNT (src->succs) != 2
5074       /* Verify that all targets will be TARGET.  Specifically, the
5075          edge that is not E must also go to TARGET.  */
5076       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
5077     return NULL;
5078
5079   i = gsi_last_bb (src);
5080   if (gsi_end_p (i))
5081     return NULL;
5082
5083   stmt = gsi_stmt (i);
5084
5085   if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
5086     {
5087       gsi_remove (&i, true);
5088       e = ssa_redirect_edge (e, target);
5089       e->flags = EDGE_FALLTHRU;
5090       return e;
5091     }
5092
5093   return NULL;
5094 }
5095
5096
5097 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
5098    edge representing the redirected branch.  */
5099
5100 static edge
5101 gimple_redirect_edge_and_branch (edge e, basic_block dest)
5102 {
5103   basic_block bb = e->src;
5104   gimple_stmt_iterator gsi;
5105   edge ret;
5106   gimple stmt;
5107
5108   if (e->flags & EDGE_ABNORMAL)
5109     return NULL;
5110
5111   if (e->dest == dest)
5112     return NULL;
5113
5114   if (e->flags & EDGE_EH)
5115     return redirect_eh_edge (e, dest);
5116
5117   if (e->src != ENTRY_BLOCK_PTR)
5118     {
5119       ret = gimple_try_redirect_by_replacing_jump (e, dest);
5120       if (ret)
5121         return ret;
5122     }
5123
5124   gsi = gsi_last_bb (bb);
5125   stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
5126
5127   switch (stmt ? gimple_code (stmt) : GIMPLE_ERROR_MARK)
5128     {
5129     case GIMPLE_COND:
5130       /* For COND_EXPR, we only need to redirect the edge.  */
5131       break;
5132
5133     case GIMPLE_GOTO:
5134       /* No non-abnormal edges should lead from a non-simple goto, and
5135          simple ones should be represented implicitly.  */
5136       gcc_unreachable ();
5137
5138     case GIMPLE_SWITCH:
5139       {
5140         tree label = gimple_block_label (dest);
5141         tree cases = get_cases_for_edge (e, stmt);
5142
5143         /* If we have a list of cases associated with E, then use it
5144            as it's a lot faster than walking the entire case vector.  */
5145         if (cases)
5146           {
5147             edge e2 = find_edge (e->src, dest);
5148             tree last, first;
5149
5150             first = cases;
5151             while (cases)
5152               {
5153                 last = cases;
5154                 CASE_LABEL (cases) = label;
5155                 cases = CASE_CHAIN (cases);
5156               }
5157
5158             /* If there was already an edge in the CFG, then we need
5159                to move all the cases associated with E to E2.  */
5160             if (e2)
5161               {
5162                 tree cases2 = get_cases_for_edge (e2, stmt);
5163
5164                 CASE_CHAIN (last) = CASE_CHAIN (cases2);
5165                 CASE_CHAIN (cases2) = first;
5166               }
5167             bitmap_set_bit (touched_switch_bbs, gimple_bb (stmt)->index);
5168           }
5169         else
5170           {
5171             size_t i, n = gimple_switch_num_labels (stmt);
5172
5173             for (i = 0; i < n; i++)
5174               {
5175                 tree elt = gimple_switch_label (stmt, i);
5176                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
5177                   CASE_LABEL (elt) = label;
5178               }
5179           }
5180       }
5181       break;
5182
5183     case GIMPLE_ASM:
5184       {
5185         int i, n = gimple_asm_nlabels (stmt);
5186         tree label = NULL;
5187
5188         for (i = 0; i < n; ++i)
5189           {
5190             tree cons = gimple_asm_label_op (stmt, i);
5191             if (label_to_block (TREE_VALUE (cons)) == e->dest)
5192               {
5193                 if (!label)
5194                   label = gimple_block_label (dest);
5195                 TREE_VALUE (cons) = label;
5196               }
5197           }
5198
5199         /* If we didn't find any label matching the former edge in the
5200            asm labels, we must be redirecting the fallthrough
5201            edge.  */
5202         gcc_assert (label || (e->flags & EDGE_FALLTHRU));
5203       }
5204       break;
5205
5206     case GIMPLE_RETURN:
5207       gsi_remove (&gsi, true);
5208       e->flags |= EDGE_FALLTHRU;
5209       break;
5210
5211     case GIMPLE_OMP_RETURN:
5212     case GIMPLE_OMP_CONTINUE:
5213     case GIMPLE_OMP_SECTIONS_SWITCH:
5214     case GIMPLE_OMP_FOR:
5215       /* The edges from OMP constructs can be simply redirected.  */
5216       break;
5217
5218     case GIMPLE_EH_DISPATCH:
5219       if (!(e->flags & EDGE_FALLTHRU))
5220         redirect_eh_dispatch_edge (stmt, e, dest);
5221       break;
5222
5223     case GIMPLE_TRANSACTION:
5224       /* The ABORT edge has a stored label associated with it, otherwise
5225          the edges are simply redirectable.  */
5226       if (e->flags == 0)
5227         gimple_transaction_set_label (stmt, gimple_block_label (dest));
5228       break;
5229
5230     default:
5231       /* Otherwise it must be a fallthru edge, and we don't need to
5232          do anything besides redirecting it.  */
5233       gcc_assert (e->flags & EDGE_FALLTHRU);
5234       break;
5235     }
5236
5237   /* Update/insert PHI nodes as necessary.  */
5238
5239   /* Now update the edges in the CFG.  */
5240   e = ssa_redirect_edge (e, dest);
5241
5242   return e;
5243 }
5244
5245 /* Returns true if it is possible to remove edge E by redirecting
5246    it to the destination of the other edge from E->src.  */
5247
5248 static bool
5249 gimple_can_remove_branch_p (const_edge e)
5250 {
5251   if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
5252     return false;
5253
5254   return true;
5255 }
5256
5257 /* Simple wrapper, as we can always redirect fallthru edges.  */
5258
5259 static basic_block
5260 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
5261 {
5262   e = gimple_redirect_edge_and_branch (e, dest);
5263   gcc_assert (e);
5264
5265   return NULL;
5266 }
5267
5268
5269 /* Splits basic block BB after statement STMT (but at least after the
5270    labels).  If STMT is NULL, BB is split just after the labels.  */
5271
5272 static basic_block
5273 gimple_split_block (basic_block bb, void *stmt)
5274 {
5275   gimple_stmt_iterator gsi;
5276   gimple_stmt_iterator gsi_tgt;
5277   gimple act;
5278   gimple_seq list;
5279   basic_block new_bb;
5280   edge e;
5281   edge_iterator ei;
5282
5283   new_bb = create_empty_bb (bb);
5284
5285   /* Redirect the outgoing edges.  */
5286   new_bb->succs = bb->succs;
5287   bb->succs = NULL;
5288   FOR_EACH_EDGE (e, ei, new_bb->succs)
5289     e->src = new_bb;
5290
5291   if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
5292     stmt = NULL;
5293
5294   /* Move everything from GSI to the new basic block.  */
5295   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5296     {
5297       act = gsi_stmt (gsi);
5298       if (gimple_code (act) == GIMPLE_LABEL)
5299         continue;
5300
5301       if (!stmt)
5302         break;
5303
5304       if (stmt == act)
5305         {
5306           gsi_next (&gsi);
5307           break;
5308         }
5309     }
5310
5311   if (gsi_end_p (gsi))
5312     return new_bb;
5313
5314   /* Split the statement list - avoid re-creating new containers as this
5315      brings ugly quadratic memory consumption in the inliner.
5316      (We are still quadratic since we need to update stmt BB pointers,
5317      sadly.)  */
5318   gsi_split_seq_before (&gsi, &list);
5319   set_bb_seq (new_bb, list);
5320   for (gsi_tgt = gsi_start (list);
5321        !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
5322     gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
5323
5324   return new_bb;
5325 }
5326
5327
5328 /* Moves basic block BB after block AFTER.  */
5329
5330 static bool
5331 gimple_move_block_after (basic_block bb, basic_block after)
5332 {
5333   if (bb->prev_bb == after)
5334     return true;
5335
5336   unlink_block (bb);
5337   link_block (bb, after);
5338
5339   return true;
5340 }
5341
5342
5343 /* Return true if basic_block can be duplicated.  */
5344
5345 static bool
5346 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5347 {
5348   return true;
5349 }
5350
5351 /* Create a duplicate of the basic block BB.  NOTE: This does not
5352    preserve SSA form.  */
5353
5354 static basic_block
5355 gimple_duplicate_bb (basic_block bb)
5356 {
5357   basic_block new_bb;
5358   gimple_stmt_iterator gsi, gsi_tgt;
5359   gimple_seq phis = phi_nodes (bb);
5360   gimple phi, stmt, copy;
5361
5362   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
5363
5364   /* Copy the PHI nodes.  We ignore PHI node arguments here because
5365      the incoming edges have not been setup yet.  */
5366   for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
5367     {
5368       phi = gsi_stmt (gsi);
5369       copy = create_phi_node (gimple_phi_result (phi), new_bb);
5370       create_new_def_for (gimple_phi_result (copy), copy,
5371                           gimple_phi_result_ptr (copy));
5372     }
5373
5374   gsi_tgt = gsi_start_bb (new_bb);
5375   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5376     {
5377       def_operand_p def_p;
5378       ssa_op_iter op_iter;
5379       tree lhs;
5380
5381       stmt = gsi_stmt (gsi);
5382       if (gimple_code (stmt) == GIMPLE_LABEL)
5383         continue;
5384
5385       /* Don't duplicate label debug stmts.  */
5386       if (gimple_debug_bind_p (stmt)
5387           && TREE_CODE (gimple_debug_bind_get_var (stmt))
5388              == LABEL_DECL)
5389         continue;
5390
5391       /* Create a new copy of STMT and duplicate STMT's virtual
5392          operands.  */
5393       copy = gimple_copy (stmt);
5394       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
5395
5396       maybe_duplicate_eh_stmt (copy, stmt);
5397       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5398
5399       /* When copying around a stmt writing into a local non-user
5400          aggregate, make sure it won't share stack slot with other
5401          vars.  */
5402       lhs = gimple_get_lhs (stmt);
5403       if (lhs && TREE_CODE (lhs) != SSA_NAME)
5404         {
5405           tree base = get_base_address (lhs);
5406           if (base
5407               && (TREE_CODE (base) == VAR_DECL
5408                   || TREE_CODE (base) == RESULT_DECL)
5409               && DECL_IGNORED_P (base)
5410               && !TREE_STATIC (base)
5411               && !DECL_EXTERNAL (base)
5412               && (TREE_CODE (base) != VAR_DECL
5413                   || !DECL_HAS_VALUE_EXPR_P (base)))
5414             DECL_NONSHAREABLE (base) = 1;
5415         }
5416
5417       /* Create new names for all the definitions created by COPY and
5418          add replacement mappings for each new name.  */
5419       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5420         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5421     }
5422
5423   return new_bb;
5424 }
5425
5426 /* Adds phi node arguments for edge E_COPY after basic block duplication.  */
5427
5428 static void
5429 add_phi_args_after_copy_edge (edge e_copy)
5430 {
5431   basic_block bb, bb_copy = e_copy->src, dest;
5432   edge e;
5433   edge_iterator ei;
5434   gimple phi, phi_copy;
5435   tree def;
5436   gimple_stmt_iterator psi, psi_copy;
5437
5438   if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
5439     return;
5440
5441   bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5442
5443   if (e_copy->dest->flags & BB_DUPLICATED)
5444     dest = get_bb_original (e_copy->dest);
5445   else
5446     dest = e_copy->dest;
5447
5448   e = find_edge (bb, dest);
5449   if (!e)
5450     {
5451       /* During loop unrolling the target of the latch edge is copied.
5452          In this case we are not looking for edge to dest, but to
5453          duplicated block whose original was dest.  */
5454       FOR_EACH_EDGE (e, ei, bb->succs)
5455         {
5456           if ((e->dest->flags & BB_DUPLICATED)
5457               && get_bb_original (e->dest) == dest)
5458             break;
5459         }
5460
5461       gcc_assert (e != NULL);
5462     }
5463
5464   for (psi = gsi_start_phis (e->dest),
5465        psi_copy = gsi_start_phis (e_copy->dest);
5466        !gsi_end_p (psi);
5467        gsi_next (&psi), gsi_next (&psi_copy))
5468     {
5469       phi = gsi_stmt (psi);
5470       phi_copy = gsi_stmt (psi_copy);
5471       def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5472       add_phi_arg (phi_copy, def, e_copy,
5473                    gimple_phi_arg_location_from_edge (phi, e));
5474     }
5475 }
5476
5477
5478 /* Basic block BB_COPY was created by code duplication.  Add phi node
5479    arguments for edges going out of BB_COPY.  The blocks that were
5480    duplicated have BB_DUPLICATED set.  */
5481
5482 void
5483 add_phi_args_after_copy_bb (basic_block bb_copy)
5484 {
5485   edge e_copy;
5486   edge_iterator ei;
5487
5488   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5489     {
5490       add_phi_args_after_copy_edge (e_copy);
5491     }
5492 }
5493
5494 /* Blocks in REGION_COPY array of length N_REGION were created by
5495    duplication of basic blocks.  Add phi node arguments for edges
5496    going from these blocks.  If E_COPY is not NULL, also add
5497    phi node arguments for its destination.*/
5498
5499 void
5500 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5501                          edge e_copy)
5502 {
5503   unsigned i;
5504
5505   for (i = 0; i < n_region; i++)
5506     region_copy[i]->flags |= BB_DUPLICATED;
5507
5508   for (i = 0; i < n_region; i++)
5509     add_phi_args_after_copy_bb (region_copy[i]);
5510   if (e_copy)
5511     add_phi_args_after_copy_edge (e_copy);
5512
5513   for (i = 0; i < n_region; i++)
5514     region_copy[i]->flags &= ~BB_DUPLICATED;
5515 }
5516
5517 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5518    important exit edge EXIT.  By important we mean that no SSA name defined
5519    inside region is live over the other exit edges of the region.  All entry
5520    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
5521    to the duplicate of the region.  SSA form, dominance and loop information
5522    is updated.  The new basic blocks are stored to REGION_COPY in the same
5523    order as they had in REGION, provided that REGION_COPY is not NULL.
5524    The function returns false if it is unable to copy the region,
5525    true otherwise.  */
5526
5527 bool
5528 gimple_duplicate_sese_region (edge entry, edge exit,
5529                             basic_block *region, unsigned n_region,
5530                             basic_block *region_copy)
5531 {
5532   unsigned i;
5533   bool free_region_copy = false, copying_header = false;
5534   struct loop *loop = entry->dest->loop_father;
5535   edge exit_copy;
5536   VEC (basic_block, heap) *doms;
5537   edge redirected;
5538   int total_freq = 0, entry_freq = 0;
5539   gcov_type total_count = 0, entry_count = 0;
5540
5541   if (!can_copy_bbs_p (region, n_region))
5542     return false;
5543
5544   /* Some sanity checking.  Note that we do not check for all possible
5545      missuses of the functions.  I.e. if you ask to copy something weird,
5546      it will work, but the state of structures probably will not be
5547      correct.  */
5548   for (i = 0; i < n_region; i++)
5549     {
5550       /* We do not handle subloops, i.e. all the blocks must belong to the
5551          same loop.  */
5552       if (region[i]->loop_father != loop)
5553         return false;
5554
5555       if (region[i] != entry->dest
5556           && region[i] == loop->header)
5557         return false;
5558     }
5559
5560   set_loop_copy (loop, loop);
5561
5562   /* In case the function is used for loop header copying (which is the primary
5563      use), ensure that EXIT and its copy will be new latch and entry edges.  */
5564   if (loop->header == entry->dest)
5565     {
5566       copying_header = true;
5567       set_loop_copy (loop, loop_outer (loop));
5568
5569       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5570         return false;
5571
5572       for (i = 0; i < n_region; i++)
5573         if (region[i] != exit->src
5574             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5575           return false;
5576     }
5577
5578   if (!region_copy)
5579     {
5580       region_copy = XNEWVEC (basic_block, n_region);
5581       free_region_copy = true;
5582     }
5583
5584   gcc_assert (!need_ssa_update_p (cfun));
5585
5586   /* Record blocks outside the region that are dominated by something
5587      inside.  */
5588   doms = NULL;
5589   initialize_original_copy_tables ();
5590
5591   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5592
5593   if (entry->dest->count)
5594     {
5595       total_count = entry->dest->count;
5596       entry_count = entry->count;
5597       /* Fix up corner cases, to avoid division by zero or creation of negative
5598          frequencies.  */
5599       if (entry_count > total_count)
5600         entry_count = total_count;
5601     }
5602   else
5603     {
5604       total_freq = entry->dest->frequency;
5605       entry_freq = EDGE_FREQUENCY (entry);
5606       /* Fix up corner cases, to avoid division by zero or creation of negative
5607          frequencies.  */
5608       if (total_freq == 0)
5609         total_freq = 1;
5610       else if (entry_freq > total_freq)
5611         entry_freq = total_freq;
5612     }
5613
5614   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5615             split_edge_bb_loc (entry));
5616   if (total_count)
5617     {
5618       scale_bbs_frequencies_gcov_type (region, n_region,
5619                                        total_count - entry_count,
5620                                        total_count);
5621       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5622                                        total_count);
5623     }
5624   else
5625     {
5626       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5627                                  total_freq);
5628       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5629     }
5630
5631   if (copying_header)
5632     {
5633       loop->header = exit->dest;
5634       loop->latch = exit->src;
5635     }
5636
5637   /* Redirect the entry and add the phi node arguments.  */
5638   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5639   gcc_assert (redirected != NULL);
5640   flush_pending_stmts (entry);
5641
5642   /* Concerning updating of dominators:  We must recount dominators
5643      for entry block and its copy.  Anything that is outside of the
5644      region, but was dominated by something inside needs recounting as
5645      well.  */
5646   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5647   VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
5648   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5649   VEC_free (basic_block, heap, doms);
5650
5651   /* Add the other PHI node arguments.  */
5652   add_phi_args_after_copy (region_copy, n_region, NULL);
5653
5654   /* Update the SSA web.  */
5655   update_ssa (TODO_update_ssa);
5656
5657   if (free_region_copy)
5658     free (region_copy);
5659
5660   free_original_copy_tables ();
5661   return true;
5662 }
5663
5664 /* Checks if BB is part of the region defined by N_REGION BBS.  */
5665 static bool
5666 bb_part_of_region_p (basic_block bb, basic_block* bbs, unsigned n_region)
5667 {
5668   unsigned int n;
5669
5670   for (n = 0; n < n_region; n++)
5671     {
5672      if (bb == bbs[n])
5673        return true;
5674     }
5675   return false;
5676 }
5677
5678 /* Duplicates REGION consisting of N_REGION blocks.  The new blocks
5679    are stored to REGION_COPY in the same order in that they appear
5680    in REGION, if REGION_COPY is not NULL.  ENTRY is the entry to
5681    the region, EXIT an exit from it.  The condition guarding EXIT
5682    is moved to ENTRY.  Returns true if duplication succeeds, false
5683    otherwise.
5684
5685    For example,
5686
5687    some_code;
5688    if (cond)
5689      A;
5690    else
5691      B;
5692
5693    is transformed to
5694
5695    if (cond)
5696      {
5697        some_code;
5698        A;
5699      }
5700    else
5701      {
5702        some_code;
5703        B;
5704      }
5705 */
5706
5707 bool
5708 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
5709                           basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
5710                           basic_block *region_copy ATTRIBUTE_UNUSED)
5711 {
5712   unsigned i;
5713   bool free_region_copy = false;
5714   struct loop *loop = exit->dest->loop_father;
5715   struct loop *orig_loop = entry->dest->loop_father;
5716   basic_block switch_bb, entry_bb, nentry_bb;
5717   VEC (basic_block, heap) *doms;
5718   int total_freq = 0, exit_freq = 0;
5719   gcov_type total_count = 0, exit_count = 0;
5720   edge exits[2], nexits[2], e;
5721   gimple_stmt_iterator gsi;
5722   gimple cond_stmt;
5723   edge sorig, snew;
5724   basic_block exit_bb;
5725   gimple_stmt_iterator psi;
5726   gimple phi;
5727   tree def;
5728   struct loop *target, *aloop, *cloop;
5729
5730   gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5731   exits[0] = exit;
5732   exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5733
5734   if (!can_copy_bbs_p (region, n_region))
5735     return false;
5736
5737   initialize_original_copy_tables ();
5738   set_loop_copy (orig_loop, loop);
5739
5740   target= loop;
5741   for (aloop = orig_loop->inner; aloop; aloop = aloop->next)
5742     {
5743       if (bb_part_of_region_p (aloop->header, region, n_region))
5744         {
5745           cloop = duplicate_loop (aloop, target);
5746           duplicate_subloops (aloop, cloop);
5747         }
5748     }
5749
5750   if (!region_copy)
5751     {
5752       region_copy = XNEWVEC (basic_block, n_region);
5753       free_region_copy = true;
5754     }
5755
5756   gcc_assert (!need_ssa_update_p (cfun));
5757
5758   /* Record blocks outside the region that are dominated by something
5759      inside.  */
5760   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5761
5762   if (exit->src->count)
5763     {
5764       total_count = exit->src->count;
5765       exit_count = exit->count;
5766       /* Fix up corner cases, to avoid division by zero or creation of negative
5767          frequencies.  */
5768       if (exit_count > total_count)
5769         exit_count = total_count;
5770     }
5771   else
5772     {
5773       total_freq = exit->src->frequency;
5774       exit_freq = EDGE_FREQUENCY (exit);
5775       /* Fix up corner cases, to avoid division by zero or creation of negative
5776          frequencies.  */
5777       if (total_freq == 0)
5778         total_freq = 1;
5779       if (exit_freq > total_freq)
5780         exit_freq = total_freq;
5781     }
5782
5783   copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5784             split_edge_bb_loc (exit));
5785   if (total_count)
5786     {
5787       scale_bbs_frequencies_gcov_type (region, n_region,
5788                                        total_count - exit_count,
5789                                        total_count);
5790       scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5791                                        total_count);
5792     }
5793   else
5794     {
5795       scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5796                                  total_freq);
5797       scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5798     }
5799
5800   /* Create the switch block, and put the exit condition to it.  */
5801   entry_bb = entry->dest;
5802   nentry_bb = get_bb_copy (entry_bb);
5803   if (!last_stmt (entry->src)
5804       || !stmt_ends_bb_p (last_stmt (entry->src)))
5805     switch_bb = entry->src;
5806   else
5807     switch_bb = split_edge (entry);
5808   set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5809
5810   gsi = gsi_last_bb (switch_bb);
5811   cond_stmt = last_stmt (exit->src);
5812   gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
5813   cond_stmt = gimple_copy (cond_stmt);
5814
5815   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
5816
5817   sorig = single_succ_edge (switch_bb);
5818   sorig->flags = exits[1]->flags;
5819   snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5820
5821   /* Register the new edge from SWITCH_BB in loop exit lists.  */
5822   rescan_loop_exit (snew, true, false);
5823
5824   /* Add the PHI node arguments.  */
5825   add_phi_args_after_copy (region_copy, n_region, snew);
5826
5827   /* Get rid of now superfluous conditions and associated edges (and phi node
5828      arguments).  */
5829   exit_bb = exit->dest;
5830
5831   e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5832   PENDING_STMT (e) = NULL;
5833
5834   /* The latch of ORIG_LOOP was copied, and so was the backedge
5835      to the original header.  We redirect this backedge to EXIT_BB.  */
5836   for (i = 0; i < n_region; i++)
5837     if (get_bb_original (region_copy[i]) == orig_loop->latch)
5838       {
5839         gcc_assert (single_succ_edge (region_copy[i]));
5840         e = redirect_edge_and_branch (single_succ_edge (region_copy[i]), exit_bb);
5841         PENDING_STMT (e) = NULL;
5842         for (psi = gsi_start_phis (exit_bb);
5843              !gsi_end_p (psi);
5844              gsi_next (&psi))
5845           {
5846             phi = gsi_stmt (psi);
5847             def = PHI_ARG_DEF (phi, nexits[0]->dest_idx);
5848             add_phi_arg (phi, def, e, gimple_phi_arg_location_from_edge (phi, e));
5849           }
5850       }
5851   e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
5852   PENDING_STMT (e) = NULL;
5853
5854   /* Anything that is outside of the region, but was dominated by something
5855      inside needs to update dominance info.  */
5856   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5857   VEC_free (basic_block, heap, doms);
5858   /* Update the SSA web.  */
5859   update_ssa (TODO_update_ssa);
5860
5861   if (free_region_copy)
5862     free (region_copy);
5863
5864   free_original_copy_tables ();
5865   return true;
5866 }
5867
5868 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
5869    adding blocks when the dominator traversal reaches EXIT.  This
5870    function silently assumes that ENTRY strictly dominates EXIT.  */
5871
5872 void
5873 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5874                               VEC(basic_block,heap) **bbs_p)
5875 {
5876   basic_block son;
5877
5878   for (son = first_dom_son (CDI_DOMINATORS, entry);
5879        son;
5880        son = next_dom_son (CDI_DOMINATORS, son))
5881     {
5882       VEC_safe_push (basic_block, heap, *bbs_p, son);
5883       if (son != exit)
5884         gather_blocks_in_sese_region (son, exit, bbs_p);
5885     }
5886 }
5887
5888 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5889    The duplicates are recorded in VARS_MAP.  */
5890
5891 static void
5892 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5893                            tree to_context)
5894 {
5895   tree t = *tp, new_t;
5896   struct function *f = DECL_STRUCT_FUNCTION (to_context);
5897   void **loc;
5898
5899   if (DECL_CONTEXT (t) == to_context)
5900     return;
5901
5902   loc = pointer_map_contains (vars_map, t);
5903
5904   if (!loc)
5905     {
5906       loc = pointer_map_insert (vars_map, t);
5907
5908       if (SSA_VAR_P (t))
5909         {
5910           new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5911           add_local_decl (f, new_t);
5912         }
5913       else
5914         {
5915           gcc_assert (TREE_CODE (t) == CONST_DECL);
5916           new_t = copy_node (t);
5917         }
5918       DECL_CONTEXT (new_t) = to_context;
5919
5920       *loc = new_t;
5921     }
5922   else
5923     new_t = (tree) *loc;
5924
5925   *tp = new_t;
5926 }
5927
5928
5929 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5930    VARS_MAP maps old ssa names and var_decls to the new ones.  */
5931
5932 static tree
5933 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5934                   tree to_context)
5935 {
5936   void **loc;
5937   tree new_name, decl = SSA_NAME_VAR (name);
5938
5939   gcc_assert (is_gimple_reg (name));
5940
5941   loc = pointer_map_contains (vars_map, name);
5942
5943   if (!loc)
5944     {
5945       replace_by_duplicate_decl (&decl, vars_map, to_context);
5946
5947       push_cfun (DECL_STRUCT_FUNCTION (to_context));
5948       if (gimple_in_ssa_p (cfun))
5949         add_referenced_var (decl);
5950
5951       new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5952       if (SSA_NAME_IS_DEFAULT_DEF (name))
5953         set_default_def (decl, new_name);
5954       pop_cfun ();
5955
5956       loc = pointer_map_insert (vars_map, name);
5957       *loc = new_name;
5958     }
5959   else
5960     new_name = (tree) *loc;
5961
5962   return new_name;
5963 }
5964
5965 struct move_stmt_d
5966 {
5967   tree orig_block;
5968   tree new_block;
5969   tree from_context;
5970   tree to_context;
5971   struct pointer_map_t *vars_map;
5972   htab_t new_label_map;
5973   struct pointer_map_t *eh_map;
5974   bool remap_decls_p;
5975 };
5976
5977 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
5978    contained in *TP if it has been ORIG_BLOCK previously and change the
5979    DECL_CONTEXT of every local variable referenced in *TP.  */
5980
5981 static tree
5982 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
5983 {
5984   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
5985   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5986   tree t = *tp;
5987
5988   if (EXPR_P (t))
5989     /* We should never have TREE_BLOCK set on non-statements.  */
5990     gcc_assert (!TREE_BLOCK (t));
5991
5992   else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
5993     {
5994       if (TREE_CODE (t) == SSA_NAME)
5995         *tp = replace_ssa_name (t, p->vars_map, p->to_context);
5996       else if (TREE_CODE (t) == LABEL_DECL)
5997         {
5998           if (p->new_label_map)
5999             {
6000               struct tree_map in, *out;
6001               in.base.from = t;
6002               out = (struct tree_map *)
6003                 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
6004               if (out)
6005                 *tp = t = out->to;
6006             }
6007
6008           DECL_CONTEXT (t) = p->to_context;
6009         }
6010       else if (p->remap_decls_p)
6011         {
6012           /* Replace T with its duplicate.  T should no longer appear in the
6013              parent function, so this looks wasteful; however, it may appear
6014              in referenced_vars, and more importantly, as virtual operands of
6015              statements, and in alias lists of other variables.  It would be
6016              quite difficult to expunge it from all those places.  ??? It might
6017              suffice to do this for addressable variables.  */
6018           if ((TREE_CODE (t) == VAR_DECL
6019                && !is_global_var (t))
6020               || TREE_CODE (t) == CONST_DECL)
6021             {
6022               struct function *to_fn = DECL_STRUCT_FUNCTION (p->to_context);
6023               replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
6024               if (gimple_referenced_vars (to_fn))
6025                 add_referenced_var_1 (*tp, to_fn);
6026             }
6027         }
6028       *walk_subtrees = 0;
6029     }
6030   else if (TYPE_P (t))
6031     *walk_subtrees = 0;
6032
6033   return NULL_TREE;
6034 }
6035
6036 /* Helper for move_stmt_r.  Given an EH region number for the source
6037    function, map that to the duplicate EH regio number in the dest.  */
6038
6039 static int
6040 move_stmt_eh_region_nr (int old_nr, struct move_stmt_d *p)
6041 {
6042   eh_region old_r, new_r;
6043   void **slot;
6044
6045   old_r = get_eh_region_from_number (old_nr);
6046   slot = pointer_map_contains (p->eh_map, old_r);
6047   new_r = (eh_region) *slot;
6048
6049   return new_r->index;
6050 }
6051
6052 /* Similar, but operate on INTEGER_CSTs.  */
6053
6054 static tree
6055 move_stmt_eh_region_tree_nr (tree old_t_nr, struct move_stmt_d *p)
6056 {
6057   int old_nr, new_nr;
6058
6059   old_nr = tree_low_cst (old_t_nr, 0);
6060   new_nr = move_stmt_eh_region_nr (old_nr, p);
6061
6062   return build_int_cst (integer_type_node, new_nr);
6063 }
6064
6065 /* Like move_stmt_op, but for gimple statements.
6066
6067    Helper for move_block_to_fn.  Set GIMPLE_BLOCK in every expression
6068    contained in the current statement in *GSI_P and change the
6069    DECL_CONTEXT of every local variable referenced in the current
6070    statement.  */
6071
6072 static tree
6073 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
6074              struct walk_stmt_info *wi)
6075 {
6076   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
6077   gimple stmt = gsi_stmt (*gsi_p);
6078   tree block = gimple_block (stmt);
6079
6080   if (p->orig_block == NULL_TREE
6081       || block == p->orig_block
6082       || block == NULL_TREE)
6083     gimple_set_block (stmt, p->new_block);
6084 #ifdef ENABLE_CHECKING
6085   else if (block != p->new_block)
6086     {
6087       while (block && block != p->orig_block)
6088         block = BLOCK_SUPERCONTEXT (block);
6089       gcc_assert (block);
6090     }
6091 #endif
6092
6093   switch (gimple_code (stmt))
6094     {
6095     case GIMPLE_CALL:
6096       /* Remap the region numbers for __builtin_eh_{pointer,filter}.  */
6097       {
6098         tree r, fndecl = gimple_call_fndecl (stmt);
6099         if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
6100           switch (DECL_FUNCTION_CODE (fndecl))
6101             {
6102             case BUILT_IN_EH_COPY_VALUES:
6103               r = gimple_call_arg (stmt, 1);
6104               r = move_stmt_eh_region_tree_nr (r, p);
6105               gimple_call_set_arg (stmt, 1, r);
6106               /* FALLTHRU */
6107
6108             case BUILT_IN_EH_POINTER:
6109             case BUILT_IN_EH_FILTER:
6110               r = gimple_call_arg (stmt, 0);
6111               r = move_stmt_eh_region_tree_nr (r, p);
6112               gimple_call_set_arg (stmt, 0, r);
6113               break;
6114
6115             default:
6116               break;
6117             }
6118       }
6119       break;
6120
6121     case GIMPLE_RESX:
6122       {
6123         int r = gimple_resx_region (stmt);
6124         r = move_stmt_eh_region_nr (r, p);
6125         gimple_resx_set_region (stmt, r);
6126       }
6127       break;
6128
6129     case GIMPLE_EH_DISPATCH:
6130       {
6131         int r = gimple_eh_dispatch_region (stmt);
6132         r = move_stmt_eh_region_nr (r, p);
6133         gimple_eh_dispatch_set_region (stmt, r);
6134       }
6135       break;
6136
6137     case GIMPLE_OMP_RETURN:
6138     case GIMPLE_OMP_CONTINUE:
6139       break;
6140     default:
6141       if (is_gimple_omp (stmt))
6142         {
6143           /* Do not remap variables inside OMP directives.  Variables
6144              referenced in clauses and directive header belong to the
6145              parent function and should not be moved into the child
6146              function.  */
6147           bool save_remap_decls_p = p->remap_decls_p;
6148           p->remap_decls_p = false;
6149           *handled_ops_p = true;
6150
6151           walk_gimple_seq_mod (gimple_omp_body_ptr (stmt), move_stmt_r,
6152                                move_stmt_op, wi);
6153
6154           p->remap_decls_p = save_remap_decls_p;
6155         }
6156       break;
6157     }
6158
6159   return NULL_TREE;
6160 }
6161
6162 /* Move basic block BB from function CFUN to function DEST_FN.  The
6163    block is moved out of the original linked list and placed after
6164    block AFTER in the new list.  Also, the block is removed from the
6165    original array of blocks and placed in DEST_FN's array of blocks.
6166    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
6167    updated to reflect the moved edges.
6168
6169    The local variables are remapped to new instances, VARS_MAP is used
6170    to record the mapping.  */
6171
6172 static void
6173 move_block_to_fn (struct function *dest_cfun, basic_block bb,
6174                   basic_block after, bool update_edge_count_p,
6175                   struct move_stmt_d *d)
6176 {
6177   struct control_flow_graph *cfg;
6178   edge_iterator ei;
6179   edge e;
6180   gimple_stmt_iterator si;
6181   unsigned old_len, new_len;
6182
6183   /* Remove BB from dominance structures.  */
6184   delete_from_dominance_info (CDI_DOMINATORS, bb);
6185   if (current_loops)
6186     remove_bb_from_loops (bb);
6187
6188   /* Link BB to the new linked list.  */
6189   move_block_after (bb, after);
6190
6191   /* Update the edge count in the corresponding flowgraphs.  */
6192   if (update_edge_count_p)
6193     FOR_EACH_EDGE (e, ei, bb->succs)
6194       {
6195         cfun->cfg->x_n_edges--;
6196         dest_cfun->cfg->x_n_edges++;
6197       }
6198
6199   /* Remove BB from the original basic block array.  */
6200   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
6201   cfun->cfg->x_n_basic_blocks--;
6202
6203   /* Grow DEST_CFUN's basic block array if needed.  */
6204   cfg = dest_cfun->cfg;
6205   cfg->x_n_basic_blocks++;
6206   if (bb->index >= cfg->x_last_basic_block)
6207     cfg->x_last_basic_block = bb->index + 1;
6208
6209   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
6210   if ((unsigned) cfg->x_last_basic_block >= old_len)
6211     {
6212       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
6213       VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
6214                              new_len);
6215     }
6216
6217   VEC_replace (basic_block, cfg->x_basic_block_info,
6218                bb->index, bb);
6219
6220   /* Remap the variables in phi nodes.  */
6221   for (si = gsi_start_phis (bb); !gsi_end_p (si); )
6222     {
6223       gimple phi = gsi_stmt (si);
6224       use_operand_p use;
6225       tree op = PHI_RESULT (phi);
6226       ssa_op_iter oi;
6227
6228       if (!is_gimple_reg (op))
6229         {
6230           /* Remove the phi nodes for virtual operands (alias analysis will be
6231              run for the new function, anyway).  */
6232           remove_phi_node (&si, true);
6233           continue;
6234         }
6235
6236       SET_PHI_RESULT (phi,
6237                       replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6238       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
6239         {
6240           op = USE_FROM_PTR (use);
6241           if (TREE_CODE (op) == SSA_NAME)
6242             SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6243         }
6244
6245       gsi_next (&si);
6246     }
6247
6248   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6249     {
6250       gimple stmt = gsi_stmt (si);
6251       struct walk_stmt_info wi;
6252
6253       memset (&wi, 0, sizeof (wi));
6254       wi.info = d;
6255       walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
6256
6257       if (gimple_code (stmt) == GIMPLE_LABEL)
6258         {
6259           tree label = gimple_label_label (stmt);
6260           int uid = LABEL_DECL_UID (label);
6261
6262           gcc_assert (uid > -1);
6263
6264           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
6265           if (old_len <= (unsigned) uid)
6266             {
6267               new_len = 3 * uid / 2 + 1;
6268               VEC_safe_grow_cleared (basic_block, gc,
6269                                      cfg->x_label_to_block_map, new_len);
6270             }
6271
6272           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
6273           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
6274
6275           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
6276
6277           if (uid >= dest_cfun->cfg->last_label_uid)
6278             dest_cfun->cfg->last_label_uid = uid + 1;
6279         }
6280
6281       maybe_duplicate_eh_stmt_fn (dest_cfun, stmt, cfun, stmt, d->eh_map, 0);
6282       remove_stmt_from_eh_lp_fn (cfun, stmt);
6283
6284       gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
6285       gimple_remove_stmt_histograms (cfun, stmt);
6286
6287       /* We cannot leave any operands allocated from the operand caches of
6288          the current function.  */
6289       free_stmt_operands (stmt);
6290       push_cfun (dest_cfun);
6291       update_stmt (stmt);
6292       pop_cfun ();
6293     }
6294
6295   FOR_EACH_EDGE (e, ei, bb->succs)
6296     if (e->goto_locus)
6297       {
6298         tree block = e->goto_block;
6299         if (d->orig_block == NULL_TREE
6300             || block == d->orig_block)
6301           e->goto_block = d->new_block;
6302 #ifdef ENABLE_CHECKING
6303         else if (block != d->new_block)
6304           {
6305             while (block && block != d->orig_block)
6306               block = BLOCK_SUPERCONTEXT (block);
6307             gcc_assert (block);
6308           }
6309 #endif
6310       }
6311 }
6312
6313 /* Examine the statements in BB (which is in SRC_CFUN); find and return
6314    the outermost EH region.  Use REGION as the incoming base EH region.  */
6315
6316 static eh_region
6317 find_outermost_region_in_block (struct function *src_cfun,
6318                                 basic_block bb, eh_region region)
6319 {
6320   gimple_stmt_iterator si;
6321
6322   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6323     {
6324       gimple stmt = gsi_stmt (si);
6325       eh_region stmt_region;
6326       int lp_nr;
6327
6328       lp_nr = lookup_stmt_eh_lp_fn (src_cfun, stmt);
6329       stmt_region = get_eh_region_from_lp_number_fn (src_cfun, lp_nr);
6330       if (stmt_region)
6331         {
6332           if (region == NULL)
6333             region = stmt_region;
6334           else if (stmt_region != region)
6335             {
6336               region = eh_region_outermost (src_cfun, stmt_region, region);
6337               gcc_assert (region != NULL);
6338             }
6339         }
6340     }
6341
6342   return region;
6343 }
6344
6345 static tree
6346 new_label_mapper (tree decl, void *data)
6347 {
6348   htab_t hash = (htab_t) data;
6349   struct tree_map *m;
6350   void **slot;
6351
6352   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
6353
6354   m = XNEW (struct tree_map);
6355   m->hash = DECL_UID (decl);
6356   m->base.from = decl;
6357   m->to = create_artificial_label (UNKNOWN_LOCATION);
6358   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
6359   if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
6360     cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
6361
6362   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
6363   gcc_assert (*slot == NULL);
6364
6365   *slot = m;
6366
6367   return m->to;
6368 }
6369
6370 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
6371    subblocks.  */
6372
6373 static void
6374 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map,
6375                                   tree to_context)
6376 {
6377   tree *tp, t;
6378
6379   for (tp = &BLOCK_VARS (block); *tp; tp = &DECL_CHAIN (*tp))
6380     {
6381       t = *tp;
6382       if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL)
6383         continue;
6384       replace_by_duplicate_decl (&t, vars_map, to_context);
6385       if (t != *tp)
6386         {
6387           if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
6388             {
6389               SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
6390               DECL_HAS_VALUE_EXPR_P (t) = 1;
6391             }
6392           DECL_CHAIN (t) = DECL_CHAIN (*tp);
6393           *tp = t;
6394         }
6395     }
6396
6397   for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
6398     replace_block_vars_by_duplicates (block, vars_map, to_context);
6399 }
6400
6401 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
6402    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
6403    single basic block in the original CFG and the new basic block is
6404    returned.  DEST_CFUN must not have a CFG yet.
6405
6406    Note that the region need not be a pure SESE region.  Blocks inside
6407    the region may contain calls to abort/exit.  The only restriction
6408    is that ENTRY_BB should be the only entry point and it must
6409    dominate EXIT_BB.
6410
6411    Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
6412    functions outermost BLOCK, move all subblocks of ORIG_BLOCK
6413    to the new function.
6414
6415    All local variables referenced in the region are assumed to be in
6416    the corresponding BLOCK_VARS and unexpanded variable lists
6417    associated with DEST_CFUN.  */
6418
6419 basic_block
6420 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
6421                         basic_block exit_bb, tree orig_block)
6422 {
6423   VEC(basic_block,heap) *bbs, *dom_bbs;
6424   basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
6425   basic_block after, bb, *entry_pred, *exit_succ, abb;
6426   struct function *saved_cfun = cfun;
6427   int *entry_flag, *exit_flag;
6428   unsigned *entry_prob, *exit_prob;
6429   unsigned i, num_entry_edges, num_exit_edges;
6430   edge e;
6431   edge_iterator ei;
6432   htab_t new_label_map;
6433   struct pointer_map_t *vars_map, *eh_map;
6434   struct loop *loop = entry_bb->loop_father;
6435   struct move_stmt_d d;
6436
6437   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
6438      region.  */
6439   gcc_assert (entry_bb != exit_bb
6440               && (!exit_bb
6441                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
6442
6443   /* Collect all the blocks in the region.  Manually add ENTRY_BB
6444      because it won't be added by dfs_enumerate_from.  */
6445   bbs = NULL;
6446   VEC_safe_push (basic_block, heap, bbs, entry_bb);
6447   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
6448
6449   /* The blocks that used to be dominated by something in BBS will now be
6450      dominated by the new block.  */
6451   dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
6452                                      VEC_address (basic_block, bbs),
6453                                      VEC_length (basic_block, bbs));
6454
6455   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
6456      the predecessor edges to ENTRY_BB and the successor edges to
6457      EXIT_BB so that we can re-attach them to the new basic block that
6458      will replace the region.  */
6459   num_entry_edges = EDGE_COUNT (entry_bb->preds);
6460   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
6461   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
6462   entry_prob = XNEWVEC (unsigned, num_entry_edges);
6463   i = 0;
6464   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
6465     {
6466       entry_prob[i] = e->probability;
6467       entry_flag[i] = e->flags;
6468       entry_pred[i++] = e->src;
6469       remove_edge (e);
6470     }
6471
6472   if (exit_bb)
6473     {
6474       num_exit_edges = EDGE_COUNT (exit_bb->succs);
6475       exit_succ = (basic_block *) xcalloc (num_exit_edges,
6476                                            sizeof (basic_block));
6477       exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
6478       exit_prob = XNEWVEC (unsigned, num_exit_edges);
6479       i = 0;
6480       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6481         {
6482           exit_prob[i] = e->probability;
6483           exit_flag[i] = e->flags;
6484           exit_succ[i++] = e->dest;
6485           remove_edge (e);
6486         }
6487     }
6488   else
6489     {
6490       num_exit_edges = 0;
6491       exit_succ = NULL;
6492       exit_flag = NULL;
6493       exit_prob = NULL;
6494     }
6495
6496   /* Switch context to the child function to initialize DEST_FN's CFG.  */
6497   gcc_assert (dest_cfun->cfg == NULL);
6498   push_cfun (dest_cfun);
6499
6500   init_empty_tree_cfg ();
6501
6502   /* Initialize EH information for the new function.  */
6503   eh_map = NULL;
6504   new_label_map = NULL;
6505   if (saved_cfun->eh)
6506     {
6507       eh_region region = NULL;
6508
6509       FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
6510         region = find_outermost_region_in_block (saved_cfun, bb, region);
6511
6512       init_eh_for_function ();
6513       if (region != NULL)
6514         {
6515           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6516           eh_map = duplicate_eh_regions (saved_cfun, region, 0,
6517                                          new_label_mapper, new_label_map);
6518         }
6519     }
6520
6521   pop_cfun ();
6522
6523   /* Move blocks from BBS into DEST_CFUN.  */
6524   gcc_assert (VEC_length (basic_block, bbs) >= 2);
6525   after = dest_cfun->cfg->x_entry_block_ptr;
6526   vars_map = pointer_map_create ();
6527
6528   memset (&d, 0, sizeof (d));
6529   d.orig_block = orig_block;
6530   d.new_block = DECL_INITIAL (dest_cfun->decl);
6531   d.from_context = cfun->decl;
6532   d.to_context = dest_cfun->decl;
6533   d.vars_map = vars_map;
6534   d.new_label_map = new_label_map;
6535   d.eh_map = eh_map;
6536   d.remap_decls_p = true;
6537
6538   FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
6539     {
6540       /* No need to update edge counts on the last block.  It has
6541          already been updated earlier when we detached the region from
6542          the original CFG.  */
6543       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d);
6544       after = bb;
6545     }
6546
6547   /* Rewire BLOCK_SUBBLOCKS of orig_block.  */
6548   if (orig_block)
6549     {
6550       tree block;
6551       gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6552                   == NULL_TREE);
6553       BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6554         = BLOCK_SUBBLOCKS (orig_block);
6555       for (block = BLOCK_SUBBLOCKS (orig_block);
6556            block; block = BLOCK_CHAIN (block))
6557         BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
6558       BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
6559     }
6560
6561   replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
6562                                     vars_map, dest_cfun->decl);
6563
6564   if (new_label_map)
6565     htab_delete (new_label_map);
6566   if (eh_map)
6567     pointer_map_destroy (eh_map);
6568   pointer_map_destroy (vars_map);
6569
6570   /* Rewire the entry and exit blocks.  The successor to the entry
6571      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6572      the child function.  Similarly, the predecessor of DEST_FN's
6573      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
6574      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6575      various CFG manipulation function get to the right CFG.
6576
6577      FIXME, this is silly.  The CFG ought to become a parameter to
6578      these helpers.  */
6579   push_cfun (dest_cfun);
6580   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6581   if (exit_bb)
6582     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
6583   pop_cfun ();
6584
6585   /* Back in the original function, the SESE region has disappeared,
6586      create a new basic block in its place.  */
6587   bb = create_empty_bb (entry_pred[0]);
6588   if (current_loops)
6589     add_bb_to_loop (bb, loop);
6590   for (i = 0; i < num_entry_edges; i++)
6591     {
6592       e = make_edge (entry_pred[i], bb, entry_flag[i]);
6593       e->probability = entry_prob[i];
6594     }
6595
6596   for (i = 0; i < num_exit_edges; i++)
6597     {
6598       e = make_edge (bb, exit_succ[i], exit_flag[i]);
6599       e->probability = exit_prob[i];
6600     }
6601
6602   set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6603   FOR_EACH_VEC_ELT (basic_block, dom_bbs, i, abb)
6604     set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6605   VEC_free (basic_block, heap, dom_bbs);
6606
6607   if (exit_bb)
6608     {
6609       free (exit_prob);
6610       free (exit_flag);
6611       free (exit_succ);
6612     }
6613   free (entry_prob);
6614   free (entry_flag);
6615   free (entry_pred);
6616   VEC_free (basic_block, heap, bbs);
6617
6618   return bb;
6619 }
6620
6621
6622 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree-pass.h)
6623    */
6624
6625 void
6626 dump_function_to_file (tree fn, FILE *file, int flags)
6627 {
6628   tree arg, var;
6629   struct function *dsf;
6630   bool ignore_topmost_bind = false, any_var = false;
6631   basic_block bb;
6632   tree chain;
6633   bool tmclone = TREE_CODE (fn) == FUNCTION_DECL && decl_is_tm_clone (fn);
6634
6635   fprintf (file, "%s %s(", current_function_name (),
6636            tmclone ? "[tm-clone] " : "");
6637
6638   arg = DECL_ARGUMENTS (fn);
6639   while (arg)
6640     {
6641       print_generic_expr (file, TREE_TYPE (arg), dump_flags);
6642       fprintf (file, " ");
6643       print_generic_expr (file, arg, dump_flags);
6644       if (flags & TDF_VERBOSE)
6645         print_node (file, "", arg, 4);
6646       if (DECL_CHAIN (arg))
6647         fprintf (file, ", ");
6648       arg = DECL_CHAIN (arg);
6649     }
6650   fprintf (file, ")\n");
6651
6652   if (flags & TDF_VERBOSE)
6653     print_node (file, "", fn, 2);
6654
6655   dsf = DECL_STRUCT_FUNCTION (fn);
6656   if (dsf && (flags & TDF_EH))
6657     dump_eh_tree (file, dsf);
6658
6659   if (flags & TDF_RAW && !gimple_has_body_p (fn))
6660     {
6661       dump_node (fn, TDF_SLIM | flags, file);
6662       return;
6663     }
6664
6665   /* Switch CFUN to point to FN.  */
6666   push_cfun (DECL_STRUCT_FUNCTION (fn));
6667
6668   /* When GIMPLE is lowered, the variables are no longer available in
6669      BIND_EXPRs, so display them separately.  */
6670   if (cfun && cfun->decl == fn && !VEC_empty (tree, cfun->local_decls))
6671     {
6672       unsigned ix;
6673       ignore_topmost_bind = true;
6674
6675       fprintf (file, "{\n");
6676       FOR_EACH_LOCAL_DECL (cfun, ix, var)
6677         {
6678           print_generic_decl (file, var, flags);
6679           if (flags & TDF_VERBOSE)
6680             print_node (file, "", var, 4);
6681           fprintf (file, "\n");
6682
6683           any_var = true;
6684         }
6685     }
6686
6687   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
6688     {
6689       /* If the CFG has been built, emit a CFG-based dump.  */
6690       check_bb_profile (ENTRY_BLOCK_PTR, file);
6691       if (!ignore_topmost_bind)
6692         fprintf (file, "{\n");
6693
6694       if (any_var && n_basic_blocks)
6695         fprintf (file, "\n");
6696
6697       FOR_EACH_BB (bb)
6698         gimple_dump_bb (file, bb, 2, flags);
6699
6700       fprintf (file, "}\n");
6701       check_bb_profile (EXIT_BLOCK_PTR, file);
6702     }
6703   else if (DECL_SAVED_TREE (fn) == NULL)
6704     {
6705       /* The function is now in GIMPLE form but the CFG has not been
6706          built yet.  Emit the single sequence of GIMPLE statements
6707          that make up its body.  */
6708       gimple_seq body = gimple_body (fn);
6709
6710       if (gimple_seq_first_stmt (body)
6711           && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
6712           && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
6713         print_gimple_seq (file, body, 0, flags);
6714       else
6715         {
6716           if (!ignore_topmost_bind)
6717             fprintf (file, "{\n");
6718
6719           if (any_var)
6720             fprintf (file, "\n");
6721
6722           print_gimple_seq (file, body, 2, flags);
6723           fprintf (file, "}\n");
6724         }
6725     }
6726   else
6727     {
6728       int indent;
6729
6730       /* Make a tree based dump.  */
6731       chain = DECL_SAVED_TREE (fn);
6732
6733       if (chain && TREE_CODE (chain) == BIND_EXPR)
6734         {
6735           if (ignore_topmost_bind)
6736             {
6737               chain = BIND_EXPR_BODY (chain);
6738               indent = 2;
6739             }
6740           else
6741             indent = 0;
6742         }
6743       else
6744         {
6745           if (!ignore_topmost_bind)
6746             fprintf (file, "{\n");
6747           indent = 2;
6748         }
6749
6750       if (any_var)
6751         fprintf (file, "\n");
6752
6753       print_generic_stmt_indented (file, chain, flags, indent);
6754       if (ignore_topmost_bind)
6755         fprintf (file, "}\n");
6756     }
6757
6758   if (flags & TDF_ENUMERATE_LOCALS)
6759     dump_enumerated_decls (file, flags);
6760   fprintf (file, "\n\n");
6761
6762   /* Restore CFUN.  */
6763   pop_cfun ();
6764 }
6765
6766
6767 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
6768
6769 DEBUG_FUNCTION void
6770 debug_function (tree fn, int flags)
6771 {
6772   dump_function_to_file (fn, stderr, flags);
6773 }
6774
6775
6776 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
6777
6778 static void
6779 print_pred_bbs (FILE *file, basic_block bb)
6780 {
6781   edge e;
6782   edge_iterator ei;
6783
6784   FOR_EACH_EDGE (e, ei, bb->preds)
6785     fprintf (file, "bb_%d ", e->src->index);
6786 }
6787
6788
6789 /* Print on FILE the indexes for the successors of basic_block BB.  */
6790
6791 static void
6792 print_succ_bbs (FILE *file, basic_block bb)
6793 {
6794   edge e;
6795   edge_iterator ei;
6796
6797   FOR_EACH_EDGE (e, ei, bb->succs)
6798     fprintf (file, "bb_%d ", e->dest->index);
6799 }
6800
6801 /* Print to FILE the basic block BB following the VERBOSITY level.  */
6802
6803 void
6804 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6805 {
6806   char *s_indent = (char *) alloca ((size_t) indent + 1);
6807   memset ((void *) s_indent, ' ', (size_t) indent);
6808   s_indent[indent] = '\0';
6809
6810   /* Print basic_block's header.  */
6811   if (verbosity >= 2)
6812     {
6813       fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
6814       print_pred_bbs (file, bb);
6815       fprintf (file, "}, succs = {");
6816       print_succ_bbs (file, bb);
6817       fprintf (file, "})\n");
6818     }
6819
6820   /* Print basic_block's body.  */
6821   if (verbosity >= 3)
6822     {
6823       fprintf (file, "%s  {\n", s_indent);
6824       gimple_dump_bb (file, bb, indent + 4, TDF_VOPS|TDF_MEMSYMS);
6825       fprintf (file, "%s  }\n", s_indent);
6826     }
6827 }
6828
6829 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6830
6831 /* Pretty print LOOP on FILE, indented INDENT spaces.  Following
6832    VERBOSITY level this outputs the contents of the loop, or just its
6833    structure.  */
6834
6835 static void
6836 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6837 {
6838   char *s_indent;
6839   basic_block bb;
6840
6841   if (loop == NULL)
6842     return;
6843
6844   s_indent = (char *) alloca ((size_t) indent + 1);
6845   memset ((void *) s_indent, ' ', (size_t) indent);
6846   s_indent[indent] = '\0';
6847
6848   /* Print loop's header.  */
6849   fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent,
6850            loop->num, loop->header->index, loop->latch->index);
6851   fprintf (file, ", niter = ");
6852   print_generic_expr (file, loop->nb_iterations, 0);
6853
6854   if (loop->any_upper_bound)
6855     {
6856       fprintf (file, ", upper_bound = ");
6857       dump_double_int (file, loop->nb_iterations_upper_bound, true);
6858     }
6859
6860   if (loop->any_estimate)
6861     {
6862       fprintf (file, ", estimate = ");
6863       dump_double_int (file, loop->nb_iterations_estimate, true);
6864     }
6865   fprintf (file, ")\n");
6866
6867   /* Print loop's body.  */
6868   if (verbosity >= 1)
6869     {
6870       fprintf (file, "%s{\n", s_indent);
6871       FOR_EACH_BB (bb)
6872         if (bb->loop_father == loop)
6873           print_loops_bb (file, bb, indent, verbosity);
6874
6875       print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
6876       fprintf (file, "%s}\n", s_indent);
6877     }
6878 }
6879
6880 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6881    spaces.  Following VERBOSITY level this outputs the contents of the
6882    loop, or just its structure.  */
6883
6884 static void
6885 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
6886 {
6887   if (loop == NULL)
6888     return;
6889
6890   print_loop (file, loop, indent, verbosity);
6891   print_loop_and_siblings (file, loop->next, indent, verbosity);
6892 }
6893
6894 /* Follow a CFG edge from the entry point of the program, and on entry
6895    of a loop, pretty print the loop structure on FILE.  */
6896
6897 void
6898 print_loops (FILE *file, int verbosity)
6899 {
6900   basic_block bb;
6901
6902   bb = ENTRY_BLOCK_PTR;
6903   if (bb && bb->loop_father)
6904     print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
6905 }
6906
6907
6908 /* Debugging loops structure at tree level, at some VERBOSITY level.  */
6909
6910 DEBUG_FUNCTION void
6911 debug_loops (int verbosity)
6912 {
6913   print_loops (stderr, verbosity);
6914 }
6915
6916 /* Print on stderr the code of LOOP, at some VERBOSITY level.  */
6917
6918 DEBUG_FUNCTION void
6919 debug_loop (struct loop *loop, int verbosity)
6920 {
6921   print_loop (stderr, loop, 0, verbosity);
6922 }
6923
6924 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6925    level.  */
6926
6927 DEBUG_FUNCTION void
6928 debug_loop_num (unsigned num, int verbosity)
6929 {
6930   debug_loop (get_loop (num), verbosity);
6931 }
6932
6933 /* Return true if BB ends with a call, possibly followed by some
6934    instructions that must stay with the call.  Return false,
6935    otherwise.  */
6936
6937 static bool
6938 gimple_block_ends_with_call_p (basic_block bb)
6939 {
6940   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
6941   return !gsi_end_p (gsi) && is_gimple_call (gsi_stmt (gsi));
6942 }
6943
6944
6945 /* Return true if BB ends with a conditional branch.  Return false,
6946    otherwise.  */
6947
6948 static bool
6949 gimple_block_ends_with_condjump_p (const_basic_block bb)
6950 {
6951   gimple stmt = last_stmt (CONST_CAST_BB (bb));
6952   return (stmt && gimple_code (stmt) == GIMPLE_COND);
6953 }
6954
6955
6956 /* Return true if we need to add fake edge to exit at statement T.
6957    Helper function for gimple_flow_call_edges_add.  */
6958
6959 static bool
6960 need_fake_edge_p (gimple t)
6961 {
6962   tree fndecl = NULL_TREE;
6963   int call_flags = 0;
6964
6965   /* NORETURN and LONGJMP calls already have an edge to exit.
6966      CONST and PURE calls do not need one.
6967      We don't currently check for CONST and PURE here, although
6968      it would be a good idea, because those attributes are
6969      figured out from the RTL in mark_constant_function, and
6970      the counter incrementation code from -fprofile-arcs
6971      leads to different results from -fbranch-probabilities.  */
6972   if (is_gimple_call (t))
6973     {
6974       fndecl = gimple_call_fndecl (t);
6975       call_flags = gimple_call_flags (t);
6976     }
6977
6978   if (is_gimple_call (t)
6979       && fndecl
6980       && DECL_BUILT_IN (fndecl)
6981       && (call_flags & ECF_NOTHROW)
6982       && !(call_flags & ECF_RETURNS_TWICE)
6983       /* fork() doesn't really return twice, but the effect of
6984          wrapping it in __gcov_fork() which calls __gcov_flush()
6985          and clears the counters before forking has the same
6986          effect as returning twice.  Force a fake edge.  */
6987       && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
6988            && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK))
6989     return false;
6990
6991   if (is_gimple_call (t))
6992     {
6993       edge_iterator ei;
6994       edge e;
6995       basic_block bb;
6996
6997       if (!(call_flags & ECF_NORETURN))
6998         return true;
6999
7000       bb = gimple_bb (t);
7001       FOR_EACH_EDGE (e, ei, bb->succs)
7002         if ((e->flags & EDGE_FAKE) == 0)
7003           return true;
7004     }
7005
7006   if (gimple_code (t) == GIMPLE_ASM
7007        && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
7008     return true;
7009
7010   return false;
7011 }
7012
7013
7014 /* Add fake edges to the function exit for any non constant and non
7015    noreturn calls (or noreturn calls with EH/abnormal edges),
7016    volatile inline assembly in the bitmap of blocks specified by BLOCKS
7017    or to the whole CFG if BLOCKS is zero.  Return the number of blocks
7018    that were split.
7019
7020    The goal is to expose cases in which entering a basic block does
7021    not imply that all subsequent instructions must be executed.  */
7022
7023 static int
7024 gimple_flow_call_edges_add (sbitmap blocks)
7025 {
7026   int i;
7027   int blocks_split = 0;
7028   int last_bb = last_basic_block;
7029   bool check_last_block = false;
7030
7031   if (n_basic_blocks == NUM_FIXED_BLOCKS)
7032     return 0;
7033
7034   if (! blocks)
7035     check_last_block = true;
7036   else
7037     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
7038
7039   /* In the last basic block, before epilogue generation, there will be
7040      a fallthru edge to EXIT.  Special care is required if the last insn
7041      of the last basic block is a call because make_edge folds duplicate
7042      edges, which would result in the fallthru edge also being marked
7043      fake, which would result in the fallthru edge being removed by
7044      remove_fake_edges, which would result in an invalid CFG.
7045
7046      Moreover, we can't elide the outgoing fake edge, since the block
7047      profiler needs to take this into account in order to solve the minimal
7048      spanning tree in the case that the call doesn't return.
7049
7050      Handle this by adding a dummy instruction in a new last basic block.  */
7051   if (check_last_block)
7052     {
7053       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
7054       gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
7055       gimple t = NULL;
7056
7057       if (!gsi_end_p (gsi))
7058         t = gsi_stmt (gsi);
7059
7060       if (t && need_fake_edge_p (t))
7061         {
7062           edge e;
7063
7064           e = find_edge (bb, EXIT_BLOCK_PTR);
7065           if (e)
7066             {
7067               gsi_insert_on_edge (e, gimple_build_nop ());
7068               gsi_commit_edge_inserts ();
7069             }
7070         }
7071     }
7072
7073   /* Now add fake edges to the function exit for any non constant
7074      calls since there is no way that we can determine if they will
7075      return or not...  */
7076   for (i = 0; i < last_bb; i++)
7077     {
7078       basic_block bb = BASIC_BLOCK (i);
7079       gimple_stmt_iterator gsi;
7080       gimple stmt, last_stmt;
7081
7082       if (!bb)
7083         continue;
7084
7085       if (blocks && !TEST_BIT (blocks, i))
7086         continue;
7087
7088       gsi = gsi_last_nondebug_bb (bb);
7089       if (!gsi_end_p (gsi))
7090         {
7091           last_stmt = gsi_stmt (gsi);
7092           do
7093             {
7094               stmt = gsi_stmt (gsi);
7095               if (need_fake_edge_p (stmt))
7096                 {
7097                   edge e;
7098
7099                   /* The handling above of the final block before the
7100                      epilogue should be enough to verify that there is
7101                      no edge to the exit block in CFG already.
7102                      Calling make_edge in such case would cause us to
7103                      mark that edge as fake and remove it later.  */
7104 #ifdef ENABLE_CHECKING
7105                   if (stmt == last_stmt)
7106                     {
7107                       e = find_edge (bb, EXIT_BLOCK_PTR);
7108                       gcc_assert (e == NULL);
7109                     }
7110 #endif
7111
7112                   /* Note that the following may create a new basic block
7113                      and renumber the existing basic blocks.  */
7114                   if (stmt != last_stmt)
7115                     {
7116                       e = split_block (bb, stmt);
7117                       if (e)
7118                         blocks_split++;
7119                     }
7120                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
7121                 }
7122               gsi_prev (&gsi);
7123             }
7124           while (!gsi_end_p (gsi));
7125         }
7126     }
7127
7128   if (blocks_split)
7129     verify_flow_info ();
7130
7131   return blocks_split;
7132 }
7133
7134 /* Removes edge E and all the blocks dominated by it, and updates dominance
7135    information.  The IL in E->src needs to be updated separately.
7136    If dominance info is not available, only the edge E is removed.*/
7137
7138 void
7139 remove_edge_and_dominated_blocks (edge e)
7140 {
7141   VEC (basic_block, heap) *bbs_to_remove = NULL;
7142   VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
7143   bitmap df, df_idom;
7144   edge f;
7145   edge_iterator ei;
7146   bool none_removed = false;
7147   unsigned i;
7148   basic_block bb, dbb;
7149   bitmap_iterator bi;
7150
7151   if (!dom_info_available_p (CDI_DOMINATORS))
7152     {
7153       remove_edge (e);
7154       return;
7155     }
7156
7157   /* No updating is needed for edges to exit.  */
7158   if (e->dest == EXIT_BLOCK_PTR)
7159     {
7160       if (cfgcleanup_altered_bbs)
7161         bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7162       remove_edge (e);
7163       return;
7164     }
7165
7166   /* First, we find the basic blocks to remove.  If E->dest has a predecessor
7167      that is not dominated by E->dest, then this set is empty.  Otherwise,
7168      all the basic blocks dominated by E->dest are removed.
7169
7170      Also, to DF_IDOM we store the immediate dominators of the blocks in
7171      the dominance frontier of E (i.e., of the successors of the
7172      removed blocks, if there are any, and of E->dest otherwise).  */
7173   FOR_EACH_EDGE (f, ei, e->dest->preds)
7174     {
7175       if (f == e)
7176         continue;
7177
7178       if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
7179         {
7180           none_removed = true;
7181           break;
7182         }
7183     }
7184
7185   df = BITMAP_ALLOC (NULL);
7186   df_idom = BITMAP_ALLOC (NULL);
7187
7188   if (none_removed)
7189     bitmap_set_bit (df_idom,
7190                     get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
7191   else
7192     {
7193       bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest);
7194       FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb)
7195         {
7196           FOR_EACH_EDGE (f, ei, bb->succs)
7197             {
7198               if (f->dest != EXIT_BLOCK_PTR)
7199                 bitmap_set_bit (df, f->dest->index);
7200             }
7201         }
7202       FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb)
7203         bitmap_clear_bit (df, bb->index);
7204
7205       EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
7206         {
7207           bb = BASIC_BLOCK (i);
7208           bitmap_set_bit (df_idom,
7209                           get_immediate_dominator (CDI_DOMINATORS, bb)->index);
7210         }
7211     }
7212
7213   if (cfgcleanup_altered_bbs)
7214     {
7215       /* Record the set of the altered basic blocks.  */
7216       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7217       bitmap_ior_into (cfgcleanup_altered_bbs, df);
7218     }
7219
7220   /* Remove E and the cancelled blocks.  */
7221   if (none_removed)
7222     remove_edge (e);
7223   else
7224     {
7225       /* Walk backwards so as to get a chance to substitute all
7226          released DEFs into debug stmts.  See
7227          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
7228          details.  */
7229       for (i = VEC_length (basic_block, bbs_to_remove); i-- > 0; )
7230         delete_basic_block (VEC_index (basic_block, bbs_to_remove, i));
7231     }
7232
7233   /* Update the dominance information.  The immediate dominator may change only
7234      for blocks whose immediate dominator belongs to DF_IDOM:
7235
7236      Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
7237      removal.  Let Z the arbitrary block such that idom(Z) = Y and
7238      Z dominates X after the removal.  Before removal, there exists a path P
7239      from Y to X that avoids Z.  Let F be the last edge on P that is
7240      removed, and let W = F->dest.  Before removal, idom(W) = Y (since Y
7241      dominates W, and because of P, Z does not dominate W), and W belongs to
7242      the dominance frontier of E.  Therefore, Y belongs to DF_IDOM.  */
7243   EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
7244     {
7245       bb = BASIC_BLOCK (i);
7246       for (dbb = first_dom_son (CDI_DOMINATORS, bb);
7247            dbb;
7248            dbb = next_dom_son (CDI_DOMINATORS, dbb))
7249         VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
7250     }
7251
7252   iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
7253
7254   BITMAP_FREE (df);
7255   BITMAP_FREE (df_idom);
7256   VEC_free (basic_block, heap, bbs_to_remove);
7257   VEC_free (basic_block, heap, bbs_to_fix_dom);
7258 }
7259
7260 /* Purge dead EH edges from basic block BB.  */
7261
7262 bool
7263 gimple_purge_dead_eh_edges (basic_block bb)
7264 {
7265   bool changed = false;
7266   edge e;
7267   edge_iterator ei;
7268   gimple stmt = last_stmt (bb);
7269
7270   if (stmt && stmt_can_throw_internal (stmt))
7271     return false;
7272
7273   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7274     {
7275       if (e->flags & EDGE_EH)
7276         {
7277           remove_edge_and_dominated_blocks (e);
7278           changed = true;
7279         }
7280       else
7281         ei_next (&ei);
7282     }
7283
7284   return changed;
7285 }
7286
7287 /* Purge dead EH edges from basic block listed in BLOCKS.  */
7288
7289 bool
7290 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
7291 {
7292   bool changed = false;
7293   unsigned i;
7294   bitmap_iterator bi;
7295
7296   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7297     {
7298       basic_block bb = BASIC_BLOCK (i);
7299
7300       /* Earlier gimple_purge_dead_eh_edges could have removed
7301          this basic block already.  */
7302       gcc_assert (bb || changed);
7303       if (bb != NULL)
7304         changed |= gimple_purge_dead_eh_edges (bb);
7305     }
7306
7307   return changed;
7308 }
7309
7310 /* Purge dead abnormal call edges from basic block BB.  */
7311
7312 bool
7313 gimple_purge_dead_abnormal_call_edges (basic_block bb)
7314 {
7315   bool changed = false;
7316   edge e;
7317   edge_iterator ei;
7318   gimple stmt = last_stmt (bb);
7319
7320   if (!cfun->has_nonlocal_label)
7321     return false;
7322
7323   if (stmt && stmt_can_make_abnormal_goto (stmt))
7324     return false;
7325
7326   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7327     {
7328       if (e->flags & EDGE_ABNORMAL)
7329         {
7330           remove_edge_and_dominated_blocks (e);
7331           changed = true;
7332         }
7333       else
7334         ei_next (&ei);
7335     }
7336
7337   return changed;
7338 }
7339
7340 /* Purge dead abnormal call edges from basic block listed in BLOCKS.  */
7341
7342 bool
7343 gimple_purge_all_dead_abnormal_call_edges (const_bitmap blocks)
7344 {
7345   bool changed = false;
7346   unsigned i;
7347   bitmap_iterator bi;
7348
7349   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7350     {
7351       basic_block bb = BASIC_BLOCK (i);
7352
7353       /* Earlier gimple_purge_dead_abnormal_call_edges could have removed
7354          this basic block already.  */
7355       gcc_assert (bb || changed);
7356       if (bb != NULL)
7357         changed |= gimple_purge_dead_abnormal_call_edges (bb);
7358     }
7359
7360   return changed;
7361 }
7362
7363 /* This function is called whenever a new edge is created or
7364    redirected.  */
7365
7366 static void
7367 gimple_execute_on_growing_pred (edge e)
7368 {
7369   basic_block bb = e->dest;
7370
7371   if (!gimple_seq_empty_p (phi_nodes (bb)))
7372     reserve_phi_args_for_new_edge (bb);
7373 }
7374
7375 /* This function is called immediately before edge E is removed from
7376    the edge vector E->dest->preds.  */
7377
7378 static void
7379 gimple_execute_on_shrinking_pred (edge e)
7380 {
7381   if (!gimple_seq_empty_p (phi_nodes (e->dest)))
7382     remove_phi_args (e);
7383 }
7384
7385 /*---------------------------------------------------------------------------
7386   Helper functions for Loop versioning
7387   ---------------------------------------------------------------------------*/
7388
7389 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
7390    of 'first'. Both of them are dominated by 'new_head' basic block. When
7391    'new_head' was created by 'second's incoming edge it received phi arguments
7392    on the edge by split_edge(). Later, additional edge 'e' was created to
7393    connect 'new_head' and 'first'. Now this routine adds phi args on this
7394    additional edge 'e' that new_head to second edge received as part of edge
7395    splitting.  */
7396
7397 static void
7398 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
7399                                   basic_block new_head, edge e)
7400 {
7401   gimple phi1, phi2;
7402   gimple_stmt_iterator psi1, psi2;
7403   tree def;
7404   edge e2 = find_edge (new_head, second);
7405
7406   /* Because NEW_HEAD has been created by splitting SECOND's incoming
7407      edge, we should always have an edge from NEW_HEAD to SECOND.  */
7408   gcc_assert (e2 != NULL);
7409
7410   /* Browse all 'second' basic block phi nodes and add phi args to
7411      edge 'e' for 'first' head. PHI args are always in correct order.  */
7412
7413   for (psi2 = gsi_start_phis (second),
7414        psi1 = gsi_start_phis (first);
7415        !gsi_end_p (psi2) && !gsi_end_p (psi1);
7416        gsi_next (&psi2),  gsi_next (&psi1))
7417     {
7418       phi1 = gsi_stmt (psi1);
7419       phi2 = gsi_stmt (psi2);
7420       def = PHI_ARG_DEF (phi2, e2->dest_idx);
7421       add_phi_arg (phi1, def, e, gimple_phi_arg_location_from_edge (phi2, e2));
7422     }
7423 }
7424
7425
7426 /* Adds a if else statement to COND_BB with condition COND_EXPR.
7427    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
7428    the destination of the ELSE part.  */
7429
7430 static void
7431 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
7432                                basic_block second_head ATTRIBUTE_UNUSED,
7433                                basic_block cond_bb, void *cond_e)
7434 {
7435   gimple_stmt_iterator gsi;
7436   gimple new_cond_expr;
7437   tree cond_expr = (tree) cond_e;
7438   edge e0;
7439
7440   /* Build new conditional expr */
7441   new_cond_expr = gimple_build_cond_from_tree (cond_expr,
7442                                                NULL_TREE, NULL_TREE);
7443
7444   /* Add new cond in cond_bb.  */
7445   gsi = gsi_last_bb (cond_bb);
7446   gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
7447
7448   /* Adjust edges appropriately to connect new head with first head
7449      as well as second head.  */
7450   e0 = single_succ_edge (cond_bb);
7451   e0->flags &= ~EDGE_FALLTHRU;
7452   e0->flags |= EDGE_FALSE_VALUE;
7453 }
7454
7455 struct cfg_hooks gimple_cfg_hooks = {
7456   "gimple",
7457   gimple_verify_flow_info,
7458   gimple_dump_bb,               /* dump_bb  */
7459   create_bb,                    /* create_basic_block  */
7460   gimple_redirect_edge_and_branch, /* redirect_edge_and_branch  */
7461   gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force  */
7462   gimple_can_remove_branch_p,   /* can_remove_branch_p  */
7463   remove_bb,                    /* delete_basic_block  */
7464   gimple_split_block,           /* split_block  */
7465   gimple_move_block_after,      /* move_block_after  */
7466   gimple_can_merge_blocks_p,    /* can_merge_blocks_p  */
7467   gimple_merge_blocks,          /* merge_blocks  */
7468   gimple_predict_edge,          /* predict_edge  */
7469   gimple_predicted_by_p,        /* predicted_by_p  */
7470   gimple_can_duplicate_bb_p,    /* can_duplicate_block_p  */
7471   gimple_duplicate_bb,          /* duplicate_block  */
7472   gimple_split_edge,            /* split_edge  */
7473   gimple_make_forwarder_block,  /* make_forward_block  */
7474   NULL,                         /* tidy_fallthru_edge  */
7475   NULL,                         /* force_nonfallthru */
7476   gimple_block_ends_with_call_p,/* block_ends_with_call_p */
7477   gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
7478   gimple_flow_call_edges_add,   /* flow_call_edges_add */
7479   gimple_execute_on_growing_pred,       /* execute_on_growing_pred */
7480   gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
7481   gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
7482   gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
7483   gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
7484   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
7485   flush_pending_stmts           /* flush_pending_stmts */
7486 };
7487
7488
7489 /* Split all critical edges.  */
7490
7491 static unsigned int
7492 split_critical_edges (void)
7493 {
7494   basic_block bb;
7495   edge e;
7496   edge_iterator ei;
7497
7498   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
7499      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
7500      mappings around the calls to split_edge.  */
7501   start_recording_case_labels ();
7502   FOR_ALL_BB (bb)
7503     {
7504       FOR_EACH_EDGE (e, ei, bb->succs)
7505         {
7506           if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
7507             split_edge (e);
7508           /* PRE inserts statements to edges and expects that
7509              since split_critical_edges was done beforehand, committing edge
7510              insertions will not split more edges.  In addition to critical
7511              edges we must split edges that have multiple successors and
7512              end by control flow statements, such as RESX.
7513              Go ahead and split them too.  This matches the logic in
7514              gimple_find_edge_insert_loc.  */
7515           else if ((!single_pred_p (e->dest)
7516                     || !gimple_seq_empty_p (phi_nodes (e->dest))
7517                     || e->dest == EXIT_BLOCK_PTR)
7518                    && e->src != ENTRY_BLOCK_PTR
7519                    && !(e->flags & EDGE_ABNORMAL))
7520             {
7521               gimple_stmt_iterator gsi;
7522
7523               gsi = gsi_last_bb (e->src);
7524               if (!gsi_end_p (gsi)
7525                   && stmt_ends_bb_p (gsi_stmt (gsi))
7526                   && (gimple_code (gsi_stmt (gsi)) != GIMPLE_RETURN
7527                       && !gimple_call_builtin_p (gsi_stmt (gsi),
7528                                                  BUILT_IN_RETURN)))
7529                 split_edge (e);
7530             }
7531         }
7532     }
7533   end_recording_case_labels ();
7534   return 0;
7535 }
7536
7537 struct gimple_opt_pass pass_split_crit_edges =
7538 {
7539  {
7540   GIMPLE_PASS,
7541   "crited",                          /* name */
7542   NULL,                          /* gate */
7543   split_critical_edges,          /* execute */
7544   NULL,                          /* sub */
7545   NULL,                          /* next */
7546   0,                             /* static_pass_number */
7547   TV_TREE_SPLIT_EDGES,           /* tv_id */
7548   PROP_cfg,                      /* properties required */
7549   PROP_no_crit_edges,            /* properties_provided */
7550   0,                             /* properties_destroyed */
7551   0,                             /* todo_flags_start */
7552   TODO_verify_flow               /* todo_flags_finish */
7553  }
7554 };
7555
7556
7557 /* Build a ternary operation and gimplify it.  Emit code before GSI.
7558    Return the gimple_val holding the result.  */
7559
7560 tree
7561 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
7562                  tree type, tree a, tree b, tree c)
7563 {
7564   tree ret;
7565   location_t loc = gimple_location (gsi_stmt (*gsi));
7566
7567   ret = fold_build3_loc (loc, code, type, a, b, c);
7568   STRIP_NOPS (ret);
7569
7570   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7571                                    GSI_SAME_STMT);
7572 }
7573
7574 /* Build a binary operation and gimplify it.  Emit code before GSI.
7575    Return the gimple_val holding the result.  */
7576
7577 tree
7578 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
7579                  tree type, tree a, tree b)
7580 {
7581   tree ret;
7582
7583   ret = fold_build2_loc (gimple_location (gsi_stmt (*gsi)), code, type, a, b);
7584   STRIP_NOPS (ret);
7585
7586   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7587                                    GSI_SAME_STMT);
7588 }
7589
7590 /* Build a unary operation and gimplify it.  Emit code before GSI.
7591    Return the gimple_val holding the result.  */
7592
7593 tree
7594 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
7595                  tree a)
7596 {
7597   tree ret;
7598
7599   ret = fold_build1_loc (gimple_location (gsi_stmt (*gsi)), code, type, a);
7600   STRIP_NOPS (ret);
7601
7602   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7603                                    GSI_SAME_STMT);
7604 }
7605
7606
7607 \f
7608 /* Emit return warnings.  */
7609
7610 static unsigned int
7611 execute_warn_function_return (void)
7612 {
7613   source_location location;
7614   gimple last;
7615   edge e;
7616   edge_iterator ei;
7617
7618   /* If we have a path to EXIT, then we do return.  */
7619   if (TREE_THIS_VOLATILE (cfun->decl)
7620       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
7621     {
7622       location = UNKNOWN_LOCATION;
7623       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7624         {
7625           last = last_stmt (e->src);
7626           if ((gimple_code (last) == GIMPLE_RETURN
7627                || gimple_call_builtin_p (last, BUILT_IN_RETURN))
7628               && (location = gimple_location (last)) != UNKNOWN_LOCATION)
7629             break;
7630         }
7631       if (location == UNKNOWN_LOCATION)
7632         location = cfun->function_end_locus;
7633       warning_at (location, 0, "%<noreturn%> function does return");
7634     }
7635
7636   /* If we see "return;" in some basic block, then we do reach the end
7637      without returning a value.  */
7638   else if (warn_return_type
7639            && !TREE_NO_WARNING (cfun->decl)
7640            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
7641            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
7642     {
7643       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7644         {
7645           gimple last = last_stmt (e->src);
7646           if (gimple_code (last) == GIMPLE_RETURN
7647               && gimple_return_retval (last) == NULL
7648               && !gimple_no_warning_p (last))
7649             {
7650               location = gimple_location (last);
7651               if (location == UNKNOWN_LOCATION)
7652                   location = cfun->function_end_locus;
7653               warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
7654               TREE_NO_WARNING (cfun->decl) = 1;
7655               break;
7656             }
7657         }
7658     }
7659   return 0;
7660 }
7661
7662
7663 /* Given a basic block B which ends with a conditional and has
7664    precisely two successors, determine which of the edges is taken if
7665    the conditional is true and which is taken if the conditional is
7666    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
7667
7668 void
7669 extract_true_false_edges_from_block (basic_block b,
7670                                      edge *true_edge,
7671                                      edge *false_edge)
7672 {
7673   edge e = EDGE_SUCC (b, 0);
7674
7675   if (e->flags & EDGE_TRUE_VALUE)
7676     {
7677       *true_edge = e;
7678       *false_edge = EDGE_SUCC (b, 1);
7679     }
7680   else
7681     {
7682       *false_edge = e;
7683       *true_edge = EDGE_SUCC (b, 1);
7684     }
7685 }
7686
7687 struct gimple_opt_pass pass_warn_function_return =
7688 {
7689  {
7690   GIMPLE_PASS,
7691   "*warn_function_return",              /* name */
7692   NULL,                                 /* gate */
7693   execute_warn_function_return,         /* execute */
7694   NULL,                                 /* sub */
7695   NULL,                                 /* next */
7696   0,                                    /* static_pass_number */
7697   TV_NONE,                              /* tv_id */
7698   PROP_cfg,                             /* properties_required */
7699   0,                                    /* properties_provided */
7700   0,                                    /* properties_destroyed */
7701   0,                                    /* todo_flags_start */
7702   0                                     /* todo_flags_finish */
7703  }
7704 };
7705
7706 /* Emit noreturn warnings.  */
7707
7708 static unsigned int
7709 execute_warn_function_noreturn (void)
7710 {
7711   if (!TREE_THIS_VOLATILE (current_function_decl)
7712       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0)
7713     warn_function_noreturn (current_function_decl);
7714   return 0;
7715 }
7716
7717 static bool
7718 gate_warn_function_noreturn (void)
7719 {
7720   return warn_suggest_attribute_noreturn;
7721 }
7722
7723 struct gimple_opt_pass pass_warn_function_noreturn =
7724 {
7725  {
7726   GIMPLE_PASS,
7727   "*warn_function_noreturn",            /* name */
7728   gate_warn_function_noreturn,          /* gate */
7729   execute_warn_function_noreturn,       /* execute */
7730   NULL,                                 /* sub */
7731   NULL,                                 /* next */
7732   0,                                    /* static_pass_number */
7733   TV_NONE,                              /* tv_id */
7734   PROP_cfg,                             /* properties_required */
7735   0,                                    /* properties_provided */
7736   0,                                    /* properties_destroyed */
7737   0,                                    /* todo_flags_start */
7738   0                                     /* todo_flags_finish */
7739  }
7740 };
7741
7742
7743 /* Walk a gimplified function and warn for functions whose return value is
7744    ignored and attribute((warn_unused_result)) is set.  This is done before
7745    inlining, so we don't have to worry about that.  */
7746
7747 static void
7748 do_warn_unused_result (gimple_seq seq)
7749 {
7750   tree fdecl, ftype;
7751   gimple_stmt_iterator i;
7752
7753   for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
7754     {
7755       gimple g = gsi_stmt (i);
7756
7757       switch (gimple_code (g))
7758         {
7759         case GIMPLE_BIND:
7760           do_warn_unused_result (gimple_bind_body (g));
7761           break;
7762         case GIMPLE_TRY:
7763           do_warn_unused_result (gimple_try_eval (g));
7764           do_warn_unused_result (gimple_try_cleanup (g));
7765           break;
7766         case GIMPLE_CATCH:
7767           do_warn_unused_result (gimple_catch_handler (g));
7768           break;
7769         case GIMPLE_EH_FILTER:
7770           do_warn_unused_result (gimple_eh_filter_failure (g));
7771           break;
7772
7773         case GIMPLE_CALL:
7774           if (gimple_call_lhs (g))
7775             break;
7776           if (gimple_call_internal_p (g))
7777             break;
7778
7779           /* This is a naked call, as opposed to a GIMPLE_CALL with an
7780              LHS.  All calls whose value is ignored should be
7781              represented like this.  Look for the attribute.  */
7782           fdecl = gimple_call_fndecl (g);
7783           ftype = gimple_call_fntype (g);
7784
7785           if (lookup_attribute ("warn_unused_result", TYPE_ATTRIBUTES (ftype)))
7786             {
7787               location_t loc = gimple_location (g);
7788
7789               if (fdecl)
7790                 warning_at (loc, OPT_Wunused_result,
7791                             "ignoring return value of %qD, "
7792                             "declared with attribute warn_unused_result",
7793                             fdecl);
7794               else
7795                 warning_at (loc, OPT_Wunused_result,
7796                             "ignoring return value of function "
7797                             "declared with attribute warn_unused_result");
7798             }
7799           break;
7800
7801         default:
7802           /* Not a container, not a call, or a call whose value is used.  */
7803           break;
7804         }
7805     }
7806 }
7807
7808 static unsigned int
7809 run_warn_unused_result (void)
7810 {
7811   do_warn_unused_result (gimple_body (current_function_decl));
7812   return 0;
7813 }
7814
7815 static bool
7816 gate_warn_unused_result (void)
7817 {
7818   return flag_warn_unused_result;
7819 }
7820
7821 struct gimple_opt_pass pass_warn_unused_result =
7822 {
7823   {
7824     GIMPLE_PASS,
7825     "*warn_unused_result",              /* name */
7826     gate_warn_unused_result,            /* gate */
7827     run_warn_unused_result,             /* execute */
7828     NULL,                               /* sub */
7829     NULL,                               /* next */
7830     0,                                  /* static_pass_number */
7831     TV_NONE,                            /* tv_id */
7832     PROP_gimple_any,                    /* properties_required */
7833     0,                                  /* properties_provided */
7834     0,                                  /* properties_destroyed */
7835     0,                                  /* todo_flags_start */
7836     0,                                  /* todo_flags_finish */
7837   }
7838 };