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