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