Branch data Line data Source code
1 : : /* Iterator routines for GIMPLE statements.
2 : : Copyright (C) 2007-2025 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 : 213251188 : update_modified_stmt (gimple *stmt)
42 : : {
43 : 213251188 : if (!ssa_operands_active (cfun))
44 : : return;
45 : 189782773 : update_stmt_if_modified (stmt);
46 : : }
47 : :
48 : :
49 : : /* Mark the statements in SEQ as modified, and update them. */
50 : :
51 : : void
52 : 49406828 : update_modified_stmts (gimple_seq seq)
53 : : {
54 : 49406828 : gimple_stmt_iterator gsi;
55 : :
56 : 49406828 : if (!ssa_operands_active (cfun))
57 : 49406828 : return;
58 : 125164183 : for (gsi = gsi_start (seq); !gsi_end_p (gsi); gsi_next (&gsi))
59 : 99953237 : 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 : 188804635 : update_bb_for_stmts (gimple_seq_node first, gimple_seq_node last,
68 : : basic_block bb)
69 : : {
70 : 188804635 : gimple_seq_node n;
71 : :
72 : 274321192 : for (n = first; n; n = n->next)
73 : : {
74 : 274321192 : gimple_set_bb (n, bb);
75 : 274321192 : if (n == last)
76 : : break;
77 : : }
78 : 188804635 : }
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 : 1557369 : update_call_edge_frequencies (gimple_seq_node first, basic_block bb)
85 : : {
86 : 1557369 : struct cgraph_node *cfun_node = NULL;
87 : 1557369 : gimple_seq_node n;
88 : :
89 : 4766814 : for (n = first; n ; n = n->next)
90 : 3209445 : if (is_gimple_call (n))
91 : : {
92 : 7774 : 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 : 7774 : if (cfun_node == NULL)
97 : 6382 : cfun_node = cgraph_node::get (current_function_decl);
98 : :
99 : 7774 : e = cfun_node->get_edge (n);
100 : 7774 : if (e != NULL)
101 : 970 : e->count = bb->count;
102 : : }
103 : 1557369 : }
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 : 48830607 : 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 : 48830607 : basic_block bb;
121 : 48830607 : gimple_seq_node cur = i->ptr;
122 : :
123 : 48830607 : gcc_assert (!cur || cur->prev);
124 : :
125 : 48830607 : if ((bb = gsi_bb (*i)) != NULL)
126 : 36014284 : update_bb_for_stmts (first, last, bb);
127 : :
128 : : /* Link SEQ before CUR in the sequence. */
129 : 48830607 : if (cur)
130 : : {
131 : 44780367 : first->prev = cur->prev;
132 : 44780367 : if (first->prev->next)
133 : 27801006 : first->prev->next = first;
134 : : else
135 : 16979361 : gimple_seq_set_first (i->seq, first);
136 : 44780367 : last->next = cur;
137 : 44780367 : cur->prev = last;
138 : : }
139 : : else
140 : : {
141 : 4050240 : 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 : 4050240 : last->next = NULL;
149 : 4050240 : if (itlast)
150 : : {
151 : 1176361 : first->prev = itlast;
152 : 1176361 : itlast->next = first;
153 : : }
154 : : else
155 : 2873879 : gimple_seq_set_first (i->seq, first);
156 : 4050240 : gimple_seq_set_last (i->seq, last);
157 : : }
158 : :
159 : : /* Update the iterator, if requested. */
160 : 48830607 : switch (mode)
161 : : {
162 : 5473441 : case GSI_NEW_STMT:
163 : 5473441 : case GSI_CONTINUE_LINKING:
164 : 5473441 : i->ptr = first;
165 : 5473441 : 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 : 48830607 : }
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 : 22891040 : gsi_insert_seq_before_without_update (gimple_stmt_iterator *i, gimple_seq seq,
188 : : enum gsi_iterator_update mode)
189 : : {
190 : 22891040 : gimple_seq_node first, last;
191 : :
192 : 22891040 : if (seq == NULL)
193 : : return;
194 : :
195 : : /* Don't allow inserting a sequence into itself. */
196 : 17875417 : gcc_assert (seq != *i->seq);
197 : :
198 : 17875417 : first = gimple_seq_first (seq);
199 : 17875417 : last = gimple_seq_last (seq);
200 : :
201 : : /* Empty sequences need no work. */
202 : 17875417 : if (!first || !last)
203 : : {
204 : 0 : gcc_assert (first == last);
205 : : return;
206 : : }
207 : :
208 : 17875417 : 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 : 18914723 : gsi_insert_seq_before (gimple_stmt_iterator *i, gimple_seq seq,
219 : : enum gsi_iterator_update mode)
220 : : {
221 : 18914723 : update_modified_stmts (seq);
222 : 18914723 : gsi_insert_seq_before_without_update (i, seq, mode);
223 : 18914723 : }
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 : 395372427 : 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 : 395372427 : basic_block bb;
242 : 395372427 : gimple_seq_node cur = i->ptr;
243 : :
244 : 395372427 : 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 : 395372427 : if ((bb = gsi_bb (*i)) != NULL)
249 : 152790351 : update_bb_for_stmts (first, last, bb);
250 : :
251 : : /* Link SEQ after CUR. */
252 : 395372427 : if (cur)
253 : : {
254 : 232197783 : last->next = cur->next;
255 : 232197783 : if (last->next)
256 : : {
257 : 9590235 : last->next->prev = last;
258 : : }
259 : : else
260 : 222607548 : gimple_seq_set_last (i->seq, last);
261 : 232197783 : first->prev = cur;
262 : 232197783 : cur->next = first;
263 : : }
264 : : else
265 : : {
266 : 163174644 : gcc_assert (!gimple_seq_last (*i->seq));
267 : 163174644 : last->next = NULL;
268 : 163174644 : gimple_seq_set_first (i->seq, first);
269 : 163174644 : gimple_seq_set_last (i->seq, last);
270 : : }
271 : :
272 : : /* Update the iterator, if requested. */
273 : 395372427 : switch (m)
274 : : {
275 : 376554654 : case GSI_NEW_STMT:
276 : 376554654 : i->ptr = first;
277 : 376554654 : break;
278 : 6337668 : case GSI_LAST_NEW_STMT:
279 : 6337668 : case GSI_CONTINUE_LINKING:
280 : 6337668 : i->ptr = last;
281 : 6337668 : break;
282 : 12480105 : case GSI_SAME_STMT:
283 : 12480105 : gcc_assert (cur);
284 : : break;
285 : 0 : default:
286 : 0 : gcc_unreachable ();
287 : : }
288 : 395372427 : }
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 : 37205628 : gsi_insert_seq_after_without_update (gimple_stmt_iterator *i, gimple_seq seq,
301 : : enum gsi_iterator_update mode)
302 : : {
303 : 37205628 : gimple_seq_node first, last;
304 : :
305 : 37205628 : if (seq == NULL)
306 : : return;
307 : :
308 : : /* Don't allow inserting a sequence into itself. */
309 : 35135971 : gcc_assert (seq != *i->seq);
310 : :
311 : 35135971 : first = gimple_seq_first (seq);
312 : 35135971 : last = gimple_seq_last (seq);
313 : :
314 : : /* Empty sequences need no work. */
315 : 35135971 : if (!first || !last)
316 : : {
317 : 0 : gcc_assert (first == last);
318 : : return;
319 : : }
320 : :
321 : 35135971 : 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 : 30439083 : gsi_insert_seq_after (gimple_stmt_iterator *i, gimple_seq seq,
331 : : enum gsi_iterator_update mode)
332 : : {
333 : 30439083 : update_modified_stmts (seq);
334 : 30439083 : gsi_insert_seq_after_without_update (i, seq, mode);
335 : 30439083 : }
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 : 608971 : gsi_split_seq_after (gimple_stmt_iterator i)
343 : : {
344 : 608971 : gimple_seq_node cur, next;
345 : 608971 : gimple_seq *pold_seq, new_seq;
346 : :
347 : 608971 : cur = i.ptr;
348 : :
349 : : /* How can we possibly split after the end, or before the beginning? */
350 : 608971 : gcc_assert (cur && cur->next);
351 : 608971 : next = cur->next;
352 : :
353 : 608971 : pold_seq = i.seq;
354 : :
355 : 608971 : gimple_seq_set_first (&new_seq, next);
356 : 608971 : gimple_seq_set_last (&new_seq, gimple_seq_last (*pold_seq));
357 : 608971 : gimple_seq_set_last (pold_seq, cur);
358 : 608971 : cur->next = NULL;
359 : :
360 : 608971 : 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 : 5339969 : gsi_set_stmt (gimple_stmt_iterator *gsi, gimple *stmt)
370 : : {
371 : 5339969 : gimple *orig_stmt = gsi_stmt (*gsi);
372 : 5339969 : gimple *prev, *next;
373 : :
374 : 5339969 : stmt->next = next = orig_stmt->next;
375 : 5339969 : 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 : 5339969 : if (prev->next)
380 : 3823350 : prev->next = stmt;
381 : : else
382 : 1516619 : gimple_seq_set_first (gsi->seq, stmt);
383 : 5339969 : if (next)
384 : 3456899 : next->prev = stmt;
385 : : else
386 : 1883070 : gimple_seq_set_last (gsi->seq, stmt);
387 : :
388 : 5339969 : gsi->ptr = stmt;
389 : 5339969 : }
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 : 24643836 : gsi_split_seq_before (gimple_stmt_iterator *i, gimple_seq *pnew_seq)
397 : : {
398 : 24643836 : gimple_seq_node cur, prev;
399 : 24643836 : gimple_seq old_seq;
400 : :
401 : 24643836 : cur = i->ptr;
402 : :
403 : : /* How can we possibly split after the end? */
404 : 24643836 : gcc_assert (cur);
405 : 24643836 : prev = cur->prev;
406 : :
407 : 24643836 : old_seq = *i->seq;
408 : 24643836 : if (!prev->next)
409 : 1745246 : *i->seq = NULL;
410 : 24643836 : i->seq = pnew_seq;
411 : :
412 : : /* Set the limits on NEW_SEQ. */
413 : 24643836 : gimple_seq_set_first (pnew_seq, cur);
414 : 49287672 : gimple_seq_set_last (pnew_seq, gimple_seq_last (old_seq));
415 : :
416 : : /* Cut OLD_SEQ before I. */
417 : 24643836 : gimple_seq_set_last (&old_seq, prev);
418 : 24643836 : if (prev->next)
419 : 22898590 : prev->next = NULL;
420 : 24643836 : }
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 : 3599043 : gsi_replace (gimple_stmt_iterator *gsi, gimple *stmt, bool update_eh_info)
431 : : {
432 : 3599043 : gimple *orig_stmt = gsi_stmt (*gsi);
433 : 3599043 : bool require_eh_edge_purge = false;
434 : :
435 : 3599043 : if (stmt == orig_stmt)
436 : : return false;
437 : :
438 : 6855067 : gcc_assert (!gimple_has_lhs (orig_stmt) || !gimple_has_lhs (stmt)
439 : : || gimple_get_lhs (orig_stmt) == gimple_get_lhs (stmt));
440 : :
441 : 3598956 : gimple_set_location (stmt, gimple_location (orig_stmt));
442 : 3598956 : gimple_set_bb (stmt, gsi_bb (*gsi));
443 : :
444 : : /* Preserve EH region information from the original statement, if
445 : : requested by the caller. */
446 : 3598956 : if (update_eh_info)
447 : 968956 : require_eh_edge_purge = maybe_clean_or_replace_eh_stmt (orig_stmt, stmt);
448 : :
449 : 3598956 : gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
450 : :
451 : : /* Free all the data flow information for ORIG_STMT. */
452 : 3598956 : gimple_set_bb (orig_stmt, NULL);
453 : 3598956 : gimple_remove_stmt_histograms (cfun, orig_stmt);
454 : 3598956 : delink_stmt_imm_use (orig_stmt);
455 : :
456 : 3598956 : gsi_set_stmt (gsi, stmt);
457 : 3598956 : gimple_set_modified (stmt, true);
458 : 3598956 : update_modified_stmt (stmt);
459 : 3598956 : 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 : 202824 : gsi_replace_with_seq (gimple_stmt_iterator *gsi, gimple_seq seq,
472 : : bool update_eh_info)
473 : : {
474 : 202824 : if (gimple_seq_empty_p (seq))
475 : : {
476 : 57 : gsi_remove (gsi, true);
477 : 57 : return;
478 : : }
479 : 202767 : gimple_seq tail;
480 : 202767 : gimple_stmt_iterator lasti = gsi_last (seq);
481 : 202767 : gsi_split_seq_before (&lasti, &tail);
482 : 202767 : gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
483 : 202767 : 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 : 30955190 : gsi_insert_before_without_update (gimple_stmt_iterator *i, gimple *stmt,
498 : : enum gsi_iterator_update m)
499 : : {
500 : 30955190 : gsi_insert_seq_nodes_before (i, stmt, stmt, m);
501 : 30955190 : }
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 : 30924243 : gsi_insert_before (gimple_stmt_iterator *i, gimple *stmt,
510 : : enum gsi_iterator_update m)
511 : : {
512 : 30924243 : update_modified_stmt (stmt);
513 : 30924243 : gsi_insert_before_without_update (i, stmt, m);
514 : 30924243 : }
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 : 360236456 : gsi_insert_after_without_update (gimple_stmt_iterator *i, gimple *stmt,
528 : : enum gsi_iterator_update m)
529 : : {
530 : 360236456 : gsi_insert_seq_nodes_after (i, stmt, stmt, m);
531 : 360236456 : }
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 : 178727989 : gsi_insert_after (gimple_stmt_iterator *i, gimple *stmt,
541 : : enum gsi_iterator_update m)
542 : : {
543 : 178727989 : update_modified_stmt (stmt);
544 : 178727989 : gsi_insert_after_without_update (i, stmt, m);
545 : 178727989 : }
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 : 160249112 : gsi_remove (gimple_stmt_iterator *i, bool remove_permanently)
559 : : {
560 : 160249112 : gimple_seq_node cur, next, prev;
561 : 160249112 : gimple *stmt = gsi_stmt (*i);
562 : 160249112 : bool require_eh_edge_purge = false;
563 : :
564 : : /* ??? Do we want to do this for non-permanent operation? */
565 : 160249112 : if (gimple_code (stmt) != GIMPLE_PHI)
566 : 140402515 : insert_debug_temps_for_defs (i);
567 : :
568 : 160249112 : gimple_set_bb (stmt, NULL);
569 : :
570 : 160249112 : if (remove_permanently)
571 : : {
572 : : /* Free all the data flow information for STMT. */
573 : 114844299 : delink_stmt_imm_use (stmt);
574 : 114844299 : gimple_set_modified (stmt, true);
575 : :
576 : 114844299 : 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 : 4369015 : cfun->debug_marker_count--;
580 : 114844299 : require_eh_edge_purge = remove_stmt_from_eh_lp (stmt);
581 : 114844299 : gimple_remove_stmt_histograms (cfun, stmt);
582 : : }
583 : :
584 : : /* Update the iterator and re-wire the links in I->SEQ. */
585 : 160249112 : cur = i->ptr;
586 : 160249112 : next = cur->next;
587 : 160249112 : prev = cur->prev;
588 : : /* See gsi_set_stmt for why we don't reset prev/next of STMT. */
589 : :
590 : 160249112 : if (next)
591 : : /* Cur is not last. */
592 : 100799098 : next->prev = prev;
593 : 59450014 : else if (prev->next)
594 : : /* Cur is last but not first. */
595 : 34664254 : gimple_seq_set_last (i->seq, prev);
596 : :
597 : 160249112 : if (prev->next)
598 : : /* Cur is not first. */
599 : 97624498 : prev->next = next;
600 : : else
601 : : /* Cur is first. */
602 : 62624614 : *i->seq = next;
603 : :
604 : 160249112 : i->ptr = next;
605 : :
606 : 160249112 : return require_eh_edge_purge;
607 : : }
608 : :
609 : :
610 : : /* Finds iterator for STMT. */
611 : :
612 : : gimple_stmt_iterator
613 : 70171693 : gsi_for_stmt (gimple *stmt)
614 : : {
615 : 70171693 : gimple_stmt_iterator i;
616 : 70171693 : basic_block bb = gimple_bb (stmt);
617 : :
618 : 70171693 : if (gimple_code (stmt) == GIMPLE_PHI)
619 : 5620113 : i = gsi_start_phis (bb);
620 : : else
621 : 129103160 : i = gsi_start_bb (bb);
622 : :
623 : 70171693 : i.ptr = stmt;
624 : 70171693 : 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 : 10558 : gsi_for_stmt (gimple *stmt, gimple_seq *seq)
633 : : {
634 : 10558 : gimple_stmt_iterator i = gsi_start (*seq);
635 : 10558 : i.ptr = stmt;
636 : 10558 : 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 : 358076 : gsi_move_after (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
657 : : {
658 : 358076 : gimple *stmt = gsi_stmt (*from);
659 : 358076 : 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 : 358076 : gsi_insert_after (to, stmt, GSI_NEW_STMT);
664 : 358076 : }
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 : 13409921 : gsi_move_before (gimple_stmt_iterator *from, gimple_stmt_iterator *to,
672 : : gsi_iterator_update m)
673 : : {
674 : 13409921 : gimple *stmt = gsi_stmt (*from);
675 : 13409921 : 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 : 13409921 : gsi_insert_before (to, stmt, m);
681 : 13409921 : }
682 : :
683 : :
684 : : /* Move the statement at FROM to the end of basic block BB. */
685 : :
686 : : void
687 : 161491 : gsi_move_to_bb_end (gimple_stmt_iterator *from, basic_block bb)
688 : : {
689 : 161491 : gimple_stmt_iterator last = gsi_last_bb (bb);
690 : 161491 : gcc_checking_assert (gsi_bb (last) == bb);
691 : :
692 : : /* Have to check gsi_end_p because it could be an empty block. */
693 : 161491 : if (!gsi_end_p (last) && is_ctrl_stmt (gsi_stmt (last)))
694 : 12254 : gsi_move_before (from, &last);
695 : : else
696 : 149237 : gsi_move_after (from, &last);
697 : 161491 : }
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 : 547533 : gsi_insert_on_edge (edge e, gimple *stmt)
705 : : {
706 : 547533 : gimple_seq_add_stmt (&PENDING_STMT (e), stmt);
707 : 547533 : }
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 : 24132 : gsi_insert_seq_on_edge (edge e, gimple_seq seq)
715 : : {
716 : 24132 : gimple_seq_add_seq (&PENDING_STMT (e), seq);
717 : 24132 : }
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 : 134962 : gsi_start_edge (edge e)
725 : : {
726 : 134962 : 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 : 1557369 : gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi,
741 : : basic_block *new_bb)
742 : : {
743 : 1557369 : basic_block dest, src;
744 : 1557369 : gimple *tmp;
745 : :
746 : 1557369 : 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 : 1605527 : restart:
756 : 1605527 : if (single_pred_p (dest)
757 : 254564 : && gimple_seq_empty_p (phi_nodes (dest))
758 : 1855399 : && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
759 : : {
760 : 249141 : *gsi = gsi_start_bb (dest);
761 : 249141 : if (gsi_end_p (*gsi))
762 : : return true;
763 : :
764 : : /* Make sure we insert after any leading labels. */
765 : 204319 : tmp = gsi_stmt (*gsi);
766 : 204319 : while (gimple_code (tmp) == GIMPLE_LABEL)
767 : : {
768 : 11647 : gsi_next (gsi);
769 : 11647 : if (gsi_end_p (*gsi))
770 : : break;
771 : 204319 : tmp = gsi_stmt (*gsi);
772 : : }
773 : :
774 : 202109 : if (gsi_end_p (*gsi))
775 : : {
776 : 9437 : *gsi = gsi_last_bb (dest);
777 : 9437 : 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 : 1356386 : src = e->src;
787 : 1356386 : if ((e->flags & EDGE_ABNORMAL) == 0
788 : 1356386 : && (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 : 47884 : || (EDGE_COUNT (src->succs) == 2
792 : 47850 : && (EDGE_SUCC (src, 0)->flags & EDGE_FAKE
793 : 47850 : || EDGE_SUCC (src, 1)->flags & EDGE_FAKE)))
794 : 2664931 : && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
795 : : {
796 : 1308234 : *gsi = gsi_last_bb (src);
797 : 1308234 : if (gsi_end_p (*gsi))
798 : : return true;
799 : :
800 : 826763 : tmp = gsi_stmt (*gsi);
801 : 826763 : if (is_gimple_debug (tmp))
802 : : {
803 : 73272 : gimple_stmt_iterator si = *gsi;
804 : 73272 : gsi_prev_nondebug (&si);
805 : 73272 : if (!gsi_end_p (si))
806 : 63614 : 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 : 73272 : if (!stmt_ends_bb_p (tmp))
812 : 73272 : return true;
813 : 0 : *gsi = si;
814 : : }
815 : 753491 : else if (!stmt_ends_bb_p (tmp))
816 : : return true;
817 : :
818 : 892 : 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 : 48158 : dest = split_edge (e);
830 : 48158 : if (new_bb)
831 : 395 : *new_bb = dest;
832 : 48158 : e = single_pred_edge (dest);
833 : 48158 : 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 : 5284 : gsi_insert_on_edge_immediate (edge e, gimple *stmt)
842 : : {
843 : 5284 : gimple_stmt_iterator gsi;
844 : 5284 : basic_block new_bb = NULL;
845 : 5284 : bool ins_after;
846 : :
847 : 5284 : gcc_assert (!PENDING_STMT (e));
848 : :
849 : 5284 : ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
850 : :
851 : 5284 : update_call_edge_frequencies (stmt, gsi.bb);
852 : :
853 : 5284 : if (ins_after)
854 : 2337 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
855 : : else
856 : 2947 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
857 : :
858 : 5284 : 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 : 1227367 : gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts)
866 : : {
867 : 1227367 : gimple_stmt_iterator gsi;
868 : 1227367 : basic_block new_bb = NULL;
869 : 1227367 : bool ins_after;
870 : :
871 : 1227367 : gcc_assert (!PENDING_STMT (e));
872 : :
873 : 1227367 : ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
874 : 1227367 : update_call_edge_frequencies (gimple_seq_first (stmts), gsi.bb);
875 : :
876 : 1227367 : if (ins_after)
877 : 1170937 : gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
878 : : else
879 : 56430 : gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
880 : :
881 : 1227367 : 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 : 2968744 : gsi_commit_edge_inserts (void)
889 : : {
890 : 2968744 : basic_block bb;
891 : 2968744 : edge e;
892 : 2968744 : edge_iterator ei;
893 : :
894 : 2968744 : gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
895 : : NULL);
896 : :
897 : 51901077 : FOR_EACH_BB_FN (bb, cfun)
898 : 118238826 : FOR_EACH_EDGE (e, ei, bb->succs)
899 : 69306493 : gsi_commit_one_edge_insert (e, NULL);
900 : 2968744 : }
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 : 72304698 : gsi_commit_one_edge_insert (edge e, basic_block *new_bb)
908 : : {
909 : 72304698 : if (new_bb)
910 : 0 : *new_bb = NULL;
911 : :
912 : 72304698 : if (PENDING_STMT (e))
913 : : {
914 : 324718 : gimple_stmt_iterator gsi;
915 : 324718 : gimple_seq seq = PENDING_STMT (e);
916 : 324718 : bool ins_after;
917 : :
918 : 324718 : PENDING_STMT (e) = NULL;
919 : :
920 : 324718 : ins_after = gimple_find_edge_insert_loc (e, &gsi, new_bb);
921 : 324718 : update_call_edge_frequencies (gimple_seq_first (seq), gsi.bb);
922 : :
923 : 324718 : if (ins_after)
924 : 190537 : gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
925 : : else
926 : 134181 : gsi_insert_seq_before (&gsi, seq, GSI_NEW_STMT);
927 : : }
928 : 72304698 : }
929 : :
930 : : /* Returns iterator at the start of the list of phi nodes of BB. */
931 : :
932 : : gphi_iterator
933 : 12090398446 : gsi_start_phis (basic_block bb)
934 : : {
935 : 12090398446 : gimple_seq *pseq = phi_nodes_ptr (bb);
936 : :
937 : : /* Adapted from gsi_start. */
938 : 12090398446 : gphi_iterator i;
939 : :
940 : 12090398446 : i.ptr = gimple_seq_first (*pseq);
941 : 12090398446 : i.seq = pseq;
942 : 12090398446 : i.bb = i.ptr ? gimple_bb (i.ptr) : NULL;
943 : :
944 : 12090398446 : 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 : 35346 : gsi_safe_insert_before (gimple_stmt_iterator *iter, gimple *g)
1046 : : {
1047 : 35346 : gimple *stmt = gsi_stmt (*iter);
1048 : 35346 : if (stmt
1049 : 34328 : && is_gimple_call (stmt)
1050 : 1009 : && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE) != 0
1051 : 35546 : && 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 : 35147 : gsi_insert_before (iter, g, GSI_SAME_STMT);
1062 : 35346 : }
1063 : :
1064 : : /* Similarly for sequence SEQ. */
1065 : :
1066 : : void
1067 : 4346 : gsi_safe_insert_seq_before (gimple_stmt_iterator *iter, gimple_seq seq)
1068 : : {
1069 : 4346 : if (gimple_seq_empty_p (seq))
1070 : : return;
1071 : 3166 : gimple *stmt = gsi_stmt (*iter);
1072 : 3166 : if (stmt
1073 : 3166 : && is_gimple_call (stmt)
1074 : 82 : && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE) != 0
1075 : 3236 : && 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 : 3096 : gsi_insert_seq_before (iter, seq, GSI_SAME_STMT);
1094 : : }
|
