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_node::get (current_function_decl);
 105             bb_freq = (compute_call_stmt_bb_frequency
 106                        (current_function_decl, bb));
 107           }
 108
 109         e = cfun_node->get_edge (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.  Returns whether EH edge
 433    cleanup is required.  */
 434
 435 bool
 436 gsi_replace (gimple_stmt_iterator *gsi, gimple stmt, bool update_eh_info)
 437 {
 438   gimple orig_stmt = gsi_stmt (*gsi);
 439   bool require_eh_edge_purge = false;
 440
 441   if (stmt == orig_stmt)
 442     return false;
 443
 444   gcc_assert (!gimple_has_lhs (orig_stmt) || !gimple_has_lhs (stmt)
 445               || gimple_get_lhs (orig_stmt) == gimple_get_lhs (stmt));
 446
 447   gimple_set_location (stmt, gimple_location (orig_stmt));
 448   gimple_set_bb (stmt, gsi_bb (*gsi));
 449
 450   /* Preserve EH region information from the original statement, if
 451      requested by the caller.  */
 452   if (update_eh_info)
 453     require_eh_edge_purge = maybe_clean_or_replace_eh_stmt (orig_stmt, stmt);
 454
 455   gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
 456
 457   /* Free all the data flow information for ORIG_STMT.  */
 458   gimple_set_bb (orig_stmt, NULL);
 459   gimple_remove_stmt_histograms (cfun, orig_stmt);
 460   delink_stmt_imm_use (orig_stmt);
 461
 462   gsi_set_stmt (gsi, stmt);
 463   gimple_set_modified (stmt, true);
 464   update_modified_stmt (stmt);
 465   return require_eh_edge_purge;
 466 }
 467
 468
 469 /* Replace the statement pointed-to by GSI with the sequence SEQ.
 470    If UPDATE_EH_INFO is true, the exception handling information of
 471    the original statement is moved to the last statement of the new
 472    sequence.  If the old statement is an assignment, then so must
 473    be the last statement of the new sequence, and they must have the
 474    same LHS.  */
 475
 476 void
 477 gsi_replace_with_seq (gimple_stmt_iterator *gsi, gimple_seq seq,
 478                       bool update_eh_info)
 479 {
 480   gimple_stmt_iterator seqi;
 481   gimple last;
 482   if (gimple_seq_empty_p (seq))
 483     {
 484       gsi_remove (gsi, true);
 485       return;
 486     }
 487   seqi = gsi_last (seq);
 488   last = gsi_stmt (seqi);
 489   gsi_remove (&seqi, false);
 490   gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
 491   gsi_replace (gsi, last, update_eh_info);
 492 }
 493
 494
 495 /* Insert statement STMT before the statement pointed-to by iterator I.
 496    M specifies how to update iterator I after insertion (see enum
 497    gsi_iterator_update).
 498
 499    This function does not scan for new operands.  It is provided for
 500    the use of the gimplifier, which manipulates statements for which
 501    def/use information has not yet been constructed.  Most callers
 502    should use gsi_insert_before.  */
 503
 504 void
 505 gsi_insert_before_without_update (gimple_stmt_iterator *i, gimple stmt,
 506                                   enum gsi_iterator_update m)
 507 {
 508   gsi_insert_seq_nodes_before (i, stmt, stmt, m);
 509 }
 510
 511 /* Insert statement STMT before the statement pointed-to by iterator I.
 512    Update STMT's basic block and scan it for new operands.  M
 513    specifies how to update iterator I after insertion (see enum
 514    gsi_iterator_update).  */
 515
 516 void
 517 gsi_insert_before (gimple_stmt_iterator *i, gimple stmt,
 518                    enum gsi_iterator_update m)
 519 {
 520   update_modified_stmt (stmt);
 521   gsi_insert_before_without_update (i, stmt, m);
 522 }
 523
 524
 525 /* Insert statement STMT after the statement pointed-to by iterator I.
 526    M specifies how to update iterator I after insertion (see enum
 527    gsi_iterator_update).
 528
 529    This function does not scan for new operands.  It is provided for
 530    the use of the gimplifier, which manipulates statements for which
 531    def/use information has not yet been constructed.  Most callers
 532    should use gsi_insert_after.  */
 533
 534 void
 535 gsi_insert_after_without_update (gimple_stmt_iterator *i, gimple stmt,
 536                                  enum gsi_iterator_update m)
 537 {
 538   gsi_insert_seq_nodes_after (i, stmt, stmt, m);
 539 }
 540
 541
 542 /* Insert statement STMT after the statement pointed-to by iterator I.
 543    Update STMT's basic block and scan it for new operands.  M
 544    specifies how to update iterator I after insertion (see enum
 545    gsi_iterator_update).  */
 546
 547 void
 548 gsi_insert_after (gimple_stmt_iterator *i, gimple stmt,
 549                   enum gsi_iterator_update m)
 550 {
 551   update_modified_stmt (stmt);
 552   gsi_insert_after_without_update (i, stmt, m);
 553 }
 554
 555
 556 /* Remove the current stmt from the sequence.  The iterator is updated
 557    to point to the next statement.
 558
 559    REMOVE_PERMANENTLY is true when the statement is going to be removed
 560    from the IL and not reinserted elsewhere.  In that case we remove the
 561    statement pointed to by iterator I from the EH tables, and free its
 562    operand caches.  Otherwise we do not modify this information.  Returns
 563    true whether EH edge cleanup is required.  */
 564
 565 bool
 566 gsi_remove (gimple_stmt_iterator *i, bool remove_permanently)
 567 {
 568   gimple_seq_node cur, next, prev;
 569   gimple stmt = gsi_stmt (*i);
 570   bool require_eh_edge_purge = false;
 571
 572   if (gimple_code (stmt) != GIMPLE_PHI)
 573     insert_debug_temps_for_defs (i);
 574
 575   /* Free all the data flow information for STMT.  */
 576   gimple_set_bb (stmt, NULL);
 577   delink_stmt_imm_use (stmt);
 578   gimple_set_modified (stmt, true);
 579
 580   if (remove_permanently)
 581     {
 582       require_eh_edge_purge = remove_stmt_from_eh_lp (stmt);
 583       gimple_remove_stmt_histograms (cfun, stmt);
 584     }
 585
 586   /* Update the iterator and re-wire the links in I->SEQ.  */
 587   cur = i->ptr;
 588   next = cur->next;
 589   prev = cur->prev;
 590   /* See gsi_set_stmt for why we don't reset prev/next of STMT.  */
 591
 592   if (next)
 593     /* Cur is not last.  */
 594     next->prev = prev;
 595   else if (prev->next)
 596     /* Cur is last but not first.  */
 597     gimple_seq_set_last (i->seq, prev);
 598
 599   if (prev->next)
 600     /* Cur is not first.  */
 601     prev->next = next;
 602   else
 603     /* Cur is first.  */
 604     *i->seq = next;
 605
 606   i->ptr = next;
 607
 608   return require_eh_edge_purge;
 609 }
 610
 611
 612 /* Finds iterator for STMT.  */
 613
 614 gimple_stmt_iterator
 615 gsi_for_stmt (gimple stmt)
 616 {
 617   gimple_stmt_iterator i;
 618   basic_block bb = gimple_bb (stmt);
 619
 620   if (gimple_code (stmt) == GIMPLE_PHI)
 621     i = gsi_start_phis (bb);
 622   else
 623     i = gsi_start_bb (bb);
 624
 625   i.ptr = stmt;
 626   return i;
 627 }
 628
 629
 630 /* Move the statement at FROM so it comes right after the statement at TO.  */
 631
 632 void
 633 gsi_move_after (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
 634 {
 635   gimple stmt = gsi_stmt (*from);
 636   gsi_remove (from, false);
 637
 638   /* We must have GSI_NEW_STMT here, as gsi_move_after is sometimes used to
 639      move statements to an empty block.  */
 640   gsi_insert_after (to, stmt, GSI_NEW_STMT);
 641 }
 642
 643
 644 /* Move the statement at FROM so it comes right before the statement
 645    at TO.  */
 646
 647 void
 648 gsi_move_before (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
 649 {
 650   gimple stmt = gsi_stmt (*from);
 651   gsi_remove (from, false);
 652
 653   /* For consistency with gsi_move_after, it might be better to have
 654      GSI_NEW_STMT here; however, that breaks several places that expect
 655      that TO does not change.  */
 656   gsi_insert_before (to, stmt, GSI_SAME_STMT);
 657 }
 658
 659
 660 /* Move the statement at FROM to the end of basic block BB.  */
 661
 662 void
 663 gsi_move_to_bb_end (gimple_stmt_iterator *from, basic_block bb)
 664 {
 665   gimple_stmt_iterator last = gsi_last_bb (bb);
 666   gcc_checking_assert (gsi_bb (last) == bb);
 667
 668   /* Have to check gsi_end_p because it could be an empty block.  */
 669   if (!gsi_end_p (last) && is_ctrl_stmt (gsi_stmt (last)))
 670     gsi_move_before (from, &last);
 671   else
 672     gsi_move_after (from, &last);
 673 }
 674
 675
 676 /* Add STMT to the pending list of edge E.  No actual insertion is
 677    made until a call to gsi_commit_edge_inserts () is made.  */
 678
 679 void
 680 gsi_insert_on_edge (edge e, gimple stmt)
 681 {
 682   gimple_seq_add_stmt (&PENDING_STMT (e), stmt);
 683 }
 684
 685 /* Add the sequence of statements SEQ to the pending list of edge E.
 686    No actual insertion is made until a call to gsi_commit_edge_inserts
 687    is made.  */
 688
 689 void
 690 gsi_insert_seq_on_edge (edge e, gimple_seq seq)
 691 {
 692   gimple_seq_add_seq (&PENDING_STMT (e), seq);
 693 }
 694
 695 /* Return a new iterator pointing to the first statement in sequence of
 696    statements on edge E.  Such statements need to be subsequently moved into a
 697    basic block by calling gsi_commit_edge_inserts.  */
 698
 699 gimple_stmt_iterator
 700 gsi_start_edge (edge e)
 701 {
 702   return gsi_start (PENDING_STMT (e));
 703 }
 704
 705 /* Insert the statement pointed-to by GSI into edge E.  Every attempt
 706    is made to place the statement in an existing basic block, but
 707    sometimes that isn't possible.  When it isn't possible, the edge is
 708    split and the statement is added to the new block.
 709
 710    In all cases, the returned *GSI points to the correct location.  The
 711    return value is true if insertion should be done after the location,
 712    or false if it should be done before the location.  If a new basic block
 713    has to be created, it is stored in *NEW_BB.  */
 714
 715 static bool
 716 gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi,
 717                              basic_block *new_bb)
 718 {
 719   basic_block dest, src;
 720   gimple tmp;
 721
 722   dest = e->dest;
 723
 724   /* If the destination has one predecessor which has no PHI nodes,
 725      insert there.  Except for the exit block.
 726
 727      The requirement for no PHI nodes could be relaxed.  Basically we
 728      would have to examine the PHIs to prove that none of them used
 729      the value set by the statement we want to insert on E.  That
 730      hardly seems worth the effort.  */
 731  restart:
 732   if (single_pred_p (dest)
 733       && gimple_seq_empty_p (phi_nodes (dest))
 734       && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
 735     {
 736       *gsi = gsi_start_bb (dest);
 737       if (gsi_end_p (*gsi))
 738         return true;
 739
 740       /* Make sure we insert after any leading labels.  */
 741       tmp = gsi_stmt (*gsi);
 742       while (gimple_code (tmp) == GIMPLE_LABEL)
 743         {
 744           gsi_next (gsi);
 745           if (gsi_end_p (*gsi))
 746             break;
 747           tmp = gsi_stmt (*gsi);
 748         }
 749
 750       if (gsi_end_p (*gsi))
 751         {
 752           *gsi = gsi_last_bb (dest);
 753           return true;
 754         }
 755       else
 756         return false;
 757     }
 758
 759   /* If the source has one successor, the edge is not abnormal and
 760      the last statement does not end a basic block, insert there.
 761      Except for the entry block.  */
 762   src = e->src;
 763   if ((e->flags & EDGE_ABNORMAL) == 0
 764       && single_succ_p (src)
 765       && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
 766     {
 767       *gsi = gsi_last_bb (src);
 768       if (gsi_end_p (*gsi))
 769         return true;
 770
 771       tmp = gsi_stmt (*gsi);
 772       if (!stmt_ends_bb_p (tmp))
 773         return true;
 774
 775       switch (gimple_code (tmp))
 776         {
 777         case GIMPLE_RETURN:
 778         case GIMPLE_RESX:
 779           return false;
 780         default:
 781           break;
 782         }
 783     }
 784
 785   /* Otherwise, create a new basic block, and split this edge.  */
 786   dest = split_edge (e);
 787   if (new_bb)
 788     *new_bb = dest;
 789   e = single_pred_edge (dest);
 790   goto restart;
 791 }
 792
 793
 794 /* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts.  If a new
 795    block has to be created, it is returned.  */
 796
 797 basic_block
 798 gsi_insert_on_edge_immediate (edge e, gimple stmt)
 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
 808   update_call_edge_frequencies (stmt, gsi.bb);
 809
 810   if (ins_after)
 811     gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 812   else
 813     gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 814
 815   return new_bb;
 816 }
 817
 818 /* Insert STMTS on edge E.  If a new block has to be created, it
 819    is returned.  */
 820
 821 basic_block
 822 gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts)
 823 {
 824   gimple_stmt_iterator gsi;
 825   basic_block new_bb = NULL;
 826   bool ins_after;
 827
 828   gcc_assert (!PENDING_STMT (e));
 829
 830   ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
 831   update_call_edge_frequencies (gimple_seq_first (stmts), gsi.bb);
 832
 833   if (ins_after)
 834     gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
 835   else
 836     gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
 837
 838   return new_bb;
 839 }
 840
 841 /* This routine will commit all pending edge insertions, creating any new
 842    basic blocks which are necessary.  */
 843
 844 void
 845 gsi_commit_edge_inserts (void)
 846 {
 847   basic_block bb;
 848   edge e;
 849   edge_iterator ei;
 850
 851   gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
 852                               NULL);
 853
 854   FOR_EACH_BB_FN (bb, cfun)
 855     FOR_EACH_EDGE (e, ei, bb->succs)
 856       gsi_commit_one_edge_insert (e, NULL);
 857 }
 858
 859
 860 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
 861    to this block, otherwise set it to NULL.  */
 862
 863 void
 864 gsi_commit_one_edge_insert (edge e, basic_block *new_bb)
 865 {
 866   if (new_bb)
 867     *new_bb = NULL;
 868
 869   if (PENDING_STMT (e))
 870     {
 871       gimple_stmt_iterator gsi;
 872       gimple_seq seq = PENDING_STMT (e);
 873       bool ins_after;
 874
 875       PENDING_STMT (e) = NULL;
 876
 877       ins_after = gimple_find_edge_insert_loc (e, &gsi, new_bb);
 878       update_call_edge_frequencies (gimple_seq_first (seq), gsi.bb);
 879
 880       if (ins_after)
 881         gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
 882       else
 883         gsi_insert_seq_before (&gsi, seq, GSI_NEW_STMT);
 884     }
 885 }
 886
 887 /* Returns iterator at the start of the list of phi nodes of BB.  */
 888
 889 gimple_stmt_iterator
 890 gsi_start_phis (basic_block bb)
 891 {
 892   gimple_seq *pseq = phi_nodes_ptr (bb);
 893   return gsi_start_1 (pseq);
 894 }