Branch data Line data Source code
1 : : /* Iterator routines for GIMPLE statements.
2 : : Copyright (C) 2007-2024 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 : 183971509 : update_modified_stmt (gimple *stmt)
42 : : {
43 : 183971509 : if (!ssa_operands_active (cfun))
44 : : return;
45 : 161921437 : update_stmt_if_modified (stmt);
46 : : }
47 : :
48 : :
49 : : /* Mark the statements in SEQ as modified, and update them. */
50 : :
51 : : void
52 : 46586895 : update_modified_stmts (gimple_seq seq)
53 : : {
54 : 46586895 : gimple_stmt_iterator gsi;
55 : :
56 : 46586895 : if (!ssa_operands_active (cfun))
57 : 46586895 : return;
58 : 106705162 : for (gsi = gsi_start (seq); !gsi_end_p (gsi); gsi_next (&gsi))
59 : 83060482 : 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 : 161406313 : update_bb_for_stmts (gimple_seq_node first, gimple_seq_node last,
68 : : basic_block bb)
69 : : {
70 : 161406313 : gimple_seq_node n;
71 : :
72 : 232986485 : for (n = first; n; n = n->next)
73 : : {
74 : 232986485 : gimple_set_bb (n, bb);
75 : 232986485 : if (n == last)
76 : : break;
77 : : }
78 : 161406313 : }
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 : 1424197 : update_call_edge_frequencies (gimple_seq_node first, basic_block bb)
85 : : {
86 : 1424197 : struct cgraph_node *cfun_node = NULL;
87 : 1424197 : gimple_seq_node n;
88 : :
89 : 4355922 : for (n = first; n ; n = n->next)
90 : 2931725 : if (is_gimple_call (n))
91 : : {
92 : 7055 : 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 : 7055 : if (cfun_node == NULL)
97 : 5742 : cfun_node = cgraph_node::get (current_function_decl);
98 : :
99 : 7055 : e = cfun_node->get_edge (n);
100 : 7055 : if (e != NULL)
101 : 963 : e->count = bb->count;
102 : : }
103 : 1424197 : }
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 : 47418670 : 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 : 47418670 : basic_block bb;
121 : 47418670 : gimple_seq_node cur = i->ptr;
122 : :
123 : 47418670 : gcc_assert (!cur || cur->prev);
124 : :
125 : 47418670 : if ((bb = gsi_bb (*i)) != NULL)
126 : 35462521 : update_bb_for_stmts (first, last, bb);
127 : :
128 : : /* Link SEQ before CUR in the sequence. */
129 : 47418670 : if (cur)
130 : : {
131 : 43372882 : first->prev = cur->prev;
132 : 43372882 : if (first->prev->next)
133 : 28510807 : first->prev->next = first;
134 : : else
135 : 14862075 : gimple_seq_set_first (i->seq, first);
136 : 43372882 : last->next = cur;
137 : 43372882 : cur->prev = last;
138 : : }
139 : : else
140 : : {
141 : 4045788 : 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 : 4045788 : last->next = NULL;
149 : 4045788 : if (itlast)
150 : : {
151 : 1503353 : first->prev = itlast;
152 : 1503353 : itlast->next = first;
153 : : }
154 : : else
155 : 2542435 : gimple_seq_set_first (i->seq, first);
156 : 4045788 : gimple_seq_set_last (i->seq, last);
157 : : }
158 : :
159 : : /* Update the iterator, if requested. */
160 : 47418670 : switch (mode)
161 : : {
162 : 4574942 : case GSI_NEW_STMT:
163 : 4574942 : case GSI_CONTINUE_LINKING:
164 : 4574942 : i->ptr = first;
165 : 4574942 : 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 : 47418670 : }
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 : 24025638 : gsi_insert_seq_before_without_update (gimple_stmt_iterator *i, gimple_seq seq,
188 : : enum gsi_iterator_update mode)
189 : : {
190 : 24025638 : gimple_seq_node first, last;
191 : :
192 : 24025638 : if (seq == NULL)
193 : : return;
194 : :
195 : : /* Don't allow inserting a sequence into itself. */
196 : 15457288 : gcc_assert (seq != *i->seq);
197 : :
198 : 15457288 : first = gimple_seq_first (seq);
199 : 15457288 : last = gimple_seq_last (seq);
200 : :
201 : : /* Empty sequences need no work. */
202 : 15457288 : if (!first || !last)
203 : : {
204 : 0 : gcc_assert (first == last);
205 : : return;
206 : : }
207 : :
208 : 15457288 : 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 : 20740602 : gsi_insert_seq_before (gimple_stmt_iterator *i, gimple_seq seq,
219 : : enum gsi_iterator_update mode)
220 : : {
221 : 20740602 : update_modified_stmts (seq);
222 : 20740602 : gsi_insert_seq_before_without_update (i, seq, mode);
223 : 20740602 : }
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 : 339061510 : 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 : 339061510 : basic_block bb;
242 : 339061510 : gimple_seq_node cur = i->ptr;
243 : :
244 : 339061510 : 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 : 339061510 : if ((bb = gsi_bb (*i)) != NULL)
249 : 125943792 : update_bb_for_stmts (first, last, bb);
250 : :
251 : : /* Link SEQ after CUR. */
252 : 339061510 : if (cur)
253 : : {
254 : 201235909 : last->next = cur->next;
255 : 201235909 : if (last->next)
256 : : {
257 : 9273934 : last->next->prev = last;
258 : : }
259 : : else
260 : 191961975 : gimple_seq_set_last (i->seq, last);
261 : 201235909 : first->prev = cur;
262 : 201235909 : cur->next = first;
263 : : }
264 : : else
265 : : {
266 : 137825601 : gcc_assert (!gimple_seq_last (*i->seq));
267 : 137825601 : last->next = NULL;
268 : 137825601 : gimple_seq_set_first (i->seq, first);
269 : 137825601 : gimple_seq_set_last (i->seq, last);
270 : : }
271 : :
272 : : /* Update the iterator, if requested. */
273 : 339061510 : switch (m)
274 : : {
275 : 322252333 : case GSI_NEW_STMT:
276 : 322252333 : i->ptr = first;
277 : 322252333 : break;
278 : 5779782 : case GSI_LAST_NEW_STMT:
279 : 5779782 : case GSI_CONTINUE_LINKING:
280 : 5779782 : i->ptr = last;
281 : 5779782 : break;
282 : 11029395 : case GSI_SAME_STMT:
283 : 11029395 : gcc_assert (cur);
284 : : break;
285 : 0 : default:
286 : 0 : gcc_unreachable ();
287 : : }
288 : 339061510 : }
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 : 32169005 : gsi_insert_seq_after_without_update (gimple_stmt_iterator *i, gimple_seq seq,
301 : : enum gsi_iterator_update mode)
302 : : {
303 : 32169005 : gimple_seq_node first, last;
304 : :
305 : 32169005 : if (seq == NULL)
306 : : return;
307 : :
308 : : /* Don't allow inserting a sequence into itself. */
309 : 30953471 : gcc_assert (seq != *i->seq);
310 : :
311 : 30953471 : first = gimple_seq_first (seq);
312 : 30953471 : last = gimple_seq_last (seq);
313 : :
314 : : /* Empty sequences need no work. */
315 : 30953471 : if (!first || !last)
316 : : {
317 : 0 : gcc_assert (first == last);
318 : : return;
319 : : }
320 : :
321 : 30953471 : 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 : 25793740 : gsi_insert_seq_after (gimple_stmt_iterator *i, gimple_seq seq,
331 : : enum gsi_iterator_update mode)
332 : : {
333 : 25793740 : update_modified_stmts (seq);
334 : 25793740 : gsi_insert_seq_after_without_update (i, seq, mode);
335 : 25793740 : }
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 : 500876 : gsi_split_seq_after (gimple_stmt_iterator i)
343 : : {
344 : 500876 : gimple_seq_node cur, next;
345 : 500876 : gimple_seq *pold_seq, new_seq;
346 : :
347 : 500876 : cur = i.ptr;
348 : :
349 : : /* How can we possibly split after the end, or before the beginning? */
350 : 500876 : gcc_assert (cur && cur->next);
351 : 500876 : next = cur->next;
352 : :
353 : 500876 : pold_seq = i.seq;
354 : :
355 : 500876 : gimple_seq_set_first (&new_seq, next);
356 : 500876 : gimple_seq_set_last (&new_seq, gimple_seq_last (*pold_seq));
357 : 500876 : gimple_seq_set_last (pold_seq, cur);
358 : 500876 : cur->next = NULL;
359 : :
360 : 500876 : 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 : 4246061 : gsi_set_stmt (gimple_stmt_iterator *gsi, gimple *stmt)
370 : : {
371 : 4246061 : gimple *orig_stmt = gsi_stmt (*gsi);
372 : 4246061 : gimple *prev, *next;
373 : :
374 : 4246061 : stmt->next = next = orig_stmt->next;
375 : 4246061 : 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 : 4246061 : if (prev->next)
380 : 3014899 : prev->next = stmt;
381 : : else
382 : 1231162 : gimple_seq_set_first (gsi->seq, stmt);
383 : 4246061 : if (next)
384 : 2744794 : next->prev = stmt;
385 : : else
386 : 1501267 : gimple_seq_set_last (gsi->seq, stmt);
387 : :
388 : 4246061 : gsi->ptr = stmt;
389 : 4246061 : }
390 : :
391 : :
392 : : /* Move all statements in the sequence before I to a new sequence.
393 : : Return this new sequence. I is set to the head of the new list. */
394 : :
395 : : void
396 : 21992916 : gsi_split_seq_before (gimple_stmt_iterator *i, gimple_seq *pnew_seq)
397 : : {
398 : 21992916 : gimple_seq_node cur, prev;
399 : 21992916 : gimple_seq old_seq;
400 : :
401 : 21992916 : cur = i->ptr;
402 : :
403 : : /* How can we possibly split after the end? */
404 : 21992916 : gcc_assert (cur);
405 : 21992916 : prev = cur->prev;
406 : :
407 : 21992916 : old_seq = *i->seq;
408 : 21992916 : if (!prev->next)
409 : 1234675 : *i->seq = NULL;
410 : 21992916 : i->seq = pnew_seq;
411 : :
412 : : /* Set the limits on NEW_SEQ. */
413 : 21992916 : gimple_seq_set_first (pnew_seq, cur);
414 : 43985832 : gimple_seq_set_last (pnew_seq, gimple_seq_last (old_seq));
415 : :
416 : : /* Cut OLD_SEQ before I. */
417 : 21992916 : gimple_seq_set_last (&old_seq, prev);
418 : 21992916 : if (prev->next)
419 : 20758241 : prev->next = NULL;
420 : 21992916 : }
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 : 3092420 : gsi_replace (gimple_stmt_iterator *gsi, gimple *stmt, bool update_eh_info)
431 : : {
432 : 3092420 : gimple *orig_stmt = gsi_stmt (*gsi);
433 : 3092420 : bool require_eh_edge_purge = false;
434 : :
435 : 3092420 : if (stmt == orig_stmt)
436 : : return false;
437 : :
438 : 5852807 : gcc_assert (!gimple_has_lhs (orig_stmt) || !gimple_has_lhs (stmt)
439 : : || gimple_get_lhs (orig_stmt) == gimple_get_lhs (stmt));
440 : :
441 : 3092331 : gimple_set_location (stmt, gimple_location (orig_stmt));
442 : 3092331 : gimple_set_bb (stmt, gsi_bb (*gsi));
443 : :
444 : : /* Preserve EH region information from the original statement, if
445 : : requested by the caller. */
446 : 3092331 : if (update_eh_info)
447 : 847372 : require_eh_edge_purge = maybe_clean_or_replace_eh_stmt (orig_stmt, stmt);
448 : :
449 : 3092331 : gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
450 : :
451 : : /* Free all the data flow information for ORIG_STMT. */
452 : 3092331 : gimple_set_bb (orig_stmt, NULL);
453 : 3092331 : gimple_remove_stmt_histograms (cfun, orig_stmt);
454 : 3092331 : delink_stmt_imm_use (orig_stmt);
455 : :
456 : 3092331 : gsi_set_stmt (gsi, stmt);
457 : 3092331 : gimple_set_modified (stmt, true);
458 : 3092331 : update_modified_stmt (stmt);
459 : 3092331 : 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 : 174242 : gsi_replace_with_seq (gimple_stmt_iterator *gsi, gimple_seq seq,
472 : : bool update_eh_info)
473 : : {
474 : 174242 : gimple_stmt_iterator seqi;
475 : 174242 : gimple *last;
476 : 174242 : if (gimple_seq_empty_p (seq))
477 : : {
478 : 51 : gsi_remove (gsi, true);
479 : 51 : return;
480 : : }
481 : 174191 : seqi = gsi_last (seq);
482 : 174191 : last = gsi_stmt (seqi);
483 : 174191 : gsi_remove (&seqi, false);
484 : 174191 : gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
485 : 174191 : gsi_replace (gsi, last, update_eh_info);
486 : : }
487 : :
488 : :
489 : : /* Insert statement STMT before the statement pointed-to by iterator I.
490 : : M specifies how to update iterator I after insertion (see enum
491 : : gsi_iterator_update).
492 : :
493 : : This function does not scan for new operands. It is provided for
494 : : the use of the gimplifier, which manipulates statements for which
495 : : def/use information has not yet been constructed. Most callers
496 : : should use gsi_insert_before. */
497 : :
498 : : void
499 : 31961382 : gsi_insert_before_without_update (gimple_stmt_iterator *i, gimple *stmt,
500 : : enum gsi_iterator_update m)
501 : : {
502 : 31961382 : gsi_insert_seq_nodes_before (i, stmt, stmt, m);
503 : 31961382 : }
504 : :
505 : : /* Insert statement STMT before the statement pointed-to by iterator I.
506 : : Update STMT's basic block and scan it for new operands. M
507 : : specifies how to update iterator I after insertion (see enum
508 : : gsi_iterator_update). */
509 : :
510 : : void
511 : 31930411 : gsi_insert_before (gimple_stmt_iterator *i, gimple *stmt,
512 : : enum gsi_iterator_update m)
513 : : {
514 : 31930411 : update_modified_stmt (stmt);
515 : 31930411 : gsi_insert_before_without_update (i, stmt, m);
516 : 31930411 : }
517 : :
518 : :
519 : : /* Insert statement STMT after the statement pointed-to by iterator I.
520 : : M specifies how to update iterator I after insertion (see enum
521 : : gsi_iterator_update).
522 : :
523 : : This function does not scan for new operands. It is provided for
524 : : the use of the gimplifier, which manipulates statements for which
525 : : def/use information has not yet been constructed. Most callers
526 : : should use gsi_insert_after. */
527 : :
528 : : void
529 : 308108039 : gsi_insert_after_without_update (gimple_stmt_iterator *i, gimple *stmt,
530 : : enum gsi_iterator_update m)
531 : : {
532 : 308108039 : gsi_insert_seq_nodes_after (i, stmt, stmt, m);
533 : 308108039 : }
534 : :
535 : :
536 : : /* Insert statement STMT after the statement pointed-to by iterator I.
537 : : Update STMT's basic block and scan it for new operands. M
538 : : specifies how to update iterator I after insertion (see enum
539 : : gsi_iterator_update). */
540 : :
541 : : void
542 : 148948767 : gsi_insert_after (gimple_stmt_iterator *i, gimple *stmt,
543 : : enum gsi_iterator_update m)
544 : : {
545 : 148948767 : update_modified_stmt (stmt);
546 : 148948767 : gsi_insert_after_without_update (i, stmt, m);
547 : 148948767 : }
548 : :
549 : :
550 : : /* Remove the current stmt from the sequence. The iterator is updated
551 : : to point to the next statement.
552 : :
553 : : REMOVE_PERMANENTLY is true when the statement is going to be removed
554 : : from the IL and not reinserted elsewhere. In that case we remove the
555 : : statement pointed to by iterator I from the EH tables, and free its
556 : : operand caches. Otherwise we do not modify this information. Returns
557 : : true whether EH edge cleanup is required. */
558 : :
559 : : bool
560 : 145810128 : gsi_remove (gimple_stmt_iterator *i, bool remove_permanently)
561 : : {
562 : 145810128 : gimple_seq_node cur, next, prev;
563 : 145810128 : gimple *stmt = gsi_stmt (*i);
564 : 145810128 : bool require_eh_edge_purge = false;
565 : :
566 : : /* ??? Do we want to do this for non-permanent operation? */
567 : 145810128 : if (gimple_code (stmt) != GIMPLE_PHI)
568 : 128818136 : insert_debug_temps_for_defs (i);
569 : :
570 : 145810128 : gimple_set_bb (stmt, NULL);
571 : :
572 : 145810128 : if (remove_permanently)
573 : : {
574 : : /* Free all the data flow information for STMT. */
575 : 100758670 : delink_stmt_imm_use (stmt);
576 : 100758670 : gimple_set_modified (stmt, true);
577 : :
578 : 100758670 : if (gimple_debug_nonbind_marker_p (stmt))
579 : : /* We don't need this to be exact, but try to keep it at least
580 : : close. */
581 : 3467453 : cfun->debug_marker_count--;
582 : 100758670 : require_eh_edge_purge = remove_stmt_from_eh_lp (stmt);
583 : 100758670 : gimple_remove_stmt_histograms (cfun, stmt);
584 : : }
585 : :
586 : : /* Update the iterator and re-wire the links in I->SEQ. */
587 : 145810128 : cur = i->ptr;
588 : 145810128 : next = cur->next;
589 : 145810128 : prev = cur->prev;
590 : : /* See gsi_set_stmt for why we don't reset prev/next of STMT. */
591 : :
592 : 145810128 : if (next)
593 : : /* Cur is not last. */
594 : 92925096 : next->prev = prev;
595 : 52885032 : else if (prev->next)
596 : : /* Cur is last but not first. */
597 : 30367227 : gimple_seq_set_last (i->seq, prev);
598 : :
599 : 145810128 : if (prev->next)
600 : : /* Cur is not first. */
601 : 85187345 : prev->next = next;
602 : : else
603 : : /* Cur is first. */
604 : 60622783 : *i->seq = next;
605 : :
606 : 145810128 : i->ptr = next;
607 : :
608 : 145810128 : return require_eh_edge_purge;
609 : : }
610 : :
611 : :
612 : : /* Finds iterator for STMT. */
613 : :
614 : : gimple_stmt_iterator
615 : 63564984 : gsi_for_stmt (gimple *stmt)
616 : : {
617 : 63564984 : gimple_stmt_iterator i;
618 : 63564984 : basic_block bb = gimple_bb (stmt);
619 : :
620 : 63564984 : if (gimple_code (stmt) == GIMPLE_PHI)
621 : 5337517 : i = gsi_start_phis (bb);
622 : : else
623 : 116454934 : i = gsi_start_bb (bb);
624 : :
625 : 63564984 : i.ptr = stmt;
626 : 63564984 : return i;
627 : : }
628 : :
629 : : /* Get an iterator for STMT, which is known to belong to SEQ. This is
630 : : equivalent to starting at the beginning of SEQ and searching forward
631 : : until STMT is found. */
632 : :
633 : : gimple_stmt_iterator
634 : 11143 : gsi_for_stmt (gimple *stmt, gimple_seq *seq)
635 : : {
636 : 11143 : gimple_stmt_iterator i = gsi_start (*seq);
637 : 11143 : i.ptr = stmt;
638 : 11143 : return i;
639 : : }
640 : :
641 : : /* Finds iterator for PHI. */
642 : :
643 : : gphi_iterator
644 : 0 : gsi_for_phi (gphi *phi)
645 : : {
646 : 0 : gphi_iterator i;
647 : 0 : basic_block bb = gimple_bb (phi);
648 : :
649 : 0 : i = gsi_start_phis (bb);
650 : 0 : i.ptr = phi;
651 : :
652 : 0 : return i;
653 : : }
654 : :
655 : : /* Move the statement at FROM so it comes right after the statement at TO. */
656 : :
657 : : void
658 : 1096385 : gsi_move_after (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
659 : : {
660 : 1096385 : gimple *stmt = gsi_stmt (*from);
661 : 1096385 : gsi_remove (from, false);
662 : :
663 : : /* We must have GSI_NEW_STMT here, as gsi_move_after is sometimes used to
664 : : move statements to an empty block. */
665 : 1096385 : gsi_insert_after (to, stmt, GSI_NEW_STMT);
666 : 1096385 : }
667 : :
668 : :
669 : : /* Move the statement at FROM so it comes right before the statement
670 : : at TO using method M. M defaults to GSI_SAME_STMT. */
671 : :
672 : : void
673 : 15752945 : gsi_move_before (gimple_stmt_iterator *from, gimple_stmt_iterator *to,
674 : : gsi_iterator_update m)
675 : : {
676 : 15752945 : gimple *stmt = gsi_stmt (*from);
677 : 15752945 : gsi_remove (from, false);
678 : :
679 : : /* For consistency with gsi_move_after, it might be better to have
680 : : GSI_NEW_STMT here; however, that breaks several places that expect
681 : : that TO does not change. */
682 : 15752945 : gsi_insert_before (to, stmt, m);
683 : 15752945 : }
684 : :
685 : :
686 : : /* Move the statement at FROM to the end of basic block BB. */
687 : :
688 : : void
689 : 127460 : gsi_move_to_bb_end (gimple_stmt_iterator *from, basic_block bb)
690 : : {
691 : 127460 : gimple_stmt_iterator last = gsi_last_bb (bb);
692 : 127460 : gcc_checking_assert (gsi_bb (last) == bb);
693 : :
694 : : /* Have to check gsi_end_p because it could be an empty block. */
695 : 127460 : if (!gsi_end_p (last) && is_ctrl_stmt (gsi_stmt (last)))
696 : 11190 : gsi_move_before (from, &last);
697 : : else
698 : 116270 : gsi_move_after (from, &last);
699 : 127460 : }
700 : :
701 : :
702 : : /* Add STMT to the pending list of edge E. No actual insertion is
703 : : made until a call to gsi_commit_edge_inserts () is made. */
704 : :
705 : : void
706 : 482214 : gsi_insert_on_edge (edge e, gimple *stmt)
707 : : {
708 : 482214 : gimple_seq_add_stmt (&PENDING_STMT (e), stmt);
709 : 482214 : }
710 : :
711 : : /* Add the sequence of statements SEQ to the pending list of edge E.
712 : : No actual insertion is made until a call to gsi_commit_edge_inserts
713 : : is made. */
714 : :
715 : : void
716 : 22771 : gsi_insert_seq_on_edge (edge e, gimple_seq seq)
717 : : {
718 : 22771 : gimple_seq_add_seq (&PENDING_STMT (e), seq);
719 : 22771 : }
720 : :
721 : : /* Return a new iterator pointing to the first statement in sequence of
722 : : statements on edge E. Such statements need to be subsequently moved into a
723 : : basic block by calling gsi_commit_edge_inserts. */
724 : :
725 : : gimple_stmt_iterator
726 : 132158 : gsi_start_edge (edge e)
727 : : {
728 : 132158 : return gsi_start (PENDING_STMT (e));
729 : : }
730 : :
731 : : /* Insert the statement pointed-to by GSI into edge E. Every attempt
732 : : is made to place the statement in an existing basic block, but
733 : : sometimes that isn't possible. When it isn't possible, the edge is
734 : : split and the statement is added to the new block.
735 : :
736 : : In all cases, the returned *GSI points to the correct location. The
737 : : return value is true if insertion should be done after the location,
738 : : or false if it should be done before the location. If a new basic block
739 : : has to be created, it is stored in *NEW_BB. */
740 : :
741 : : static bool
742 : 1424197 : gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi,
743 : : basic_block *new_bb)
744 : : {
745 : 1424197 : basic_block dest, src;
746 : 1424197 : gimple *tmp;
747 : :
748 : 1424197 : dest = e->dest;
749 : :
750 : : /* If the destination has one predecessor which has no PHI nodes,
751 : : insert there. Except for the exit block.
752 : :
753 : : The requirement for no PHI nodes could be relaxed. Basically we
754 : : would have to examine the PHIs to prove that none of them used
755 : : the value set by the statement we want to insert on E. That
756 : : hardly seems worth the effort. */
757 : 1467151 : restart:
758 : 1467151 : if (single_pred_p (dest)
759 : 236400 : && gimple_seq_empty_p (phi_nodes (dest))
760 : 1698669 : && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
761 : : {
762 : 230787 : *gsi = gsi_start_bb (dest);
763 : 230787 : if (gsi_end_p (*gsi))
764 : : return true;
765 : :
766 : : /* Make sure we insert after any leading labels. */
767 : 190021 : tmp = gsi_stmt (*gsi);
768 : 190021 : while (gimple_code (tmp) == GIMPLE_LABEL)
769 : : {
770 : 8354 : gsi_next (gsi);
771 : 8354 : if (gsi_end_p (*gsi))
772 : : break;
773 : 190021 : tmp = gsi_stmt (*gsi);
774 : : }
775 : :
776 : 188598 : if (gsi_end_p (*gsi))
777 : : {
778 : 6931 : *gsi = gsi_last_bb (dest);
779 : 6931 : return true;
780 : : }
781 : : else
782 : : return false;
783 : : }
784 : :
785 : : /* If the source has one successor, the edge is not abnormal and
786 : : the last statement does not end a basic block, insert there.
787 : : Except for the entry block. */
788 : 1236364 : src = e->src;
789 : 1236364 : if ((e->flags & EDGE_ABNORMAL) == 0
790 : 1236364 : && (single_succ_p (src)
791 : : /* Do not count a fake edge as successor as added to infinite
792 : : loops by connect_infinite_loops_to_exit. */
793 : 42702 : || (EDGE_COUNT (src->succs) == 2
794 : 42680 : && (EDGE_SUCC (src, 0)->flags & EDGE_FAKE
795 : 42680 : || EDGE_SUCC (src, 1)->flags & EDGE_FAKE)))
796 : 2430073 : && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
797 : : {
798 : 1193415 : *gsi = gsi_last_bb (src);
799 : 1193415 : if (gsi_end_p (*gsi))
800 : : return true;
801 : :
802 : 763973 : tmp = gsi_stmt (*gsi);
803 : 763973 : if (is_gimple_debug (tmp))
804 : : {
805 : 60239 : gimple_stmt_iterator si = *gsi;
806 : 60239 : gsi_prev_nondebug (&si);
807 : 60239 : if (!gsi_end_p (si))
808 : 51364 : tmp = gsi_stmt (si);
809 : : /* If we don't have a BB-ending nondebug stmt, we want to
810 : : insert after the trailing debug stmts. Otherwise, we may
811 : : insert before the BB-ending nondebug stmt, or split the
812 : : edge. */
813 : 60239 : if (!stmt_ends_bb_p (tmp))
814 : 60239 : return true;
815 : 0 : *gsi = si;
816 : : }
817 : 703734 : else if (!stmt_ends_bb_p (tmp))
818 : : return true;
819 : :
820 : 890 : switch (gimple_code (tmp))
821 : : {
822 : : case GIMPLE_RETURN:
823 : : case GIMPLE_RESX:
824 : : return false;
825 : : default:
826 : : break;
827 : : }
828 : : }
829 : :
830 : : /* Otherwise, create a new basic block, and split this edge. */
831 : 42954 : dest = split_edge (e);
832 : 42954 : if (new_bb)
833 : 384 : *new_bb = dest;
834 : 42954 : e = single_pred_edge (dest);
835 : 42954 : goto restart;
836 : : }
837 : :
838 : :
839 : : /* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts. If a new
840 : : block has to be created, it is returned. */
841 : :
842 : : basic_block
843 : 4894 : gsi_insert_on_edge_immediate (edge e, gimple *stmt)
844 : : {
845 : 4894 : gimple_stmt_iterator gsi;
846 : 4894 : basic_block new_bb = NULL;
847 : 4894 : bool ins_after;
848 : :
849 : 4894 : gcc_assert (!PENDING_STMT (e));
850 : :
851 : 4894 : ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
852 : :
853 : 4894 : update_call_edge_frequencies (stmt, gsi.bb);
854 : :
855 : 4894 : if (ins_after)
856 : 1967 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
857 : : else
858 : 2927 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
859 : :
860 : 4894 : return new_bb;
861 : : }
862 : :
863 : : /* Insert STMTS on edge E. If a new block has to be created, it
864 : : is returned. */
865 : :
866 : : basic_block
867 : 1134565 : gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts)
868 : : {
869 : 1134565 : gimple_stmt_iterator gsi;
870 : 1134565 : basic_block new_bb = NULL;
871 : 1134565 : bool ins_after;
872 : :
873 : 1134565 : gcc_assert (!PENDING_STMT (e));
874 : :
875 : 1134565 : ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
876 : 1134565 : update_call_edge_frequencies (gimple_seq_first (stmts), gsi.bb);
877 : :
878 : 1134565 : if (ins_after)
879 : 1086487 : gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
880 : : else
881 : 48078 : gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
882 : :
883 : 1134565 : return new_bb;
884 : : }
885 : :
886 : : /* This routine will commit all pending edge insertions, creating any new
887 : : basic blocks which are necessary. */
888 : :
889 : : void
890 : 2818377 : gsi_commit_edge_inserts (void)
891 : : {
892 : 2818377 : basic_block bb;
893 : 2818377 : edge e;
894 : 2818377 : edge_iterator ei;
895 : :
896 : 2818377 : gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
897 : : NULL);
898 : :
899 : 48392177 : FOR_EACH_BB_FN (bb, cfun)
900 : 109939307 : FOR_EACH_EDGE (e, ei, bb->succs)
901 : 64365507 : gsi_commit_one_edge_insert (e, NULL);
902 : 2818377 : }
903 : :
904 : :
905 : : /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
906 : : to this block, otherwise set it to NULL. */
907 : :
908 : : void
909 : 67209811 : gsi_commit_one_edge_insert (edge e, basic_block *new_bb)
910 : : {
911 : 67209811 : if (new_bb)
912 : 0 : *new_bb = NULL;
913 : :
914 : 67209811 : if (PENDING_STMT (e))
915 : : {
916 : 284738 : gimple_stmt_iterator gsi;
917 : 284738 : gimple_seq seq = PENDING_STMT (e);
918 : 284738 : bool ins_after;
919 : :
920 : 284738 : PENDING_STMT (e) = NULL;
921 : :
922 : 284738 : ins_after = gimple_find_edge_insert_loc (e, &gsi, new_bb);
923 : 284738 : update_call_edge_frequencies (gimple_seq_first (seq), gsi.bb);
924 : :
925 : 284738 : if (ins_after)
926 : 153191 : gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
927 : : else
928 : 131547 : gsi_insert_seq_before (&gsi, seq, GSI_NEW_STMT);
929 : : }
930 : 67209811 : }
931 : :
932 : : /* Returns iterator at the start of the list of phi nodes of BB. */
933 : :
934 : : gphi_iterator
935 : 11033577755 : gsi_start_phis (basic_block bb)
936 : : {
937 : 11033577755 : gimple_seq *pseq = phi_nodes_ptr (bb);
938 : :
939 : : /* Adapted from gsi_start. */
940 : 11033577755 : gphi_iterator i;
941 : :
942 : 11033577755 : i.ptr = gimple_seq_first (*pseq);
943 : 11033577755 : i.seq = pseq;
944 : 11033577755 : i.bb = i.ptr ? gimple_bb (i.ptr) : NULL;
945 : :
946 : 11033577755 : return i;
947 : : }
948 : :
949 : : /* Helper function for gsi_safe_insert_before and gsi_safe_insert_seq_before.
950 : : Find edge to insert statements before returns_twice call at the start of BB,
951 : : if there isn't just one, split the bb and adjust PHIs to ensure that. */
952 : :
953 : : static edge
954 : 269 : edge_before_returns_twice_call (basic_block bb)
955 : : {
956 : 269 : gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
957 : 269 : gcc_checking_assert (is_gimple_call (gsi_stmt (gsi))
958 : : && (gimple_call_flags (gsi_stmt (gsi))
959 : : & ECF_RETURNS_TWICE) != 0);
960 : 269 : edge_iterator ei;
961 : 269 : edge e, ad_edge = NULL, other_edge = NULL;
962 : 269 : bool split = false;
963 : 871 : FOR_EACH_EDGE (e, ei, bb->preds)
964 : : {
965 : 602 : if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) == EDGE_ABNORMAL)
966 : : {
967 : 269 : gimple_stmt_iterator gsi
968 : 269 : = gsi_start_nondebug_after_labels_bb (e->src);
969 : 269 : gimple *ad = gsi_stmt (gsi);
970 : 269 : if (ad && gimple_call_internal_p (ad, IFN_ABNORMAL_DISPATCHER))
971 : : {
972 : 269 : gcc_checking_assert (ad_edge == NULL);
973 : 269 : ad_edge = e;
974 : 269 : continue;
975 : : }
976 : : }
977 : 333 : if (other_edge || e->flags & (EDGE_ABNORMAL | EDGE_EH))
978 : 64 : split = true;
979 : : other_edge = e;
980 : : }
981 : 269 : gcc_checking_assert (ad_edge);
982 : 269 : if (other_edge == NULL)
983 : : split = true;
984 : 269 : if (split)
985 : : {
986 : 33 : other_edge = split_block_after_labels (bb);
987 : 33 : e = make_edge (ad_edge->src, other_edge->dest, EDGE_ABNORMAL);
988 : 33 : for (gphi_iterator gsi = gsi_start_phis (other_edge->src);
989 : 115 : !gsi_end_p (gsi); gsi_next (&gsi))
990 : : {
991 : 82 : gphi *phi = gsi.phi ();
992 : 82 : tree lhs = gimple_phi_result (phi);
993 : 82 : tree new_lhs = copy_ssa_name (lhs);
994 : 82 : gimple_phi_set_result (phi, new_lhs);
995 : 82 : gphi *new_phi = create_phi_node (lhs, other_edge->dest);
996 : 82 : add_phi_arg (new_phi, new_lhs, other_edge, UNKNOWN_LOCATION);
997 : 82 : add_phi_arg (new_phi, gimple_phi_arg_def_from_edge (phi, ad_edge),
998 : : e, gimple_phi_arg_location_from_edge (phi, ad_edge));
999 : : }
1000 : 33 : e->flags = ad_edge->flags;
1001 : 33 : e->probability = ad_edge->probability;
1002 : 33 : remove_edge (ad_edge);
1003 : 33 : if (dom_info_available_p (CDI_DOMINATORS))
1004 : : {
1005 : 12 : set_immediate_dominator (CDI_DOMINATORS, other_edge->src,
1006 : : recompute_dominator (CDI_DOMINATORS,
1007 : : other_edge->src));
1008 : 12 : set_immediate_dominator (CDI_DOMINATORS, other_edge->dest,
1009 : : recompute_dominator (CDI_DOMINATORS,
1010 : : other_edge->dest));
1011 : : }
1012 : : }
1013 : 269 : return other_edge;
1014 : : }
1015 : :
1016 : : /* Helper function for gsi_safe_insert_before and gsi_safe_insert_seq_before.
1017 : : Replace SSA_NAME uses in G if they are PHI results of PHIs on E->dest
1018 : : bb with the corresponding PHI argument from E edge. */
1019 : :
1020 : : static void
1021 : 269 : adjust_before_returns_twice_call (edge e, gimple *g)
1022 : : {
1023 : 269 : use_operand_p use_p;
1024 : 269 : ssa_op_iter iter;
1025 : 269 : bool m = false;
1026 : 585 : FOR_EACH_SSA_USE_OPERAND (use_p, g, iter, SSA_OP_USE)
1027 : : {
1028 : 316 : tree s = USE_FROM_PTR (use_p);
1029 : 316 : if (SSA_NAME_DEF_STMT (s)
1030 : 316 : && gimple_code (SSA_NAME_DEF_STMT (s)) == GIMPLE_PHI
1031 : 493 : && gimple_bb (SSA_NAME_DEF_STMT (s)) == e->dest)
1032 : : {
1033 : 177 : tree r = gimple_phi_arg_def_from_edge (SSA_NAME_DEF_STMT (s), e);
1034 : 177 : SET_USE (use_p, unshare_expr (r));
1035 : 177 : m = true;
1036 : : }
1037 : : }
1038 : 269 : if (m)
1039 : 177 : update_stmt (g);
1040 : 269 : }
1041 : :
1042 : : /* Insert G stmt before ITER and keep ITER pointing to the same statement
1043 : : as before. If ITER is a returns_twice call, insert it on an appropriate
1044 : : edge instead. */
1045 : :
1046 : : void
1047 : 31096 : gsi_safe_insert_before (gimple_stmt_iterator *iter, gimple *g)
1048 : : {
1049 : 31096 : gimple *stmt = gsi_stmt (*iter);
1050 : 31096 : if (stmt
1051 : 30230 : && is_gimple_call (stmt)
1052 : 934 : && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE) != 0
1053 : 31296 : && bb_has_abnormal_pred (gsi_bb (*iter)))
1054 : : {
1055 : 199 : edge e = edge_before_returns_twice_call (gsi_bb (*iter));
1056 : 199 : basic_block new_bb = gsi_insert_on_edge_immediate (e, g);
1057 : 199 : if (new_bb)
1058 : 33 : e = single_succ_edge (new_bb);
1059 : 199 : adjust_before_returns_twice_call (e, g);
1060 : 199 : *iter = gsi_for_stmt (stmt);
1061 : : }
1062 : : else
1063 : 30897 : gsi_insert_before (iter, g, GSI_SAME_STMT);
1064 : 31096 : }
1065 : :
1066 : : /* Similarly for sequence SEQ. */
1067 : :
1068 : : void
1069 : 4128 : gsi_safe_insert_seq_before (gimple_stmt_iterator *iter, gimple_seq seq)
1070 : : {
1071 : 4128 : if (gimple_seq_empty_p (seq))
1072 : : return;
1073 : 3025 : gimple *stmt = gsi_stmt (*iter);
1074 : 3025 : if (stmt
1075 : 3025 : && is_gimple_call (stmt)
1076 : 82 : && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE) != 0
1077 : 3095 : && bb_has_abnormal_pred (gsi_bb (*iter)))
1078 : : {
1079 : 70 : edge e = edge_before_returns_twice_call (gsi_bb (*iter));
1080 : 70 : gimple *f = gimple_seq_first_stmt (seq);
1081 : 70 : gimple *l = gimple_seq_last_stmt (seq);
1082 : 70 : basic_block new_bb = gsi_insert_seq_on_edge_immediate (e, seq);
1083 : 70 : if (new_bb)
1084 : 0 : e = single_succ_edge (new_bb);
1085 : 70 : for (gimple_stmt_iterator gsi = gsi_for_stmt (f); ; gsi_next (&gsi))
1086 : : {
1087 : 70 : gimple *g = gsi_stmt (gsi);
1088 : 70 : adjust_before_returns_twice_call (e, g);
1089 : 70 : if (g == l)
1090 : : break;
1091 : : }
1092 : 70 : *iter = gsi_for_stmt (stmt);
1093 : : }
1094 : : else
1095 : 2955 : gsi_insert_seq_before (iter, seq, GSI_SAME_STMT);
1096 : : }
|
