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