gcc/gimple-iterator.c

   1 /* Iterator routines for GIMPLE statements.
   2    Copyright (C) 2007-2013 Free Software Foundation, Inc.
   3    Contributed by Aldy Hernandez  <aldy@quesejoda.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "gimple-ssa.h"
  28 #include "cgraph.h"
  29 #include "tree-cfg.h"
  30 #include "tree-phinodes.h"
  31 #include "ssa-iterators.h"
  32 #include "tree-ssa.h"
  33 #include "value-prof.h"
  34
  35
  36 /* Mark the statement STMT as modified, and update it.  */
  37
  38 static inline void
  39 update_modified_stmt (gimple stmt)
  40 {
  41   if (!ssa_operands_active (cfun))
  42     return;
  43   update_stmt_if_modified (stmt);
  44 }
  45
  46
  47 /* Mark the statements in SEQ as modified, and update them.  */
  48
  49 static void
  50 update_modified_stmts (gimple_seq seq)
  51 {
  52   gimple_stmt_iterator gsi;
  53
  54   if (!ssa_operands_active (cfun))
  55     return;
  56   for (gsi = gsi_start (seq); !gsi_end_p (gsi); gsi_next (&gsi))
  57     update_stmt_if_modified (gsi_stmt (gsi));
  58 }
  59
  60
  61 /* Set BB to be the basic block for all the statements in the list
  62    starting at FIRST and LAST.  */
  63
  64 static void
  65 update_bb_for_stmts (gimple_seq_node first, gimple_seq_node last,
  66                      basic_block bb)
  67 {
  68   gimple_seq_node n;
  69
  70   for (n = first; n; n = n->gsbase.next)
  71     {
  72       gimple_set_bb (n, bb);
  73       if (n == last)
  74         break;
  75     }
  76 }
  77
  78 /* Set the frequencies for the cgraph_edges for each of the calls
  79    starting at FIRST for their new position within BB.  */
  80
  81 static void
  82 update_call_edge_frequencies (gimple_seq_node first, basic_block bb)
  83 {
  84   struct cgraph_node *cfun_node = NULL;
  85   int bb_freq = 0;
  86   gimple_seq_node n;
  87
  88   for (n = first; n ; n = n->gsbase.next)
  89     if (is_gimple_call (n))
  90       {
  91         struct cgraph_edge *e;
  92
  93         /* These function calls are expensive enough that we want
  94            to avoid calling them if we never see any calls.  */
  95         if (cfun_node == NULL)
  96           {
  97             cfun_node = cgraph_get_node (current_function_decl);
  98             bb_freq = (compute_call_stmt_bb_frequency
  99                        (current_function_decl, bb));
 100           }
 101
 102         e = cgraph_edge (cfun_node, n);
 103         if (e != NULL)
 104           e->frequency = bb_freq;
 105       }
 106 }
 107
 108 /* Insert the sequence delimited by nodes FIRST and LAST before
 109    iterator I.  M specifies how to update iterator I after insertion
 110    (see enum gsi_iterator_update).
 111
 112    This routine assumes that there is a forward and backward path
 113    between FIRST and LAST (i.e., they are linked in a doubly-linked
 114    list).  Additionally, if FIRST == LAST, this routine will properly
 115    insert a single node.  */
 116
 117 static void
 118 gsi_insert_seq_nodes_before (gimple_stmt_iterator *i,
 119                              gimple_seq_node first,
 120                              gimple_seq_node last,
 121                              enum gsi_iterator_update mode)
 122 {
 123   basic_block bb;
 124   gimple_seq_node cur = i->ptr;
 125
 126   gcc_assert (!cur || cur->gsbase.prev);
 127
 128   if ((bb = gsi_bb (*i)) != NULL)
 129     update_bb_for_stmts (first, last, bb);
 130
 131   /* Link SEQ before CUR in the sequence.  */
 132   if (cur)
 133     {
 134       first->gsbase.prev = cur->gsbase.prev;
 135       if (first->gsbase.prev->gsbase.next)
 136         first->gsbase.prev->gsbase.next = first;
 137       else
 138         gimple_seq_set_first (i->seq, first);
 139       last->gsbase.next = cur;
 140       cur->gsbase.prev = last;
 141     }
 142   else
 143     {
 144       gimple_seq_node itlast = gimple_seq_last (*i->seq);
 145
 146       /* If CUR is NULL, we link at the end of the sequence (this case happens
 147          when gsi_after_labels is called for a basic block that contains only
 148          labels, so it returns an iterator after the end of the block, and
 149          we need to insert before it; it might be cleaner to add a flag to the
 150          iterator saying whether we are at the start or end of the list).  */
 151       last->gsbase.next = NULL;
 152       if (itlast)
 153         {
 154           first->gsbase.prev = itlast;
 155           itlast->gsbase.next = first;
 156         }
 157       else
 158         gimple_seq_set_first (i->seq, first);
 159       gimple_seq_set_last (i->seq, last);
 160     }
 161
 162   /* Update the iterator, if requested.  */
 163   switch (mode)
 164     {
 165     case GSI_NEW_STMT:
 166     case GSI_CONTINUE_LINKING:
 167       i->ptr = first;
 168       break;
 169     case GSI_SAME_STMT:
 170       break;
 171     default:
 172       gcc_unreachable ();
 173     }
 174 }
 175
 176
 177 /* Inserts the sequence of statements SEQ before the statement pointed
 178    by iterator I.  MODE indicates what to do with the iterator after
 179    insertion (see enum gsi_iterator_update).
 180
 181    This function does not scan for new operands.  It is provided for
 182    the use of the gimplifier, which manipulates statements for which
 183    def/use information has not yet been constructed.  Most callers
 184    should use gsi_insert_seq_before.  */
 185
 186 void
 187 gsi_insert_seq_before_without_update (gimple_stmt_iterator *i, gimple_seq seq,
 188                                       enum gsi_iterator_update mode)
 189 {
 190   gimple_seq_node first, last;
 191
 192   if (seq == NULL)
 193     return;
 194
 195   /* Don't allow inserting a sequence into itself.  */
 196   gcc_assert (seq != *i->seq);
 197
 198   first = gimple_seq_first (seq);
 199   last = gimple_seq_last (seq);
 200
 201   /* Empty sequences need no work.  */
 202   if (!first || !last)
 203     {
 204       gcc_assert (first == last);
 205       return;
 206     }
 207
 208   gsi_insert_seq_nodes_before (i, first, last, mode);
 209 }
 210
 211
 212 /* Inserts the sequence of statements SEQ before the statement pointed
 213    by iterator I.  MODE indicates what to do with the iterator after
 214    insertion (see enum gsi_iterator_update). Scan the statements in SEQ
 215    for new operands.  */
 216
 217 void
 218 gsi_insert_seq_before (gimple_stmt_iterator *i, gimple_seq seq,
 219                        enum gsi_iterator_update mode)
 220 {
 221   update_modified_stmts (seq);
 222   gsi_insert_seq_before_without_update (i, seq, mode);
 223 }
 224
 225
 226 /* Insert the sequence delimited by nodes FIRST and LAST after
 227    iterator I.  M specifies how to update iterator I after insertion
 228    (see enum gsi_iterator_update).
 229
 230    This routine assumes that there is a forward and backward path
 231    between FIRST and LAST (i.e., they are linked in a doubly-linked
 232    list).  Additionally, if FIRST == LAST, this routine will properly
 233    insert a single node.  */
 234
 235 static void
 236 gsi_insert_seq_nodes_after (gimple_stmt_iterator *i,
 237                             gimple_seq_node first,
 238                             gimple_seq_node last,
 239                             enum gsi_iterator_update m)
 240 {
 241   basic_block bb;
 242   gimple_seq_node cur = i->ptr;
 243
 244   gcc_assert (!cur || cur->gsbase.prev);
 245
 246   /* If the iterator is inside a basic block, we need to update the
 247      basic block information for all the nodes between FIRST and LAST.  */
 248   if ((bb = gsi_bb (*i)) != NULL)
 249     update_bb_for_stmts (first, last, bb);
 250
 251   /* Link SEQ after CUR.  */
 252   if (cur)
 253     {
 254       last->gsbase.next = cur->gsbase.next;
 255       if (last->gsbase.next)
 256         {
 257           last->gsbase.next->gsbase.prev = last;
 258         }
 259       else
 260         gimple_seq_set_last (i->seq, last);
 261       first->gsbase.prev = cur;
 262       cur->gsbase.next = first;
 263     }
 264   else
 265     {
 266       gcc_assert (!gimple_seq_last (*i->seq));
 267       last->gsbase.next = NULL;
 268       gimple_seq_set_first (i->seq, first);
 269       gimple_seq_set_last (i->seq, last);
 270     }
 271
 272   /* Update the iterator, if requested.  */
 273   switch (m)
 274     {
 275     case GSI_NEW_STMT:
 276       i->ptr = first;
 277       break;
 278     case GSI_CONTINUE_LINKING:
 279       i->ptr = last;
 280       break;
 281     case GSI_SAME_STMT:
 282       gcc_assert (cur);
 283       break;
 284     default:
 285       gcc_unreachable ();
 286     }
 287 }
 288
 289
 290 /* Links sequence SEQ after the statement pointed-to by iterator I.
 291    MODE is as in gsi_insert_after.
 292
 293    This function does not scan for new operands.  It is provided for
 294    the use of the gimplifier, which manipulates statements for which
 295    def/use information has not yet been constructed.  Most callers
 296    should use gsi_insert_seq_after.  */
 297
 298 void
 299 gsi_insert_seq_after_without_update (gimple_stmt_iterator *i, gimple_seq seq,
 300                                      enum gsi_iterator_update mode)
 301 {
 302   gimple_seq_node first, last;
 303
 304   if (seq == NULL)
 305     return;
 306
 307   /* Don't allow inserting a sequence into itself.  */
 308   gcc_assert (seq != *i->seq);
 309
 310   first = gimple_seq_first (seq);
 311   last = gimple_seq_last (seq);
 312
 313   /* Empty sequences need no work.  */
 314   if (!first || !last)
 315     {
 316       gcc_assert (first == last);
 317       return;
 318     }
 319
 320   gsi_insert_seq_nodes_after (i, first, last, mode);
 321 }
 322
 323
 324 /* Links sequence SEQ after the statement pointed-to by iterator I.
 325    MODE is as in gsi_insert_after.  Scan the statements in SEQ
 326    for new operands.  */
 327
 328 void
 329 gsi_insert_seq_after (gimple_stmt_iterator *i, gimple_seq seq,
 330                       enum gsi_iterator_update mode)
 331 {
 332   update_modified_stmts (seq);
 333   gsi_insert_seq_after_without_update (i, seq, mode);
 334 }
 335
 336
 337 /* Move all statements in the sequence after I to a new sequence.
 338    Return this new sequence.  */
 339
 340 gimple_seq
 341 gsi_split_seq_after (gimple_stmt_iterator i)
 342 {
 343   gimple_seq_node cur, next;
 344   gimple_seq *pold_seq, new_seq;
 345
 346   cur = i.ptr;
 347
 348   /* How can we possibly split after the end, or before the beginning?  */
 349   gcc_assert (cur && cur->gsbase.next);
 350   next = cur->gsbase.next;
 351
 352   pold_seq = i.seq;
 353
 354   gimple_seq_set_first (&new_seq, next);
 355   gimple_seq_set_last (&new_seq, gimple_seq_last (*pold_seq));
 356   gimple_seq_set_last (pold_seq, cur);
 357   cur->gsbase.next = NULL;
 358
 359   return new_seq;
 360 }
 361
 362
 363 /* Set the statement to which GSI points to STMT.  This only updates
 364    the iterator and the gimple sequence, it doesn't do the bookkeeping
 365    of gsi_replace.  */
 366
 367 void
 368 gsi_set_stmt (gimple_stmt_iterator *gsi, gimple stmt)
 369 {
 370   gimple orig_stmt = gsi_stmt (*gsi);
 371   gimple prev, next;
 372
 373   stmt->gsbase.next = next = orig_stmt->gsbase.next;
 374   stmt->gsbase.prev = prev = orig_stmt->gsbase.prev;
 375   /* Note how we don't clear next/prev of orig_stmt.  This is so that
 376      copies of *GSI our callers might still hold (to orig_stmt)
 377      can be advanced as if they too were replaced.  */
 378   if (prev->gsbase.next)
 379     prev->gsbase.next = stmt;
 380   else
 381     gimple_seq_set_first (gsi->seq, stmt);
 382   if (next)
 383     next->gsbase.prev = stmt;
 384   else
 385     gimple_seq_set_last (gsi->seq, stmt);
 386
 387   gsi->ptr = stmt;
 388 }
 389
 390
 391 /* Move all statements in the sequence before I to a new sequence.
 392    Return this new sequence.  I is set to the head of the new list.  */
 393
 394 void
 395 gsi_split_seq_before (gimple_stmt_iterator *i, gimple_seq *pnew_seq)
 396 {
 397   gimple_seq_node cur, prev;
 398   gimple_seq old_seq;
 399
 400   cur = i->ptr;
 401
 402   /* How can we possibly split after the end?  */
 403   gcc_assert (cur);
 404   prev = cur->gsbase.prev;
 405
 406   old_seq = *i->seq;
 407   if (!prev->gsbase.next)
 408     *i->seq = NULL;
 409   i->seq = pnew_seq;
 410
 411   /* Set the limits on NEW_SEQ.  */
 412   gimple_seq_set_first (pnew_seq, cur);
 413   gimple_seq_set_last (pnew_seq, gimple_seq_last (old_seq));
 414
 415   /* Cut OLD_SEQ before I.  */
 416   gimple_seq_set_last (&old_seq, prev);
 417   if (prev->gsbase.next)
 418     prev->gsbase.next = NULL;
 419 }
 420
 421
 422 /* Replace the statement pointed-to by GSI to STMT.  If UPDATE_EH_INFO
 423    is true, the exception handling information of the original
 424    statement is moved to the new statement.  Assignments must only be
 425    replaced with assignments to the same LHS.  */
 426
 427 void
 428 gsi_replace (gimple_stmt_iterator *gsi, gimple stmt, bool update_eh_info)
 429 {
 430   gimple orig_stmt = gsi_stmt (*gsi);
 431
 432   if (stmt == orig_stmt)
 433     return;
 434
 435   gcc_assert (!gimple_has_lhs (orig_stmt) || !gimple_has_lhs (stmt)
 436               || gimple_get_lhs (orig_stmt) == gimple_get_lhs (stmt));
 437
 438   gimple_set_location (stmt, gimple_location (orig_stmt));
 439   gimple_set_bb (stmt, gsi_bb (*gsi));
 440
 441   /* Preserve EH region information from the original statement, if
 442      requested by the caller.  */
 443   if (update_eh_info)
 444     maybe_clean_or_replace_eh_stmt (orig_stmt, stmt);
 445
 446   gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
 447
 448   /* Free all the data flow information for ORIG_STMT.  */
 449   gimple_set_bb (orig_stmt, NULL);
 450   gimple_remove_stmt_histograms (cfun, orig_stmt);
 451   delink_stmt_imm_use (orig_stmt);
 452
 453   gsi_set_stmt (gsi, stmt);
 454   gimple_set_modified (stmt, true);
 455   update_modified_stmt (stmt);
 456 }
 457
 458
 459 /* Replace the statement pointed-to by GSI with the sequence SEQ.
 460    If UPDATE_EH_INFO is true, the exception handling information of
 461    the original statement is moved to the last statement of the new
 462    sequence.  If the old statement is an assignment, then so must
 463    be the last statement of the new sequence, and they must have the
 464    same LHS.  */
 465
 466 void
 467 gsi_replace_with_seq (gimple_stmt_iterator *gsi, gimple_seq seq,
 468                       bool update_eh_info)
 469 {
 470   gimple_stmt_iterator seqi;
 471   gimple last;
 472   if (gimple_seq_empty_p (seq))
 473     {
 474       gsi_remove (gsi, true);
 475       return;
 476     }
 477   seqi = gsi_last (seq);
 478   last = gsi_stmt (seqi);
 479   gsi_remove (&seqi, false);
 480   gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
 481   gsi_replace (gsi, last, update_eh_info);
 482 }
 483
 484
 485 /* Insert statement STMT before the statement pointed-to by iterator I.
 486    M specifies how to update iterator I after insertion (see enum
 487    gsi_iterator_update).
 488
 489    This function does not scan for new operands.  It is provided for
 490    the use of the gimplifier, which manipulates statements for which
 491    def/use information has not yet been constructed.  Most callers
 492    should use gsi_insert_before.  */
 493
 494 void
 495 gsi_insert_before_without_update (gimple_stmt_iterator *i, gimple stmt,
 496                                   enum gsi_iterator_update m)
 497 {
 498   gsi_insert_seq_nodes_before (i, stmt, stmt, m);
 499 }
 500
 501 /* Insert statement STMT before the statement pointed-to by iterator I.
 502    Update STMT's basic block and scan it for new operands.  M
 503    specifies how to update iterator I after insertion (see enum
 504    gsi_iterator_update).  */
 505
 506 void
 507 gsi_insert_before (gimple_stmt_iterator *i, gimple stmt,
 508                    enum gsi_iterator_update m)
 509 {
 510   update_modified_stmt (stmt);
 511   gsi_insert_before_without_update (i, stmt, m);
 512 }
 513
 514
 515 /* Insert statement STMT after the statement pointed-to by iterator I.
 516    M specifies how to update iterator I after insertion (see enum
 517    gsi_iterator_update).
 518
 519    This function does not scan for new operands.  It is provided for
 520    the use of the gimplifier, which manipulates statements for which
 521    def/use information has not yet been constructed.  Most callers
 522    should use gsi_insert_after.  */
 523
 524 void
 525 gsi_insert_after_without_update (gimple_stmt_iterator *i, gimple stmt,
 526                                  enum gsi_iterator_update m)
 527 {
 528   gsi_insert_seq_nodes_after (i, stmt, stmt, m);
 529 }
 530
 531
 532 /* Insert statement STMT after the statement pointed-to by iterator I.
 533    Update STMT's basic block and scan it for new operands.  M
 534    specifies how to update iterator I after insertion (see enum
 535    gsi_iterator_update).  */
 536
 537 void
 538 gsi_insert_after (gimple_stmt_iterator *i, gimple stmt,
 539                   enum gsi_iterator_update m)
 540 {
 541   update_modified_stmt (stmt);
 542   gsi_insert_after_without_update (i, stmt, m);
 543 }
 544
 545
 546 /* Remove the current stmt from the sequence.  The iterator is updated
 547    to point to the next statement.
 548
 549    REMOVE_PERMANENTLY is true when the statement is going to be removed
 550    from the IL and not reinserted elsewhere.  In that case we remove the
 551    statement pointed to by iterator I from the EH tables, and free its
 552    operand caches.  Otherwise we do not modify this information.  Returns
 553    true whether EH edge cleanup is required.  */
 554
 555 bool
 556 gsi_remove (gimple_stmt_iterator *i, bool remove_permanently)
 557 {
 558   gimple_seq_node cur, next, prev;
 559   gimple stmt = gsi_stmt (*i);
 560   bool require_eh_edge_purge = false;
 561
 562   if (gimple_code (stmt) != GIMPLE_PHI)
 563     insert_debug_temps_for_defs (i);
 564
 565   /* Free all the data flow information for STMT.  */
 566   gimple_set_bb (stmt, NULL);
 567   delink_stmt_imm_use (stmt);
 568   gimple_set_modified (stmt, true);
 569
 570   if (remove_permanently)
 571     {
 572       require_eh_edge_purge = remove_stmt_from_eh_lp (stmt);
 573       gimple_remove_stmt_histograms (cfun, stmt);
 574     }
 575
 576   /* Update the iterator and re-wire the links in I->SEQ.  */
 577   cur = i->ptr;
 578   next = cur->gsbase.next;
 579   prev = cur->gsbase.prev;
 580   /* See gsi_set_stmt for why we don't reset prev/next of STMT.  */
 581
 582   if (next)
 583     /* Cur is not last.  */
 584     next->gsbase.prev = prev;
 585   else if (prev->gsbase.next)
 586     /* Cur is last but not first.  */
 587     gimple_seq_set_last (i->seq, prev);
 588
 589   if (prev->gsbase.next)
 590     /* Cur is not first.  */
 591     prev->gsbase.next = next;
 592   else
 593     /* Cur is first.  */
 594     *i->seq = next;
 595
 596   i->ptr = next;
 597
 598   return require_eh_edge_purge;
 599 }
 600
 601
 602 /* Finds iterator for STMT.  */
 603
 604 gimple_stmt_iterator
 605 gsi_for_stmt (gimple stmt)
 606 {
 607   gimple_stmt_iterator i;
 608   basic_block bb = gimple_bb (stmt);
 609
 610   if (gimple_code (stmt) == GIMPLE_PHI)
 611     i = gsi_start_phis (bb);
 612   else
 613     i = gsi_start_bb (bb);
 614
 615   i.ptr = stmt;
 616   return i;
 617 }
 618
 619
 620 /* Move the statement at FROM so it comes right after the statement at TO.  */
 621
 622 void
 623 gsi_move_after (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
 624 {
 625   gimple stmt = gsi_stmt (*from);
 626   gsi_remove (from, false);
 627
 628   /* We must have GSI_NEW_STMT here, as gsi_move_after is sometimes used to
 629      move statements to an empty block.  */
 630   gsi_insert_after (to, stmt, GSI_NEW_STMT);
 631 }
 632
 633
 634 /* Move the statement at FROM so it comes right before the statement
 635    at TO.  */
 636
 637 void
 638 gsi_move_before (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
 639 {
 640   gimple stmt = gsi_stmt (*from);
 641   gsi_remove (from, false);
 642
 643   /* For consistency with gsi_move_after, it might be better to have
 644      GSI_NEW_STMT here; however, that breaks several places that expect
 645      that TO does not change.  */
 646   gsi_insert_before (to, stmt, GSI_SAME_STMT);
 647 }
 648
 649
 650 /* Move the statement at FROM to the end of basic block BB.  */
 651
 652 void
 653 gsi_move_to_bb_end (gimple_stmt_iterator *from, basic_block bb)
 654 {
 655   gimple_stmt_iterator last = gsi_last_bb (bb);
 656   gcc_checking_assert (gsi_bb (last) == bb);
 657
 658   /* Have to check gsi_end_p because it could be an empty block.  */
 659   if (!gsi_end_p (last) && is_ctrl_stmt (gsi_stmt (last)))
 660     gsi_move_before (from, &last);
 661   else
 662     gsi_move_after (from, &last);
 663 }
 664
 665
 666 /* Add STMT to the pending list of edge E.  No actual insertion is
 667    made until a call to gsi_commit_edge_inserts () is made.  */
 668
 669 void
 670 gsi_insert_on_edge (edge e, gimple stmt)
 671 {
 672   gimple_seq_add_stmt (&PENDING_STMT (e), stmt);
 673 }
 674
 675 /* Add the sequence of statements SEQ to the pending list of edge E.
 676    No actual insertion is made until a call to gsi_commit_edge_inserts
 677    is made.  */
 678
 679 void
 680 gsi_insert_seq_on_edge (edge e, gimple_seq seq)
 681 {
 682   gimple_seq_add_seq (&PENDING_STMT (e), seq);
 683 }
 684
 685
 686 /* Insert the statement pointed-to by GSI into edge E.  Every attempt
 687    is made to place the statement in an existing basic block, but
 688    sometimes that isn't possible.  When it isn't possible, the edge is
 689    split and the statement is added to the new block.
 690
 691    In all cases, the returned *GSI points to the correct location.  The
 692    return value is true if insertion should be done after the location,
 693    or false if it should be done before the location.  If a new basic block
 694    has to be created, it is stored in *NEW_BB.  */
 695
 696 static bool
 697 gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi,
 698                              basic_block *new_bb)
 699 {
 700   basic_block dest, src;
 701   gimple tmp;
 702
 703   dest = e->dest;
 704
 705   /* If the destination has one predecessor which has no PHI nodes,
 706      insert there.  Except for the exit block.
 707
 708      The requirement for no PHI nodes could be relaxed.  Basically we
 709      would have to examine the PHIs to prove that none of them used
 710      the value set by the statement we want to insert on E.  That
 711      hardly seems worth the effort.  */
 712  restart:
 713   if (single_pred_p (dest)
 714       && gimple_seq_empty_p (phi_nodes (dest))
 715       && dest != EXIT_BLOCK_PTR)
 716     {
 717       *gsi = gsi_start_bb (dest);
 718       if (gsi_end_p (*gsi))
 719         return true;
 720
 721       /* Make sure we insert after any leading labels.  */
 722       tmp = gsi_stmt (*gsi);
 723       while (gimple_code (tmp) == GIMPLE_LABEL)
 724         {
 725           gsi_next (gsi);
 726           if (gsi_end_p (*gsi))
 727             break;
 728           tmp = gsi_stmt (*gsi);
 729         }
 730
 731       if (gsi_end_p (*gsi))
 732         {
 733           *gsi = gsi_last_bb (dest);
 734           return true;
 735         }
 736       else
 737         return false;
 738     }
 739
 740   /* If the source has one successor, the edge is not abnormal and
 741      the last statement does not end a basic block, insert there.
 742      Except for the entry block.  */
 743   src = e->src;
 744   if ((e->flags & EDGE_ABNORMAL) == 0
 745       && single_succ_p (src)
 746       && src != ENTRY_BLOCK_PTR)
 747     {
 748       *gsi = gsi_last_bb (src);
 749       if (gsi_end_p (*gsi))
 750         return true;
 751
 752       tmp = gsi_stmt (*gsi);
 753       if (!stmt_ends_bb_p (tmp))
 754         return true;
 755
 756       switch (gimple_code (tmp))
 757         {
 758         case GIMPLE_RETURN:
 759         case GIMPLE_RESX:
 760           return false;
 761         default:
 762           break;
 763         }
 764     }
 765
 766   /* Otherwise, create a new basic block, and split this edge.  */
 767   dest = split_edge (e);
 768   if (new_bb)
 769     *new_bb = dest;
 770   e = single_pred_edge (dest);
 771   goto restart;
 772 }
 773
 774
 775 /* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts.  If a new
 776    block has to be created, it is returned.  */
 777
 778 basic_block
 779 gsi_insert_on_edge_immediate (edge e, gimple stmt)
 780 {
 781   gimple_stmt_iterator gsi;
 782   basic_block new_bb = NULL;
 783   bool ins_after;
 784
 785   gcc_assert (!PENDING_STMT (e));
 786
 787   ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
 788
 789   update_call_edge_frequencies (stmt, gsi.bb);
 790
 791   if (ins_after)
 792     gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 793   else
 794     gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 795
 796   return new_bb;
 797 }
 798
 799 /* Insert STMTS on edge E.  If a new block has to be created, it
 800    is returned.  */
 801
 802 basic_block
 803 gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts)
 804 {
 805   gimple_stmt_iterator gsi;
 806   basic_block new_bb = NULL;
 807   bool ins_after;
 808
 809   gcc_assert (!PENDING_STMT (e));
 810
 811   ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
 812   update_call_edge_frequencies (gimple_seq_first (stmts), gsi.bb);
 813
 814   if (ins_after)
 815     gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
 816   else
 817     gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
 818
 819   return new_bb;
 820 }
 821
 822 /* This routine will commit all pending edge insertions, creating any new
 823    basic blocks which are necessary.  */
 824
 825 void
 826 gsi_commit_edge_inserts (void)
 827 {
 828   basic_block bb;
 829   edge e;
 830   edge_iterator ei;
 831
 832   gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
 833
 834   FOR_EACH_BB (bb)
 835     FOR_EACH_EDGE (e, ei, bb->succs)
 836       gsi_commit_one_edge_insert (e, NULL);
 837 }
 838
 839
 840 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
 841    to this block, otherwise set it to NULL.  */
 842
 843 void
 844 gsi_commit_one_edge_insert (edge e, basic_block *new_bb)
 845 {
 846   if (new_bb)
 847     *new_bb = NULL;
 848
 849   if (PENDING_STMT (e))
 850     {
 851       gimple_stmt_iterator gsi;
 852       gimple_seq seq = PENDING_STMT (e);
 853       bool ins_after;
 854
 855       PENDING_STMT (e) = NULL;
 856
 857       ins_after = gimple_find_edge_insert_loc (e, &gsi, new_bb);
 858       update_call_edge_frequencies (gimple_seq_first (seq), gsi.bb);
 859
 860       if (ins_after)
 861         gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
 862       else
 863         gsi_insert_seq_before (&gsi, seq, GSI_NEW_STMT);
 864     }
 865 }
 866
 867 /* Returns iterator at the start of the list of phi nodes of BB.  */
 868
 869 gimple_stmt_iterator
 870 gsi_start_phis (basic_block bb)
 871 {
 872   gimple_seq *pseq = phi_nodes_ptr (bb);
 873   return gsi_start_1 (pseq);
 874 }