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