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