Line data Source code
1 : /* Iterator routines for GIMPLE statements.
2 : Copyright (C) 2007-2026 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 "backend.h"
25 : #include "tree.h"
26 : #include "gimple.h"
27 : #include "cfghooks.h"
28 : #include "ssa.h"
29 : #include "cgraph.h"
30 : #include "tree-eh.h"
31 : #include "gimple-iterator.h"
32 : #include "tree-cfg.h"
33 : #include "tree-ssa.h"
34 : #include "value-prof.h"
35 : #include "gimplify.h"
36 :
37 :
38 : /* Mark the statement STMT as modified, and update it. */
39 :
40 : static inline void
41 214397680 : update_modified_stmt (gimple *stmt)
42 : {
43 214397680 : if (!ssa_operands_active (cfun))
44 : return;
45 191418443 : update_stmt_if_modified (stmt);
46 : }
47 :
48 :
49 : /* Mark the statements in SEQ as modified, and update them. */
50 :
51 : void
52 48703655 : update_modified_stmts (gimple_seq seq)
53 : {
54 48703655 : gimple_stmt_iterator gsi;
55 :
56 48703655 : if (!ssa_operands_active (cfun))
57 48703655 : return;
58 123220136 : for (gsi = gsi_start (seq); !gsi_end_p (gsi); gsi_next (&gsi))
59 98306206 : update_stmt_if_modified (gsi_stmt (gsi));
60 : }
61 :
62 :
63 : /* Set BB to be the basic block for all the statements in the list
64 : starting at FIRST and LAST. */
65 :
66 : static void
67 190100631 : update_bb_for_stmts (gimple_seq_node first, gimple_seq_node last,
68 : basic_block bb)
69 : {
70 190100631 : gimple_seq_node n;
71 :
72 274531306 : for (n = first; n; n = n->next)
73 : {
74 274531306 : gimple_set_bb (n, bb);
75 274531306 : if (n == last)
76 : break;
77 : }
78 190100631 : }
79 :
80 : /* Set the frequencies for the cgraph_edges for each of the calls
81 : starting at FIRST for their new position within BB. */
82 :
83 : static void
84 1534205 : update_call_edge_frequencies (gimple_seq_node first, basic_block bb)
85 : {
86 1534205 : struct cgraph_node *cfun_node = NULL;
87 1534205 : gimple_seq_node n;
88 :
89 4733490 : for (n = first; n ; n = n->next)
90 3199285 : if (is_gimple_call (n))
91 : {
92 7935 : struct cgraph_edge *e;
93 :
94 : /* These function calls are expensive enough that we want
95 : to avoid calling them if we never see any calls. */
96 7935 : if (cfun_node == NULL)
97 6483 : cfun_node = cgraph_node::get (current_function_decl);
98 :
99 7935 : e = cfun_node->get_edge (n);
100 7935 : if (e != NULL)
101 970 : e->count = bb->count;
102 : }
103 1534205 : }
104 :
105 : /* Insert the sequence delimited by nodes FIRST and LAST before
106 : iterator I. M specifies how to update iterator I after insertion
107 : (see enum gsi_iterator_update).
108 :
109 : This routine assumes that there is a forward and backward path
110 : between FIRST and LAST (i.e., they are linked in a doubly-linked
111 : list). Additionally, if FIRST == LAST, this routine will properly
112 : insert a single node. */
113 :
114 : static void
115 49912689 : gsi_insert_seq_nodes_before (gimple_stmt_iterator *i,
116 : gimple_seq_node first,
117 : gimple_seq_node last,
118 : enum gsi_iterator_update mode)
119 : {
120 49912689 : basic_block bb;
121 49912689 : gimple_seq_node cur = i->ptr;
122 :
123 49912689 : gcc_assert (!cur || cur->prev);
124 :
125 49912689 : if ((bb = gsi_bb (*i)) != NULL)
126 37345132 : update_bb_for_stmts (first, last, bb);
127 :
128 : /* Link SEQ before CUR in the sequence. */
129 49912689 : if (cur)
130 : {
131 45569769 : first->prev = cur->prev;
132 45569769 : if (first->prev->next)
133 29203564 : first->prev->next = first;
134 : else
135 16366205 : gimple_seq_set_first (i->seq, first);
136 45569769 : last->next = cur;
137 45569769 : cur->prev = last;
138 : }
139 : else
140 : {
141 4342920 : gimple_seq_node itlast = gimple_seq_last (*i->seq);
142 :
143 : /* If CUR is NULL, we link at the end of the sequence (this case happens
144 : when gsi_after_labels is called for a basic block that contains only
145 : labels, so it returns an iterator after the end of the block, and
146 : we need to insert before it; it might be cleaner to add a flag to the
147 : iterator saying whether we are at the start or end of the list). */
148 4342920 : last->next = NULL;
149 4342920 : if (itlast)
150 : {
151 1733488 : first->prev = itlast;
152 1733488 : itlast->next = first;
153 : }
154 : else
155 2609432 : gimple_seq_set_first (i->seq, first);
156 4342920 : gimple_seq_set_last (i->seq, last);
157 : }
158 :
159 : /* Update the iterator, if requested. */
160 49912689 : switch (mode)
161 : {
162 5143215 : case GSI_NEW_STMT:
163 5143215 : case GSI_CONTINUE_LINKING:
164 5143215 : i->ptr = first;
165 5143215 : break;
166 0 : case GSI_LAST_NEW_STMT:
167 0 : i->ptr = last;
168 0 : break;
169 : case GSI_SAME_STMT:
170 : break;
171 0 : default:
172 0 : gcc_unreachable ();
173 : }
174 49912689 : }
175 :
176 :
177 : /* Inserts the sequence of statements SEQ before the statement pointed
178 : by iterator I. MODE indicates what to do with the iterator after
179 : insertion (see enum gsi_iterator_update).
180 :
181 : This function does not scan for new operands. It is provided for
182 : the use of the gimplifier, which manipulates statements for which
183 : def/use information has not yet been constructed. Most callers
184 : should use gsi_insert_seq_before. */
185 :
186 : void
187 22658908 : gsi_insert_seq_before_without_update (gimple_stmt_iterator *i, gimple_seq seq,
188 : enum gsi_iterator_update mode)
189 : {
190 22658908 : gimple_seq_node first, last;
191 :
192 22658908 : if (seq == NULL)
193 : return;
194 :
195 : /* Don't allow inserting a sequence into itself. */
196 17435144 : gcc_assert (seq != *i->seq);
197 :
198 17435144 : first = gimple_seq_first (seq);
199 17435144 : last = gimple_seq_last (seq);
200 :
201 : /* Empty sequences need no work. */
202 17435144 : if (!first || !last)
203 : {
204 0 : gcc_assert (first == last);
205 : return;
206 : }
207 :
208 17435144 : gsi_insert_seq_nodes_before (i, first, last, mode);
209 : }
210 :
211 :
212 : /* Inserts the sequence of statements SEQ before the statement pointed
213 : by iterator I. MODE indicates what to do with the iterator after
214 : insertion (see enum gsi_iterator_update). Scan the statements in SEQ
215 : for new operands. */
216 :
217 : void
218 18864424 : gsi_insert_seq_before (gimple_stmt_iterator *i, gimple_seq seq,
219 : enum gsi_iterator_update mode)
220 : {
221 18864424 : update_modified_stmts (seq);
222 18864424 : gsi_insert_seq_before_without_update (i, seq, mode);
223 18864424 : }
224 :
225 :
226 : /* Insert the sequence delimited by nodes FIRST and LAST after
227 : iterator I. M specifies how to update iterator I after insertion
228 : (see enum gsi_iterator_update).
229 :
230 : This routine assumes that there is a forward and backward path
231 : between FIRST and LAST (i.e., they are linked in a doubly-linked
232 : list). Additionally, if FIRST == LAST, this routine will properly
233 : insert a single node. */
234 :
235 : static void
236 394178078 : gsi_insert_seq_nodes_after (gimple_stmt_iterator *i,
237 : gimple_seq_node first,
238 : gimple_seq_node last,
239 : enum gsi_iterator_update m)
240 : {
241 394178078 : basic_block bb;
242 394178078 : gimple_seq_node cur = i->ptr;
243 :
244 394178078 : gcc_assert (!cur || cur->prev);
245 :
246 : /* If the iterator is inside a basic block, we need to update the
247 : basic block information for all the nodes between FIRST and LAST. */
248 394178078 : if ((bb = gsi_bb (*i)) != NULL)
249 152755499 : update_bb_for_stmts (first, last, bb);
250 :
251 : /* Link SEQ after CUR. */
252 394178078 : if (cur)
253 : {
254 231750317 : last->next = cur->next;
255 231750317 : if (last->next)
256 : {
257 9337859 : last->next->prev = last;
258 : }
259 : else
260 222412458 : gimple_seq_set_last (i->seq, last);
261 231750317 : first->prev = cur;
262 231750317 : cur->next = first;
263 : }
264 : else
265 : {
266 162427761 : gcc_assert (!gimple_seq_last (*i->seq));
267 162427761 : last->next = NULL;
268 162427761 : gimple_seq_set_first (i->seq, first);
269 162427761 : gimple_seq_set_last (i->seq, last);
270 : }
271 :
272 : /* Update the iterator, if requested. */
273 394178078 : switch (m)
274 : {
275 375722448 : case GSI_NEW_STMT:
276 375722448 : i->ptr = first;
277 375722448 : break;
278 6233514 : case GSI_LAST_NEW_STMT:
279 6233514 : case GSI_CONTINUE_LINKING:
280 6233514 : i->ptr = last;
281 6233514 : break;
282 12222116 : case GSI_SAME_STMT:
283 12222116 : gcc_assert (cur);
284 : break;
285 0 : default:
286 0 : gcc_unreachable ();
287 : }
288 394178078 : }
289 :
290 :
291 : /* Links sequence SEQ after the statement pointed-to by iterator I.
292 : MODE is as in gsi_insert_after.
293 :
294 : This function does not scan for new operands. It is provided for
295 : the use of the gimplifier, which manipulates statements for which
296 : def/use information has not yet been constructed. Most callers
297 : should use gsi_insert_seq_after. */
298 :
299 : void
300 36456526 : gsi_insert_seq_after_without_update (gimple_stmt_iterator *i, gimple_seq seq,
301 : enum gsi_iterator_update mode)
302 : {
303 36456526 : gimple_seq_node first, last;
304 :
305 36456526 : if (seq == NULL)
306 : return;
307 :
308 : /* Don't allow inserting a sequence into itself. */
309 34406977 : gcc_assert (seq != *i->seq);
310 :
311 34406977 : first = gimple_seq_first (seq);
312 34406977 : last = gimple_seq_last (seq);
313 :
314 : /* Empty sequences need no work. */
315 34406977 : if (!first || !last)
316 : {
317 0 : gcc_assert (first == last);
318 : return;
319 : }
320 :
321 34406977 : gsi_insert_seq_nodes_after (i, first, last, mode);
322 : }
323 :
324 :
325 : /* Links sequence SEQ after the statement pointed-to by iterator I.
326 : MODE is as in gsi_insert_after. Scan the statements in SEQ
327 : for new operands. */
328 :
329 : void
330 29786206 : gsi_insert_seq_after (gimple_stmt_iterator *i, gimple_seq seq,
331 : enum gsi_iterator_update mode)
332 : {
333 29786206 : update_modified_stmts (seq);
334 29786206 : gsi_insert_seq_after_without_update (i, seq, mode);
335 29786206 : }
336 :
337 :
338 : /* Move all statements in the sequence after I to a new sequence.
339 : Return this new sequence. */
340 :
341 : gimple_seq
342 578854 : gsi_split_seq_after (gimple_stmt_iterator i)
343 : {
344 578854 : gimple_seq_node cur, next;
345 578854 : gimple_seq *pold_seq, new_seq;
346 :
347 578854 : cur = i.ptr;
348 :
349 : /* How can we possibly split after the end, or before the beginning? */
350 578854 : gcc_assert (cur && cur->next);
351 578854 : next = cur->next;
352 :
353 578854 : pold_seq = i.seq;
354 :
355 578854 : gimple_seq_set_first (&new_seq, next);
356 578854 : gimple_seq_set_last (&new_seq, gimple_seq_last (*pold_seq));
357 578854 : gimple_seq_set_last (pold_seq, cur);
358 578854 : cur->next = NULL;
359 :
360 578854 : return new_seq;
361 : }
362 :
363 :
364 : /* Set the statement to which GSI points to STMT. This only updates
365 : the iterator and the gimple sequence, it doesn't do the bookkeeping
366 : of gsi_replace. */
367 :
368 : void
369 5025440 : gsi_set_stmt (gimple_stmt_iterator *gsi, gimple *stmt)
370 : {
371 5025440 : gimple *orig_stmt = gsi_stmt (*gsi);
372 5025440 : gimple *prev, *next;
373 :
374 5025440 : stmt->next = next = orig_stmt->next;
375 5025440 : stmt->prev = prev = orig_stmt->prev;
376 : /* Note how we don't clear next/prev of orig_stmt. This is so that
377 : copies of *GSI our callers might still hold (to orig_stmt)
378 : can be advanced as if they too were replaced. */
379 5025440 : if (prev->next)
380 3560263 : prev->next = stmt;
381 : else
382 1465177 : gimple_seq_set_first (gsi->seq, stmt);
383 5025440 : if (next)
384 3263501 : next->prev = stmt;
385 : else
386 1761939 : gimple_seq_set_last (gsi->seq, stmt);
387 :
388 5025440 : gsi->ptr = stmt;
389 5025440 : }
390 :
391 :
392 : /* Move all statements in the sequence starting at I to a new sequence.
393 : Set *PNEW_SEQ to this sequence. I is set to the head of the new list. */
394 :
395 : void
396 24097203 : gsi_split_seq_before (gimple_stmt_iterator *i, gimple_seq *pnew_seq)
397 : {
398 24097203 : gimple_seq_node cur, prev;
399 24097203 : gimple_seq old_seq;
400 :
401 24097203 : cur = i->ptr;
402 :
403 : /* How can we possibly split after the end? */
404 24097203 : gcc_assert (cur);
405 24097203 : prev = cur->prev;
406 :
407 24097203 : old_seq = *i->seq;
408 24097203 : if (!prev->next)
409 1380166 : *i->seq = NULL;
410 24097203 : i->seq = pnew_seq;
411 :
412 : /* Set the limits on NEW_SEQ. */
413 24097203 : gimple_seq_set_first (pnew_seq, cur);
414 48194406 : gimple_seq_set_last (pnew_seq, gimple_seq_last (old_seq));
415 :
416 : /* Cut OLD_SEQ before I. */
417 24097203 : gimple_seq_set_last (&old_seq, prev);
418 24097203 : if (prev->next)
419 22717037 : prev->next = NULL;
420 24097203 : }
421 :
422 :
423 : /* Replace the statement pointed-to by GSI to STMT. If UPDATE_EH_INFO
424 : is true, the exception handling information of the original
425 : statement is moved to the new statement. Assignments must only be
426 : replaced with assignments to the same LHS. Returns whether EH edge
427 : cleanup is required. */
428 :
429 : bool
430 3677864 : gsi_replace (gimple_stmt_iterator *gsi, gimple *stmt, bool update_eh_info)
431 : {
432 3677864 : gimple *orig_stmt = gsi_stmt (*gsi);
433 3677864 : bool require_eh_edge_purge = false;
434 :
435 3677864 : if (stmt == orig_stmt)
436 : return false;
437 :
438 7036356 : gcc_assert (!gimple_has_lhs (orig_stmt) || !gimple_has_lhs (stmt)
439 : || gimple_get_lhs (orig_stmt) == gimple_get_lhs (stmt));
440 :
441 3677777 : gimple_set_location (stmt, gimple_location (orig_stmt));
442 3677777 : gimple_set_bb (stmt, gsi_bb (*gsi));
443 :
444 : /* Preserve EH region information from the original statement, if
445 : requested by the caller. */
446 3677777 : if (update_eh_info)
447 1071384 : require_eh_edge_purge = maybe_clean_or_replace_eh_stmt (orig_stmt, stmt);
448 :
449 3677777 : gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
450 :
451 : /* Free all the data flow information for ORIG_STMT. */
452 3677777 : gimple_set_bb (orig_stmt, NULL);
453 3677777 : gimple_remove_stmt_histograms (cfun, orig_stmt);
454 3677777 : delink_stmt_imm_use (orig_stmt);
455 :
456 3677777 : gsi_set_stmt (gsi, stmt);
457 3677777 : gimple_set_modified (stmt, true);
458 3677777 : update_modified_stmt (stmt);
459 3677777 : return require_eh_edge_purge;
460 : }
461 :
462 :
463 : /* Replace the statement pointed-to by GSI with the sequence SEQ.
464 : If UPDATE_EH_INFO is true, the exception handling information of
465 : the original statement is moved to the last statement of the new
466 : sequence. If the old statement is an assignment, then so must
467 : be the last statement of the new sequence, and they must have the
468 : same LHS. */
469 :
470 : void
471 206390 : gsi_replace_with_seq (gimple_stmt_iterator *gsi, gimple_seq seq,
472 : bool update_eh_info)
473 : {
474 206390 : if (gimple_seq_empty_p (seq))
475 : {
476 57 : gsi_remove (gsi, true);
477 57 : return;
478 : }
479 206333 : gimple_seq tail;
480 206333 : gimple_stmt_iterator lasti = gsi_last (seq);
481 206333 : gsi_split_seq_before (&lasti, &tail);
482 206333 : gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
483 206333 : gsi_replace (gsi, gsi_stmt (lasti), update_eh_info);
484 : }
485 :
486 :
487 : /* Insert statement STMT before the statement pointed-to by iterator I.
488 : M specifies how to update iterator I after insertion (see enum
489 : gsi_iterator_update).
490 :
491 : This function does not scan for new operands. It is provided for
492 : the use of the gimplifier, which manipulates statements for which
493 : def/use information has not yet been constructed. Most callers
494 : should use gsi_insert_before. */
495 :
496 : void
497 32477545 : gsi_insert_before_without_update (gimple_stmt_iterator *i, gimple *stmt,
498 : enum gsi_iterator_update m)
499 : {
500 32477545 : gsi_insert_seq_nodes_before (i, stmt, stmt, m);
501 32477545 : }
502 :
503 : /* Insert statement STMT before the statement pointed-to by iterator I.
504 : Update STMT's basic block and scan it for new operands. M
505 : specifies how to update iterator I after insertion (see enum
506 : gsi_iterator_update). */
507 :
508 : void
509 32446726 : gsi_insert_before (gimple_stmt_iterator *i, gimple *stmt,
510 : enum gsi_iterator_update m)
511 : {
512 32446726 : update_modified_stmt (stmt);
513 32446726 : gsi_insert_before_without_update (i, stmt, m);
514 32446726 : }
515 :
516 :
517 : /* Insert statement STMT after the statement pointed-to by iterator I.
518 : M specifies how to update iterator I after insertion (see enum
519 : gsi_iterator_update).
520 :
521 : This function does not scan for new operands. It is provided for
522 : the use of the gimplifier, which manipulates statements for which
523 : def/use information has not yet been constructed. Most callers
524 : should use gsi_insert_after. */
525 :
526 : void
527 359771101 : gsi_insert_after_without_update (gimple_stmt_iterator *i, gimple *stmt,
528 : enum gsi_iterator_update m)
529 : {
530 359771101 : gsi_insert_seq_nodes_after (i, stmt, stmt, m);
531 359771101 : }
532 :
533 :
534 : /* Insert statement STMT after the statement pointed-to by iterator I.
535 : Update STMT's basic block and scan it for new operands. M
536 : specifies how to update iterator I after insertion (see enum
537 : gsi_iterator_update). */
538 :
539 : void
540 178273177 : gsi_insert_after (gimple_stmt_iterator *i, gimple *stmt,
541 : enum gsi_iterator_update m)
542 : {
543 178273177 : update_modified_stmt (stmt);
544 178273177 : gsi_insert_after_without_update (i, stmt, m);
545 178273177 : }
546 :
547 :
548 : /* Remove the current stmt from the sequence. The iterator is updated
549 : to point to the next statement.
550 :
551 : REMOVE_PERMANENTLY is true when the statement is going to be removed
552 : from the IL and not reinserted elsewhere. In that case we remove the
553 : statement pointed to by iterator I from the EH tables, and free its
554 : operand caches. Otherwise we do not modify this information. Returns
555 : true whether EH edge cleanup is required. */
556 :
557 : bool
558 161997645 : gsi_remove (gimple_stmt_iterator *i, bool remove_permanently)
559 : {
560 161997645 : gimple_seq_node cur, next, prev;
561 161997645 : gimple *stmt = gsi_stmt (*i);
562 161997645 : bool require_eh_edge_purge = false;
563 :
564 : /* ??? Do we want to do this for non-permanent operation? */
565 161997645 : if (gimple_code (stmt) != GIMPLE_PHI)
566 143116773 : insert_debug_temps_for_defs (i);
567 :
568 161997645 : gimple_set_bb (stmt, NULL);
569 :
570 161997645 : if (remove_permanently)
571 : {
572 : /* Free all the data flow information for STMT. */
573 115667789 : delink_stmt_imm_use (stmt);
574 115667789 : gimple_set_modified (stmt, true);
575 :
576 115667789 : if (gimple_debug_nonbind_marker_p (stmt))
577 : /* We don't need this to be exact, but try to keep it at least
578 : close. */
579 4672122 : cfun->debug_marker_count--;
580 115667789 : require_eh_edge_purge = remove_stmt_from_eh_lp (stmt);
581 115667789 : gimple_remove_stmt_histograms (cfun, stmt);
582 : }
583 :
584 : /* Update the iterator and re-wire the links in I->SEQ. */
585 161997645 : cur = i->ptr;
586 161997645 : next = cur->next;
587 161997645 : prev = cur->prev;
588 : /* See gsi_set_stmt for why we don't reset prev/next of STMT. */
589 :
590 161997645 : if (next)
591 : /* Cur is not last. */
592 101474962 : next->prev = prev;
593 60522683 : else if (prev->next)
594 : /* Cur is last but not first. */
595 35886163 : gimple_seq_set_last (i->seq, prev);
596 :
597 161997645 : if (prev->next)
598 : /* Cur is not first. */
599 98262765 : prev->next = next;
600 : else
601 : /* Cur is first. */
602 63734880 : *i->seq = next;
603 :
604 161997645 : i->ptr = next;
605 :
606 161997645 : return require_eh_edge_purge;
607 : }
608 :
609 :
610 : /* Finds iterator for STMT. */
611 :
612 : gimple_stmt_iterator
613 68884404 : gsi_for_stmt (gimple *stmt)
614 : {
615 68884404 : gimple_stmt_iterator i;
616 68884404 : basic_block bb = gimple_bb (stmt);
617 :
618 68884404 : if (gimple_code (stmt) == GIMPLE_PHI)
619 5475515 : i = gsi_start_phis (bb);
620 : else
621 126817778 : i = gsi_start_bb (bb);
622 :
623 68884404 : i.ptr = stmt;
624 68884404 : return i;
625 : }
626 :
627 : /* Get an iterator for STMT, which is known to belong to SEQ. This is
628 : equivalent to starting at the beginning of SEQ and searching forward
629 : until STMT is found. */
630 :
631 : gimple_stmt_iterator
632 10228 : gsi_for_stmt (gimple *stmt, gimple_seq *seq)
633 : {
634 10228 : gimple_stmt_iterator i = gsi_start (*seq);
635 10228 : i.ptr = stmt;
636 10228 : return i;
637 : }
638 :
639 : /* Finds iterator for PHI. */
640 :
641 : gphi_iterator
642 0 : gsi_for_phi (gphi *phi)
643 : {
644 0 : gphi_iterator i;
645 0 : basic_block bb = gimple_bb (phi);
646 :
647 0 : i = gsi_start_phis (bb);
648 0 : i.ptr = phi;
649 :
650 0 : return i;
651 : }
652 :
653 : /* Move the statement at FROM so it comes right after the statement at TO. */
654 :
655 : void
656 337983 : gsi_move_after (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
657 : {
658 337983 : gimple *stmt = gsi_stmt (*from);
659 337983 : gsi_remove (from, false);
660 :
661 : /* We must have GSI_NEW_STMT here, as gsi_move_after is sometimes used to
662 : move statements to an empty block. */
663 337983 : gsi_insert_after (to, stmt, GSI_NEW_STMT);
664 337983 : }
665 :
666 :
667 : /* Move the statement at FROM so it comes right before the statement
668 : at TO using method M. M defaults to GSI_SAME_STMT. */
669 :
670 : void
671 15490892 : gsi_move_before (gimple_stmt_iterator *from, gimple_stmt_iterator *to,
672 : gsi_iterator_update m)
673 : {
674 15490892 : gimple *stmt = gsi_stmt (*from);
675 15490892 : gsi_remove (from, false);
676 :
677 : /* For consistency with gsi_move_after, it might be better to have
678 : GSI_NEW_STMT here; however, that breaks several places that expect
679 : that TO does not change. */
680 15490892 : gsi_insert_before (to, stmt, m);
681 15490892 : }
682 :
683 :
684 : /* Move the statement at FROM to the end of basic block BB. */
685 :
686 : void
687 150848 : gsi_move_to_bb_end (gimple_stmt_iterator *from, basic_block bb)
688 : {
689 150848 : gimple_stmt_iterator last = gsi_last_bb (bb);
690 150848 : gcc_checking_assert (gsi_bb (last) == bb);
691 :
692 : /* Have to check gsi_end_p because it could be an empty block. */
693 150848 : if (!gsi_end_p (last) && is_ctrl_stmt (gsi_stmt (last)))
694 11886 : gsi_move_before (from, &last);
695 : else
696 138962 : gsi_move_after (from, &last);
697 150848 : }
698 :
699 :
700 : /* Add STMT to the pending list of edge E. No actual insertion is
701 : made until a call to gsi_commit_edge_inserts () is made. */
702 :
703 : void
704 547369 : gsi_insert_on_edge (edge e, gimple *stmt)
705 : {
706 547369 : gimple_seq_add_stmt (&PENDING_STMT (e), stmt);
707 547369 : }
708 :
709 : /* Add the sequence of statements SEQ to the pending list of edge E.
710 : No actual insertion is made until a call to gsi_commit_edge_inserts
711 : is made. */
712 :
713 : void
714 24695 : gsi_insert_seq_on_edge (edge e, gimple_seq seq)
715 : {
716 24695 : gimple_seq_add_seq (&PENDING_STMT (e), seq);
717 24695 : }
718 :
719 : /* Return a new iterator pointing to the first statement in sequence of
720 : statements on edge E. Such statements need to be subsequently moved into a
721 : basic block by calling gsi_commit_edge_inserts. */
722 :
723 : gimple_stmt_iterator
724 129084 : gsi_start_edge (edge e)
725 : {
726 129084 : return gsi_start (PENDING_STMT (e));
727 : }
728 :
729 : /* Insert the statement pointed-to by GSI into edge E. Every attempt
730 : is made to place the statement in an existing basic block, but
731 : sometimes that isn't possible. When it isn't possible, the edge is
732 : split and the statement is added to the new block.
733 :
734 : In all cases, the returned *GSI points to the correct location. The
735 : return value is true if insertion should be done after the location,
736 : or false if it should be done before the location. If a new basic block
737 : has to be created, it is stored in *NEW_BB. */
738 :
739 : static bool
740 1534205 : gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi,
741 : basic_block *new_bb)
742 : {
743 1534205 : basic_block dest, src;
744 1534205 : gimple *tmp;
745 :
746 1534205 : dest = e->dest;
747 :
748 : /* If the destination has one predecessor which has no PHI nodes,
749 : insert there. Except for the exit block.
750 :
751 : The requirement for no PHI nodes could be relaxed. Basically we
752 : would have to examine the PHIs to prove that none of them used
753 : the value set by the statement we want to insert on E. That
754 : hardly seems worth the effort. */
755 1581517 : restart:
756 1581517 : if (single_pred_p (dest)
757 243574 : && gimple_seq_empty_p (phi_nodes (dest))
758 1820400 : && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
759 : {
760 238152 : *gsi = gsi_start_bb (dest);
761 238152 : if (gsi_end_p (*gsi))
762 : return true;
763 :
764 : /* Make sure we insert after any leading labels. */
765 195059 : tmp = gsi_stmt (*gsi);
766 195059 : while (gimple_code (tmp) == GIMPLE_LABEL)
767 : {
768 10963 : gsi_next (gsi);
769 10963 : if (gsi_end_p (*gsi))
770 : break;
771 195059 : tmp = gsi_stmt (*gsi);
772 : }
773 :
774 193506 : if (gsi_end_p (*gsi))
775 : {
776 9410 : *gsi = gsi_last_bb (dest);
777 9410 : return true;
778 : }
779 : else
780 : return false;
781 : }
782 :
783 : /* If the source has one successor, the edge is not abnormal and
784 : the last statement does not end a basic block, insert there.
785 : Except for the entry block. */
786 1343365 : src = e->src;
787 1343365 : if ((e->flags & EDGE_ABNORMAL) == 0
788 1343365 : && (single_succ_p (src)
789 : /* Do not count a fake edge as successor as added to infinite
790 : loops by connect_infinite_loops_to_exit. */
791 47060 : || (EDGE_COUNT (src->succs) == 2
792 47032 : && (EDGE_SUCC (src, 0)->flags & EDGE_FAKE
793 47032 : || EDGE_SUCC (src, 1)->flags & EDGE_FAKE)))
794 2639722 : && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
795 : {
796 1296058 : *gsi = gsi_last_bb (src);
797 1296058 : if (gsi_end_p (*gsi))
798 : return true;
799 :
800 818660 : tmp = gsi_stmt (*gsi);
801 818660 : if (is_gimple_debug (tmp))
802 : {
803 68500 : gimple_stmt_iterator si = *gsi;
804 68500 : gsi_prev_nondebug (&si);
805 68500 : if (!gsi_end_p (si))
806 61240 : tmp = gsi_stmt (si);
807 : /* If we don't have a BB-ending nondebug stmt, we want to
808 : insert after the trailing debug stmts. Otherwise, we may
809 : insert before the BB-ending nondebug stmt, or split the
810 : edge. */
811 68500 : if (!stmt_ends_bb_p (tmp))
812 68500 : return true;
813 0 : *gsi = si;
814 : }
815 750160 : else if (!stmt_ends_bb_p (tmp))
816 : return true;
817 :
818 891 : switch (gimple_code (tmp))
819 : {
820 : case GIMPLE_RETURN:
821 : case GIMPLE_RESX:
822 : return false;
823 : default:
824 : break;
825 : }
826 : }
827 :
828 : /* Otherwise, create a new basic block, and split this edge. */
829 47312 : dest = split_edge (e);
830 47312 : if (new_bb)
831 388 : *new_bb = dest;
832 47312 : e = single_pred_edge (dest);
833 47312 : goto restart;
834 : }
835 :
836 :
837 : /* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts. If a new
838 : block has to be created, it is returned. */
839 :
840 : basic_block
841 5457 : gsi_insert_on_edge_immediate (edge e, gimple *stmt)
842 : {
843 5457 : gimple_stmt_iterator gsi;
844 5457 : basic_block new_bb = NULL;
845 5457 : bool ins_after;
846 :
847 5457 : gcc_assert (!PENDING_STMT (e));
848 :
849 5457 : ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
850 :
851 5457 : update_call_edge_frequencies (stmt, gsi.bb);
852 :
853 5457 : if (ins_after)
854 2467 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
855 : else
856 2990 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
857 :
858 5457 : return new_bb;
859 : }
860 :
861 : /* Insert STMTS on edge E. If a new block has to be created, it
862 : is returned. */
863 :
864 : basic_block
865 1213863 : gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts)
866 : {
867 1213863 : gimple_stmt_iterator gsi;
868 1213863 : basic_block new_bb = NULL;
869 1213863 : bool ins_after;
870 :
871 1213863 : gcc_assert (!PENDING_STMT (e));
872 :
873 1213863 : ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
874 1213863 : update_call_edge_frequencies (gimple_seq_first (stmts), gsi.bb);
875 :
876 1213863 : if (ins_after)
877 1159963 : gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
878 : else
879 53900 : gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
880 :
881 1213863 : return new_bb;
882 : }
883 :
884 : /* This routine will commit all pending edge insertions, creating any new
885 : basic blocks which are necessary. */
886 :
887 : void
888 2935711 : gsi_commit_edge_inserts (void)
889 : {
890 2935711 : basic_block bb;
891 2935711 : edge e;
892 2935711 : edge_iterator ei;
893 :
894 2935711 : gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
895 : NULL);
896 :
897 50514940 : FOR_EACH_BB_FN (bb, cfun)
898 114851014 : FOR_EACH_EDGE (e, ei, bb->succs)
899 67271785 : gsi_commit_one_edge_insert (e, NULL);
900 2935711 : }
901 :
902 :
903 : /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
904 : to this block, otherwise set it to NULL. */
905 :
906 : void
907 70234801 : gsi_commit_one_edge_insert (edge e, basic_block *new_bb)
908 : {
909 70234801 : if (new_bb)
910 0 : *new_bb = NULL;
911 :
912 70234801 : if (PENDING_STMT (e))
913 : {
914 314885 : gimple_stmt_iterator gsi;
915 314885 : gimple_seq seq = PENDING_STMT (e);
916 314885 : bool ins_after;
917 :
918 314885 : PENDING_STMT (e) = NULL;
919 :
920 314885 : ins_after = gimple_find_edge_insert_loc (e, &gsi, new_bb);
921 314885 : update_call_edge_frequencies (gimple_seq_first (seq), gsi.bb);
922 :
923 314885 : if (ins_after)
924 186793 : gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
925 : else
926 128092 : gsi_insert_seq_before (&gsi, seq, GSI_NEW_STMT);
927 : }
928 70234801 : }
929 :
930 : /* Returns iterator at the start of the list of phi nodes of BB. */
931 :
932 : gphi_iterator
933 11915139594 : gsi_start_phis (basic_block bb)
934 : {
935 11915139594 : gimple_seq *pseq = phi_nodes_ptr (bb);
936 :
937 : /* Adapted from gsi_start. */
938 11915139594 : gphi_iterator i;
939 :
940 11915139594 : i.ptr = gimple_seq_first (*pseq);
941 11915139594 : i.seq = pseq;
942 11915139594 : i.bb = i.ptr ? gimple_bb (i.ptr) : NULL;
943 :
944 11915139594 : return i;
945 : }
946 :
947 : /* Helper function for gsi_safe_insert_before and gsi_safe_insert_seq_before.
948 : Find edge to insert statements before returns_twice call at the start of BB,
949 : if there isn't just one, split the bb and adjust PHIs to ensure that. */
950 :
951 : static edge
952 269 : edge_before_returns_twice_call (basic_block bb)
953 : {
954 269 : gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
955 269 : gcc_checking_assert (is_gimple_call (gsi_stmt (gsi))
956 : && (gimple_call_flags (gsi_stmt (gsi))
957 : & ECF_RETURNS_TWICE) != 0);
958 269 : edge_iterator ei;
959 269 : edge e, ad_edge = NULL, other_edge = NULL;
960 269 : bool split = false;
961 871 : FOR_EACH_EDGE (e, ei, bb->preds)
962 : {
963 602 : if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) == EDGE_ABNORMAL)
964 : {
965 269 : gimple_stmt_iterator gsi
966 269 : = gsi_start_nondebug_after_labels_bb (e->src);
967 269 : gimple *ad = gsi_stmt (gsi);
968 269 : if (ad && gimple_call_internal_p (ad, IFN_ABNORMAL_DISPATCHER))
969 : {
970 269 : gcc_checking_assert (ad_edge == NULL);
971 269 : ad_edge = e;
972 269 : continue;
973 : }
974 : }
975 333 : if (other_edge || e->flags & (EDGE_ABNORMAL | EDGE_EH))
976 64 : split = true;
977 : other_edge = e;
978 : }
979 269 : gcc_checking_assert (ad_edge);
980 269 : if (other_edge == NULL)
981 : split = true;
982 269 : if (split)
983 : {
984 33 : other_edge = split_block_after_labels (bb);
985 33 : e = make_edge (ad_edge->src, other_edge->dest, EDGE_ABNORMAL);
986 33 : for (gphi_iterator gsi = gsi_start_phis (other_edge->src);
987 115 : !gsi_end_p (gsi); gsi_next (&gsi))
988 : {
989 82 : gphi *phi = gsi.phi ();
990 82 : tree lhs = gimple_phi_result (phi);
991 82 : tree new_lhs = copy_ssa_name (lhs);
992 82 : gimple_phi_set_result (phi, new_lhs);
993 82 : gphi *new_phi = create_phi_node (lhs, other_edge->dest);
994 82 : add_phi_arg (new_phi, new_lhs, other_edge, UNKNOWN_LOCATION);
995 82 : add_phi_arg (new_phi, gimple_phi_arg_def_from_edge (phi, ad_edge),
996 : e, gimple_phi_arg_location_from_edge (phi, ad_edge));
997 : }
998 33 : e->flags = ad_edge->flags;
999 33 : e->probability = ad_edge->probability;
1000 33 : remove_edge (ad_edge);
1001 33 : if (dom_info_available_p (CDI_DOMINATORS))
1002 : {
1003 12 : set_immediate_dominator (CDI_DOMINATORS, other_edge->src,
1004 : recompute_dominator (CDI_DOMINATORS,
1005 : other_edge->src));
1006 12 : set_immediate_dominator (CDI_DOMINATORS, other_edge->dest,
1007 : recompute_dominator (CDI_DOMINATORS,
1008 : other_edge->dest));
1009 : }
1010 : }
1011 269 : return other_edge;
1012 : }
1013 :
1014 : /* Helper function for gsi_safe_insert_before and gsi_safe_insert_seq_before.
1015 : Replace SSA_NAME uses in G if they are PHI results of PHIs on E->dest
1016 : bb with the corresponding PHI argument from E edge. */
1017 :
1018 : static void
1019 269 : adjust_before_returns_twice_call (edge e, gimple *g)
1020 : {
1021 269 : use_operand_p use_p;
1022 269 : ssa_op_iter iter;
1023 269 : bool m = false;
1024 585 : FOR_EACH_SSA_USE_OPERAND (use_p, g, iter, SSA_OP_USE)
1025 : {
1026 316 : tree s = USE_FROM_PTR (use_p);
1027 316 : if (SSA_NAME_DEF_STMT (s)
1028 316 : && gimple_code (SSA_NAME_DEF_STMT (s)) == GIMPLE_PHI
1029 493 : && gimple_bb (SSA_NAME_DEF_STMT (s)) == e->dest)
1030 : {
1031 177 : tree r = gimple_phi_arg_def_from_edge (SSA_NAME_DEF_STMT (s), e);
1032 177 : SET_USE (use_p, unshare_expr (r));
1033 177 : m = true;
1034 : }
1035 : }
1036 269 : if (m)
1037 177 : update_stmt (g);
1038 269 : }
1039 :
1040 : /* Insert G stmt before ITER and keep ITER pointing to the same statement
1041 : as before. If ITER is a returns_twice call, insert it on an appropriate
1042 : edge instead. */
1043 :
1044 : void
1045 36189 : gsi_safe_insert_before (gimple_stmt_iterator *iter, gimple *g)
1046 : {
1047 36189 : gimple *stmt = gsi_stmt (*iter);
1048 36189 : if (stmt
1049 35171 : && is_gimple_call (stmt)
1050 1044 : && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE) != 0
1051 36389 : && bb_has_abnormal_pred (gsi_bb (*iter)))
1052 : {
1053 199 : edge e = edge_before_returns_twice_call (gsi_bb (*iter));
1054 199 : basic_block new_bb = gsi_insert_on_edge_immediate (e, g);
1055 199 : if (new_bb)
1056 33 : e = single_succ_edge (new_bb);
1057 199 : adjust_before_returns_twice_call (e, g);
1058 199 : *iter = gsi_for_stmt (stmt);
1059 : }
1060 : else
1061 35990 : gsi_insert_before (iter, g, GSI_SAME_STMT);
1062 36189 : }
1063 :
1064 : /* Similarly for sequence SEQ. */
1065 :
1066 : void
1067 4394 : gsi_safe_insert_seq_before (gimple_stmt_iterator *iter, gimple_seq seq)
1068 : {
1069 4394 : if (gimple_seq_empty_p (seq))
1070 : return;
1071 3178 : gimple *stmt = gsi_stmt (*iter);
1072 3178 : if (stmt
1073 3178 : && is_gimple_call (stmt)
1074 82 : && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE) != 0
1075 3248 : && bb_has_abnormal_pred (gsi_bb (*iter)))
1076 : {
1077 70 : edge e = edge_before_returns_twice_call (gsi_bb (*iter));
1078 70 : gimple *f = gimple_seq_first_stmt (seq);
1079 70 : gimple *l = gimple_seq_last_stmt (seq);
1080 70 : basic_block new_bb = gsi_insert_seq_on_edge_immediate (e, seq);
1081 70 : if (new_bb)
1082 0 : e = single_succ_edge (new_bb);
1083 70 : for (gimple_stmt_iterator gsi = gsi_for_stmt (f); ; gsi_next (&gsi))
1084 : {
1085 70 : gimple *g = gsi_stmt (gsi);
1086 70 : adjust_before_returns_twice_call (e, g);
1087 70 : if (g == l)
1088 : break;
1089 : }
1090 70 : *iter = gsi_for_stmt (stmt);
1091 : }
1092 : else
1093 3108 : gsi_insert_seq_before (iter, seq, GSI_SAME_STMT);
1094 : }
|
