summaryrefslogtreecommitdiff
path: root/gcc/gimple-iterator.c
blob: 0b0151f84374c9df4085507ba583fb6573e6f172 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
/* Iterator routines for GIMPLE statements.
   Copyright (C) 2007-2013 Free Software Foundation, Inc.
   Contributed by Aldy Hernandez  <aldy@quesejoda.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "gimple.h"
#include "tree-flow.h"
#include "value-prof.h"


/* Mark the statement STMT as modified, and update it.  */

static inline void
update_modified_stmt (gimple stmt)
{
  if (!ssa_operands_active (cfun))
    return;
  update_stmt_if_modified (stmt);
}


/* Mark the statements in SEQ as modified, and update them.  */

static void
update_modified_stmts (gimple_seq seq)
{
  gimple_stmt_iterator gsi;

  if (!ssa_operands_active (cfun))
    return;
  for (gsi = gsi_start (seq); !gsi_end_p (gsi); gsi_next (&gsi))
    update_stmt_if_modified (gsi_stmt (gsi));
}


/* Set BB to be the basic block for all the statements in the list
   starting at FIRST and LAST.  */

static void
update_bb_for_stmts (gimple_seq_node first, gimple_seq_node last,
		     basic_block bb)
{
  gimple_seq_node n;

  for (n = first; n; n = n->gsbase.next)
    {
      gimple_set_bb (n, bb);
      if (n == last)
	break;
    }
}

/* Set the frequencies for the cgraph_edges for each of the calls
   starting at FIRST for their new position within BB.  */

static void
update_call_edge_frequencies (gimple_seq_node first, basic_block bb)
{
  struct cgraph_node *cfun_node = NULL;
  int bb_freq = 0;
  gimple_seq_node n;

  for (n = first; n ; n = n->gsbase.next)
    if (is_gimple_call (n))
      {
	struct cgraph_edge *e;

	/* These function calls are expensive enough that we want
	   to avoid calling them if we never see any calls.  */
	if (cfun_node == NULL)
	  {
	    cfun_node = cgraph_get_node (current_function_decl);
	    bb_freq = (compute_call_stmt_bb_frequency
		       (current_function_decl, bb));
	  }

	e = cgraph_edge (cfun_node, n);
	if (e != NULL)
	  e->frequency = bb_freq;
      }
}

/* Insert the sequence delimited by nodes FIRST and LAST before
   iterator I.  M specifies how to update iterator I after insertion
   (see enum gsi_iterator_update).

   This routine assumes that there is a forward and backward path
   between FIRST and LAST (i.e., they are linked in a doubly-linked
   list).  Additionally, if FIRST == LAST, this routine will properly
   insert a single node.  */

static void
gsi_insert_seq_nodes_before (gimple_stmt_iterator *i,
			     gimple_seq_node first,
			     gimple_seq_node last,
			     enum gsi_iterator_update mode)
{
  basic_block bb;
  gimple_seq_node cur = i->ptr;

  gcc_assert (!cur || cur->gsbase.prev);

  if ((bb = gsi_bb (*i)) != NULL)
    update_bb_for_stmts (first, last, bb);

  /* Link SEQ before CUR in the sequence.  */
  if (cur)
    {
      first->gsbase.prev = cur->gsbase.prev;
      if (first->gsbase.prev->gsbase.next)
	first->gsbase.prev->gsbase.next = first;
      else
	gimple_seq_set_first (i->seq, first);
      last->gsbase.next = cur;
      cur->gsbase.prev = last;
    }
  else
    {
      gimple_seq_node itlast = gimple_seq_last (*i->seq);

      /* If CUR is NULL, we link at the end of the sequence (this case happens
	 when gsi_after_labels is called for a basic block that contains only
	 labels, so it returns an iterator after the end of the block, and
	 we need to insert before it; it might be cleaner to add a flag to the
	 iterator saying whether we are at the start or end of the list).  */
      last->gsbase.next = NULL;
      if (itlast)
	{
	  first->gsbase.prev = itlast;
	  itlast->gsbase.next = first;
	}
      else
	gimple_seq_set_first (i->seq, first);
      gimple_seq_set_last (i->seq, last);
    }

  /* Update the iterator, if requested.  */
  switch (mode)
    {
    case GSI_NEW_STMT:
    case GSI_CONTINUE_LINKING:
      i->ptr = first;
      break;
    case GSI_SAME_STMT:
      break;
    default:
      gcc_unreachable ();
    }
}


/* Inserts the sequence of statements SEQ before the statement pointed
   by iterator I.  MODE indicates what to do with the iterator after
   insertion (see enum gsi_iterator_update).

   This function does not scan for new operands.  It is provided for
   the use of the gimplifier, which manipulates statements for which
   def/use information has not yet been constructed.  Most callers
   should use gsi_insert_seq_before.  */

void
gsi_insert_seq_before_without_update (gimple_stmt_iterator *i, gimple_seq seq,
                                      enum gsi_iterator_update mode)
{
  gimple_seq_node first, last;

  if (seq == NULL)
    return;

  /* Don't allow inserting a sequence into itself.  */
  gcc_assert (seq != *i->seq);

  first = gimple_seq_first (seq);
  last = gimple_seq_last (seq);

  /* Empty sequences need no work.  */
  if (!first || !last)
    {
      gcc_assert (first == last);
      return;
    }

  gsi_insert_seq_nodes_before (i, first, last, mode);
}


/* Inserts the sequence of statements SEQ before the statement pointed
   by iterator I.  MODE indicates what to do with the iterator after
   insertion (see enum gsi_iterator_update). Scan the statements in SEQ
   for new operands.  */

void
gsi_insert_seq_before (gimple_stmt_iterator *i, gimple_seq seq,
		       enum gsi_iterator_update mode)
{
  update_modified_stmts (seq);
  gsi_insert_seq_before_without_update (i, seq, mode);
}


/* Insert the sequence delimited by nodes FIRST and LAST after
   iterator I.  M specifies how to update iterator I after insertion
   (see enum gsi_iterator_update).

   This routine assumes that there is a forward and backward path
   between FIRST and LAST (i.e., they are linked in a doubly-linked
   list).  Additionally, if FIRST == LAST, this routine will properly
   insert a single node.  */

static void
gsi_insert_seq_nodes_after (gimple_stmt_iterator *i,
			    gimple_seq_node first,
			    gimple_seq_node last,
			    enum gsi_iterator_update m)
{
  basic_block bb;
  gimple_seq_node cur = i->ptr;

  gcc_assert (!cur || cur->gsbase.prev);

  /* If the iterator is inside a basic block, we need to update the
     basic block information for all the nodes between FIRST and LAST.  */
  if ((bb = gsi_bb (*i)) != NULL)
    update_bb_for_stmts (first, last, bb);

  /* Link SEQ after CUR.  */
  if (cur)
    {
      last->gsbase.next = cur->gsbase.next;
      if (last->gsbase.next)
	{
	  last->gsbase.next->gsbase.prev = last;
	}
      else
	gimple_seq_set_last (i->seq, last);
      first->gsbase.prev = cur;
      cur->gsbase.next = first;
    }
  else
    {
      gcc_assert (!gimple_seq_last (*i->seq));
      last->gsbase.next = NULL;
      gimple_seq_set_first (i->seq, first);
      gimple_seq_set_last (i->seq, last);
    }

  /* Update the iterator, if requested.  */
  switch (m)
    {
    case GSI_NEW_STMT:
      i->ptr = first;
      break;
    case GSI_CONTINUE_LINKING:
      i->ptr = last;
      break;
    case GSI_SAME_STMT:
      gcc_assert (cur);
      break;
    default:
      gcc_unreachable ();
    }
}


/* Links sequence SEQ after the statement pointed-to by iterator I.
   MODE is as in gsi_insert_after.

   This function does not scan for new operands.  It is provided for
   the use of the gimplifier, which manipulates statements for which
   def/use information has not yet been constructed.  Most callers
   should use gsi_insert_seq_after.  */

void
gsi_insert_seq_after_without_update (gimple_stmt_iterator *i, gimple_seq seq,
                                     enum gsi_iterator_update mode)
{
  gimple_seq_node first, last;

  if (seq == NULL)
    return;

  /* Don't allow inserting a sequence into itself.  */
  gcc_assert (seq != *i->seq);

  first = gimple_seq_first (seq);
  last = gimple_seq_last (seq);

  /* Empty sequences need no work.  */
  if (!first || !last)
    {
      gcc_assert (first == last);
      return;
    }

  gsi_insert_seq_nodes_after (i, first, last, mode);
}


/* Links sequence SEQ after the statement pointed-to by iterator I.
   MODE is as in gsi_insert_after.  Scan the statements in SEQ
   for new operands.  */

void
gsi_insert_seq_after (gimple_stmt_iterator *i, gimple_seq seq,
		      enum gsi_iterator_update mode)
{
  update_modified_stmts (seq);
  gsi_insert_seq_after_without_update (i, seq, mode);
}


/* Move all statements in the sequence after I to a new sequence.
   Return this new sequence.  */

gimple_seq
gsi_split_seq_after (gimple_stmt_iterator i)
{
  gimple_seq_node cur, next;
  gimple_seq *pold_seq, new_seq;

  cur = i.ptr;

  /* How can we possibly split after the end, or before the beginning?  */
  gcc_assert (cur && cur->gsbase.next);
  next = cur->gsbase.next;

  pold_seq = i.seq;

  gimple_seq_set_first (&new_seq, next);
  gimple_seq_set_last (&new_seq, gimple_seq_last (*pold_seq));
  gimple_seq_set_last (pold_seq, cur);
  cur->gsbase.next = NULL;

  return new_seq;
}


/* Set the statement to which GSI points to STMT.  This only updates
   the iterator and the gimple sequence, it doesn't do the bookkeeping
   of gsi_replace.  */

void
gsi_set_stmt (gimple_stmt_iterator *gsi, gimple stmt)
{
  gimple orig_stmt = gsi_stmt (*gsi);
  gimple prev, next;

  stmt->gsbase.next = next = orig_stmt->gsbase.next;
  stmt->gsbase.prev = prev = orig_stmt->gsbase.prev;
  /* Note how we don't clear next/prev of orig_stmt.  This is so that
     copies of *GSI our callers might still hold (to orig_stmt)
     can be advanced as if they too were replaced.  */
  if (prev->gsbase.next)
    prev->gsbase.next = stmt;
  else
    gimple_seq_set_first (gsi->seq, stmt);
  if (next)
    next->gsbase.prev = stmt;
  else
    gimple_seq_set_last (gsi->seq, stmt);

  gsi->ptr = stmt;
}


/* Move all statements in the sequence before I to a new sequence.
   Return this new sequence.  I is set to the head of the new list.  */

void
gsi_split_seq_before (gimple_stmt_iterator *i, gimple_seq *pnew_seq)
{
  gimple_seq_node cur, prev;
  gimple_seq old_seq;

  cur = i->ptr;

  /* How can we possibly split after the end?  */
  gcc_assert (cur);
  prev = cur->gsbase.prev;

  old_seq = *i->seq;
  if (!prev->gsbase.next)
    *i->seq = NULL;
  i->seq = pnew_seq;

  /* Set the limits on NEW_SEQ.  */
  gimple_seq_set_first (pnew_seq, cur);
  gimple_seq_set_last (pnew_seq, gimple_seq_last (old_seq));

  /* Cut OLD_SEQ before I.  */
  gimple_seq_set_last (&old_seq, prev);
  if (prev->gsbase.next)
    prev->gsbase.next = NULL;
}


/* Replace the statement pointed-to by GSI to STMT.  If UPDATE_EH_INFO
   is true, the exception handling information of the original
   statement is moved to the new statement.  Assignments must only be
   replaced with assignments to the same LHS.  */

void
gsi_replace (gimple_stmt_iterator *gsi, gimple stmt, bool update_eh_info)
{
  gimple orig_stmt = gsi_stmt (*gsi);

  if (stmt == orig_stmt)
    return;

  gcc_assert (!gimple_has_lhs (orig_stmt) || !gimple_has_lhs (stmt)
	      || gimple_get_lhs (orig_stmt) == gimple_get_lhs (stmt));

  gimple_set_location (stmt, gimple_location (orig_stmt));
  gimple_set_bb (stmt, gsi_bb (*gsi));

  /* Preserve EH region information from the original statement, if
     requested by the caller.  */
  if (update_eh_info)
    maybe_clean_or_replace_eh_stmt (orig_stmt, stmt);

  gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);

  /* Free all the data flow information for ORIG_STMT.  */
  gimple_set_bb (orig_stmt, NULL);
  gimple_remove_stmt_histograms (cfun, orig_stmt);
  delink_stmt_imm_use (orig_stmt);

  gsi_set_stmt (gsi, stmt);
  gimple_set_modified (stmt, true);
  update_modified_stmt (stmt);
}


/* Replace the statement pointed-to by GSI with the sequence SEQ.
   If UPDATE_EH_INFO is true, the exception handling information of
   the original statement is moved to the last statement of the new
   sequence.  If the old statement is an assignment, then so must
   be the last statement of the new sequence, and they must have the
   same LHS.  */

void
gsi_replace_with_seq (gimple_stmt_iterator *gsi, gimple_seq seq,
		      bool update_eh_info)
{
  gimple_stmt_iterator seqi;
  gimple last;
  if (gimple_seq_empty_p (seq))
    {
      gsi_remove (gsi, true);
      return;
    }
  seqi = gsi_last (seq);
  last = gsi_stmt (seqi);
  gsi_remove (&seqi, false);
  gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
  gsi_replace (gsi, last, update_eh_info);
}


/* Insert statement STMT before the statement pointed-to by iterator I.
   M specifies how to update iterator I after insertion (see enum
   gsi_iterator_update).

   This function does not scan for new operands.  It is provided for
   the use of the gimplifier, which manipulates statements for which
   def/use information has not yet been constructed.  Most callers
   should use gsi_insert_before.  */

void
gsi_insert_before_without_update (gimple_stmt_iterator *i, gimple stmt,
                                  enum gsi_iterator_update m)
{
  gsi_insert_seq_nodes_before (i, stmt, stmt, m);
}

/* Insert statement STMT before the statement pointed-to by iterator I.
   Update STMT's basic block and scan it for new operands.  M
   specifies how to update iterator I after insertion (see enum
   gsi_iterator_update).  */

void
gsi_insert_before (gimple_stmt_iterator *i, gimple stmt,
                   enum gsi_iterator_update m)
{
  update_modified_stmt (stmt);
  gsi_insert_before_without_update (i, stmt, m);
}


/* Insert statement STMT after the statement pointed-to by iterator I.
   M specifies how to update iterator I after insertion (see enum
   gsi_iterator_update).

   This function does not scan for new operands.  It is provided for
   the use of the gimplifier, which manipulates statements for which
   def/use information has not yet been constructed.  Most callers
   should use gsi_insert_after.  */

void
gsi_insert_after_without_update (gimple_stmt_iterator *i, gimple stmt,
                                 enum gsi_iterator_update m)
{
  gsi_insert_seq_nodes_after (i, stmt, stmt, m);
}


/* Insert statement STMT after the statement pointed-to by iterator I.
   Update STMT's basic block and scan it for new operands.  M
   specifies how to update iterator I after insertion (see enum
   gsi_iterator_update).  */

void
gsi_insert_after (gimple_stmt_iterator *i, gimple stmt,
		  enum gsi_iterator_update m)
{
  update_modified_stmt (stmt);
  gsi_insert_after_without_update (i, stmt, m);
}


/* Remove the current stmt from the sequence.  The iterator is updated
   to point to the next statement.

   REMOVE_PERMANENTLY is true when the statement is going to be removed
   from the IL and not reinserted elsewhere.  In that case we remove the
   statement pointed to by iterator I from the EH tables, and free its
   operand caches.  Otherwise we do not modify this information.  Returns
   true whether EH edge cleanup is required.  */

bool
gsi_remove (gimple_stmt_iterator *i, bool remove_permanently)
{
  gimple_seq_node cur, next, prev;
  gimple stmt = gsi_stmt (*i);
  bool require_eh_edge_purge = false;

  if (gimple_code (stmt) != GIMPLE_PHI)
    insert_debug_temps_for_defs (i);

  /* Free all the data flow information for STMT.  */
  gimple_set_bb (stmt, NULL);
  delink_stmt_imm_use (stmt);
  gimple_set_modified (stmt, true);

  if (remove_permanently)
    {
      require_eh_edge_purge = remove_stmt_from_eh_lp (stmt);
      gimple_remove_stmt_histograms (cfun, stmt);
    }

  /* Update the iterator and re-wire the links in I->SEQ.  */
  cur = i->ptr;
  next = cur->gsbase.next;
  prev = cur->gsbase.prev;
  /* See gsi_set_stmt for why we don't reset prev/next of STMT.  */

  if (next)
    /* Cur is not last.  */
    next->gsbase.prev = prev;
  else if (prev->gsbase.next)
    /* Cur is last but not first.  */
    gimple_seq_set_last (i->seq, prev);

  if (prev->gsbase.next)
    /* Cur is not first.  */
    prev->gsbase.next = next;
  else
    /* Cur is first.  */
    *i->seq = next;

  i->ptr = next;

  return require_eh_edge_purge;
}


/* Finds iterator for STMT.  */

gimple_stmt_iterator
gsi_for_stmt (gimple stmt)
{
  gimple_stmt_iterator i;
  basic_block bb = gimple_bb (stmt);

  if (gimple_code (stmt) == GIMPLE_PHI)
    i = gsi_start_phis (bb);
  else
    i = gsi_start_bb (bb);

  i.ptr = stmt;
  return i;
}


/* Move the statement at FROM so it comes right after the statement at TO.  */

void
gsi_move_after (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
{
  gimple stmt = gsi_stmt (*from);
  gsi_remove (from, false);

  /* We must have GSI_NEW_STMT here, as gsi_move_after is sometimes used to
     move statements to an empty block.  */
  gsi_insert_after (to, stmt, GSI_NEW_STMT);
}


/* Move the statement at FROM so it comes right before the statement
   at TO.  */

void
gsi_move_before (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
{
  gimple stmt = gsi_stmt (*from);
  gsi_remove (from, false);

  /* For consistency with gsi_move_after, it might be better to have
     GSI_NEW_STMT here; however, that breaks several places that expect
     that TO does not change.  */
  gsi_insert_before (to, stmt, GSI_SAME_STMT);
}


/* Move the statement at FROM to the end of basic block BB.  */

void
gsi_move_to_bb_end (gimple_stmt_iterator *from, basic_block bb)
{
  gimple_stmt_iterator last = gsi_last_bb (bb);
  gcc_checking_assert (gsi_bb (last) == bb);

  /* Have to check gsi_end_p because it could be an empty block.  */
  if (!gsi_end_p (last) && is_ctrl_stmt (gsi_stmt (last)))
    gsi_move_before (from, &last);
  else
    gsi_move_after (from, &last);
}


/* Add STMT to the pending list of edge E.  No actual insertion is
   made until a call to gsi_commit_edge_inserts () is made.  */

void
gsi_insert_on_edge (edge e, gimple stmt)
{
  gimple_seq_add_stmt (&PENDING_STMT (e), stmt);
}

/* Add the sequence of statements SEQ to the pending list of edge E.
   No actual insertion is made until a call to gsi_commit_edge_inserts
   is made.  */

void
gsi_insert_seq_on_edge (edge e, gimple_seq seq)
{
  gimple_seq_add_seq (&PENDING_STMT (e), seq);
}


/* Insert the statement pointed-to by GSI into edge E.  Every attempt
   is made to place the statement in an existing basic block, but
   sometimes that isn't possible.  When it isn't possible, the edge is
   split and the statement is added to the new block.

   In all cases, the returned *GSI points to the correct location.  The
   return value is true if insertion should be done after the location,
   or false if it should be done before the location.  If a new basic block
   has to be created, it is stored in *NEW_BB.  */

static bool
gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi,
			     basic_block *new_bb)
{
  basic_block dest, src;
  gimple tmp;

  dest = e->dest;

  /* If the destination has one predecessor which has no PHI nodes,
     insert there.  Except for the exit block.

     The requirement for no PHI nodes could be relaxed.  Basically we
     would have to examine the PHIs to prove that none of them used
     the value set by the statement we want to insert on E.  That
     hardly seems worth the effort.  */
 restart:
  if (single_pred_p (dest)
      && gimple_seq_empty_p (phi_nodes (dest))
      && dest != EXIT_BLOCK_PTR)
    {
      *gsi = gsi_start_bb (dest);
      if (gsi_end_p (*gsi))
	return true;

      /* Make sure we insert after any leading labels.  */
      tmp = gsi_stmt (*gsi);
      while (gimple_code (tmp) == GIMPLE_LABEL)
	{
	  gsi_next (gsi);
	  if (gsi_end_p (*gsi))
	    break;
	  tmp = gsi_stmt (*gsi);
	}

      if (gsi_end_p (*gsi))
	{
	  *gsi = gsi_last_bb (dest);
	  return true;
	}
      else
	return false;
    }

  /* If the source has one successor, the edge is not abnormal and
     the last statement does not end a basic block, insert there.
     Except for the entry block.  */
  src = e->src;
  if ((e->flags & EDGE_ABNORMAL) == 0
      && single_succ_p (src)
      && src != ENTRY_BLOCK_PTR)
    {
      *gsi = gsi_last_bb (src);
      if (gsi_end_p (*gsi))
	return true;

      tmp = gsi_stmt (*gsi);
      if (!stmt_ends_bb_p (tmp))
	return true;

      switch (gimple_code (tmp))
	{
	case GIMPLE_RETURN:
	case GIMPLE_RESX:
	  return false;
	default:
	  break;
        }
    }

  /* Otherwise, create a new basic block, and split this edge.  */
  dest = split_edge (e);
  if (new_bb)
    *new_bb = dest;
  e = single_pred_edge (dest);
  goto restart;
}


/* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts.  If a new
   block has to be created, it is returned.  */

basic_block
gsi_insert_on_edge_immediate (edge e, gimple stmt)
{
  gimple_stmt_iterator gsi;
  basic_block new_bb = NULL;
  bool ins_after;

  gcc_assert (!PENDING_STMT (e));

  ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);

  update_call_edge_frequencies (stmt, gsi.bb);

  if (ins_after)
    gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
  else
    gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);

  return new_bb;
}

/* Insert STMTS on edge E.  If a new block has to be created, it
   is returned.  */

basic_block
gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts)
{
  gimple_stmt_iterator gsi;
  basic_block new_bb = NULL;
  bool ins_after;

  gcc_assert (!PENDING_STMT (e));

  ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
  update_call_edge_frequencies (gimple_seq_first (stmts), gsi.bb);

  if (ins_after)
    gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
  else
    gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);

  return new_bb;
}

/* This routine will commit all pending edge insertions, creating any new
   basic blocks which are necessary.  */

void
gsi_commit_edge_inserts (void)
{
  basic_block bb;
  edge e;
  edge_iterator ei;

  gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);

  FOR_EACH_BB (bb)
    FOR_EACH_EDGE (e, ei, bb->succs)
      gsi_commit_one_edge_insert (e, NULL);
}


/* Commit insertions pending at edge E. If a new block is created, set NEW_BB
   to this block, otherwise set it to NULL.  */

void
gsi_commit_one_edge_insert (edge e, basic_block *new_bb)
{
  if (new_bb)
    *new_bb = NULL;

  if (PENDING_STMT (e))
    {
      gimple_stmt_iterator gsi;
      gimple_seq seq = PENDING_STMT (e);
      bool ins_after;

      PENDING_STMT (e) = NULL;

      ins_after = gimple_find_edge_insert_loc (e, &gsi, new_bb);
      update_call_edge_frequencies (gimple_seq_first (seq), gsi.bb);

      if (ins_after)
	gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
      else
	gsi_insert_seq_before (&gsi, seq, GSI_NEW_STMT);
    }
}

/* Returns iterator at the start of the list of phi nodes of BB.  */

gimple_stmt_iterator
gsi_start_phis (basic_block bb)
{
  gimple_seq *pseq = phi_nodes_ptr (bb);
  return gsi_start_1 (pseq);
}