1/* Shrink-wrapping related optimizations.
2 Copyright (C) 1987-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20/* This file handles shrink-wrapping related optimizations. */
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "backend.h"
26#include "target.h"
27#include "rtl.h"
28#include "tree.h"
29#include "cfghooks.h"
30#include "df.h"
31#include "memmodel.h"
32#include "tm_p.h"
33#include "regs.h"
34#include "insn-config.h"
35#include "emit-rtl.h"
36#include "output.h"
37#include "tree-pass.h"
38#include "cfgrtl.h"
39#include "cfgbuild.h"
40#include "params.h"
41#include "bb-reorder.h"
42#include "shrink-wrap.h"
43#include "regcprop.h"
44#include "rtl-iter.h"
45#include "valtrack.h"
46
47
48/* Return true if INSN requires the stack frame to be set up.
49 PROLOGUE_USED contains the hard registers used in the function
50 prologue. SET_UP_BY_PROLOGUE is the set of registers we expect the
51 prologue to set up for the function. */
52bool
53requires_stack_frame_p (rtx_insn *insn, HARD_REG_SET prologue_used,
54 HARD_REG_SET set_up_by_prologue)
55{
56 df_ref def, use;
57 HARD_REG_SET hardregs;
58 unsigned regno;
59
60 if (CALL_P (insn))
61 return !SIBLING_CALL_P (insn);
62
63 /* We need a frame to get the unique CFA expected by the unwinder. */
64 if (cfun->can_throw_non_call_exceptions && can_throw_internal (insn))
65 return true;
66
67 CLEAR_HARD_REG_SET (hardregs);
68 FOR_EACH_INSN_DEF (def, insn)
69 {
70 rtx dreg = DF_REF_REG (def);
71
72 if (!REG_P (dreg))
73 continue;
74
75 add_to_hard_reg_set (&hardregs, GET_MODE (dreg), REGNO (dreg));
76 }
77 if (hard_reg_set_intersect_p (hardregs, prologue_used))
78 return true;
79 AND_COMPL_HARD_REG_SET (hardregs, call_used_reg_set);
80 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
81 if (TEST_HARD_REG_BIT (hardregs, regno)
82 && df_regs_ever_live_p (regno))
83 return true;
84
85 FOR_EACH_INSN_USE (use, insn)
86 {
87 rtx reg = DF_REF_REG (use);
88
89 if (!REG_P (reg))
90 continue;
91
92 add_to_hard_reg_set (&hardregs, GET_MODE (reg),
93 REGNO (reg));
94 }
95 if (hard_reg_set_intersect_p (hardregs, set_up_by_prologue))
96 return true;
97
98 return false;
99}
100
101/* See whether there has a single live edge from BB, which dest uses
102 [REGNO, END_REGNO). Return the live edge if its dest bb has
103 one or two predecessors. Otherwise return NULL. */
104
105static edge
106live_edge_for_reg (basic_block bb, int regno, int end_regno)
107{
108 edge e, live_edge;
109 edge_iterator ei;
110 bitmap live;
111 int i;
112
113 live_edge = NULL;
114 FOR_EACH_EDGE (e, ei, bb->succs)
115 {
116 live = df_get_live_in (e->dest);
117 for (i = regno; i < end_regno; i++)
118 if (REGNO_REG_SET_P (live, i))
119 {
120 if (live_edge && live_edge != e)
121 return NULL;
122 live_edge = e;
123 }
124 }
125
126 /* We can sometimes encounter dead code. Don't try to move it
127 into the exit block. */
128 if (!live_edge || live_edge->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
129 return NULL;
130
131 /* Reject targets of abnormal edges. This is needed for correctness
132 on ports like Alpha and MIPS, whose pic_offset_table_rtx can die on
133 exception edges even though it is generally treated as call-saved
134 for the majority of the compilation. Moving across abnormal edges
135 isn't going to be interesting for shrink-wrap usage anyway. */
136 if (live_edge->flags & EDGE_ABNORMAL)
137 return NULL;
138
139 /* When live_edge->dest->preds == 2, we can create a new block on
140 the edge to make it meet the requirement. */
141 if (EDGE_COUNT (live_edge->dest->preds) > 2)
142 return NULL;
143
144 return live_edge;
145}
146
147/* Try to move INSN from BB to a successor. Return true on success.
148 USES and DEFS are the set of registers that are used and defined
149 after INSN in BB. SPLIT_P indicates whether a live edge from BB
150 is splitted or not. */
151
152static bool
153move_insn_for_shrink_wrap (basic_block bb, rtx_insn *insn,
154 const HARD_REG_SET uses,
155 const HARD_REG_SET defs,
156 bool *split_p,
157 struct dead_debug_local *debug)
158{
159 rtx set, src, dest;
160 bitmap live_out, live_in, bb_uses, bb_defs;
161 unsigned int i, dregno, end_dregno;
162 unsigned int sregno = FIRST_PSEUDO_REGISTER;
163 unsigned int end_sregno = FIRST_PSEUDO_REGISTER;
164 basic_block next_block;
165 edge live_edge;
166 rtx_insn *dinsn;
167 df_ref def;
168
169 /* Look for a simple register assignment. We don't use single_set here
170 because we can't deal with any CLOBBERs, USEs, or REG_UNUSED secondary
171 destinations. */
172 if (!INSN_P (insn))
173 return false;
174 set = PATTERN (insn);
175 if (GET_CODE (set) != SET)
176 return false;
177 src = SET_SRC (set);
178 dest = SET_DEST (set);
179
180 /* For the destination, we want only a register. Also disallow STACK
181 or FRAME related adjustments. They are likely part of the prologue,
182 so keep them in the entry block. */
183 if (!REG_P (dest)
184 || dest == stack_pointer_rtx
185 || dest == frame_pointer_rtx
186 || dest == hard_frame_pointer_rtx)
187 return false;
188
189 /* For the source, we want one of:
190 (1) A (non-overlapping) register
191 (2) A constant,
192 (3) An expression involving no more than one register.
193
194 That last point comes from the code following, which was originally
195 written to handle only register move operations, and still only handles
196 a single source register when checking for overlaps. Happily, the
197 same checks can be applied to expressions like (plus reg const). */
198
199 if (CONSTANT_P (src))
200 ;
201 else if (!REG_P (src))
202 {
203 rtx src_inner = NULL_RTX;
204
205 if (can_throw_internal (insn))
206 return false;
207
208 subrtx_var_iterator::array_type array;
209 FOR_EACH_SUBRTX_VAR (iter, array, src, ALL)
210 {
211 rtx x = *iter;
212 switch (GET_RTX_CLASS (GET_CODE (x)))
213 {
214 case RTX_CONST_OBJ:
215 case RTX_COMPARE:
216 case RTX_COMM_COMPARE:
217 case RTX_BIN_ARITH:
218 case RTX_COMM_ARITH:
219 case RTX_UNARY:
220 case RTX_TERNARY:
221 /* Constant or expression. Continue. */
222 break;
223
224 case RTX_OBJ:
225 case RTX_EXTRA:
226 switch (GET_CODE (x))
227 {
228 case UNSPEC:
229 case SUBREG:
230 case STRICT_LOW_PART:
231 case PC:
232 case LO_SUM:
233 /* Ok. Continue. */
234 break;
235
236 case REG:
237 /* Fail if we see a second inner register. */
238 if (src_inner != NULL)
239 return false;
240 src_inner = x;
241 break;
242
243 default:
244 return false;
245 }
246 break;
247
248 default:
249 return false;
250 }
251 }
252
253 if (src_inner != NULL)
254 src = src_inner;
255 }
256
257 /* Make sure that the source register isn't defined later in BB. */
258 if (REG_P (src))
259 {
260 sregno = REGNO (src);
261 end_sregno = END_REGNO (src);
262 if (overlaps_hard_reg_set_p (defs, GET_MODE (src), sregno))
263 return false;
264 }
265
266 /* Make sure that the destination register isn't referenced later in BB. */
267 dregno = REGNO (dest);
268 end_dregno = END_REGNO (dest);
269 if (overlaps_hard_reg_set_p (uses, GET_MODE (dest), dregno)
270 || overlaps_hard_reg_set_p (defs, GET_MODE (dest), dregno))
271 return false;
272
273 /* See whether there is a successor block to which we could move INSN. */
274 live_edge = live_edge_for_reg (bb, dregno, end_dregno);
275 if (!live_edge)
276 return false;
277
278 next_block = live_edge->dest;
279 /* Create a new basic block on the edge. */
280 if (EDGE_COUNT (next_block->preds) == 2)
281 {
282 /* split_edge for a block with only one successor is meaningless. */
283 if (EDGE_COUNT (bb->succs) == 1)
284 return false;
285
286 /* If DF_LIVE doesn't exist, i.e. at -O1, just give up. */
287 if (!df_live)
288 return false;
289
290 basic_block old_dest = live_edge->dest;
291 next_block = split_edge (live_edge);
292
293 /* We create a new basic block. Call df_grow_bb_info to make sure
294 all data structures are allocated. */
295 df_grow_bb_info (df_live);
296
297 bitmap_and (df_get_live_in (next_block), df_get_live_out (bb),
298 df_get_live_in (old_dest));
299 df_set_bb_dirty (next_block);
300
301 /* We should not split more than once for a function. */
302 if (*split_p)
303 return false;
304
305 *split_p = true;
306 }
307
308 /* At this point we are committed to moving INSN, but let's try to
309 move it as far as we can. */
310 do
311 {
312 if (MAY_HAVE_DEBUG_BIND_INSNS)
313 {
314 FOR_BB_INSNS_REVERSE (bb, dinsn)
315 if (DEBUG_BIND_INSN_P (dinsn))
316 {
317 df_ref use;
318 FOR_EACH_INSN_USE (use, dinsn)
319 if (refers_to_regno_p (dregno, end_dregno,
320 DF_REF_REG (use), (rtx *) NULL))
321 dead_debug_add (debug, use, DF_REF_REGNO (use));
322 }
323 else if (dinsn == insn)
324 break;
325 }
326 live_out = df_get_live_out (bb);
327 live_in = df_get_live_in (next_block);
328 bb = next_block;
329
330 /* Check whether BB uses DEST or clobbers DEST. We need to add
331 INSN to BB if so. Either way, DEST is no longer live on entry,
332 except for any part that overlaps SRC (next loop). */
333 bb_uses = &DF_LR_BB_INFO (bb)->use;
334 bb_defs = &DF_LR_BB_INFO (bb)->def;
335 if (df_live)
336 {
337 for (i = dregno; i < end_dregno; i++)
338 {
339 if (*split_p
340 || REGNO_REG_SET_P (bb_uses, i)
341 || REGNO_REG_SET_P (bb_defs, i)
342 || REGNO_REG_SET_P (&DF_LIVE_BB_INFO (bb)->gen, i))
343 next_block = NULL;
344 CLEAR_REGNO_REG_SET (live_out, i);
345 CLEAR_REGNO_REG_SET (live_in, i);
346 }
347
348 /* Check whether BB clobbers SRC. We need to add INSN to BB if so.
349 Either way, SRC is now live on entry. */
350 for (i = sregno; i < end_sregno; i++)
351 {
352 if (*split_p
353 || REGNO_REG_SET_P (bb_defs, i)
354 || REGNO_REG_SET_P (&DF_LIVE_BB_INFO (bb)->gen, i))
355 next_block = NULL;
356 SET_REGNO_REG_SET (live_out, i);
357 SET_REGNO_REG_SET (live_in, i);
358 }
359 }
360 else
361 {
362 /* DF_LR_BB_INFO (bb)->def does not comprise the DF_REF_PARTIAL and
363 DF_REF_CONDITIONAL defs. So if DF_LIVE doesn't exist, i.e.
364 at -O1, just give up searching NEXT_BLOCK. */
365 next_block = NULL;
366 for (i = dregno; i < end_dregno; i++)
367 {
368 CLEAR_REGNO_REG_SET (live_out, i);
369 CLEAR_REGNO_REG_SET (live_in, i);
370 }
371
372 for (i = sregno; i < end_sregno; i++)
373 {
374 SET_REGNO_REG_SET (live_out, i);
375 SET_REGNO_REG_SET (live_in, i);
376 }
377 }
378
379 /* If we don't need to add the move to BB, look for a single
380 successor block. */
381 if (next_block)
382 {
383 live_edge = live_edge_for_reg (next_block, dregno, end_dregno);
384 if (!live_edge || EDGE_COUNT (live_edge->dest->preds) > 1)
385 break;
386 next_block = live_edge->dest;
387 }
388 }
389 while (next_block);
390
391 /* For the new created basic block, there is no dataflow info at all.
392 So skip the following dataflow update and check. */
393 if (!(*split_p))
394 {
395 /* BB now defines DEST. It only uses the parts of DEST that overlap SRC
396 (next loop). */
397 for (i = dregno; i < end_dregno; i++)
398 {
399 CLEAR_REGNO_REG_SET (bb_uses, i);
400 SET_REGNO_REG_SET (bb_defs, i);
401 }
402
403 /* BB now uses SRC. */
404 for (i = sregno; i < end_sregno; i++)
405 SET_REGNO_REG_SET (bb_uses, i);
406 }
407
408 /* Insert debug temps for dead REGs used in subsequent debug insns. */
409 if (debug->used && !bitmap_empty_p (debug->used))
410 FOR_EACH_INSN_DEF (def, insn)
411 dead_debug_insert_temp (debug, DF_REF_REGNO (def), insn,
412 DEBUG_TEMP_BEFORE_WITH_VALUE);
413
414 emit_insn_after (PATTERN (insn), bb_note (bb));
415 delete_insn (insn);
416 return true;
417}
418
419/* Look for register copies in the first block of the function, and move
420 them down into successor blocks if the register is used only on one
421 path. This exposes more opportunities for shrink-wrapping. These
422 kinds of sets often occur when incoming argument registers are moved
423 to call-saved registers because their values are live across one or
424 more calls during the function. */
425
426static void
427prepare_shrink_wrap (basic_block entry_block)
428{
429 rtx_insn *insn, *curr;
430 rtx x;
431 HARD_REG_SET uses, defs;
432 df_ref def, use;
433 bool split_p = false;
434 unsigned int i;
435 struct dead_debug_local debug;
436
437 if (JUMP_P (BB_END (entry_block)))
438 {
439 /* To have more shrink-wrapping opportunities, prepare_shrink_wrap tries
440 to sink the copies from parameter to callee saved register out of
441 entry block. copyprop_hardreg_forward_bb_without_debug_insn is called
442 to release some dependences. */
443 copyprop_hardreg_forward_bb_without_debug_insn (entry_block);
444 }
445
446 dead_debug_local_init (&debug, NULL, NULL);
447 CLEAR_HARD_REG_SET (uses);
448 CLEAR_HARD_REG_SET (defs);
449
450 FOR_BB_INSNS_REVERSE_SAFE (entry_block, insn, curr)
451 if (NONDEBUG_INSN_P (insn)
452 && !move_insn_for_shrink_wrap (entry_block, insn, uses, defs,
453 &split_p, &debug))
454 {
455 /* Add all defined registers to DEFs. */
456 FOR_EACH_INSN_DEF (def, insn)
457 {
458 x = DF_REF_REG (def);
459 if (REG_P (x) && HARD_REGISTER_P (x))
460 for (i = REGNO (x); i < END_REGNO (x); i++)
461 SET_HARD_REG_BIT (defs, i);
462 }
463
464 /* Add all used registers to USESs. */
465 FOR_EACH_INSN_USE (use, insn)
466 {
467 x = DF_REF_REG (use);
468 if (REG_P (x) && HARD_REGISTER_P (x))
469 for (i = REGNO (x); i < END_REGNO (x); i++)
470 SET_HARD_REG_BIT (uses, i);
471 }
472 }
473
474 dead_debug_local_finish (&debug, NULL);
475}
476
477/* Return whether basic block PRO can get the prologue. It can not if it
478 has incoming complex edges that need a prologue inserted (we make a new
479 block for the prologue, so those edges would need to be redirected, which
480 does not work). It also can not if there exist registers live on entry
481 to PRO that are clobbered by the prologue. */
482
483static bool
484can_get_prologue (basic_block pro, HARD_REG_SET prologue_clobbered)
485{
486 edge e;
487 edge_iterator ei;
488 FOR_EACH_EDGE (e, ei, pro->preds)
489 if (e->flags & (EDGE_COMPLEX | EDGE_CROSSING)
490 && !dominated_by_p (CDI_DOMINATORS, e->src, pro))
491 return false;
492
493 HARD_REG_SET live;
494 REG_SET_TO_HARD_REG_SET (live, df_get_live_in (pro));
495 if (hard_reg_set_intersect_p (live, prologue_clobbered))
496 return false;
497
498 return true;
499}
500
501/* Return whether we can duplicate basic block BB for shrink wrapping. We
502 cannot if the block cannot be duplicated at all, or if any of its incoming
503 edges are complex and come from a block that does not require a prologue
504 (we cannot redirect such edges), or if the block is too big to copy.
505 PRO is the basic block before which we would put the prologue, MAX_SIZE is
506 the maximum size block we allow to be copied. */
507
508static bool
509can_dup_for_shrink_wrapping (basic_block bb, basic_block pro, unsigned max_size)
510{
511 if (!can_duplicate_block_p (bb))
512 return false;
513
514 edge e;
515 edge_iterator ei;
516 FOR_EACH_EDGE (e, ei, bb->preds)
517 if (e->flags & (EDGE_COMPLEX | EDGE_CROSSING)
518 && !dominated_by_p (CDI_DOMINATORS, e->src, pro))
519 return false;
520
521 unsigned size = 0;
522
523 rtx_insn *insn;
524 FOR_BB_INSNS (bb, insn)
525 if (NONDEBUG_INSN_P (insn))
526 {
527 size += get_attr_min_length (insn);
528 if (size > max_size)
529 return false;
530 }
531
532 return true;
533}
534
535/* Do whatever needs to be done for exits that run without prologue.
536 Sibcalls need nothing done. Normal exits get a simple_return inserted. */
537
538static void
539handle_simple_exit (edge e)
540{
541
542 if (e->flags & EDGE_SIBCALL)
543 {
544 /* Tell function.c to take no further action on this edge. */
545 e->flags |= EDGE_IGNORE;
546
547 e->flags &= ~EDGE_FALLTHRU;
548 emit_barrier_after_bb (e->src);
549 return;
550 }
551
552 /* If the basic block the edge comes from has multiple successors,
553 split the edge. */
554 if (EDGE_COUNT (e->src->succs) > 1)
555 {
556 basic_block old_bb = e->src;
557 rtx_insn *end = BB_END (old_bb);
558 rtx_note *note = emit_note_after (NOTE_INSN_DELETED, end);
559 basic_block new_bb = create_basic_block (note, note, old_bb);
560 BB_COPY_PARTITION (new_bb, old_bb);
561 BB_END (old_bb) = end;
562
563 redirect_edge_succ (e, new_bb);
564 new_bb->count = e->count ();
565 e->flags |= EDGE_FALLTHRU;
566
567 e = make_single_succ_edge (new_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
568 }
569
570 e->flags &= ~EDGE_FALLTHRU;
571 rtx_jump_insn *ret = emit_jump_insn_after (targetm.gen_simple_return (),
572 BB_END (e->src));
573 JUMP_LABEL (ret) = simple_return_rtx;
574 emit_barrier_after_bb (e->src);
575
576 if (dump_file)
577 fprintf (dump_file, "Made simple_return with UID %d in bb %d\n",
578 INSN_UID (ret), e->src->index);
579}
580
581/* Try to perform a kind of shrink-wrapping, making sure the
582 prologue/epilogue is emitted only around those parts of the
583 function that require it.
584
585 There will be exactly one prologue, and it will be executed either
586 zero or one time, on any path. Depending on where the prologue is
587 placed, some of the basic blocks can be reached via both paths with
588 and without a prologue. Such blocks will be duplicated here, and the
589 edges changed to match.
590
591 Paths that go to the exit without going through the prologue will use
592 a simple_return instead of the epilogue. We maximize the number of
593 those, making sure to only duplicate blocks that can be duplicated.
594 If the prologue can then still be placed in multiple locations, we
595 place it as early as possible.
596
597 An example, where we duplicate blocks with control flow (legend:
598 _B_egin, _R_eturn and _S_imple_return; edges without arrowhead should
599 be taken to point down or to the right, to simplify the diagram; here,
600 block 3 needs a prologue, the rest does not):
601
602
603 B B
604 | |
605 2 2
606 |\ |\
607 | 3 becomes | 3
608 |/ | \
609 4 7 4
610 |\ |\ |\
611 | 5 | 8 | 5
612 |/ |/ |/
613 6 9 6
614 | | |
615 R S R
616
617
618 (bb 4 is duplicated to 7, and so on; the prologue is inserted on the
619 edge 2->3).
620
621 Another example, where part of a loop is duplicated (again, bb 3 is
622 the only block that needs a prologue):
623
624
625 B 3<-- B ->3<--
626 | | | | | | |
627 | v | becomes | | v |
628 2---4--- 2---5-- 4---
629 | | |
630 R S R
631
632
633 (bb 4 is duplicated to 5; the prologue is inserted on the edge 5->3).
634
635 ENTRY_EDGE is the edge where the prologue will be placed, possibly
636 changed by this function. PROLOGUE_SEQ is the prologue we will insert. */
637
638void
639try_shrink_wrapping (edge *entry_edge, rtx_insn *prologue_seq)
640{
641 /* If we cannot shrink-wrap, are told not to shrink-wrap, or it makes
642 no sense to shrink-wrap: then do not shrink-wrap! */
643
644 if (!SHRINK_WRAPPING_ENABLED)
645 return;
646
647 if (crtl->profile && !targetm.profile_before_prologue ())
648 return;
649
650 if (crtl->calls_eh_return)
651 return;
652
653 bool empty_prologue = true;
654 for (rtx_insn *insn = prologue_seq; insn; insn = NEXT_INSN (insn))
655 if (!(NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_PROLOGUE_END))
656 {
657 empty_prologue = false;
658 break;
659 }
660 if (empty_prologue)
661 return;
662
663 /* Move some code down to expose more shrink-wrapping opportunities. */
664
665 basic_block entry = (*entry_edge)->dest;
666 prepare_shrink_wrap (entry);
667
668 if (dump_file)
669 fprintf (dump_file, "Attempting shrink-wrapping optimization.\n");
670
671 /* Compute the registers set and used in the prologue. */
672
673 HARD_REG_SET prologue_clobbered, prologue_used;
674 CLEAR_HARD_REG_SET (prologue_clobbered);
675 CLEAR_HARD_REG_SET (prologue_used);
676 for (rtx_insn *insn = prologue_seq; insn; insn = NEXT_INSN (insn))
677 if (NONDEBUG_INSN_P (insn))
678 {
679 HARD_REG_SET this_used;
680 CLEAR_HARD_REG_SET (this_used);
681 note_uses (&PATTERN (insn), record_hard_reg_uses, &this_used);
682 AND_COMPL_HARD_REG_SET (this_used, prologue_clobbered);
683 IOR_HARD_REG_SET (prologue_used, this_used);
684 note_stores (PATTERN (insn), record_hard_reg_sets, &prologue_clobbered);
685 }
686 CLEAR_HARD_REG_BIT (prologue_clobbered, STACK_POINTER_REGNUM);
687 if (frame_pointer_needed)
688 CLEAR_HARD_REG_BIT (prologue_clobbered, HARD_FRAME_POINTER_REGNUM);
689
690 /* Find out what registers are set up by the prologue; any use of these
691 cannot happen before the prologue. */
692
693 struct hard_reg_set_container set_up_by_prologue;
694 CLEAR_HARD_REG_SET (set_up_by_prologue.set);
695 add_to_hard_reg_set (&set_up_by_prologue.set, Pmode, STACK_POINTER_REGNUM);
696 add_to_hard_reg_set (&set_up_by_prologue.set, Pmode, ARG_POINTER_REGNUM);
697 if (frame_pointer_needed)
698 add_to_hard_reg_set (&set_up_by_prologue.set, Pmode,
699 HARD_FRAME_POINTER_REGNUM);
700 if (pic_offset_table_rtx
701 && (unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM)
702 add_to_hard_reg_set (&set_up_by_prologue.set, Pmode,
703 PIC_OFFSET_TABLE_REGNUM);
704 if (crtl->drap_reg)
705 add_to_hard_reg_set (&set_up_by_prologue.set,
706 GET_MODE (crtl->drap_reg),
707 REGNO (crtl->drap_reg));
708 if (targetm.set_up_by_prologue)
709 targetm.set_up_by_prologue (&set_up_by_prologue);
710
711 /* We will insert the prologue before the basic block PRO. PRO should
712 dominate all basic blocks that need the prologue to be executed
713 before them. First, make PRO the "tightest wrap" possible. */
714
715 calculate_dominance_info (CDI_DOMINATORS);
716
717 basic_block pro = 0;
718
719 basic_block bb;
720 edge e;
721 edge_iterator ei;
722 FOR_EACH_BB_FN (bb, cfun)
723 {
724 rtx_insn *insn;
725 FOR_BB_INSNS (bb, insn)
726 if (NONDEBUG_INSN_P (insn)
727 && requires_stack_frame_p (insn, prologue_used,
728 set_up_by_prologue.set))
729 {
730 if (dump_file)
731 fprintf (dump_file, "Block %d needs the prologue.\n", bb->index);
732 pro = nearest_common_dominator (CDI_DOMINATORS, pro, bb);
733 break;
734 }
735 }
736
737 /* If nothing needs a prologue, just put it at the start. This really
738 shouldn't happen, but we cannot fix it here. */
739
740 if (pro == 0)
741 {
742 if (dump_file)
743 fprintf(dump_file, "Nothing needs a prologue, but it isn't empty; "
744 "putting it at the start.\n");
745 pro = entry;
746 }
747
748 if (dump_file)
749 fprintf (dump_file, "After wrapping required blocks, PRO is now %d\n",
750 pro->index);
751
752 /* Now see if we can put the prologue at the start of PRO. Putting it
753 there might require duplicating a block that cannot be duplicated,
754 or in some cases we cannot insert the prologue there at all. If PRO
755 wont't do, try again with the immediate dominator of PRO, and so on.
756
757 The blocks that need duplicating are those reachable from PRO but
758 not dominated by it. We keep in BB_WITH a bitmap of the blocks
759 reachable from PRO that we already found, and in VEC a stack of
760 those we still need to consider (to find successors). */
761
762 auto_bitmap bb_with;
763 bitmap_set_bit (bb_with, pro->index);
764
765 vec<basic_block> vec;
766 vec.create (n_basic_blocks_for_fn (cfun));
767 vec.quick_push (pro);
768
769 unsigned max_grow_size = get_uncond_jump_length ();
770 max_grow_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
771
772 while (!vec.is_empty () && pro != entry)
773 {
774 while (pro != entry && !can_get_prologue (pro, prologue_clobbered))
775 {
776 pro = get_immediate_dominator (CDI_DOMINATORS, pro);
777
778 if (bitmap_set_bit (bb_with, pro->index))
779 vec.quick_push (pro);
780 }
781
782 basic_block bb = vec.pop ();
783 if (!can_dup_for_shrink_wrapping (bb, pro, max_grow_size))
784 while (!dominated_by_p (CDI_DOMINATORS, bb, pro))
785 {
786 gcc_assert (pro != entry);
787
788 pro = get_immediate_dominator (CDI_DOMINATORS, pro);
789
790 if (bitmap_set_bit (bb_with, pro->index))
791 vec.quick_push (pro);
792 }
793
794 FOR_EACH_EDGE (e, ei, bb->succs)
795 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
796 && bitmap_set_bit (bb_with, e->dest->index))
797 vec.quick_push (e->dest);
798 }
799
800 if (dump_file)
801 fprintf (dump_file, "Avoiding non-duplicatable blocks, PRO is now %d\n",
802 pro->index);
803
804 /* If we can move PRO back without having to duplicate more blocks, do so.
805 We do this because putting the prologue earlier is better for scheduling.
806
807 We can move back to a block PRE if every path from PRE will eventually
808 need a prologue, that is, PRO is a post-dominator of PRE. PRE needs
809 to dominate every block reachable from itself. We keep in BB_TMP a
810 bitmap of the blocks reachable from PRE that we already found, and in
811 VEC a stack of those we still need to consider.
812
813 Any block reachable from PRE is also reachable from all predecessors
814 of PRE, so if we find we need to move PRE back further we can leave
815 everything not considered so far on the stack. Any block dominated
816 by PRE is also dominated by all other dominators of PRE, so anything
817 found good for some PRE does not need to be reconsidered later.
818
819 We don't need to update BB_WITH because none of the new blocks found
820 can jump to a block that does not need the prologue. */
821
822 if (pro != entry)
823 {
824 calculate_dominance_info (CDI_POST_DOMINATORS);
825
826 auto_bitmap bb_tmp;
827 bitmap_copy (bb_tmp, bb_with);
828 basic_block last_ok = pro;
829 vec.truncate (0);
830
831 while (pro != entry)
832 {
833 basic_block pre = get_immediate_dominator (CDI_DOMINATORS, pro);
834 if (!dominated_by_p (CDI_POST_DOMINATORS, pre, pro))
835 break;
836
837 if (bitmap_set_bit (bb_tmp, pre->index))
838 vec.quick_push (pre);
839
840 bool ok = true;
841 while (!vec.is_empty ())
842 {
843 if (!dominated_by_p (CDI_DOMINATORS, vec.last (), pre))
844 {
845 ok = false;
846 break;
847 }
848
849 basic_block bb = vec.pop ();
850 FOR_EACH_EDGE (e, ei, bb->succs)
851 if (bitmap_set_bit (bb_tmp, e->dest->index))
852 vec.quick_push (e->dest);
853 }
854
855 if (ok && can_get_prologue (pre, prologue_clobbered))
856 last_ok = pre;
857
858 pro = pre;
859 }
860
861 pro = last_ok;
862
863 free_dominance_info (CDI_POST_DOMINATORS);
864 }
865
866 vec.release ();
867
868 if (dump_file)
869 fprintf (dump_file, "Bumping back to anticipatable blocks, PRO is now %d\n",
870 pro->index);
871
872 if (pro == entry)
873 {
874 free_dominance_info (CDI_DOMINATORS);
875 return;
876 }
877
878 /* Compute what fraction of the frequency and count of the blocks that run
879 both with and without prologue are for running with prologue. This gives
880 the correct answer for reducible flow graphs; for irreducible flow graphs
881 our profile is messed up beyond repair anyway. */
882
883 profile_count num = profile_count::zero ();
884 profile_count den = profile_count::zero ();
885
886 FOR_EACH_EDGE (e, ei, pro->preds)
887 if (!dominated_by_p (CDI_DOMINATORS, e->src, pro))
888 {
889 if (e->count ().initialized_p ())
890 num += e->count ();
891 if (e->src->count.initialized_p ())
892 den += e->src->count;
893 }
894
895 /* All is okay, so do it. */
896
897 crtl->shrink_wrapped = true;
898 if (dump_file)
899 fprintf (dump_file, "Performing shrink-wrapping.\n");
900
901 /* Copy the blocks that can run both with and without prologue. The
902 originals run with prologue, the copies without. Store a pointer to
903 the copy in the ->aux field of the original. */
904
905 FOR_EACH_BB_FN (bb, cfun)
906 if (bitmap_bit_p (bb_with, bb->index)
907 && !dominated_by_p (CDI_DOMINATORS, bb, pro))
908 {
909 basic_block dup = duplicate_block (bb, 0, 0);
910
911 bb->aux = dup;
912
913 if (JUMP_P (BB_END (dup)) && !any_condjump_p (BB_END (dup)))
914 emit_barrier_after_bb (dup);
915
916 if (EDGE_COUNT (dup->succs) == 0)
917 emit_barrier_after_bb (dup);
918
919 if (dump_file)
920 fprintf (dump_file, "Duplicated %d to %d\n", bb->index, dup->index);
921
922 if (num == profile_count::zero () || den.nonzero_p ())
923 bb->count = bb->count.apply_scale (num, den);
924 dup->count -= bb->count;
925 }
926
927 /* Now change the edges to point to the copies, where appropriate. */
928
929 FOR_EACH_BB_FN (bb, cfun)
930 if (!dominated_by_p (CDI_DOMINATORS, bb, pro))
931 {
932 basic_block src = bb;
933 if (bitmap_bit_p (bb_with, bb->index))
934 src = (basic_block) bb->aux;
935
936 FOR_EACH_EDGE (e, ei, src->succs)
937 {
938 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
939 continue;
940
941 if (bitmap_bit_p (bb_with, e->dest->index)
942 && !dominated_by_p (CDI_DOMINATORS, e->dest, pro))
943 {
944 if (dump_file)
945 fprintf (dump_file, "Redirecting edge %d->%d to %d\n",
946 e->src->index, e->dest->index,
947 ((basic_block) e->dest->aux)->index);
948 redirect_edge_and_branch_force (e, (basic_block) e->dest->aux);
949 }
950 else if (e->flags & EDGE_FALLTHRU
951 && bitmap_bit_p (bb_with, bb->index))
952 force_nonfallthru (e);
953 }
954 }
955
956 /* Also redirect the function entry edge if necessary. */
957
958 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
959 if (bitmap_bit_p (bb_with, e->dest->index)
960 && !dominated_by_p (CDI_DOMINATORS, e->dest, pro))
961 {
962 basic_block split_bb = split_edge (e);
963 e = single_succ_edge (split_bb);
964 redirect_edge_and_branch_force (e, (basic_block) e->dest->aux);
965 }
966
967 /* Make a simple_return for those exits that run without prologue. */
968
969 FOR_EACH_BB_REVERSE_FN (bb, cfun)
970 if (!bitmap_bit_p (bb_with, bb->index))
971 FOR_EACH_EDGE (e, ei, bb->succs)
972 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
973 handle_simple_exit (e);
974
975 /* Finally, we want a single edge to put the prologue on. Make a new
976 block before the PRO block; the edge beteen them is the edge we want.
977 Then redirect those edges into PRO that come from blocks without the
978 prologue, to point to the new block instead. The new prologue block
979 is put at the end of the insn chain. */
980
981 basic_block new_bb = create_empty_bb (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
982 BB_COPY_PARTITION (new_bb, pro);
983 new_bb->count = profile_count::zero ();
984 if (dump_file)
985 fprintf (dump_file, "Made prologue block %d\n", new_bb->index);
986
987 for (ei = ei_start (pro->preds); (e = ei_safe_edge (ei)); )
988 {
989 if (bitmap_bit_p (bb_with, e->src->index)
990 || dominated_by_p (CDI_DOMINATORS, e->src, pro))
991 {
992 ei_next (&ei);
993 continue;
994 }
995
996 new_bb->count += e->count ();
997
998 redirect_edge_and_branch_force (e, new_bb);
999 if (dump_file)
1000 fprintf (dump_file, "Redirected edge from %d\n", e->src->index);
1001 }
1002
1003 *entry_edge = make_single_succ_edge (new_bb, pro, EDGE_FALLTHRU);
1004 force_nonfallthru (*entry_edge);
1005
1006 free_dominance_info (CDI_DOMINATORS);
1007}
1008
1009/* Separate shrink-wrapping
1010
1011 Instead of putting all of the prologue and epilogue in one spot, we
1012 can put parts of it in places where those components are executed less
1013 frequently. The following code does this, for prologue and epilogue
1014 components that can be put in more than one location, and where those
1015 components can be executed more than once (the epilogue component will
1016 always be executed before the prologue component is executed a second
1017 time).
1018
1019 What exactly is a component is target-dependent. The more usual
1020 components are simple saves/restores to/from the frame of callee-saved
1021 registers. This code treats components abstractly (as an sbitmap),
1022 letting the target handle all details.
1023
1024 Prologue components are placed in such a way that for every component
1025 the prologue is executed as infrequently as possible. We do this by
1026 walking the dominator tree, comparing the cost of placing a prologue
1027 component before a block to the sum of costs determined for all subtrees
1028 of that block.
1029
1030 From this placement, we then determine for each component all blocks
1031 where at least one of this block's dominators (including itself) will
1032 get a prologue inserted. That then is how the components are placed.
1033 We could place the epilogue components a bit smarter (we can save a
1034 bit of code size sometimes); this is a possible future improvement.
1035
1036 Prologues and epilogues are preferably placed into a block, either at
1037 the beginning or end of it, if it is needed for all predecessor resp.
1038 successor edges; or placed on the edge otherwise.
1039
1040 If the placement of any prologue/epilogue leads to a situation we cannot
1041 handle (for example, an abnormal edge would need to be split, or some
1042 targets want to use some specific registers that may not be available
1043 where we want to put them), separate shrink-wrapping for the components
1044 in that prologue/epilogue is aborted. */
1045
1046
1047/* Print the sbitmap COMPONENTS to the DUMP_FILE if not empty, with the
1048 label LABEL. */
1049static void
1050dump_components (const char *label, sbitmap components)
1051{
1052 if (bitmap_empty_p (components))
1053 return;
1054
1055 fprintf (dump_file, " [%s", label);
1056
1057 for (unsigned int j = 0; j < components->n_bits; j++)
1058 if (bitmap_bit_p (components, j))
1059 fprintf (dump_file, " %u", j);
1060
1061 fprintf (dump_file, "]");
1062}
1063
1064/* The data we collect for each bb. */
1065struct sw {
1066 /* What components does this BB need? */
1067 sbitmap needs_components;
1068
1069 /* What components does this BB have? This is the main decision this
1070 pass makes. */
1071 sbitmap has_components;
1072
1073 /* The components for which we placed code at the start of the BB (instead
1074 of on all incoming edges). */
1075 sbitmap head_components;
1076
1077 /* The components for which we placed code at the end of the BB (instead
1078 of on all outgoing edges). */
1079 sbitmap tail_components;
1080
1081 /* The frequency of executing the prologue for this BB, if a prologue is
1082 placed on this BB. This is a pessimistic estimate (no prologue is
1083 needed for edges from blocks that have the component under consideration
1084 active already). */
1085 gcov_type own_cost;
1086
1087 /* The frequency of executing the prologue for this BB and all BBs
1088 dominated by it. */
1089 gcov_type total_cost;
1090};
1091
1092/* A helper function for accessing the pass-specific info. */
1093static inline struct sw *
1094SW (basic_block bb)
1095{
1096 gcc_assert (bb->aux);
1097 return (struct sw *) bb->aux;
1098}
1099
1100/* Create the pass-specific data structures for separately shrink-wrapping
1101 with components COMPONENTS. */
1102static void
1103init_separate_shrink_wrap (sbitmap components)
1104{
1105 basic_block bb;
1106 FOR_ALL_BB_FN (bb, cfun)
1107 {
1108 bb->aux = xcalloc (1, sizeof (struct sw));
1109
1110 SW (bb)->needs_components = targetm.shrink_wrap.components_for_bb (bb);
1111
1112 /* Mark all basic blocks without successor as needing all components.
1113 This avoids problems in at least cfgcleanup, sel-sched, and
1114 regrename (largely to do with all paths to such a block still
1115 needing the same dwarf CFI info). */
1116 if (EDGE_COUNT (bb->succs) == 0)
1117 bitmap_copy (SW (bb)->needs_components, components);
1118
1119 if (dump_file)
1120 {
1121 fprintf (dump_file, "bb %d components:", bb->index);
1122 dump_components ("has", SW (bb)->needs_components);
1123 fprintf (dump_file, "\n");
1124 }
1125
1126 SW (bb)->has_components = sbitmap_alloc (SBITMAP_SIZE (components));
1127 SW (bb)->head_components = sbitmap_alloc (SBITMAP_SIZE (components));
1128 SW (bb)->tail_components = sbitmap_alloc (SBITMAP_SIZE (components));
1129 bitmap_clear (SW (bb)->has_components);
1130 }
1131}
1132
1133/* Destroy the pass-specific data. */
1134static void
1135fini_separate_shrink_wrap (void)
1136{
1137 basic_block bb;
1138 FOR_ALL_BB_FN (bb, cfun)
1139 if (bb->aux)
1140 {
1141 sbitmap_free (SW (bb)->needs_components);
1142 sbitmap_free (SW (bb)->has_components);
1143 sbitmap_free (SW (bb)->head_components);
1144 sbitmap_free (SW (bb)->tail_components);
1145 free (bb->aux);
1146 bb->aux = 0;
1147 }
1148}
1149
1150/* Place the prologue for component WHICH, in the basic blocks dominated
1151 by HEAD. Do a DFS over the dominator tree, and set bit WHICH in the
1152 HAS_COMPONENTS of a block if either the block has that bit set in
1153 NEEDS_COMPONENTS, or it is cheaper to place the prologue here than in all
1154 dominator subtrees separately. */
1155static void
1156place_prologue_for_one_component (unsigned int which, basic_block head)
1157{
1158 /* The block we are currently dealing with. */
1159 basic_block bb = head;
1160 /* Is this the first time we visit this block, i.e. have we just gone
1161 down the tree. */
1162 bool first_visit = true;
1163
1164 /* Walk the dominator tree, visit one block per iteration of this loop.
1165 Each basic block is visited twice: once before visiting any children
1166 of the block, and once after visiting all of them (leaf nodes are
1167 visited only once). As an optimization, we do not visit subtrees
1168 that can no longer influence the prologue placement. */
1169 for (;;)
1170 {
1171 /* First visit of a block: set the (children) cost accumulator to zero;
1172 if the block does not have the component itself, walk down. */
1173 if (first_visit)
1174 {
1175 /* Initialize the cost. The cost is the block execution frequency
1176 that does not come from backedges. Calculating this by simply
1177 adding the cost of all edges that aren't backedges does not
1178 work: this does not always add up to the block frequency at
1179 all, and even if it does, rounding error makes for bad
1180 decisions. */
1181 SW (bb)->own_cost = bb->count.to_frequency (cfun);
1182
1183 edge e;
1184 edge_iterator ei;
1185 FOR_EACH_EDGE (e, ei, bb->preds)
1186 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1187 {
1188 if (SW (bb)->own_cost > EDGE_FREQUENCY (e))
1189 SW (bb)->own_cost -= EDGE_FREQUENCY (e);
1190 else
1191 SW (bb)->own_cost = 0;
1192 }
1193
1194 SW (bb)->total_cost = 0;
1195
1196 if (!bitmap_bit_p (SW (bb)->needs_components, which)
1197 && first_dom_son (CDI_DOMINATORS, bb))
1198 {
1199 bb = first_dom_son (CDI_DOMINATORS, bb);
1200 continue;
1201 }
1202 }
1203
1204 /* If this block does need the component itself, or it is cheaper to
1205 put the prologue here than in all the descendants that need it,
1206 mark it so. If this block's immediate post-dominator is dominated
1207 by this block, and that needs the prologue, we can put it on this
1208 block as well (earlier is better). */
1209 if (bitmap_bit_p (SW (bb)->needs_components, which)
1210 || SW (bb)->total_cost > SW (bb)->own_cost)
1211 {
1212 SW (bb)->total_cost = SW (bb)->own_cost;
1213 bitmap_set_bit (SW (bb)->has_components, which);
1214 }
1215 else
1216 {
1217 basic_block kid = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
1218 if (dominated_by_p (CDI_DOMINATORS, kid, bb)
1219 && bitmap_bit_p (SW (kid)->has_components, which))
1220 {
1221 SW (bb)->total_cost = SW (bb)->own_cost;
1222 bitmap_set_bit (SW (bb)->has_components, which);
1223 }
1224 }
1225
1226 /* We are back where we started, so we are done now. */
1227 if (bb == head)
1228 return;
1229
1230 /* We now know the cost of the subtree rooted at the current block.
1231 Accumulate this cost in the parent. */
1232 basic_block parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1233 SW (parent)->total_cost += SW (bb)->total_cost;
1234
1235 /* Don't walk the tree down unless necessary. */
1236 if (next_dom_son (CDI_DOMINATORS, bb)
1237 && SW (parent)->total_cost <= SW (parent)->own_cost)
1238 {
1239 bb = next_dom_son (CDI_DOMINATORS, bb);
1240 first_visit = true;
1241 }
1242 else
1243 {
1244 bb = parent;
1245 first_visit = false;
1246 }
1247 }
1248}
1249
1250/* Set HAS_COMPONENTS in every block to the maximum it can be set to without
1251 setting it on any path from entry to exit where it was not already set
1252 somewhere (or, for blocks that have no path to the exit, consider only
1253 paths from the entry to the block itself). */
1254static void
1255spread_components (sbitmap components)
1256{
1257 basic_block entry_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1258 basic_block exit_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
1259
1260 /* A stack of all blocks left to consider, and a bitmap of all blocks
1261 on that stack. */
1262 vec<basic_block> todo;
1263 todo.create (n_basic_blocks_for_fn (cfun));
1264 auto_bitmap seen;
1265
1266 auto_sbitmap old (SBITMAP_SIZE (components));
1267
1268 /* Find for every block the components that are *not* needed on some path
1269 from the entry to that block. Do this with a flood fill from the entry
1270 block. Every block can be visited at most as often as the number of
1271 components (plus one), and usually much less often. */
1272
1273 if (dump_file)
1274 fprintf (dump_file, "Spreading down...\n");
1275
1276 basic_block bb;
1277 FOR_ALL_BB_FN (bb, cfun)
1278 bitmap_clear (SW (bb)->head_components);
1279
1280 bitmap_copy (SW (entry_block)->head_components, components);
1281
1282 edge e;
1283 edge_iterator ei;
1284
1285 todo.quick_push (single_succ (entry_block));
1286 bitmap_set_bit (seen, single_succ (entry_block)->index);
1287 while (!todo.is_empty ())
1288 {
1289 bb = todo.pop ();
1290
1291 bitmap_copy (old, SW (bb)->head_components);
1292
1293 FOR_EACH_EDGE (e, ei, bb->preds)
1294 bitmap_ior (SW (bb)->head_components, SW (bb)->head_components,
1295 SW (e->src)->head_components);
1296
1297 bitmap_and_compl (SW (bb)->head_components, SW (bb)->head_components,
1298 SW (bb)->has_components);
1299
1300 if (!bitmap_equal_p (old, SW (bb)->head_components))
1301 FOR_EACH_EDGE (e, ei, bb->succs)
1302 if (bitmap_set_bit (seen, e->dest->index))
1303 todo.quick_push (e->dest);
1304
1305 bitmap_clear_bit (seen, bb->index);
1306 }
1307
1308 /* Find for every block the components that are *not* needed on some reverse
1309 path from the exit to that block. */
1310
1311 if (dump_file)
1312 fprintf (dump_file, "Spreading up...\n");
1313
1314 /* First, mark all blocks not reachable from the exit block as not needing
1315 any component on any path to the exit. Mark everything, and then clear
1316 again by a flood fill. */
1317
1318 FOR_ALL_BB_FN (bb, cfun)
1319 bitmap_copy (SW (bb)->tail_components, components);
1320
1321 FOR_EACH_EDGE (e, ei, exit_block->preds)
1322 {
1323 todo.quick_push (e->src);
1324 bitmap_set_bit (seen, e->src->index);
1325 }
1326
1327 while (!todo.is_empty ())
1328 {
1329 bb = todo.pop ();
1330
1331 if (!bitmap_empty_p (SW (bb)->tail_components))
1332 FOR_EACH_EDGE (e, ei, bb->preds)
1333 if (bitmap_set_bit (seen, e->src->index))
1334 todo.quick_push (e->src);
1335
1336 bitmap_clear (SW (bb)->tail_components);
1337
1338 bitmap_clear_bit (seen, bb->index);
1339 }
1340
1341 /* And then, flood fill backwards to find for every block the components
1342 not needed on some path to the exit. */
1343
1344 bitmap_copy (SW (exit_block)->tail_components, components);
1345
1346 FOR_EACH_EDGE (e, ei, exit_block->preds)
1347 {
1348 todo.quick_push (e->src);
1349 bitmap_set_bit (seen, e->src->index);
1350 }
1351
1352 while (!todo.is_empty ())
1353 {
1354 bb = todo.pop ();
1355
1356 bitmap_copy (old, SW (bb)->tail_components);
1357
1358 FOR_EACH_EDGE (e, ei, bb->succs)
1359 bitmap_ior (SW (bb)->tail_components, SW (bb)->tail_components,
1360 SW (e->dest)->tail_components);
1361
1362 bitmap_and_compl (SW (bb)->tail_components, SW (bb)->tail_components,
1363 SW (bb)->has_components);
1364
1365 if (!bitmap_equal_p (old, SW (bb)->tail_components))
1366 FOR_EACH_EDGE (e, ei, bb->preds)
1367 if (bitmap_set_bit (seen, e->src->index))
1368 todo.quick_push (e->src);
1369
1370 bitmap_clear_bit (seen, bb->index);
1371 }
1372
1373 /* Finally, mark everything not not needed both forwards and backwards. */
1374
1375 FOR_EACH_BB_FN (bb, cfun)
1376 {
1377 bitmap_and (SW (bb)->head_components, SW (bb)->head_components,
1378 SW (bb)->tail_components);
1379 bitmap_and_compl (SW (bb)->has_components, components,
1380 SW (bb)->head_components);
1381 }
1382
1383 FOR_ALL_BB_FN (bb, cfun)
1384 {
1385 if (dump_file)
1386 {
1387 fprintf (dump_file, "bb %d components:", bb->index);
1388 dump_components ("has", SW (bb)->has_components);
1389 fprintf (dump_file, "\n");
1390 }
1391 }
1392}
1393
1394/* If we cannot handle placing some component's prologues or epilogues where
1395 we decided we should place them, unmark that component in COMPONENTS so
1396 that it is not wrapped separately. */
1397static void
1398disqualify_problematic_components (sbitmap components)
1399{
1400 auto_sbitmap pro (SBITMAP_SIZE (components));
1401 auto_sbitmap epi (SBITMAP_SIZE (components));
1402
1403 basic_block bb;
1404 FOR_EACH_BB_FN (bb, cfun)
1405 {
1406 edge e;
1407 edge_iterator ei;
1408 FOR_EACH_EDGE (e, ei, bb->succs)
1409 {
1410 /* Find which components we want pro/epilogues for here. */
1411 bitmap_and_compl (epi, SW (e->src)->has_components,
1412 SW (e->dest)->has_components);
1413 bitmap_and_compl (pro, SW (e->dest)->has_components,
1414 SW (e->src)->has_components);
1415
1416 /* Ask the target what it thinks about things. */
1417 if (!bitmap_empty_p (epi))
1418 targetm.shrink_wrap.disqualify_components (components, e, epi,
1419 false);
1420 if (!bitmap_empty_p (pro))
1421 targetm.shrink_wrap.disqualify_components (components, e, pro,
1422 true);
1423
1424 /* If this edge doesn't need splitting, we're fine. */
1425 if (single_pred_p (e->dest)
1426 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1427 continue;
1428
1429 /* If the edge can be split, that is fine too. */
1430 if ((e->flags & EDGE_ABNORMAL) == 0)
1431 continue;
1432
1433 /* We also can handle sibcalls. */
1434 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1435 {
1436 gcc_assert (e->flags & EDGE_SIBCALL);
1437 continue;
1438 }
1439
1440 /* Remove from consideration those components we would need
1441 pro/epilogues for on edges where we cannot insert them. */
1442 bitmap_and_compl (components, components, epi);
1443 bitmap_and_compl (components, components, pro);
1444
1445 if (dump_file && !bitmap_subset_p (epi, components))
1446 {
1447 fprintf (dump_file, " BAD epi %d->%d", e->src->index,
1448 e->dest->index);
1449 if (e->flags & EDGE_EH)
1450 fprintf (dump_file, " for EH");
1451 dump_components ("epi", epi);
1452 fprintf (dump_file, "\n");
1453 }
1454
1455 if (dump_file && !bitmap_subset_p (pro, components))
1456 {
1457 fprintf (dump_file, " BAD pro %d->%d", e->src->index,
1458 e->dest->index);
1459 if (e->flags & EDGE_EH)
1460 fprintf (dump_file, " for EH");
1461 dump_components ("pro", pro);
1462 fprintf (dump_file, "\n");
1463 }
1464 }
1465 }
1466}
1467
1468/* Place code for prologues and epilogues for COMPONENTS where we can put
1469 that code at the start of basic blocks. */
1470static void
1471emit_common_heads_for_components (sbitmap components)
1472{
1473 auto_sbitmap pro (SBITMAP_SIZE (components));
1474 auto_sbitmap epi (SBITMAP_SIZE (components));
1475 auto_sbitmap tmp (SBITMAP_SIZE (components));
1476
1477 basic_block bb;
1478 FOR_ALL_BB_FN (bb, cfun)
1479 bitmap_clear (SW (bb)->head_components);
1480
1481 FOR_EACH_BB_FN (bb, cfun)
1482 {
1483 /* Find which prologue resp. epilogue components are needed for all
1484 predecessor edges to this block. */
1485
1486 /* First, select all possible components. */
1487 bitmap_copy (epi, components);
1488 bitmap_copy (pro, components);
1489
1490 edge e;
1491 edge_iterator ei;
1492 FOR_EACH_EDGE (e, ei, bb->preds)
1493 {
1494 if (e->flags & EDGE_ABNORMAL)
1495 {
1496 bitmap_clear (epi);
1497 bitmap_clear (pro);
1498 break;
1499 }
1500
1501 /* Deselect those epilogue components that should not be inserted
1502 for this edge. */
1503 bitmap_and_compl (tmp, SW (e->src)->has_components,
1504 SW (e->dest)->has_components);
1505 bitmap_and (epi, epi, tmp);
1506
1507 /* Similar, for the prologue. */
1508 bitmap_and_compl (tmp, SW (e->dest)->has_components,
1509 SW (e->src)->has_components);
1510 bitmap_and (pro, pro, tmp);
1511 }
1512
1513 if (dump_file && !(bitmap_empty_p (epi) && bitmap_empty_p (pro)))
1514 fprintf (dump_file, " bb %d", bb->index);
1515
1516 if (dump_file && !bitmap_empty_p (epi))
1517 dump_components ("epi", epi);
1518 if (dump_file && !bitmap_empty_p (pro))
1519 dump_components ("pro", pro);
1520
1521 if (dump_file && !(bitmap_empty_p (epi) && bitmap_empty_p (pro)))
1522 fprintf (dump_file, "\n");
1523
1524 /* Place code after the BB note. */
1525 if (!bitmap_empty_p (pro))
1526 {
1527 start_sequence ();
1528 targetm.shrink_wrap.emit_prologue_components (pro);
1529 rtx_insn *seq = get_insns ();
1530 end_sequence ();
1531 record_prologue_seq (seq);
1532
1533 emit_insn_after (seq, bb_note (bb));
1534
1535 bitmap_ior (SW (bb)->head_components, SW (bb)->head_components, pro);
1536 }
1537
1538 if (!bitmap_empty_p (epi))
1539 {
1540 start_sequence ();
1541 targetm.shrink_wrap.emit_epilogue_components (epi);
1542 rtx_insn *seq = get_insns ();
1543 end_sequence ();
1544 record_epilogue_seq (seq);
1545
1546 emit_insn_after (seq, bb_note (bb));
1547
1548 bitmap_ior (SW (bb)->head_components, SW (bb)->head_components, epi);
1549 }
1550 }
1551}
1552
1553/* Place code for prologues and epilogues for COMPONENTS where we can put
1554 that code at the end of basic blocks. */
1555static void
1556emit_common_tails_for_components (sbitmap components)
1557{
1558 auto_sbitmap pro (SBITMAP_SIZE (components));
1559 auto_sbitmap epi (SBITMAP_SIZE (components));
1560 auto_sbitmap tmp (SBITMAP_SIZE (components));
1561
1562 basic_block bb;
1563 FOR_ALL_BB_FN (bb, cfun)
1564 bitmap_clear (SW (bb)->tail_components);
1565
1566 FOR_EACH_BB_FN (bb, cfun)
1567 {
1568 /* Find which prologue resp. epilogue components are needed for all
1569 successor edges from this block. */
1570 if (EDGE_COUNT (bb->succs) == 0)
1571 continue;
1572
1573 /* First, select all possible components. */
1574 bitmap_copy (epi, components);
1575 bitmap_copy (pro, components);
1576
1577 edge e;
1578 edge_iterator ei;
1579 FOR_EACH_EDGE (e, ei, bb->succs)
1580 {
1581 if (e->flags & EDGE_ABNORMAL)
1582 {
1583 bitmap_clear (epi);
1584 bitmap_clear (pro);
1585 break;
1586 }
1587
1588 /* Deselect those epilogue components that should not be inserted
1589 for this edge, and also those that are already put at the head
1590 of the successor block. */
1591 bitmap_and_compl (tmp, SW (e->src)->has_components,
1592 SW (e->dest)->has_components);
1593 bitmap_and_compl (tmp, tmp, SW (e->dest)->head_components);
1594 bitmap_and (epi, epi, tmp);
1595
1596 /* Similarly, for the prologue. */
1597 bitmap_and_compl (tmp, SW (e->dest)->has_components,
1598 SW (e->src)->has_components);
1599 bitmap_and_compl (tmp, tmp, SW (e->dest)->head_components);
1600 bitmap_and (pro, pro, tmp);
1601 }
1602
1603 /* If the last insn of this block is a control flow insn we cannot
1604 put anything after it. We can put our code before it instead,
1605 but only if that jump insn is a simple jump. */
1606 rtx_insn *last_insn = BB_END (bb);
1607 if (control_flow_insn_p (last_insn) && !simplejump_p (last_insn))
1608 {
1609 bitmap_clear (epi);
1610 bitmap_clear (pro);
1611 }
1612
1613 if (dump_file && !(bitmap_empty_p (epi) && bitmap_empty_p (pro)))
1614 fprintf (dump_file, " bb %d", bb->index);
1615
1616 if (dump_file && !bitmap_empty_p (epi))
1617 dump_components ("epi", epi);
1618 if (dump_file && !bitmap_empty_p (pro))
1619 dump_components ("pro", pro);
1620
1621 if (dump_file && !(bitmap_empty_p (epi) && bitmap_empty_p (pro)))
1622 fprintf (dump_file, "\n");
1623
1624 /* Put the code at the end of the BB, but before any final jump. */
1625 if (!bitmap_empty_p (epi))
1626 {
1627 start_sequence ();
1628 targetm.shrink_wrap.emit_epilogue_components (epi);
1629 rtx_insn *seq = get_insns ();
1630 end_sequence ();
1631 record_epilogue_seq (seq);
1632
1633 if (control_flow_insn_p (last_insn))
1634 emit_insn_before (seq, last_insn);
1635 else
1636 emit_insn_after (seq, last_insn);
1637
1638 bitmap_ior (SW (bb)->tail_components, SW (bb)->tail_components, epi);
1639 }
1640
1641 if (!bitmap_empty_p (pro))
1642 {
1643 start_sequence ();
1644 targetm.shrink_wrap.emit_prologue_components (pro);
1645 rtx_insn *seq = get_insns ();
1646 end_sequence ();
1647 record_prologue_seq (seq);
1648
1649 if (control_flow_insn_p (last_insn))
1650 emit_insn_before (seq, last_insn);
1651 else
1652 emit_insn_after (seq, last_insn);
1653
1654 bitmap_ior (SW (bb)->tail_components, SW (bb)->tail_components, pro);
1655 }
1656 }
1657}
1658
1659/* Place prologues and epilogues for COMPONENTS on edges, if we haven't already
1660 placed them inside blocks directly. */
1661static void
1662insert_prologue_epilogue_for_components (sbitmap components)
1663{
1664 auto_sbitmap pro (SBITMAP_SIZE (components));
1665 auto_sbitmap epi (SBITMAP_SIZE (components));
1666
1667 basic_block bb;
1668 FOR_EACH_BB_FN (bb, cfun)
1669 {
1670 if (!bb->aux)
1671 continue;
1672
1673 edge e;
1674 edge_iterator ei;
1675 FOR_EACH_EDGE (e, ei, bb->succs)
1676 {
1677 /* Find which pro/epilogue components are needed on this edge. */
1678 bitmap_and_compl (epi, SW (e->src)->has_components,
1679 SW (e->dest)->has_components);
1680 bitmap_and_compl (pro, SW (e->dest)->has_components,
1681 SW (e->src)->has_components);
1682 bitmap_and (epi, epi, components);
1683 bitmap_and (pro, pro, components);
1684
1685 /* Deselect those we already have put at the head or tail of the
1686 edge's dest resp. src. */
1687 bitmap_and_compl (epi, epi, SW (e->dest)->head_components);
1688 bitmap_and_compl (pro, pro, SW (e->dest)->head_components);
1689 bitmap_and_compl (epi, epi, SW (e->src)->tail_components);
1690 bitmap_and_compl (pro, pro, SW (e->src)->tail_components);
1691
1692 if (!bitmap_empty_p (epi) || !bitmap_empty_p (pro))
1693 {
1694 if (dump_file)
1695 {
1696 fprintf (dump_file, " %d->%d", e->src->index,
1697 e->dest->index);
1698 dump_components ("epi", epi);
1699 dump_components ("pro", pro);
1700 if (e->flags & EDGE_SIBCALL)
1701 fprintf (dump_file, " (SIBCALL)");
1702 else if (e->flags & EDGE_ABNORMAL)
1703 fprintf (dump_file, " (ABNORMAL)");
1704 fprintf (dump_file, "\n");
1705 }
1706
1707 /* Put the epilogue components in place. */
1708 start_sequence ();
1709 targetm.shrink_wrap.emit_epilogue_components (epi);
1710 rtx_insn *seq = get_insns ();
1711 end_sequence ();
1712 record_epilogue_seq (seq);
1713
1714 if (e->flags & EDGE_SIBCALL)
1715 {
1716 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun));
1717
1718 rtx_insn *insn = BB_END (e->src);
1719 gcc_assert (CALL_P (insn) && SIBLING_CALL_P (insn));
1720 emit_insn_before (seq, insn);
1721 }
1722 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1723 {
1724 gcc_assert (e->flags & EDGE_FALLTHRU);
1725 basic_block new_bb = split_edge (e);
1726 emit_insn_after (seq, BB_END (new_bb));
1727 }
1728 else
1729 insert_insn_on_edge (seq, e);
1730
1731 /* Put the prologue components in place. */
1732 start_sequence ();
1733 targetm.shrink_wrap.emit_prologue_components (pro);
1734 seq = get_insns ();
1735 end_sequence ();
1736 record_prologue_seq (seq);
1737
1738 insert_insn_on_edge (seq, e);
1739 }
1740 }
1741 }
1742
1743 commit_edge_insertions ();
1744}
1745
1746/* The main entry point to this subpass. FIRST_BB is where the prologue
1747 would be normally put. */
1748void
1749try_shrink_wrapping_separate (basic_block first_bb)
1750{
1751 if (HAVE_cc0)
1752 return;
1753
1754 if (!(SHRINK_WRAPPING_ENABLED
1755 && flag_shrink_wrap_separate
1756 && optimize_function_for_speed_p (cfun)
1757 && targetm.shrink_wrap.get_separate_components))
1758 return;
1759
1760 /* We don't handle "strange" functions. */
1761 if (cfun->calls_alloca
1762 || cfun->calls_setjmp
1763 || cfun->can_throw_non_call_exceptions
1764 || crtl->calls_eh_return
1765 || crtl->has_nonlocal_goto
1766 || crtl->saves_all_registers)
1767 return;
1768
1769 /* Ask the target what components there are. If it returns NULL, don't
1770 do anything. */
1771 sbitmap components = targetm.shrink_wrap.get_separate_components ();
1772 if (!components)
1773 return;
1774
1775 /* We need LIVE info, not defining anything in the entry block and not
1776 using anything in the exit block. A block then needs a component if
1777 the register for that component is in the IN or GEN or KILL set for
1778 that block. */
1779 df_scan->local_flags |= DF_SCAN_EMPTY_ENTRY_EXIT;
1780 df_update_entry_exit_and_calls ();
1781 df_live_add_problem ();
1782 df_live_set_all_dirty ();
1783 df_analyze ();
1784
1785 calculate_dominance_info (CDI_DOMINATORS);
1786 calculate_dominance_info (CDI_POST_DOMINATORS);
1787
1788 init_separate_shrink_wrap (components);
1789
1790 sbitmap_iterator sbi;
1791 unsigned int j;
1792 EXECUTE_IF_SET_IN_BITMAP (components, 0, j, sbi)
1793 place_prologue_for_one_component (j, first_bb);
1794
1795 spread_components (components);
1796
1797 disqualify_problematic_components (components);
1798
1799 /* Don't separately shrink-wrap anything where the "main" prologue will
1800 go; the target code can often optimize things if it is presented with
1801 all components together (say, if it generates store-multiple insns). */
1802 bitmap_and_compl (components, components, SW (first_bb)->has_components);
1803
1804 if (bitmap_empty_p (components))
1805 {
1806 if (dump_file)
1807 fprintf (dump_file, "Not wrapping anything separately.\n");
1808 }
1809 else
1810 {
1811 if (dump_file)
1812 {
1813 fprintf (dump_file, "The components we wrap separately are");
1814 dump_components ("sep", components);
1815 fprintf (dump_file, "\n");
1816
1817 fprintf (dump_file, "... Inserting common heads...\n");
1818 }
1819
1820 emit_common_heads_for_components (components);
1821
1822 if (dump_file)
1823 fprintf (dump_file, "... Inserting common tails...\n");
1824
1825 emit_common_tails_for_components (components);
1826
1827 if (dump_file)
1828 fprintf (dump_file, "... Inserting the more difficult ones...\n");
1829
1830 insert_prologue_epilogue_for_components (components);
1831
1832 if (dump_file)
1833 fprintf (dump_file, "... Done.\n");
1834
1835 targetm.shrink_wrap.set_handled_components (components);
1836
1837 crtl->shrink_wrapped_separate = true;
1838 }
1839
1840 fini_separate_shrink_wrap ();
1841
1842 sbitmap_free (components);
1843 free_dominance_info (CDI_DOMINATORS);
1844 free_dominance_info (CDI_POST_DOMINATORS);
1845
1846 /* All done. */
1847 df_scan->local_flags &= ~DF_SCAN_EMPTY_ENTRY_EXIT;
1848 df_update_entry_exit_and_calls ();
1849 df_live_set_all_dirty ();
1850 df_analyze ();
1851}
1852