gcc/gimple-iterator.c

   1 /* Iterator routines for GIMPLE statements.
   2    Copyright (C) 2007-2014 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 /* Return a new iterator pointing to the first statement in sequence of
 693    statements on edge E.  Such statements need to be subsequently moved into a
 694    basic block by calling gsi_commit_edge_inserts.  */
 695
 696 gimple_stmt_iterator
 697 gsi_start_edge (edge e)
 698 {
 699   return gsi_start (PENDING_STMT (e));
 700 }
 701
 702 /* Insert the statement pointed-to by GSI into edge E.  Every attempt
 703    is made to place the statement in an existing basic block, but
 704    sometimes that isn't possible.  When it isn't possible, the edge is
 705    split and the statement is added to the new block.
 706
 707    In all cases, the returned *GSI points to the correct location.  The
 708    return value is true if insertion should be done after the location,
 709    or false if it should be done before the location.  If a new basic block
 710    has to be created, it is stored in *NEW_BB.  */
 711
 712 static bool
 713 gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi,
 714                              basic_block *new_bb)
 715 {
 716   basic_block dest, src;
 717   gimple tmp;
 718
 719   dest = e->dest;
 720
 721   /* If the destination has one predecessor which has no PHI nodes,
 722      insert there.  Except for the exit block.
 723
 724      The requirement for no PHI nodes could be relaxed.  Basically we
 725      would have to examine the PHIs to prove that none of them used
 726      the value set by the statement we want to insert on E.  That
 727      hardly seems worth the effort.  */
 728  restart:
 729   if (single_pred_p (dest)
 730       && gimple_seq_empty_p (phi_nodes (dest))
 731       && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
 732     {
 733       *gsi = gsi_start_bb (dest);
 734       if (gsi_end_p (*gsi))
 735         return true;
 736
 737       /* Make sure we insert after any leading labels.  */
 738       tmp = gsi_stmt (*gsi);
 739       while (gimple_code (tmp) == GIMPLE_LABEL)
 740         {
 741           gsi_next (gsi);
 742           if (gsi_end_p (*gsi))
 743             break;
 744           tmp = gsi_stmt (*gsi);
 745         }
 746
 747       if (gsi_end_p (*gsi))
 748         {
 749           *gsi = gsi_last_bb (dest);
 750           return true;
 751         }
 752       else
 753         return false;
 754     }
 755
 756   /* If the source has one successor, the edge is not abnormal and
 757      the last statement does not end a basic block, insert there.
 758      Except for the entry block.  */
 759   src = e->src;
 760   if ((e->flags & EDGE_ABNORMAL) == 0
 761       && single_succ_p (src)
 762       && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
 763     {
 764       *gsi = gsi_last_bb (src);
 765       if (gsi_end_p (*gsi))
 766         return true;
 767
 768       tmp = gsi_stmt (*gsi);
 769       if (!stmt_ends_bb_p (tmp))
 770         return true;
 771
 772       switch (gimple_code (tmp))
 773         {
 774         case GIMPLE_RETURN:
 775         case GIMPLE_RESX:
 776           return false;
 777         default:
 778           break;
 779         }
 780     }
 781
 782   /* Otherwise, create a new basic block, and split this edge.  */
 783   dest = split_edge (e);
 784   if (new_bb)
 785     *new_bb = dest;
 786   e = single_pred_edge (dest);
 787   goto restart;
 788 }
 789
 790
 791 /* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts.  If a new
 792    block has to be created, it is returned.  */
 793
 794 basic_block
 795 gsi_insert_on_edge_immediate (edge e, gimple stmt)
 796 {
 797   gimple_stmt_iterator gsi;
 798   basic_block new_bb = NULL;
 799   bool ins_after;
 800
 801   gcc_assert (!PENDING_STMT (e));
 802
 803   ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
 804
 805   update_call_edge_frequencies (stmt, gsi.bb);
 806
 807   if (ins_after)
 808     gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 809   else
 810     gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 811
 812   return new_bb;
 813 }
 814
 815 /* Insert STMTS on edge E.  If a new block has to be created, it
 816    is returned.  */
 817
 818 basic_block
 819 gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts)
 820 {
 821   gimple_stmt_iterator gsi;
 822   basic_block new_bb = NULL;
 823   bool ins_after;
 824
 825   gcc_assert (!PENDING_STMT (e));
 826
 827   ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
 828   update_call_edge_frequencies (gimple_seq_first (stmts), gsi.bb);
 829
 830   if (ins_after)
 831     gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
 832   else
 833     gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
 834
 835   return new_bb;
 836 }
 837
 838 /* This routine will commit all pending edge insertions, creating any new
 839    basic blocks which are necessary.  */
 840
 841 void
 842 gsi_commit_edge_inserts (void)
 843 {
 844   basic_block bb;
 845   edge e;
 846   edge_iterator ei;
 847
 848   gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
 849                               NULL);
 850
 851   FOR_EACH_BB_FN (bb, cfun)
 852     FOR_EACH_EDGE (e, ei, bb->succs)
 853       gsi_commit_one_edge_insert (e, NULL);
 854 }
 855
 856
 857 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
 858    to this block, otherwise set it to NULL.  */
 859
 860 void
 861 gsi_commit_one_edge_insert (edge e, basic_block *new_bb)
 862 {
 863   if (new_bb)
 864     *new_bb = NULL;
 865
 866   if (PENDING_STMT (e))
 867     {
 868       gimple_stmt_iterator gsi;
 869       gimple_seq seq = PENDING_STMT (e);
 870       bool ins_after;
 871
 872       PENDING_STMT (e) = NULL;
 873
 874       ins_after = gimple_find_edge_insert_loc (e, &gsi, new_bb);
 875       update_call_edge_frequencies (gimple_seq_first (seq), gsi.bb);
 876
 877       if (ins_after)
 878         gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
 879       else
 880         gsi_insert_seq_before (&gsi, seq, GSI_NEW_STMT);
 881     }
 882 }
 883
 884 /* Returns iterator at the start of the list of phi nodes of BB.  */
 885
 886 gimple_stmt_iterator
 887 gsi_start_phis (basic_block bb)
 888 {
 889   gimple_seq *pseq = phi_nodes_ptr (bb);
 890   return gsi_start_1 (pseq);
 891 }