gcc/gimple-iterator.c

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