gcc/gimple-iterator.c

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