]>
Commit | Line | Data |
---|---|---|
e974b93b | 1 | /* Shrink-wrapping related optimizations. |
818ab71a | 2 | Copyright (C) 1987-2016 Free Software Foundation, Inc. |
f30e25a3 ZC |
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" | |
c7131fb2 | 25 | #include "backend.h" |
957060b5 | 26 | #include "target.h" |
c7131fb2 | 27 | #include "rtl.h" |
957060b5 | 28 | #include "tree.h" |
957060b5 | 29 | #include "cfghooks.h" |
c7131fb2 | 30 | #include "df.h" |
4d0cdd0c | 31 | #include "memmodel.h" |
957060b5 | 32 | #include "tm_p.h" |
957060b5 | 33 | #include "regs.h" |
c997869f | 34 | #include "insn-config.h" |
957060b5 | 35 | #include "emit-rtl.h" |
f30e25a3 | 36 | #include "output.h" |
f30e25a3 | 37 | #include "tree-pass.h" |
60393bbc | 38 | #include "cfgrtl.h" |
c997869f | 39 | #include "cfgbuild.h" |
f30e25a3 ZC |
40 | #include "params.h" |
41 | #include "bb-reorder.h" | |
42 | #include "shrink-wrap.h" | |
a2e6c10c | 43 | #include "regcprop.h" |
2b63a3ac | 44 | #include "rtl-iter.h" |
015337d3 | 45 | #include "valtrack.h" |
f30e25a3 | 46 | |
f30e25a3 ZC |
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. */ | |
2eba0ed5 | 52 | bool |
939d7575 | 53 | requires_stack_frame_p (rtx_insn *insn, HARD_REG_SET prologue_used, |
f30e25a3 ZC |
54 | HARD_REG_SET set_up_by_prologue) |
55 | { | |
bfac633a | 56 | df_ref def, use; |
f30e25a3 ZC |
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); | |
bfac633a | 68 | FOR_EACH_INSN_DEF (def, insn) |
f30e25a3 | 69 | { |
bfac633a | 70 | rtx dreg = DF_REF_REG (def); |
f30e25a3 ZC |
71 | |
72 | if (!REG_P (dreg)) | |
73 | continue; | |
74 | ||
23997c53 | 75 | add_to_hard_reg_set (&hardregs, GET_MODE (dreg), REGNO (dreg)); |
f30e25a3 ZC |
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 | ||
bfac633a | 85 | FOR_EACH_INSN_USE (use, insn) |
f30e25a3 | 86 | { |
bfac633a | 87 | rtx reg = DF_REF_REG (use); |
f30e25a3 ZC |
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 | ||
e974b93b ZC |
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. */ | |
f30e25a3 | 104 | |
e974b93b ZC |
105 | static edge |
106 | live_edge_for_reg (basic_block bb, int regno, int end_regno) | |
f30e25a3 ZC |
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 | ||
e974b93b ZC |
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) | |
f30e25a3 ZC |
142 | return NULL; |
143 | ||
e974b93b | 144 | return live_edge; |
f30e25a3 ZC |
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 | |
e974b93b ZC |
149 | after INSN in BB. SPLIT_P indicates whether a live edge from BB |
150 | is splitted or not. */ | |
f30e25a3 ZC |
151 | |
152 | static bool | |
939d7575 | 153 | move_insn_for_shrink_wrap (basic_block bb, rtx_insn *insn, |
f30e25a3 | 154 | const HARD_REG_SET uses, |
e974b93b | 155 | const HARD_REG_SET defs, |
015337d3 JJ |
156 | bool *split_p, |
157 | struct dead_debug_local *debug) | |
f30e25a3 ZC |
158 | { |
159 | rtx set, src, dest; | |
160 | bitmap live_out, live_in, bb_uses, bb_defs; | |
2b63a3ac JW |
161 | unsigned int i, dregno, end_dregno; |
162 | unsigned int sregno = FIRST_PSEUDO_REGISTER; | |
163 | unsigned int end_sregno = FIRST_PSEUDO_REGISTER; | |
f30e25a3 | 164 | basic_block next_block; |
e974b93b | 165 | edge live_edge; |
015337d3 JJ |
166 | rtx_insn *dinsn; |
167 | df_ref def; | |
f30e25a3 | 168 | |
069d7fc5 RH |
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) | |
f30e25a3 ZC |
176 | return false; |
177 | src = SET_SRC (set); | |
178 | dest = SET_DEST (set); | |
2b63a3ac | 179 | |
069d7fc5 RH |
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)) | |
2b63a3ac | 202 | { |
2b63a3ac JW |
203 | rtx src_inner = NULL_RTX; |
204 | ||
2cfc4ade JW |
205 | if (can_throw_internal (insn)) |
206 | return false; | |
207 | ||
2b63a3ac JW |
208 | subrtx_var_iterator::array_type array; |
209 | FOR_EACH_SUBRTX_VAR (iter, array, src, ALL) | |
210 | { | |
211 | rtx x = *iter; | |
069d7fc5 | 212 | switch (GET_RTX_CLASS (GET_CODE (x))) |
2b63a3ac | 213 | { |
069d7fc5 RH |
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: | |
3f2012e4 | 232 | case LO_SUM: |
069d7fc5 RH |
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; | |
2b63a3ac | 250 | } |
2b63a3ac JW |
251 | } |
252 | ||
069d7fc5 | 253 | if (src_inner != NULL) |
2b63a3ac JW |
254 | src = src_inner; |
255 | } | |
256 | ||
f30e25a3 | 257 | /* Make sure that the source register isn't defined later in BB. */ |
2b63a3ac JW |
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 | } | |
f30e25a3 ZC |
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. */ | |
e974b93b ZC |
274 | live_edge = live_edge_for_reg (bb, dregno, end_dregno); |
275 | if (!live_edge) | |
f30e25a3 ZC |
276 | return false; |
277 | ||
e974b93b ZC |
278 | next_block = live_edge->dest; |
279 | /* Create a new basic block on the edge. */ | |
280 | if (EDGE_COUNT (next_block->preds) == 2) | |
281 | { | |
88f32f0f ZC |
282 | /* split_edge for a block with only one successor is meaningless. */ |
283 | if (EDGE_COUNT (bb->succs) == 1) | |
284 | return false; | |
285 | ||
d29d688a ZC |
286 | /* If DF_LIVE doesn't exist, i.e. at -O1, just give up. */ |
287 | if (!df_live) | |
288 | return false; | |
289 | ||
d0d9aad7 | 290 | basic_block old_dest = live_edge->dest; |
e974b93b ZC |
291 | next_block = split_edge (live_edge); |
292 | ||
d29d688a ZC |
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); | |
d0d9aad7 JW |
296 | |
297 | bitmap_and (df_get_live_in (next_block), df_get_live_out (bb), | |
298 | df_get_live_in (old_dest)); | |
e974b93b ZC |
299 | df_set_bb_dirty (next_block); |
300 | ||
301 | /* We should not split more than once for a function. */ | |
d0d9aad7 JW |
302 | if (*split_p) |
303 | return false; | |
304 | ||
e974b93b ZC |
305 | *split_p = true; |
306 | } | |
307 | ||
f30e25a3 ZC |
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 | { | |
015337d3 JJ |
312 | if (MAY_HAVE_DEBUG_INSNS) |
313 | { | |
314 | FOR_BB_INSNS_REVERSE (bb, dinsn) | |
315 | if (DEBUG_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 | } | |
f30e25a3 ZC |
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 | { | |
e974b93b ZC |
339 | if (*split_p |
340 | || REGNO_REG_SET_P (bb_uses, i) | |
341 | || REGNO_REG_SET_P (bb_defs, i) | |
f30e25a3 ZC |
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 | { | |
e974b93b ZC |
352 | if (*split_p |
353 | || REGNO_REG_SET_P (bb_defs, i) | |
f30e25a3 ZC |
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) | |
e974b93b ZC |
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 | } | |
f30e25a3 ZC |
388 | } |
389 | while (next_block); | |
390 | ||
e974b93b ZC |
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)) | |
f30e25a3 | 394 | { |
e974b93b ZC |
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 | } | |
f30e25a3 | 402 | |
e974b93b ZC |
403 | /* BB now uses SRC. */ |
404 | for (i = sregno; i < end_sregno; i++) | |
405 | SET_REGNO_REG_SET (bb_uses, i); | |
406 | } | |
f30e25a3 | 407 | |
015337d3 JJ |
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 | ||
f30e25a3 ZC |
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 | ||
8b661145 | 426 | static void |
f30e25a3 ZC |
427 | prepare_shrink_wrap (basic_block entry_block) |
428 | { | |
939d7575 DM |
429 | rtx_insn *insn, *curr; |
430 | rtx x; | |
f30e25a3 | 431 | HARD_REG_SET uses, defs; |
bfac633a | 432 | df_ref def, use; |
e974b93b | 433 | bool split_p = false; |
015337d3 JJ |
434 | unsigned int i; |
435 | struct dead_debug_local debug; | |
f30e25a3 | 436 | |
a2e6c10c ZC |
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 | ||
015337d3 | 446 | dead_debug_local_init (&debug, NULL, NULL); |
f30e25a3 ZC |
447 | CLEAR_HARD_REG_SET (uses); |
448 | CLEAR_HARD_REG_SET (defs); | |
015337d3 | 449 | |
f30e25a3 ZC |
450 | FOR_BB_INSNS_REVERSE_SAFE (entry_block, insn, curr) |
451 | if (NONDEBUG_INSN_P (insn) | |
e974b93b | 452 | && !move_insn_for_shrink_wrap (entry_block, insn, uses, defs, |
015337d3 | 453 | &split_p, &debug)) |
f30e25a3 ZC |
454 | { |
455 | /* Add all defined registers to DEFs. */ | |
bfac633a | 456 | FOR_EACH_INSN_DEF (def, insn) |
f30e25a3 | 457 | { |
bfac633a | 458 | x = DF_REF_REG (def); |
f30e25a3 | 459 | if (REG_P (x) && HARD_REGISTER_P (x)) |
015337d3 JJ |
460 | for (i = REGNO (x); i < END_REGNO (x); i++) |
461 | SET_HARD_REG_BIT (defs, i); | |
f30e25a3 ZC |
462 | } |
463 | ||
464 | /* Add all used registers to USESs. */ | |
bfac633a | 465 | FOR_EACH_INSN_USE (use, insn) |
f30e25a3 | 466 | { |
bfac633a | 467 | x = DF_REF_REG (use); |
f30e25a3 | 468 | if (REG_P (x) && HARD_REGISTER_P (x)) |
015337d3 JJ |
469 | for (i = REGNO (x); i < END_REGNO (x); i++) |
470 | SET_HARD_REG_BIT (uses, i); | |
f30e25a3 ZC |
471 | } |
472 | } | |
015337d3 JJ |
473 | |
474 | dead_debug_local_finish (&debug, NULL); | |
f30e25a3 ZC |
475 | } |
476 | ||
6c98d499 SB |
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 | ||
483 | static bool | |
484 | can_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 | ||
23997c53 SB |
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 | ||
508 | static bool | |
509 | can_dup_for_shrink_wrapping (basic_block bb, basic_block pro, unsigned max_size) | |
f30e25a3 | 510 | { |
23997c53 SB |
511 | if (!can_duplicate_block_p (bb)) |
512 | return false; | |
f30e25a3 | 513 | |
23997c53 SB |
514 | edge e; |
515 | edge_iterator ei; | |
516 | FOR_EACH_EDGE (e, ei, bb->preds) | |
6c98d499 | 517 | if (e->flags & (EDGE_COMPLEX | EDGE_CROSSING) |
23997c53 SB |
518 | && !dominated_by_p (CDI_DOMINATORS, e->src, pro)) |
519 | return false; | |
f30e25a3 | 520 | |
23997c53 | 521 | unsigned size = 0; |
f30e25a3 | 522 | |
23997c53 SB |
523 | rtx_insn *insn; |
524 | FOR_BB_INSNS (bb, insn) | |
525 | if (NONDEBUG_INSN_P (insn)) | |
f30e25a3 | 526 | { |
23997c53 SB |
527 | size += get_attr_min_length (insn); |
528 | if (size > max_size) | |
529 | return false; | |
f30e25a3 | 530 | } |
23997c53 SB |
531 | |
532 | return true; | |
f30e25a3 ZC |
533 | } |
534 | ||
33fec8d5 SB |
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. */ | |
23997c53 | 537 | |
33fec8d5 SB |
538 | static void |
539 | handle_simple_exit (edge e) | |
23997c53 | 540 | { |
23997c53 | 541 | |
33fec8d5 SB |
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 | e->flags |= EDGE_FALLTHRU; | |
565 | ||
566 | e = make_edge (new_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0); | |
567 | } | |
23997c53 | 568 | |
33fec8d5 SB |
569 | e->flags &= ~EDGE_FALLTHRU; |
570 | rtx_jump_insn *ret = emit_jump_insn_after (targetm.gen_simple_return (), | |
571 | BB_END (e->src)); | |
572 | JUMP_LABEL (ret) = simple_return_rtx; | |
573 | emit_barrier_after_bb (e->src); | |
23997c53 | 574 | |
33fec8d5 SB |
575 | if (dump_file) |
576 | fprintf (dump_file, "Made simple_return with UID %d in bb %d\n", | |
577 | INSN_UID (ret), e->src->index); | |
23997c53 | 578 | } |
f30e25a3 ZC |
579 | |
580 | /* Try to perform a kind of shrink-wrapping, making sure the | |
581 | prologue/epilogue is emitted only around those parts of the | |
23997c53 SB |
582 | function that require it. |
583 | ||
584 | There will be exactly one prologue, and it will be executed either | |
585 | zero or one time, on any path. Depending on where the prologue is | |
586 | placed, some of the basic blocks can be reached via both paths with | |
587 | and without a prologue. Such blocks will be duplicated here, and the | |
588 | edges changed to match. | |
589 | ||
590 | Paths that go to the exit without going through the prologue will use | |
591 | a simple_return instead of the epilogue. We maximize the number of | |
592 | those, making sure to only duplicate blocks that can be duplicated. | |
593 | If the prologue can then still be placed in multiple locations, we | |
594 | place it as early as possible. | |
595 | ||
596 | An example, where we duplicate blocks with control flow (legend: | |
597 | _B_egin, _R_eturn and _S_imple_return; edges without arrowhead should | |
598 | be taken to point down or to the right, to simplify the diagram; here, | |
599 | block 3 needs a prologue, the rest does not): | |
600 | ||
601 | ||
602 | B B | |
603 | | | | |
604 | 2 2 | |
605 | |\ |\ | |
606 | | 3 becomes | 3 | |
607 | |/ | \ | |
608 | 4 7 4 | |
609 | |\ |\ |\ | |
610 | | 5 | 8 | 5 | |
611 | |/ |/ |/ | |
612 | 6 9 6 | |
613 | | | | | |
614 | R S R | |
615 | ||
616 | ||
617 | (bb 4 is duplicated to 7, and so on; the prologue is inserted on the | |
618 | edge 2->3). | |
619 | ||
620 | Another example, where part of a loop is duplicated (again, bb 3 is | |
621 | the only block that needs a prologue): | |
622 | ||
623 | ||
624 | B 3<-- B ->3<-- | |
625 | | | | | | | | | |
626 | | v | becomes | | v | | |
627 | 2---4--- 2---5-- 4--- | |
628 | | | | | |
629 | R S R | |
630 | ||
631 | ||
632 | (bb 4 is duplicated to 5; the prologue is inserted on the edge 5->3). | |
633 | ||
634 | ENTRY_EDGE is the edge where the prologue will be placed, possibly | |
33fec8d5 | 635 | changed by this function. PROLOGUE_SEQ is the prologue we will insert. */ |
f30e25a3 ZC |
636 | |
637 | void | |
33fec8d5 | 638 | try_shrink_wrapping (edge *entry_edge, rtx_insn *prologue_seq) |
f30e25a3 | 639 | { |
23997c53 SB |
640 | /* If we cannot shrink-wrap, are told not to shrink-wrap, or it makes |
641 | no sense to shrink-wrap: then do not shrink-wrap! */ | |
642 | ||
643 | if (!SHRINK_WRAPPING_ENABLED) | |
644 | return; | |
645 | ||
646 | if (crtl->profile && !targetm.profile_before_prologue ()) | |
647 | return; | |
f30e25a3 | 648 | |
23997c53 SB |
649 | if (crtl->calls_eh_return) |
650 | return; | |
651 | ||
652 | bool empty_prologue = true; | |
653 | for (rtx_insn *insn = prologue_seq; insn; insn = NEXT_INSN (insn)) | |
654 | if (!(NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_PROLOGUE_END)) | |
f30e25a3 | 655 | { |
23997c53 | 656 | empty_prologue = false; |
f30e25a3 ZC |
657 | break; |
658 | } | |
23997c53 SB |
659 | if (empty_prologue) |
660 | return; | |
661 | ||
662 | /* Move some code down to expose more shrink-wrapping opportunities. */ | |
663 | ||
664 | basic_block entry = (*entry_edge)->dest; | |
665 | prepare_shrink_wrap (entry); | |
666 | ||
667 | if (dump_file) | |
668 | fprintf (dump_file, "Attempting shrink-wrapping optimization.\n"); | |
669 | ||
670 | /* Compute the registers set and used in the prologue. */ | |
671 | ||
672 | HARD_REG_SET prologue_clobbered, prologue_used; | |
673 | CLEAR_HARD_REG_SET (prologue_clobbered); | |
674 | CLEAR_HARD_REG_SET (prologue_used); | |
675 | for (rtx_insn *insn = prologue_seq; insn; insn = NEXT_INSN (insn)) | |
676 | if (NONDEBUG_INSN_P (insn)) | |
677 | { | |
678 | HARD_REG_SET this_used; | |
679 | CLEAR_HARD_REG_SET (this_used); | |
680 | note_uses (&PATTERN (insn), record_hard_reg_uses, &this_used); | |
681 | AND_COMPL_HARD_REG_SET (this_used, prologue_clobbered); | |
682 | IOR_HARD_REG_SET (prologue_used, this_used); | |
683 | note_stores (PATTERN (insn), record_hard_reg_sets, &prologue_clobbered); | |
684 | } | |
6c98d499 SB |
685 | CLEAR_HARD_REG_BIT (prologue_clobbered, STACK_POINTER_REGNUM); |
686 | if (frame_pointer_needed) | |
687 | CLEAR_HARD_REG_BIT (prologue_clobbered, HARD_FRAME_POINTER_REGNUM); | |
f30e25a3 | 688 | |
23997c53 SB |
689 | /* Find out what registers are set up by the prologue; any use of these |
690 | cannot happen before the prologue. */ | |
691 | ||
692 | struct hard_reg_set_container set_up_by_prologue; | |
693 | CLEAR_HARD_REG_SET (set_up_by_prologue.set); | |
694 | add_to_hard_reg_set (&set_up_by_prologue.set, Pmode, STACK_POINTER_REGNUM); | |
695 | add_to_hard_reg_set (&set_up_by_prologue.set, Pmode, ARG_POINTER_REGNUM); | |
696 | if (frame_pointer_needed) | |
697 | add_to_hard_reg_set (&set_up_by_prologue.set, Pmode, | |
698 | HARD_FRAME_POINTER_REGNUM); | |
699 | if (pic_offset_table_rtx | |
700 | && (unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM) | |
701 | add_to_hard_reg_set (&set_up_by_prologue.set, Pmode, | |
702 | PIC_OFFSET_TABLE_REGNUM); | |
703 | if (crtl->drap_reg) | |
704 | add_to_hard_reg_set (&set_up_by_prologue.set, | |
705 | GET_MODE (crtl->drap_reg), | |
706 | REGNO (crtl->drap_reg)); | |
707 | if (targetm.set_up_by_prologue) | |
708 | targetm.set_up_by_prologue (&set_up_by_prologue); | |
709 | ||
710 | /* We will insert the prologue before the basic block PRO. PRO should | |
711 | dominate all basic blocks that need the prologue to be executed | |
712 | before them. First, make PRO the "tightest wrap" possible. */ | |
713 | ||
714 | calculate_dominance_info (CDI_DOMINATORS); | |
715 | ||
716 | basic_block pro = 0; | |
717 | ||
718 | basic_block bb; | |
719 | edge e; | |
720 | edge_iterator ei; | |
721 | FOR_EACH_BB_FN (bb, cfun) | |
f30e25a3 | 722 | { |
23997c53 SB |
723 | rtx_insn *insn; |
724 | FOR_BB_INSNS (bb, insn) | |
725 | if (NONDEBUG_INSN_P (insn) | |
726 | && requires_stack_frame_p (insn, prologue_used, | |
727 | set_up_by_prologue.set)) | |
728 | { | |
729 | if (dump_file) | |
730 | fprintf (dump_file, "Block %d needs the prologue.\n", bb->index); | |
731 | pro = nearest_common_dominator (CDI_DOMINATORS, pro, bb); | |
732 | break; | |
733 | } | |
734 | } | |
f30e25a3 | 735 | |
23997c53 SB |
736 | /* If nothing needs a prologue, just put it at the start. This really |
737 | shouldn't happen, but we cannot fix it here. */ | |
738 | ||
739 | if (pro == 0) | |
740 | { | |
f30e25a3 | 741 | if (dump_file) |
23997c53 SB |
742 | fprintf(dump_file, "Nothing needs a prologue, but it isn't empty; " |
743 | "putting it at the start.\n"); | |
744 | pro = entry; | |
745 | } | |
f30e25a3 | 746 | |
23997c53 SB |
747 | if (dump_file) |
748 | fprintf (dump_file, "After wrapping required blocks, PRO is now %d\n", | |
749 | pro->index); | |
f30e25a3 | 750 | |
23997c53 | 751 | /* Now see if we can put the prologue at the start of PRO. Putting it |
6c98d499 SB |
752 | there might require duplicating a block that cannot be duplicated, |
753 | or in some cases we cannot insert the prologue there at all. If PRO | |
754 | wont't do, try again with the immediate dominator of PRO, and so on. | |
f30e25a3 | 755 | |
23997c53 SB |
756 | The blocks that need duplicating are those reachable from PRO but |
757 | not dominated by it. We keep in BB_WITH a bitmap of the blocks | |
758 | reachable from PRO that we already found, and in VEC a stack of | |
759 | those we still need to consider (to find successors). */ | |
f30e25a3 | 760 | |
33fec8d5 | 761 | bitmap bb_with = BITMAP_ALLOC (NULL); |
23997c53 | 762 | bitmap_set_bit (bb_with, pro->index); |
f30e25a3 | 763 | |
23997c53 SB |
764 | vec<basic_block> vec; |
765 | vec.create (n_basic_blocks_for_fn (cfun)); | |
766 | vec.quick_push (pro); | |
f30e25a3 | 767 | |
23997c53 SB |
768 | unsigned max_grow_size = get_uncond_jump_length (); |
769 | max_grow_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS); | |
f30e25a3 | 770 | |
23997c53 SB |
771 | while (!vec.is_empty () && pro != entry) |
772 | { | |
6c98d499 SB |
773 | while (pro != entry && !can_get_prologue (pro, prologue_clobbered)) |
774 | { | |
775 | pro = get_immediate_dominator (CDI_DOMINATORS, pro); | |
776 | ||
82ad5144 SB |
777 | if (bitmap_set_bit (bb_with, pro->index)) |
778 | vec.quick_push (pro); | |
6c98d499 SB |
779 | } |
780 | ||
23997c53 SB |
781 | basic_block bb = vec.pop (); |
782 | if (!can_dup_for_shrink_wrapping (bb, pro, max_grow_size)) | |
783 | while (!dominated_by_p (CDI_DOMINATORS, bb, pro)) | |
784 | { | |
785 | gcc_assert (pro != entry); | |
f30e25a3 | 786 | |
23997c53 SB |
787 | pro = get_immediate_dominator (CDI_DOMINATORS, pro); |
788 | ||
82ad5144 SB |
789 | if (bitmap_set_bit (bb_with, pro->index)) |
790 | vec.quick_push (pro); | |
23997c53 SB |
791 | } |
792 | ||
793 | FOR_EACH_EDGE (e, ei, bb->succs) | |
794 | if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) | |
795 | && bitmap_set_bit (bb_with, e->dest->index)) | |
796 | vec.quick_push (e->dest); | |
797 | } | |
798 | ||
23997c53 SB |
799 | if (dump_file) |
800 | fprintf (dump_file, "Avoiding non-duplicatable blocks, PRO is now %d\n", | |
801 | pro->index); | |
802 | ||
803 | /* If we can move PRO back without having to duplicate more blocks, do so. | |
5d59ed63 | 804 | We do this because putting the prologue earlier is better for scheduling. |
52ad5601 | 805 | |
23997c53 | 806 | We can move back to a block PRE if every path from PRE will eventually |
5d59ed63 | 807 | need a prologue, that is, PRO is a post-dominator of PRE. PRE needs |
52ad5601 SB |
808 | to dominate every block reachable from itself. We keep in BB_TMP a |
809 | bitmap of the blocks reachable from PRE that we already found, and in | |
810 | VEC a stack of those we still need to consider. | |
811 | ||
812 | Any block reachable from PRE is also reachable from all predecessors | |
813 | of PRE, so if we find we need to move PRE back further we can leave | |
814 | everything not considered so far on the stack. Any block dominated | |
815 | by PRE is also dominated by all other dominators of PRE, so anything | |
816 | found good for some PRE does not need to be reconsidered later. | |
817 | ||
818 | We don't need to update BB_WITH because none of the new blocks found | |
819 | can jump to a block that does not need the prologue. */ | |
23997c53 SB |
820 | |
821 | if (pro != entry) | |
822 | { | |
823 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
f30e25a3 | 824 | |
5d59ed63 SB |
825 | bitmap bb_tmp = BITMAP_ALLOC (NULL); |
826 | bitmap_copy (bb_tmp, bb_with); | |
6c98d499 | 827 | basic_block last_ok = pro; |
5d59ed63 SB |
828 | vec.truncate (0); |
829 | ||
23997c53 | 830 | while (pro != entry) |
f30e25a3 | 831 | { |
23997c53 | 832 | basic_block pre = get_immediate_dominator (CDI_DOMINATORS, pro); |
6c98d499 | 833 | if (!dominated_by_p (CDI_POST_DOMINATORS, pre, pro)) |
23997c53 | 834 | break; |
6c98d499 | 835 | |
5d59ed63 SB |
836 | if (bitmap_set_bit (bb_tmp, pre->index)) |
837 | vec.quick_push (pre); | |
838 | ||
839 | bool ok = true; | |
840 | while (!vec.is_empty ()) | |
841 | { | |
52ad5601 | 842 | if (!dominated_by_p (CDI_DOMINATORS, vec.last (), pre)) |
5d59ed63 SB |
843 | { |
844 | ok = false; | |
845 | break; | |
846 | } | |
847 | ||
52ad5601 | 848 | basic_block bb = vec.pop (); |
5d59ed63 | 849 | FOR_EACH_EDGE (e, ei, bb->succs) |
52ad5601 | 850 | if (bitmap_set_bit (bb_tmp, e->dest->index)) |
5d59ed63 SB |
851 | vec.quick_push (e->dest); |
852 | } | |
853 | ||
854 | if (ok && can_get_prologue (pre, prologue_clobbered)) | |
855 | last_ok = pre; | |
856 | ||
6c98d499 | 857 | pro = pre; |
f30e25a3 | 858 | } |
5d59ed63 | 859 | |
6c98d499 | 860 | pro = last_ok; |
f30e25a3 | 861 | |
5d59ed63 | 862 | BITMAP_FREE (bb_tmp); |
23997c53 SB |
863 | free_dominance_info (CDI_POST_DOMINATORS); |
864 | } | |
f30e25a3 | 865 | |
5d59ed63 SB |
866 | vec.release (); |
867 | ||
23997c53 SB |
868 | if (dump_file) |
869 | fprintf (dump_file, "Bumping back to anticipatable blocks, PRO is now %d\n", | |
870 | pro->index); | |
871 | ||
6c98d499 | 872 | if (pro == entry) |
23997c53 | 873 | { |
33fec8d5 | 874 | BITMAP_FREE (bb_with); |
6c98d499 SB |
875 | free_dominance_info (CDI_DOMINATORS); |
876 | return; | |
23997c53 SB |
877 | } |
878 | ||
23997c53 SB |
879 | /* Compute what fraction of the frequency and count of the blocks that run |
880 | both with and without prologue are for running with prologue. This gives | |
881 | the correct answer for reducible flow graphs; for irreducible flow graphs | |
882 | our profile is messed up beyond repair anyway. */ | |
883 | ||
6c98d499 SB |
884 | gcov_type num = 0; |
885 | gcov_type den = 0; | |
23997c53 | 886 | |
6c98d499 SB |
887 | FOR_EACH_EDGE (e, ei, pro->preds) |
888 | if (!dominated_by_p (CDI_DOMINATORS, e->src, pro)) | |
889 | { | |
890 | num += EDGE_FREQUENCY (e); | |
891 | den += e->src->frequency; | |
892 | } | |
23997c53 | 893 | |
6c98d499 SB |
894 | if (den == 0) |
895 | den = 1; | |
23997c53 SB |
896 | |
897 | /* All is okay, so do it. */ | |
898 | ||
899 | crtl->shrink_wrapped = true; | |
900 | if (dump_file) | |
901 | fprintf (dump_file, "Performing shrink-wrapping.\n"); | |
902 | ||
903 | /* Copy the blocks that can run both with and without prologue. The | |
904 | originals run with prologue, the copies without. Store a pointer to | |
905 | the copy in the ->aux field of the original. */ | |
906 | ||
907 | FOR_EACH_BB_FN (bb, cfun) | |
908 | if (bitmap_bit_p (bb_with, bb->index) | |
909 | && !dominated_by_p (CDI_DOMINATORS, bb, pro)) | |
910 | { | |
911 | basic_block dup = duplicate_block (bb, 0, 0); | |
912 | ||
913 | bb->aux = dup; | |
914 | ||
915 | if (JUMP_P (BB_END (dup)) && !any_condjump_p (BB_END (dup))) | |
916 | emit_barrier_after_bb (dup); | |
917 | ||
918 | if (EDGE_COUNT (dup->succs) == 0) | |
919 | emit_barrier_after_bb (dup); | |
920 | ||
921 | if (dump_file) | |
922 | fprintf (dump_file, "Duplicated %d to %d\n", bb->index, dup->index); | |
923 | ||
924 | bb->frequency = RDIV (num * bb->frequency, den); | |
925 | dup->frequency -= bb->frequency; | |
926 | bb->count = RDIV (num * bb->count, den); | |
927 | dup->count -= bb->count; | |
928 | } | |
929 | ||
23997c53 SB |
930 | /* Now change the edges to point to the copies, where appropriate. */ |
931 | ||
932 | FOR_EACH_BB_FN (bb, cfun) | |
933 | if (!dominated_by_p (CDI_DOMINATORS, bb, pro)) | |
934 | { | |
935 | basic_block src = bb; | |
936 | if (bitmap_bit_p (bb_with, bb->index)) | |
937 | src = (basic_block) bb->aux; | |
938 | ||
939 | FOR_EACH_EDGE (e, ei, src->succs) | |
f30e25a3 | 940 | { |
23997c53 | 941 | if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
f30e25a3 | 942 | continue; |
f30e25a3 | 943 | |
23997c53 SB |
944 | if (bitmap_bit_p (bb_with, e->dest->index) |
945 | && !dominated_by_p (CDI_DOMINATORS, e->dest, pro)) | |
f30e25a3 | 946 | { |
23997c53 SB |
947 | if (dump_file) |
948 | fprintf (dump_file, "Redirecting edge %d->%d to %d\n", | |
949 | e->src->index, e->dest->index, | |
950 | ((basic_block) e->dest->aux)->index); | |
951 | redirect_edge_and_branch_force (e, (basic_block) e->dest->aux); | |
f30e25a3 | 952 | } |
23997c53 SB |
953 | else if (e->flags & EDGE_FALLTHRU |
954 | && bitmap_bit_p (bb_with, bb->index)) | |
955 | force_nonfallthru (e); | |
956 | } | |
957 | } | |
f30e25a3 | 958 | |
23997c53 | 959 | /* Also redirect the function entry edge if necessary. */ |
f30e25a3 | 960 | |
23997c53 SB |
961 | FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) |
962 | if (bitmap_bit_p (bb_with, e->dest->index) | |
963 | && !dominated_by_p (CDI_DOMINATORS, e->dest, pro)) | |
964 | { | |
965 | basic_block split_bb = split_edge (e); | |
966 | e = single_succ_edge (split_bb); | |
967 | redirect_edge_and_branch_force (e, (basic_block) e->dest->aux); | |
968 | } | |
f30e25a3 | 969 | |
d07d2177 | 970 | /* Make a simple_return for those exits that run without prologue. */ |
23997c53 | 971 | |
d07d2177 | 972 | FOR_EACH_BB_REVERSE_FN (bb, cfun) |
23997c53 SB |
973 | if (!bitmap_bit_p (bb_with, bb->index)) |
974 | FOR_EACH_EDGE (e, ei, bb->succs) | |
975 | if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
33fec8d5 | 976 | handle_simple_exit (e); |
23997c53 | 977 | |
6c98d499 SB |
978 | /* Finally, we want a single edge to put the prologue on. Make a new |
979 | block before the PRO block; the edge beteen them is the edge we want. | |
980 | Then redirect those edges into PRO that come from blocks without the | |
981 | prologue, to point to the new block instead. The new prologue block | |
982 | is put at the end of the insn chain. */ | |
983 | ||
984 | basic_block new_bb = create_empty_bb (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb); | |
985 | BB_COPY_PARTITION (new_bb, pro); | |
986 | if (dump_file) | |
987 | fprintf (dump_file, "Made prologue block %d\n", new_bb->index); | |
988 | ||
989 | for (ei = ei_start (pro->preds); (e = ei_safe_edge (ei)); ) | |
990 | { | |
991 | if (bitmap_bit_p (bb_with, e->src->index) | |
992 | || dominated_by_p (CDI_DOMINATORS, e->src, pro)) | |
993 | { | |
994 | ei_next (&ei); | |
995 | continue; | |
996 | } | |
997 | ||
998 | new_bb->count += RDIV (e->src->count * e->probability, REG_BR_PROB_BASE); | |
999 | new_bb->frequency += EDGE_FREQUENCY (e); | |
1000 | ||
1001 | redirect_edge_and_branch_force (e, new_bb); | |
1002 | if (dump_file) | |
1003 | fprintf (dump_file, "Redirected edge from %d\n", e->src->index); | |
1004 | } | |
1005 | ||
1006 | *entry_edge = make_single_succ_edge (new_bb, pro, EDGE_FALLTHRU); | |
1007 | force_nonfallthru (*entry_edge); | |
1008 | ||
33fec8d5 | 1009 | BITMAP_FREE (bb_with); |
23997c53 | 1010 | free_dominance_info (CDI_DOMINATORS); |
f30e25a3 | 1011 | } |
c997869f SB |
1012 | \f |
1013 | /* Separate shrink-wrapping | |
1014 | ||
1015 | Instead of putting all of the prologue and epilogue in one spot, we | |
1016 | can put parts of it in places where those components are executed less | |
1017 | frequently. The following code does this, for prologue and epilogue | |
1018 | components that can be put in more than one location, and where those | |
1019 | components can be executed more than once (the epilogue component will | |
1020 | always be executed before the prologue component is executed a second | |
1021 | time). | |
1022 | ||
1023 | What exactly is a component is target-dependent. The more usual | |
1024 | components are simple saves/restores to/from the frame of callee-saved | |
1025 | registers. This code treats components abstractly (as an sbitmap), | |
1026 | letting the target handle all details. | |
1027 | ||
1028 | Prologue components are placed in such a way that for every component | |
1029 | the prologue is executed as infrequently as possible. We do this by | |
1030 | walking the dominator tree, comparing the cost of placing a prologue | |
1031 | component before a block to the sum of costs determined for all subtrees | |
1032 | of that block. | |
1033 | ||
1034 | From this placement, we then determine for each component all blocks | |
1035 | where at least one of this block's dominators (including itself) will | |
1036 | get a prologue inserted. That then is how the components are placed. | |
1037 | We could place the epilogue components a bit smarter (we can save a | |
1038 | bit of code size sometimes); this is a possible future improvement. | |
1039 | ||
1040 | Prologues and epilogues are preferably placed into a block, either at | |
1041 | the beginning or end of it, if it is needed for all predecessor resp. | |
1042 | successor edges; or placed on the edge otherwise. | |
1043 | ||
1044 | If the placement of any prologue/epilogue leads to a situation we cannot | |
1045 | handle (for example, an abnormal edge would need to be split, or some | |
1046 | targets want to use some specific registers that may not be available | |
1047 | where we want to put them), separate shrink-wrapping for the components | |
1048 | in that prologue/epilogue is aborted. */ | |
1049 | ||
1050 | ||
1051 | /* Print the sbitmap COMPONENTS to the DUMP_FILE if not empty, with the | |
1052 | label LABEL. */ | |
1053 | static void | |
1054 | dump_components (const char *label, sbitmap components) | |
1055 | { | |
1056 | if (bitmap_empty_p (components)) | |
1057 | return; | |
1058 | ||
1059 | fprintf (dump_file, " [%s", label); | |
1060 | ||
1061 | for (unsigned int j = 0; j < components->n_bits; j++) | |
1062 | if (bitmap_bit_p (components, j)) | |
1063 | fprintf (dump_file, " %u", j); | |
1064 | ||
1065 | fprintf (dump_file, "]"); | |
1066 | } | |
1067 | ||
1068 | /* The data we collect for each bb. */ | |
1069 | struct sw { | |
1070 | /* What components does this BB need? */ | |
1071 | sbitmap needs_components; | |
1072 | ||
1073 | /* What components does this BB have? This is the main decision this | |
1074 | pass makes. */ | |
1075 | sbitmap has_components; | |
1076 | ||
1077 | /* The components for which we placed code at the start of the BB (instead | |
1078 | of on all incoming edges). */ | |
1079 | sbitmap head_components; | |
1080 | ||
1081 | /* The components for which we placed code at the end of the BB (instead | |
1082 | of on all outgoing edges). */ | |
1083 | sbitmap tail_components; | |
1084 | ||
1085 | /* The frequency of executing the prologue for this BB, if a prologue is | |
1086 | placed on this BB. This is a pessimistic estimate (no prologue is | |
1087 | needed for edges from blocks that have the component under consideration | |
1088 | active already). */ | |
1089 | gcov_type own_cost; | |
1090 | ||
1091 | /* The frequency of executing the prologue for this BB and all BBs | |
1092 | dominated by it. */ | |
1093 | gcov_type total_cost; | |
1094 | }; | |
1095 | ||
1096 | /* A helper function for accessing the pass-specific info. */ | |
1097 | static inline struct sw * | |
1098 | SW (basic_block bb) | |
1099 | { | |
1100 | gcc_assert (bb->aux); | |
1101 | return (struct sw *) bb->aux; | |
1102 | } | |
1103 | ||
1104 | /* Create the pass-specific data structures for separately shrink-wrapping | |
1105 | with components COMPONENTS. */ | |
1106 | static void | |
1107 | init_separate_shrink_wrap (sbitmap components) | |
1108 | { | |
1109 | basic_block bb; | |
1110 | FOR_ALL_BB_FN (bb, cfun) | |
1111 | { | |
1112 | bb->aux = xcalloc (1, sizeof (struct sw)); | |
1113 | ||
1114 | SW (bb)->needs_components = targetm.shrink_wrap.components_for_bb (bb); | |
1115 | ||
1116 | /* Mark all basic blocks without successor as needing all components. | |
1117 | This avoids problems in at least cfgcleanup, sel-sched, and | |
1118 | regrename (largely to do with all paths to such a block still | |
1119 | needing the same dwarf CFI info). */ | |
1120 | if (EDGE_COUNT (bb->succs) == 0) | |
1121 | bitmap_copy (SW (bb)->needs_components, components); | |
1122 | ||
1123 | if (dump_file) | |
1124 | { | |
1125 | fprintf (dump_file, "bb %d components:", bb->index); | |
1126 | dump_components ("has", SW (bb)->needs_components); | |
1127 | fprintf (dump_file, "\n"); | |
1128 | } | |
1129 | ||
1130 | SW (bb)->has_components = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1131 | SW (bb)->head_components = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1132 | SW (bb)->tail_components = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1133 | bitmap_clear (SW (bb)->has_components); | |
1134 | bitmap_clear (SW (bb)->head_components); | |
1135 | bitmap_clear (SW (bb)->tail_components); | |
1136 | } | |
1137 | } | |
1138 | ||
1139 | /* Destroy the pass-specific data. */ | |
1140 | static void | |
1141 | fini_separate_shrink_wrap (void) | |
1142 | { | |
1143 | basic_block bb; | |
1144 | FOR_ALL_BB_FN (bb, cfun) | |
1145 | if (bb->aux) | |
1146 | { | |
1147 | sbitmap_free (SW (bb)->needs_components); | |
1148 | sbitmap_free (SW (bb)->has_components); | |
1149 | sbitmap_free (SW (bb)->head_components); | |
1150 | sbitmap_free (SW (bb)->tail_components); | |
1151 | free (bb->aux); | |
1152 | bb->aux = 0; | |
1153 | } | |
1154 | } | |
1155 | ||
1156 | /* Place the prologue for component WHICH, in the basic blocks dominated | |
1157 | by HEAD. Do a DFS over the dominator tree, and set bit WHICH in the | |
1158 | HAS_COMPONENTS of a block if either the block has that bit set in | |
1159 | NEEDS_COMPONENTS, or it is cheaper to place the prologue here than in all | |
1160 | dominator subtrees separately. */ | |
1161 | static void | |
1162 | place_prologue_for_one_component (unsigned int which, basic_block head) | |
1163 | { | |
1164 | /* The block we are currently dealing with. */ | |
1165 | basic_block bb = head; | |
1166 | /* Is this the first time we visit this block, i.e. have we just gone | |
1167 | down the tree. */ | |
1168 | bool first_visit = true; | |
1169 | ||
1170 | /* Walk the dominator tree, visit one block per iteration of this loop. | |
1171 | Each basic block is visited twice: once before visiting any children | |
1172 | of the block, and once after visiting all of them (leaf nodes are | |
1173 | visited only once). As an optimization, we do not visit subtrees | |
1174 | that can no longer influence the prologue placement. */ | |
1175 | for (;;) | |
1176 | { | |
1177 | /* First visit of a block: set the (children) cost accumulator to zero; | |
1178 | if the block does not have the component itself, walk down. */ | |
1179 | if (first_visit) | |
1180 | { | |
1181 | /* Initialize the cost. The cost is the block execution frequency | |
1182 | that does not come from backedges. Calculating this by simply | |
1183 | adding the cost of all edges that aren't backedges does not | |
1184 | work: this does not always add up to the block frequency at | |
1185 | all, and even if it does, rounding error makes for bad | |
1186 | decisions. */ | |
1187 | SW (bb)->own_cost = bb->frequency; | |
1188 | ||
1189 | edge e; | |
1190 | edge_iterator ei; | |
1191 | FOR_EACH_EDGE (e, ei, bb->preds) | |
1192 | if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) | |
1193 | { | |
1194 | if (SW (bb)->own_cost > EDGE_FREQUENCY (e)) | |
1195 | SW (bb)->own_cost -= EDGE_FREQUENCY (e); | |
1196 | else | |
1197 | SW (bb)->own_cost = 0; | |
1198 | } | |
1199 | ||
1200 | SW (bb)->total_cost = 0; | |
1201 | ||
1202 | if (!bitmap_bit_p (SW (bb)->needs_components, which) | |
1203 | && first_dom_son (CDI_DOMINATORS, bb)) | |
1204 | { | |
1205 | bb = first_dom_son (CDI_DOMINATORS, bb); | |
1206 | continue; | |
1207 | } | |
1208 | } | |
1209 | ||
1210 | /* If this block does need the component itself, or it is cheaper to | |
1211 | put the prologue here than in all the descendants that need it, | |
1212 | mark it so. If this block's immediate post-dominator is dominated | |
1213 | by this block, and that needs the prologue, we can put it on this | |
1214 | block as well (earlier is better). */ | |
1215 | if (bitmap_bit_p (SW (bb)->needs_components, which) | |
1216 | || SW (bb)->total_cost > SW (bb)->own_cost) | |
1217 | { | |
1218 | SW (bb)->total_cost = SW (bb)->own_cost; | |
1219 | bitmap_set_bit (SW (bb)->has_components, which); | |
1220 | } | |
1221 | else | |
1222 | { | |
1223 | basic_block kid = get_immediate_dominator (CDI_POST_DOMINATORS, bb); | |
1224 | if (dominated_by_p (CDI_DOMINATORS, kid, bb) | |
1225 | && bitmap_bit_p (SW (kid)->has_components, which)) | |
1226 | { | |
1227 | SW (bb)->total_cost = SW (bb)->own_cost; | |
1228 | bitmap_set_bit (SW (bb)->has_components, which); | |
1229 | } | |
1230 | } | |
1231 | ||
1232 | /* We are back where we started, so we are done now. */ | |
1233 | if (bb == head) | |
1234 | return; | |
1235 | ||
1236 | /* We now know the cost of the subtree rooted at the current block. | |
1237 | Accumulate this cost in the parent. */ | |
1238 | basic_block parent = get_immediate_dominator (CDI_DOMINATORS, bb); | |
1239 | SW (parent)->total_cost += SW (bb)->total_cost; | |
1240 | ||
1241 | /* Don't walk the tree down unless necessary. */ | |
1242 | if (next_dom_son (CDI_DOMINATORS, bb) | |
1243 | && SW (parent)->total_cost <= SW (parent)->own_cost) | |
1244 | { | |
1245 | bb = next_dom_son (CDI_DOMINATORS, bb); | |
1246 | first_visit = true; | |
1247 | } | |
1248 | else | |
1249 | { | |
1250 | bb = parent; | |
1251 | first_visit = false; | |
1252 | } | |
1253 | } | |
1254 | } | |
1255 | ||
1256 | /* Mark HAS_COMPONENTS for every block dominated by at least one block with | |
1257 | HAS_COMPONENTS set for the respective components, starting at HEAD. */ | |
1258 | static void | |
1259 | spread_components (basic_block head) | |
1260 | { | |
1261 | basic_block bb = head; | |
1262 | bool first_visit = true; | |
1263 | /* This keeps a tally of all components active. */ | |
1264 | sbitmap components = SW (head)->has_components; | |
1265 | ||
1266 | for (;;) | |
1267 | { | |
1268 | if (first_visit) | |
1269 | { | |
1270 | bitmap_ior (SW (bb)->has_components, SW (bb)->has_components, | |
1271 | components); | |
1272 | ||
1273 | if (first_dom_son (CDI_DOMINATORS, bb)) | |
1274 | { | |
1275 | components = SW (bb)->has_components; | |
1276 | bb = first_dom_son (CDI_DOMINATORS, bb); | |
1277 | continue; | |
1278 | } | |
1279 | } | |
1280 | ||
1281 | components = SW (bb)->has_components; | |
1282 | ||
1283 | if (next_dom_son (CDI_DOMINATORS, bb)) | |
1284 | { | |
1285 | bb = next_dom_son (CDI_DOMINATORS, bb); | |
1286 | basic_block parent = get_immediate_dominator (CDI_DOMINATORS, bb); | |
1287 | components = SW (parent)->has_components; | |
1288 | first_visit = true; | |
1289 | } | |
1290 | else | |
1291 | { | |
1292 | if (bb == head) | |
1293 | return; | |
1294 | bb = get_immediate_dominator (CDI_DOMINATORS, bb); | |
1295 | first_visit = false; | |
1296 | } | |
1297 | } | |
1298 | } | |
1299 | ||
1300 | /* If we cannot handle placing some component's prologues or epilogues where | |
1301 | we decided we should place them, unmark that component in COMPONENTS so | |
1302 | that it is not wrapped separately. */ | |
1303 | static void | |
1304 | disqualify_problematic_components (sbitmap components) | |
1305 | { | |
1306 | sbitmap pro = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1307 | sbitmap epi = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1308 | ||
1309 | basic_block bb; | |
1310 | FOR_EACH_BB_FN (bb, cfun) | |
1311 | { | |
1312 | edge e; | |
1313 | edge_iterator ei; | |
1314 | FOR_EACH_EDGE (e, ei, bb->succs) | |
1315 | { | |
1316 | /* Find which components we want pro/epilogues for here. */ | |
1317 | bitmap_and_compl (epi, SW (e->src)->has_components, | |
1318 | SW (e->dest)->has_components); | |
1319 | bitmap_and_compl (pro, SW (e->dest)->has_components, | |
1320 | SW (e->src)->has_components); | |
1321 | ||
1322 | /* Ask the target what it thinks about things. */ | |
1323 | if (!bitmap_empty_p (epi)) | |
1324 | targetm.shrink_wrap.disqualify_components (components, e, epi, | |
1325 | false); | |
1326 | if (!bitmap_empty_p (pro)) | |
1327 | targetm.shrink_wrap.disqualify_components (components, e, pro, | |
1328 | true); | |
1329 | ||
1330 | /* If this edge doesn't need splitting, we're fine. */ | |
1331 | if (single_pred_p (e->dest) | |
1332 | && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
1333 | continue; | |
1334 | ||
1335 | /* If the edge can be split, that is fine too. */ | |
1336 | if ((e->flags & EDGE_ABNORMAL) == 0) | |
1337 | continue; | |
1338 | ||
1339 | /* We also can handle sibcalls. */ | |
1340 | if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
1341 | { | |
1342 | gcc_assert (e->flags & EDGE_SIBCALL); | |
1343 | continue; | |
1344 | } | |
1345 | ||
1346 | /* Remove from consideration those components we would need | |
1347 | pro/epilogues for on edges where we cannot insert them. */ | |
1348 | bitmap_and_compl (components, components, epi); | |
1349 | bitmap_and_compl (components, components, pro); | |
1350 | ||
1351 | if (dump_file && !bitmap_subset_p (epi, components)) | |
1352 | { | |
1353 | fprintf (dump_file, " BAD epi %d->%d", e->src->index, | |
1354 | e->dest->index); | |
1355 | if (e->flags & EDGE_EH) | |
1356 | fprintf (dump_file, " for EH"); | |
1357 | dump_components ("epi", epi); | |
1358 | fprintf (dump_file, "\n"); | |
1359 | } | |
1360 | ||
1361 | if (dump_file && !bitmap_subset_p (pro, components)) | |
1362 | { | |
1363 | fprintf (dump_file, " BAD pro %d->%d", e->src->index, | |
1364 | e->dest->index); | |
1365 | if (e->flags & EDGE_EH) | |
1366 | fprintf (dump_file, " for EH"); | |
1367 | dump_components ("pro", pro); | |
1368 | fprintf (dump_file, "\n"); | |
1369 | } | |
1370 | } | |
1371 | } | |
1372 | ||
1373 | sbitmap_free (pro); | |
1374 | sbitmap_free (epi); | |
1375 | } | |
1376 | ||
1377 | /* Place code for prologues and epilogues for COMPONENTS where we can put | |
1378 | that code at the start of basic blocks. */ | |
1379 | static void | |
1380 | emit_common_heads_for_components (sbitmap components) | |
1381 | { | |
1382 | sbitmap pro = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1383 | sbitmap epi = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1384 | sbitmap tmp = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1385 | ||
1386 | basic_block bb; | |
1387 | FOR_EACH_BB_FN (bb, cfun) | |
1388 | { | |
1389 | /* Find which prologue resp. epilogue components are needed for all | |
1390 | predecessor edges to this block. */ | |
1391 | ||
1392 | /* First, select all possible components. */ | |
1393 | bitmap_copy (epi, components); | |
1394 | bitmap_copy (pro, components); | |
1395 | ||
1396 | edge e; | |
1397 | edge_iterator ei; | |
1398 | FOR_EACH_EDGE (e, ei, bb->preds) | |
1399 | { | |
1400 | if (e->flags & EDGE_ABNORMAL) | |
1401 | { | |
1402 | bitmap_clear (epi); | |
1403 | bitmap_clear (pro); | |
1404 | break; | |
1405 | } | |
1406 | ||
1407 | /* Deselect those epilogue components that should not be inserted | |
1408 | for this edge. */ | |
1409 | bitmap_and_compl (tmp, SW (e->src)->has_components, | |
1410 | SW (e->dest)->has_components); | |
1411 | bitmap_and (epi, epi, tmp); | |
1412 | ||
1413 | /* Similar, for the prologue. */ | |
1414 | bitmap_and_compl (tmp, SW (e->dest)->has_components, | |
1415 | SW (e->src)->has_components); | |
1416 | bitmap_and (pro, pro, tmp); | |
1417 | } | |
1418 | ||
1419 | if (dump_file && !(bitmap_empty_p (epi) && bitmap_empty_p (pro))) | |
1420 | fprintf (dump_file, " bb %d", bb->index); | |
1421 | ||
1422 | if (dump_file && !bitmap_empty_p (epi)) | |
1423 | dump_components ("epi", epi); | |
1424 | if (dump_file && !bitmap_empty_p (pro)) | |
1425 | dump_components ("pro", pro); | |
1426 | ||
1427 | if (dump_file && !(bitmap_empty_p (epi) && bitmap_empty_p (pro))) | |
1428 | fprintf (dump_file, "\n"); | |
1429 | ||
1430 | /* Place code after the BB note. */ | |
1431 | if (!bitmap_empty_p (pro)) | |
1432 | { | |
1433 | start_sequence (); | |
1434 | targetm.shrink_wrap.emit_prologue_components (pro); | |
1435 | rtx_insn *seq = get_insns (); | |
1436 | end_sequence (); | |
1437 | ||
1438 | emit_insn_after (seq, bb_note (bb)); | |
1439 | ||
1440 | bitmap_ior (SW (bb)->head_components, SW (bb)->head_components, pro); | |
1441 | } | |
1442 | ||
1443 | if (!bitmap_empty_p (epi)) | |
1444 | { | |
1445 | start_sequence (); | |
1446 | targetm.shrink_wrap.emit_epilogue_components (epi); | |
1447 | rtx_insn *seq = get_insns (); | |
1448 | end_sequence (); | |
1449 | ||
1450 | emit_insn_after (seq, bb_note (bb)); | |
1451 | ||
1452 | bitmap_ior (SW (bb)->head_components, SW (bb)->head_components, epi); | |
1453 | } | |
1454 | } | |
1455 | ||
1456 | sbitmap_free (pro); | |
1457 | sbitmap_free (epi); | |
1458 | sbitmap_free (tmp); | |
1459 | } | |
1460 | ||
1461 | /* Place code for prologues and epilogues for COMPONENTS where we can put | |
1462 | that code at the end of basic blocks. */ | |
1463 | static void | |
1464 | emit_common_tails_for_components (sbitmap components) | |
1465 | { | |
1466 | sbitmap pro = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1467 | sbitmap epi = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1468 | sbitmap tmp = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1469 | ||
1470 | basic_block bb; | |
1471 | FOR_EACH_BB_FN (bb, cfun) | |
1472 | { | |
1473 | /* Find which prologue resp. epilogue components are needed for all | |
1474 | successor edges from this block. */ | |
1475 | if (EDGE_COUNT (bb->succs) == 0) | |
1476 | continue; | |
1477 | ||
1478 | /* First, select all possible components. */ | |
1479 | bitmap_copy (epi, components); | |
1480 | bitmap_copy (pro, components); | |
1481 | ||
1482 | edge e; | |
1483 | edge_iterator ei; | |
1484 | FOR_EACH_EDGE (e, ei, bb->succs) | |
1485 | { | |
1486 | if (e->flags & EDGE_ABNORMAL) | |
1487 | { | |
1488 | bitmap_clear (epi); | |
1489 | bitmap_clear (pro); | |
1490 | break; | |
1491 | } | |
1492 | ||
1493 | /* Deselect those epilogue components that should not be inserted | |
1494 | for this edge, and also those that are already put at the head | |
1495 | of the successor block. */ | |
1496 | bitmap_and_compl (tmp, SW (e->src)->has_components, | |
1497 | SW (e->dest)->has_components); | |
1498 | bitmap_and_compl (tmp, tmp, SW (e->dest)->head_components); | |
1499 | bitmap_and (epi, epi, tmp); | |
1500 | ||
1501 | /* Similarly, for the prologue. */ | |
1502 | bitmap_and_compl (tmp, SW (e->dest)->has_components, | |
1503 | SW (e->src)->has_components); | |
1504 | bitmap_and_compl (tmp, tmp, SW (e->dest)->head_components); | |
1505 | bitmap_and (pro, pro, tmp); | |
1506 | } | |
1507 | ||
1508 | /* If the last insn of this block is a control flow insn we cannot | |
1509 | put anything after it. We can put our code before it instead, | |
1510 | but only if that jump insn is a simple jump. */ | |
1511 | rtx_insn *last_insn = BB_END (bb); | |
1512 | if (control_flow_insn_p (last_insn) && !simplejump_p (last_insn)) | |
1513 | { | |
1514 | bitmap_clear (epi); | |
1515 | bitmap_clear (pro); | |
1516 | } | |
1517 | ||
1518 | if (dump_file && !(bitmap_empty_p (epi) && bitmap_empty_p (pro))) | |
1519 | fprintf (dump_file, " bb %d", bb->index); | |
1520 | ||
1521 | if (dump_file && !bitmap_empty_p (epi)) | |
1522 | dump_components ("epi", epi); | |
1523 | if (dump_file && !bitmap_empty_p (pro)) | |
1524 | dump_components ("pro", pro); | |
1525 | ||
1526 | if (dump_file && !(bitmap_empty_p (epi) && bitmap_empty_p (pro))) | |
1527 | fprintf (dump_file, "\n"); | |
1528 | ||
1529 | /* Put the code at the end of the BB, but before any final jump. */ | |
1530 | if (!bitmap_empty_p (epi)) | |
1531 | { | |
1532 | start_sequence (); | |
1533 | targetm.shrink_wrap.emit_epilogue_components (epi); | |
1534 | rtx_insn *seq = get_insns (); | |
1535 | end_sequence (); | |
1536 | ||
1537 | if (control_flow_insn_p (last_insn)) | |
1538 | emit_insn_before (seq, last_insn); | |
1539 | else | |
1540 | emit_insn_after (seq, last_insn); | |
1541 | ||
1542 | bitmap_ior (SW (bb)->tail_components, SW (bb)->tail_components, epi); | |
1543 | } | |
1544 | ||
1545 | if (!bitmap_empty_p (pro)) | |
1546 | { | |
1547 | start_sequence (); | |
1548 | targetm.shrink_wrap.emit_prologue_components (pro); | |
1549 | rtx_insn *seq = get_insns (); | |
1550 | end_sequence (); | |
1551 | ||
1552 | if (control_flow_insn_p (last_insn)) | |
1553 | emit_insn_before (seq, last_insn); | |
1554 | else | |
1555 | emit_insn_after (seq, last_insn); | |
1556 | ||
1557 | bitmap_ior (SW (bb)->tail_components, SW (bb)->tail_components, pro); | |
1558 | } | |
1559 | } | |
1560 | ||
1561 | sbitmap_free (pro); | |
1562 | sbitmap_free (epi); | |
1563 | sbitmap_free (tmp); | |
1564 | } | |
1565 | ||
1566 | /* Place prologues and epilogues for COMPONENTS on edges, if we haven't already | |
1567 | placed them inside blocks directly. */ | |
1568 | static void | |
1569 | insert_prologue_epilogue_for_components (sbitmap components) | |
1570 | { | |
1571 | sbitmap pro = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1572 | sbitmap epi = sbitmap_alloc (SBITMAP_SIZE (components)); | |
1573 | ||
1574 | basic_block bb; | |
1575 | FOR_EACH_BB_FN (bb, cfun) | |
1576 | { | |
1577 | if (!bb->aux) | |
1578 | continue; | |
1579 | ||
1580 | edge e; | |
1581 | edge_iterator ei; | |
1582 | FOR_EACH_EDGE (e, ei, bb->succs) | |
1583 | { | |
1584 | /* Find which pro/epilogue components are needed on this edge. */ | |
1585 | bitmap_and_compl (epi, SW (e->src)->has_components, | |
1586 | SW (e->dest)->has_components); | |
1587 | bitmap_and_compl (pro, SW (e->dest)->has_components, | |
1588 | SW (e->src)->has_components); | |
1589 | bitmap_and (epi, epi, components); | |
1590 | bitmap_and (pro, pro, components); | |
1591 | ||
1592 | /* Deselect those we already have put at the head or tail of the | |
1593 | edge's dest resp. src. */ | |
1594 | bitmap_and_compl (epi, epi, SW (e->dest)->head_components); | |
1595 | bitmap_and_compl (pro, pro, SW (e->dest)->head_components); | |
1596 | bitmap_and_compl (epi, epi, SW (e->src)->tail_components); | |
1597 | bitmap_and_compl (pro, pro, SW (e->src)->tail_components); | |
1598 | ||
1599 | if (!bitmap_empty_p (epi) || !bitmap_empty_p (pro)) | |
1600 | { | |
1601 | if (dump_file) | |
1602 | { | |
1603 | fprintf (dump_file, " %d->%d", e->src->index, | |
1604 | e->dest->index); | |
1605 | dump_components ("epi", epi); | |
1606 | dump_components ("pro", pro); | |
1607 | fprintf (dump_file, "\n"); | |
1608 | } | |
1609 | ||
1610 | /* Put the epilogue components in place. */ | |
1611 | start_sequence (); | |
1612 | targetm.shrink_wrap.emit_epilogue_components (epi); | |
1613 | rtx_insn *seq = get_insns (); | |
1614 | end_sequence (); | |
1615 | ||
1616 | if (e->flags & EDGE_SIBCALL) | |
1617 | { | |
1618 | gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
1619 | ||
1620 | rtx_insn *insn = BB_END (e->src); | |
1621 | gcc_assert (CALL_P (insn) && SIBLING_CALL_P (insn)); | |
1622 | emit_insn_before (seq, insn); | |
1623 | } | |
1624 | else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
1625 | { | |
1626 | gcc_assert (e->flags & EDGE_FALLTHRU); | |
1627 | basic_block new_bb = split_edge (e); | |
1628 | emit_insn_after (seq, BB_END (new_bb)); | |
1629 | } | |
1630 | else | |
1631 | insert_insn_on_edge (seq, e); | |
1632 | ||
1633 | /* Put the prologue components in place. */ | |
1634 | start_sequence (); | |
1635 | targetm.shrink_wrap.emit_prologue_components (pro); | |
1636 | seq = get_insns (); | |
1637 | end_sequence (); | |
1638 | ||
1639 | insert_insn_on_edge (seq, e); | |
1640 | } | |
1641 | } | |
1642 | } | |
1643 | ||
1644 | sbitmap_free (pro); | |
1645 | sbitmap_free (epi); | |
1646 | ||
1647 | commit_edge_insertions (); | |
1648 | } | |
1649 | ||
1650 | /* The main entry point to this subpass. FIRST_BB is where the prologue | |
1651 | would be normally put. */ | |
1652 | void | |
1653 | try_shrink_wrapping_separate (basic_block first_bb) | |
1654 | { | |
1655 | if (HAVE_cc0) | |
1656 | return; | |
1657 | ||
1658 | if (!(SHRINK_WRAPPING_ENABLED | |
1659 | && flag_shrink_wrap_separate | |
1660 | && optimize_function_for_speed_p (cfun) | |
1661 | && targetm.shrink_wrap.get_separate_components)) | |
1662 | return; | |
1663 | ||
1664 | /* We don't handle "strange" functions. */ | |
1665 | if (cfun->calls_alloca | |
1666 | || cfun->calls_setjmp | |
1667 | || cfun->can_throw_non_call_exceptions | |
1668 | || crtl->calls_eh_return | |
1669 | || crtl->has_nonlocal_goto | |
1670 | || crtl->saves_all_registers) | |
1671 | return; | |
1672 | ||
1673 | /* Ask the target what components there are. If it returns NULL, don't | |
1674 | do anything. */ | |
1675 | sbitmap components = targetm.shrink_wrap.get_separate_components (); | |
1676 | if (!components) | |
1677 | return; | |
1678 | ||
1679 | /* We need LIVE info. */ | |
1680 | df_live_add_problem (); | |
1681 | df_live_set_all_dirty (); | |
1682 | df_analyze (); | |
1683 | ||
1684 | calculate_dominance_info (CDI_DOMINATORS); | |
1685 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
1686 | ||
1687 | init_separate_shrink_wrap (components); | |
1688 | ||
1689 | sbitmap_iterator sbi; | |
1690 | unsigned int j; | |
1691 | EXECUTE_IF_SET_IN_BITMAP (components, 0, j, sbi) | |
1692 | place_prologue_for_one_component (j, first_bb); | |
1693 | ||
1694 | spread_components (first_bb); | |
1695 | ||
1696 | disqualify_problematic_components (components); | |
1697 | ||
1698 | /* Don't separately shrink-wrap anything where the "main" prologue will | |
1699 | go; the target code can often optimize things if it is presented with | |
1700 | all components together (say, if it generates store-multiple insns). */ | |
1701 | bitmap_and_compl (components, components, SW (first_bb)->has_components); | |
1702 | ||
1703 | if (bitmap_empty_p (components)) | |
1704 | { | |
1705 | if (dump_file) | |
1706 | fprintf (dump_file, "Not wrapping anything separately.\n"); | |
1707 | } | |
1708 | else | |
1709 | { | |
1710 | if (dump_file) | |
1711 | { | |
1712 | fprintf (dump_file, "The components we wrap separately are"); | |
1713 | dump_components ("sep", components); | |
1714 | fprintf (dump_file, "\n"); | |
1715 | ||
1716 | fprintf (dump_file, "... Inserting common heads...\n"); | |
1717 | } | |
1718 | ||
1719 | emit_common_heads_for_components (components); | |
1720 | ||
1721 | if (dump_file) | |
1722 | fprintf (dump_file, "... Inserting common tails...\n"); | |
1723 | ||
1724 | emit_common_tails_for_components (components); | |
1725 | ||
1726 | if (dump_file) | |
1727 | fprintf (dump_file, "... Inserting the more difficult ones...\n"); | |
1728 | ||
1729 | insert_prologue_epilogue_for_components (components); | |
1730 | ||
1731 | if (dump_file) | |
1732 | fprintf (dump_file, "... Done.\n"); | |
1733 | ||
1734 | targetm.shrink_wrap.set_handled_components (components); | |
1735 | ||
1736 | crtl->shrink_wrapped_separate = true; | |
1737 | } | |
1738 | ||
1739 | fini_separate_shrink_wrap (); | |
1740 | ||
1741 | sbitmap_free (components); | |
1742 | free_dominance_info (CDI_DOMINATORS); | |
1743 | free_dominance_info (CDI_POST_DOMINATORS); | |
1744 | ||
1745 | if (crtl->shrink_wrapped_separate) | |
1746 | { | |
1747 | df_live_set_all_dirty (); | |
1748 | df_analyze (); | |
1749 | } | |
1750 | } |