Mercurial > hg > CbC > CbC_gcc

comparison gcc/gimple-iterator.c @ 0:a06113de4d67

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