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 | update_modified_stmt (gimple *stmt) |
42 | { |
43 | if (!ssa_operands_active (cfun)) |
44 | return; |
45 | update_stmt_if_modified (s: stmt); |
46 | } |
47 | |
48 | |
49 | /* Mark the statements in SEQ as modified, and update them. */ |
50 | |
51 | void |
52 | update_modified_stmts (gimple_seq seq) |
53 | { |
54 | gimple_stmt_iterator gsi; |
55 | |
56 | if (!ssa_operands_active (cfun)) |
57 | return; |
58 | for (gsi = gsi_start (seq); !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
59 | update_stmt_if_modified (s: gsi_stmt (i: 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 | update_bb_for_stmts (gimple_seq_node first, gimple_seq_node last, |
68 | basic_block bb) |
69 | { |
70 | gimple_seq_node n; |
71 | |
72 | for (n = first; n; n = n->next) |
73 | { |
74 | gimple_set_bb (n, bb); |
75 | if (n == last) |
76 | break; |
77 | } |
78 | } |
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 | update_call_edge_frequencies (gimple_seq_node first, basic_block bb) |
85 | { |
86 | struct cgraph_node *cfun_node = NULL; |
87 | gimple_seq_node n; |
88 | |
89 | for (n = first; n ; n = n->next) |
90 | if (is_gimple_call (gs: n)) |
91 | { |
92 | 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 | if (cfun_node == NULL) |
97 | cfun_node = cgraph_node::get (decl: current_function_decl); |
98 | |
99 | e = cfun_node->get_edge (call_stmt: n); |
100 | if (e != NULL) |
101 | e->count = bb->count; |
102 | } |
103 | } |
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 | 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 | basic_block bb; |
121 | gimple_seq_node cur = i->ptr; |
122 | |
123 | gcc_assert (!cur || cur->prev); |
124 | |
125 | if ((bb = gsi_bb (i: *i)) != NULL) |
126 | update_bb_for_stmts (first, last, bb); |
127 | |
128 | /* Link SEQ before CUR in the sequence. */ |
129 | if (cur) |
130 | { |
131 | first->prev = cur->prev; |
132 | if (first->prev->next) |
133 | first->prev->next = first; |
134 | else |
135 | gimple_seq_set_first (ps: i->seq, first); |
136 | last->next = cur; |
137 | cur->prev = last; |
138 | } |
139 | else |
140 | { |
141 | gimple_seq_node itlast = gimple_seq_last (s: *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 | last->next = NULL; |
149 | if (itlast) |
150 | { |
151 | first->prev = itlast; |
152 | itlast->next = first; |
153 | } |
154 | else |
155 | gimple_seq_set_first (ps: i->seq, first); |
156 | gimple_seq_set_last (ps: i->seq, last); |
157 | } |
158 | |
159 | /* Update the iterator, if requested. */ |
160 | switch (mode) |
161 | { |
162 | case GSI_NEW_STMT: |
163 | case GSI_CONTINUE_LINKING: |
164 | i->ptr = first; |
165 | break; |
166 | case GSI_LAST_NEW_STMT: |
167 | i->ptr = last; |
168 | break; |
169 | case GSI_SAME_STMT: |
170 | break; |
171 | default: |
172 | gcc_unreachable (); |
173 | } |
174 | } |
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 | gsi_insert_seq_before_without_update (gimple_stmt_iterator *i, gimple_seq seq, |
188 | enum gsi_iterator_update mode) |
189 | { |
190 | gimple_seq_node first, last; |
191 | |
192 | if (seq == NULL) |
193 | return; |
194 | |
195 | /* Don't allow inserting a sequence into itself. */ |
196 | gcc_assert (seq != *i->seq); |
197 | |
198 | first = gimple_seq_first (s: seq); |
199 | last = gimple_seq_last (s: seq); |
200 | |
201 | /* Empty sequences need no work. */ |
202 | if (!first || !last) |
203 | { |
204 | gcc_assert (first == last); |
205 | return; |
206 | } |
207 | |
208 | 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 | gsi_insert_seq_before (gimple_stmt_iterator *i, gimple_seq seq, |
219 | enum gsi_iterator_update mode) |
220 | { |
221 | update_modified_stmts (seq); |
222 | gsi_insert_seq_before_without_update (i, seq, mode); |
223 | } |
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 | 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 | basic_block bb; |
242 | gimple_seq_node cur = i->ptr; |
243 | |
244 | 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 | if ((bb = gsi_bb (i: *i)) != NULL) |
249 | update_bb_for_stmts (first, last, bb); |
250 | |
251 | /* Link SEQ after CUR. */ |
252 | if (cur) |
253 | { |
254 | last->next = cur->next; |
255 | if (last->next) |
256 | { |
257 | last->next->prev = last; |
258 | } |
259 | else |
260 | gimple_seq_set_last (ps: i->seq, last); |
261 | first->prev = cur; |
262 | cur->next = first; |
263 | } |
264 | else |
265 | { |
266 | gcc_assert (!gimple_seq_last (*i->seq)); |
267 | last->next = NULL; |
268 | gimple_seq_set_first (ps: i->seq, first); |
269 | gimple_seq_set_last (ps: i->seq, last); |
270 | } |
271 | |
272 | /* Update the iterator, if requested. */ |
273 | switch (m) |
274 | { |
275 | case GSI_NEW_STMT: |
276 | i->ptr = first; |
277 | break; |
278 | case GSI_LAST_NEW_STMT: |
279 | case GSI_CONTINUE_LINKING: |
280 | i->ptr = last; |
281 | break; |
282 | case GSI_SAME_STMT: |
283 | gcc_assert (cur); |
284 | break; |
285 | default: |
286 | gcc_unreachable (); |
287 | } |
288 | } |
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 | gsi_insert_seq_after_without_update (gimple_stmt_iterator *i, gimple_seq seq, |
301 | enum gsi_iterator_update mode) |
302 | { |
303 | gimple_seq_node first, last; |
304 | |
305 | if (seq == NULL) |
306 | return; |
307 | |
308 | /* Don't allow inserting a sequence into itself. */ |
309 | gcc_assert (seq != *i->seq); |
310 | |
311 | first = gimple_seq_first (s: seq); |
312 | last = gimple_seq_last (s: seq); |
313 | |
314 | /* Empty sequences need no work. */ |
315 | if (!first || !last) |
316 | { |
317 | gcc_assert (first == last); |
318 | return; |
319 | } |
320 | |
321 | gsi_insert_seq_nodes_after (i, first, last, m: 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 | gsi_insert_seq_after (gimple_stmt_iterator *i, gimple_seq seq, |
331 | enum gsi_iterator_update mode) |
332 | { |
333 | update_modified_stmts (seq); |
334 | gsi_insert_seq_after_without_update (i, seq, mode); |
335 | } |
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 | gsi_split_seq_after (gimple_stmt_iterator i) |
343 | { |
344 | gimple_seq_node cur, next; |
345 | gimple_seq *pold_seq, new_seq; |
346 | |
347 | cur = i.ptr; |
348 | |
349 | /* How can we possibly split after the end, or before the beginning? */ |
350 | gcc_assert (cur && cur->next); |
351 | next = cur->next; |
352 | |
353 | pold_seq = i.seq; |
354 | |
355 | gimple_seq_set_first (ps: &new_seq, first: next); |
356 | gimple_seq_set_last (ps: &new_seq, last: gimple_seq_last (s: *pold_seq)); |
357 | gimple_seq_set_last (ps: pold_seq, last: cur); |
358 | cur->next = NULL; |
359 | |
360 | 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 | gsi_set_stmt (gimple_stmt_iterator *gsi, gimple *stmt) |
370 | { |
371 | gimple *orig_stmt = gsi_stmt (i: *gsi); |
372 | gimple *prev, *next; |
373 | |
374 | stmt->next = next = orig_stmt->next; |
375 | 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 | if (prev->next) |
380 | prev->next = stmt; |
381 | else |
382 | gimple_seq_set_first (ps: gsi->seq, first: stmt); |
383 | if (next) |
384 | next->prev = stmt; |
385 | else |
386 | gimple_seq_set_last (ps: gsi->seq, last: stmt); |
387 | |
388 | gsi->ptr = stmt; |
389 | } |
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 | gsi_split_seq_before (gimple_stmt_iterator *i, gimple_seq *pnew_seq) |
397 | { |
398 | gimple_seq_node cur, prev; |
399 | gimple_seq old_seq; |
400 | |
401 | cur = i->ptr; |
402 | |
403 | /* How can we possibly split after the end? */ |
404 | gcc_assert (cur); |
405 | prev = cur->prev; |
406 | |
407 | old_seq = *i->seq; |
408 | if (!prev->next) |
409 | *i->seq = NULL; |
410 | i->seq = pnew_seq; |
411 | |
412 | /* Set the limits on NEW_SEQ. */ |
413 | gimple_seq_set_first (ps: pnew_seq, first: cur); |
414 | gimple_seq_set_last (ps: pnew_seq, last: gimple_seq_last (s: old_seq)); |
415 | |
416 | /* Cut OLD_SEQ before I. */ |
417 | gimple_seq_set_last (ps: &old_seq, last: prev); |
418 | if (prev->next) |
419 | prev->next = NULL; |
420 | } |
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 | gsi_replace (gimple_stmt_iterator *gsi, gimple *stmt, bool update_eh_info) |
431 | { |
432 | gimple *orig_stmt = gsi_stmt (i: *gsi); |
433 | bool require_eh_edge_purge = false; |
434 | |
435 | if (stmt == orig_stmt) |
436 | return false; |
437 | |
438 | gcc_assert (!gimple_has_lhs (orig_stmt) || !gimple_has_lhs (stmt) |
439 | || gimple_get_lhs (orig_stmt) == gimple_get_lhs (stmt)); |
440 | |
441 | gimple_set_location (g: stmt, location: gimple_location (g: orig_stmt)); |
442 | gimple_set_bb (stmt, gsi_bb (i: *gsi)); |
443 | |
444 | /* Preserve EH region information from the original statement, if |
445 | requested by the caller. */ |
446 | if (update_eh_info) |
447 | require_eh_edge_purge = maybe_clean_or_replace_eh_stmt (orig_stmt, stmt); |
448 | |
449 | gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt); |
450 | |
451 | /* Free all the data flow information for ORIG_STMT. */ |
452 | gimple_set_bb (orig_stmt, NULL); |
453 | gimple_remove_stmt_histograms (cfun, orig_stmt); |
454 | delink_stmt_imm_use (stmt: orig_stmt); |
455 | |
456 | gsi_set_stmt (gsi, stmt); |
457 | gimple_set_modified (s: stmt, modifiedp: true); |
458 | update_modified_stmt (stmt); |
459 | 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 | gsi_replace_with_seq (gimple_stmt_iterator *gsi, gimple_seq seq, |
472 | bool update_eh_info) |
473 | { |
474 | gimple_stmt_iterator seqi; |
475 | gimple *last; |
476 | if (gimple_seq_empty_p (s: seq)) |
477 | { |
478 | gsi_remove (gsi, true); |
479 | return; |
480 | } |
481 | seqi = gsi_last (seq); |
482 | last = gsi_stmt (i: seqi); |
483 | gsi_remove (&seqi, false); |
484 | gsi_insert_seq_before (i: gsi, seq, mode: GSI_SAME_STMT); |
485 | gsi_replace (gsi, stmt: 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 | gsi_insert_before_without_update (gimple_stmt_iterator *i, gimple *stmt, |
500 | enum gsi_iterator_update m) |
501 | { |
502 | gsi_insert_seq_nodes_before (i, first: stmt, last: stmt, mode: m); |
503 | } |
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 | gsi_insert_before (gimple_stmt_iterator *i, gimple *stmt, |
512 | enum gsi_iterator_update m) |
513 | { |
514 | update_modified_stmt (stmt); |
515 | gsi_insert_before_without_update (i, stmt, m); |
516 | } |
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 | gsi_insert_after_without_update (gimple_stmt_iterator *i, gimple *stmt, |
530 | enum gsi_iterator_update m) |
531 | { |
532 | gsi_insert_seq_nodes_after (i, first: stmt, last: stmt, m); |
533 | } |
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 | gsi_insert_after (gimple_stmt_iterator *i, gimple *stmt, |
543 | enum gsi_iterator_update m) |
544 | { |
545 | update_modified_stmt (stmt); |
546 | gsi_insert_after_without_update (i, stmt, m); |
547 | } |
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 | gsi_remove (gimple_stmt_iterator *i, bool remove_permanently) |
561 | { |
562 | gimple_seq_node cur, next, prev; |
563 | gimple *stmt = gsi_stmt (i: *i); |
564 | bool require_eh_edge_purge = false; |
565 | |
566 | /* ??? Do we want to do this for non-permanent operation? */ |
567 | if (gimple_code (g: stmt) != GIMPLE_PHI) |
568 | insert_debug_temps_for_defs (i); |
569 | |
570 | gimple_set_bb (stmt, NULL); |
571 | |
572 | if (remove_permanently) |
573 | { |
574 | /* Free all the data flow information for STMT. */ |
575 | delink_stmt_imm_use (stmt); |
576 | gimple_set_modified (s: stmt, modifiedp: true); |
577 | |
578 | if (gimple_debug_nonbind_marker_p (s: stmt)) |
579 | /* We don't need this to be exact, but try to keep it at least |
580 | close. */ |
581 | cfun->debug_marker_count--; |
582 | require_eh_edge_purge = remove_stmt_from_eh_lp (stmt); |
583 | gimple_remove_stmt_histograms (cfun, stmt); |
584 | } |
585 | |
586 | /* Update the iterator and re-wire the links in I->SEQ. */ |
587 | cur = i->ptr; |
588 | next = cur->next; |
589 | prev = cur->prev; |
590 | /* See gsi_set_stmt for why we don't reset prev/next of STMT. */ |
591 | |
592 | if (next) |
593 | /* Cur is not last. */ |
594 | next->prev = prev; |
595 | else if (prev->next) |
596 | /* Cur is last but not first. */ |
597 | gimple_seq_set_last (ps: i->seq, last: prev); |
598 | |
599 | if (prev->next) |
600 | /* Cur is not first. */ |
601 | prev->next = next; |
602 | else |
603 | /* Cur is first. */ |
604 | *i->seq = next; |
605 | |
606 | i->ptr = next; |
607 | |
608 | return require_eh_edge_purge; |
609 | } |
610 | |
611 | |
612 | /* Finds iterator for STMT. */ |
613 | |
614 | gimple_stmt_iterator |
615 | gsi_for_stmt (gimple *stmt) |
616 | { |
617 | gimple_stmt_iterator i; |
618 | basic_block bb = gimple_bb (g: stmt); |
619 | |
620 | if (gimple_code (g: stmt) == GIMPLE_PHI) |
621 | i = gsi_start_phis (bb); |
622 | else |
623 | i = gsi_start_bb (bb); |
624 | |
625 | i.ptr = stmt; |
626 | 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 | gsi_for_stmt (gimple *stmt, gimple_seq *seq) |
635 | { |
636 | gimple_stmt_iterator i = gsi_start (seq&: *seq); |
637 | i.ptr = stmt; |
638 | return i; |
639 | } |
640 | |
641 | /* Finds iterator for PHI. */ |
642 | |
643 | gphi_iterator |
644 | gsi_for_phi (gphi *phi) |
645 | { |
646 | gphi_iterator i; |
647 | basic_block bb = gimple_bb (g: phi); |
648 | |
649 | i = gsi_start_phis (bb); |
650 | i.ptr = phi; |
651 | |
652 | return i; |
653 | } |
654 | |
655 | /* Move the statement at FROM so it comes right after the statement at TO. */ |
656 | |
657 | void |
658 | gsi_move_after (gimple_stmt_iterator *from, gimple_stmt_iterator *to) |
659 | { |
660 | gimple *stmt = gsi_stmt (i: *from); |
661 | gsi_remove (i: from, remove_permanently: 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 | gsi_insert_after (i: to, stmt, m: GSI_NEW_STMT); |
666 | } |
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 | gsi_move_before (gimple_stmt_iterator *from, gimple_stmt_iterator *to, |
674 | gsi_iterator_update m) |
675 | { |
676 | gimple *stmt = gsi_stmt (i: *from); |
677 | gsi_remove (i: from, remove_permanently: 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 | gsi_insert_before (i: to, stmt, m); |
683 | } |
684 | |
685 | |
686 | /* Move the statement at FROM to the end of basic block BB. */ |
687 | |
688 | void |
689 | gsi_move_to_bb_end (gimple_stmt_iterator *from, basic_block bb) |
690 | { |
691 | gimple_stmt_iterator last = gsi_last_bb (bb); |
692 | gcc_checking_assert (gsi_bb (last) == bb); |
693 | |
694 | /* Have to check gsi_end_p because it could be an empty block. */ |
695 | if (!gsi_end_p (i: last) && is_ctrl_stmt (gsi_stmt (i: last))) |
696 | gsi_move_before (from, to: &last); |
697 | else |
698 | gsi_move_after (from, to: &last); |
699 | } |
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 | gsi_insert_on_edge (edge e, gimple *stmt) |
707 | { |
708 | gimple_seq_add_stmt (&PENDING_STMT (e), stmt); |
709 | } |
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 | gsi_insert_seq_on_edge (edge e, gimple_seq seq) |
717 | { |
718 | gimple_seq_add_seq (&PENDING_STMT (e), seq); |
719 | } |
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 | gsi_start_edge (edge e) |
727 | { |
728 | 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 | gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi, |
743 | basic_block *new_bb) |
744 | { |
745 | basic_block dest, src; |
746 | gimple *tmp; |
747 | |
748 | 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 | restart: |
758 | if (single_pred_p (bb: dest) |
759 | && gimple_seq_empty_p (s: phi_nodes (bb: dest)) |
760 | && dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) |
761 | { |
762 | *gsi = gsi_start_bb (bb: dest); |
763 | if (gsi_end_p (i: *gsi)) |
764 | return true; |
765 | |
766 | /* Make sure we insert after any leading labels. */ |
767 | tmp = gsi_stmt (i: *gsi); |
768 | while (gimple_code (g: tmp) == GIMPLE_LABEL) |
769 | { |
770 | gsi_next (i: gsi); |
771 | if (gsi_end_p (i: *gsi)) |
772 | break; |
773 | tmp = gsi_stmt (i: *gsi); |
774 | } |
775 | |
776 | if (gsi_end_p (i: *gsi)) |
777 | { |
778 | *gsi = gsi_last_bb (bb: dest); |
779 | 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 | src = e->src; |
789 | if ((e->flags & EDGE_ABNORMAL) == 0 |
790 | && (single_succ_p (bb: src) |
791 | /* Do not count a fake edge as successor as added to infinite |
792 | loops by connect_infinite_loops_to_exit. */ |
793 | || (EDGE_COUNT (src->succs) == 2 |
794 | && (EDGE_SUCC (src, 0)->flags & EDGE_FAKE |
795 | || EDGE_SUCC (src, 1)->flags & EDGE_FAKE))) |
796 | && src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
797 | { |
798 | *gsi = gsi_last_bb (bb: src); |
799 | if (gsi_end_p (i: *gsi)) |
800 | return true; |
801 | |
802 | tmp = gsi_stmt (i: *gsi); |
803 | if (is_gimple_debug (gs: tmp)) |
804 | { |
805 | gimple_stmt_iterator si = *gsi; |
806 | gsi_prev_nondebug (i: &si); |
807 | if (!gsi_end_p (i: si)) |
808 | tmp = gsi_stmt (i: 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 | if (!stmt_ends_bb_p (tmp)) |
814 | return true; |
815 | *gsi = si; |
816 | } |
817 | else if (!stmt_ends_bb_p (tmp)) |
818 | return true; |
819 | |
820 | switch (gimple_code (g: 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 | dest = split_edge (e); |
832 | if (new_bb) |
833 | *new_bb = dest; |
834 | e = single_pred_edge (bb: dest); |
835 | 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 | gsi_insert_on_edge_immediate (edge e, gimple *stmt) |
844 | { |
845 | gimple_stmt_iterator gsi; |
846 | basic_block new_bb = NULL; |
847 | bool ins_after; |
848 | |
849 | gcc_assert (!PENDING_STMT (e)); |
850 | |
851 | ins_after = gimple_find_edge_insert_loc (e, gsi: &gsi, new_bb: &new_bb); |
852 | |
853 | update_call_edge_frequencies (first: stmt, bb: gsi.bb); |
854 | |
855 | if (ins_after) |
856 | gsi_insert_after (i: &gsi, stmt, m: GSI_NEW_STMT); |
857 | else |
858 | gsi_insert_before (i: &gsi, stmt, m: GSI_NEW_STMT); |
859 | |
860 | 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 | gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts) |
868 | { |
869 | gimple_stmt_iterator gsi; |
870 | basic_block new_bb = NULL; |
871 | bool ins_after; |
872 | |
873 | gcc_assert (!PENDING_STMT (e)); |
874 | |
875 | ins_after = gimple_find_edge_insert_loc (e, gsi: &gsi, new_bb: &new_bb); |
876 | update_call_edge_frequencies (first: gimple_seq_first (s: stmts), bb: gsi.bb); |
877 | |
878 | if (ins_after) |
879 | gsi_insert_seq_after (i: &gsi, seq: stmts, mode: GSI_NEW_STMT); |
880 | else |
881 | gsi_insert_seq_before (i: &gsi, seq: stmts, mode: GSI_NEW_STMT); |
882 | |
883 | 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 | gsi_commit_edge_inserts (void) |
891 | { |
892 | basic_block bb; |
893 | edge e; |
894 | edge_iterator ei; |
895 | |
896 | gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), |
897 | NULL); |
898 | |
899 | FOR_EACH_BB_FN (bb, cfun) |
900 | FOR_EACH_EDGE (e, ei, bb->succs) |
901 | gsi_commit_one_edge_insert (e, NULL); |
902 | } |
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 | gsi_commit_one_edge_insert (edge e, basic_block *new_bb) |
910 | { |
911 | if (new_bb) |
912 | *new_bb = NULL; |
913 | |
914 | if (PENDING_STMT (e)) |
915 | { |
916 | gimple_stmt_iterator gsi; |
917 | gimple_seq seq = PENDING_STMT (e); |
918 | bool ins_after; |
919 | |
920 | PENDING_STMT (e) = NULL; |
921 | |
922 | ins_after = gimple_find_edge_insert_loc (e, gsi: &gsi, new_bb); |
923 | update_call_edge_frequencies (first: gimple_seq_first (s: seq), bb: gsi.bb); |
924 | |
925 | if (ins_after) |
926 | gsi_insert_seq_after (i: &gsi, seq, mode: GSI_NEW_STMT); |
927 | else |
928 | gsi_insert_seq_before (i: &gsi, seq, mode: GSI_NEW_STMT); |
929 | } |
930 | } |
931 | |
932 | /* Returns iterator at the start of the list of phi nodes of BB. */ |
933 | |
934 | gphi_iterator |
935 | gsi_start_phis (basic_block bb) |
936 | { |
937 | gimple_seq *pseq = phi_nodes_ptr (bb); |
938 | |
939 | /* Adapted from gsi_start. */ |
940 | gphi_iterator i; |
941 | |
942 | i.ptr = gimple_seq_first (s: *pseq); |
943 | i.seq = pseq; |
944 | i.bb = i.ptr ? gimple_bb (g: i.ptr) : NULL; |
945 | |
946 | 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 | edge_before_returns_twice_call (basic_block bb) |
955 | { |
956 | gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb); |
957 | gcc_checking_assert (is_gimple_call (gsi_stmt (gsi)) |
958 | && (gimple_call_flags (gsi_stmt (gsi)) |
959 | & ECF_RETURNS_TWICE) != 0); |
960 | edge_iterator ei; |
961 | edge e, ad_edge = NULL, other_edge = NULL; |
962 | bool split = false; |
963 | FOR_EACH_EDGE (e, ei, bb->preds) |
964 | { |
965 | if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) == EDGE_ABNORMAL) |
966 | { |
967 | gimple_stmt_iterator gsi |
968 | = gsi_start_nondebug_after_labels_bb (bb: e->src); |
969 | gimple *ad = gsi_stmt (i: gsi); |
970 | if (ad && gimple_call_internal_p (gs: ad, fn: IFN_ABNORMAL_DISPATCHER)) |
971 | { |
972 | gcc_checking_assert (ad_edge == NULL); |
973 | ad_edge = e; |
974 | continue; |
975 | } |
976 | } |
977 | if (other_edge || e->flags & (EDGE_ABNORMAL | EDGE_EH)) |
978 | split = true; |
979 | other_edge = e; |
980 | } |
981 | gcc_checking_assert (ad_edge); |
982 | if (other_edge == NULL) |
983 | split = true; |
984 | if (split) |
985 | { |
986 | other_edge = split_block_after_labels (bb); |
987 | e = make_edge (ad_edge->src, other_edge->dest, EDGE_ABNORMAL); |
988 | for (gphi_iterator gsi = gsi_start_phis (bb: other_edge->src); |
989 | !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
990 | { |
991 | gphi *phi = gsi.phi (); |
992 | tree lhs = gimple_phi_result (gs: phi); |
993 | tree new_lhs = copy_ssa_name (var: lhs); |
994 | gimple_phi_set_result (phi, result: new_lhs); |
995 | gphi *new_phi = create_phi_node (lhs, other_edge->dest); |
996 | add_phi_arg (new_phi, new_lhs, other_edge, UNKNOWN_LOCATION); |
997 | add_phi_arg (new_phi, gimple_phi_arg_def_from_edge (gs: phi, e: ad_edge), |
998 | e, gimple_phi_arg_location_from_edge (phi, e: ad_edge)); |
999 | } |
1000 | e->flags = ad_edge->flags; |
1001 | e->probability = ad_edge->probability; |
1002 | remove_edge (ad_edge); |
1003 | if (dom_info_available_p (CDI_DOMINATORS)) |
1004 | { |
1005 | set_immediate_dominator (CDI_DOMINATORS, other_edge->src, |
1006 | recompute_dominator (CDI_DOMINATORS, |
1007 | other_edge->src)); |
1008 | set_immediate_dominator (CDI_DOMINATORS, other_edge->dest, |
1009 | recompute_dominator (CDI_DOMINATORS, |
1010 | other_edge->dest)); |
1011 | } |
1012 | } |
1013 | 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 | adjust_before_returns_twice_call (edge e, gimple *g) |
1022 | { |
1023 | use_operand_p use_p; |
1024 | ssa_op_iter iter; |
1025 | bool m = false; |
1026 | FOR_EACH_SSA_USE_OPERAND (use_p, g, iter, SSA_OP_USE) |
1027 | { |
1028 | tree s = USE_FROM_PTR (use_p); |
1029 | if (SSA_NAME_DEF_STMT (s) |
1030 | && gimple_code (SSA_NAME_DEF_STMT (s)) == GIMPLE_PHI |
1031 | && gimple_bb (SSA_NAME_DEF_STMT (s)) == e->dest) |
1032 | { |
1033 | tree r = gimple_phi_arg_def_from_edge (SSA_NAME_DEF_STMT (s), e); |
1034 | SET_USE (use_p, unshare_expr (r)); |
1035 | m = true; |
1036 | } |
1037 | } |
1038 | if (m) |
1039 | update_stmt (s: g); |
1040 | } |
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 | gsi_safe_insert_before (gimple_stmt_iterator *iter, gimple *g) |
1048 | { |
1049 | gimple *stmt = gsi_stmt (i: *iter); |
1050 | if (stmt |
1051 | && is_gimple_call (gs: stmt) |
1052 | && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE) != 0 |
1053 | && bb_has_abnormal_pred (bb: gsi_bb (i: *iter))) |
1054 | { |
1055 | edge e = edge_before_returns_twice_call (bb: gsi_bb (i: *iter)); |
1056 | basic_block new_bb = gsi_insert_on_edge_immediate (e, stmt: g); |
1057 | if (new_bb) |
1058 | e = single_succ_edge (bb: new_bb); |
1059 | adjust_before_returns_twice_call (e, g); |
1060 | *iter = gsi_for_stmt (stmt); |
1061 | } |
1062 | else |
1063 | gsi_insert_before (i: iter, stmt: g, m: GSI_SAME_STMT); |
1064 | } |
1065 | |
1066 | /* Similarly for sequence SEQ. */ |
1067 | |
1068 | void |
1069 | gsi_safe_insert_seq_before (gimple_stmt_iterator *iter, gimple_seq seq) |
1070 | { |
1071 | if (gimple_seq_empty_p (s: seq)) |
1072 | return; |
1073 | gimple *stmt = gsi_stmt (i: *iter); |
1074 | if (stmt |
1075 | && is_gimple_call (gs: stmt) |
1076 | && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE) != 0 |
1077 | && bb_has_abnormal_pred (bb: gsi_bb (i: *iter))) |
1078 | { |
1079 | edge e = edge_before_returns_twice_call (bb: gsi_bb (i: *iter)); |
1080 | gimple *f = gimple_seq_first_stmt (s: seq); |
1081 | gimple *l = gimple_seq_last_stmt (s: seq); |
1082 | basic_block new_bb = gsi_insert_seq_on_edge_immediate (e, stmts: seq); |
1083 | if (new_bb) |
1084 | e = single_succ_edge (bb: new_bb); |
1085 | for (gimple_stmt_iterator gsi = gsi_for_stmt (stmt: f); ; gsi_next (i: &gsi)) |
1086 | { |
1087 | gimple *g = gsi_stmt (i: gsi); |
1088 | adjust_before_returns_twice_call (e, g); |
1089 | if (g == l) |
1090 | break; |
1091 | } |
1092 | *iter = gsi_for_stmt (stmt); |
1093 | } |
1094 | else |
1095 | gsi_insert_seq_before (i: iter, seq, mode: GSI_SAME_STMT); |
1096 | } |
1097 | |