1 /* Combine stack adjustments.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
3 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Track stack adjustments and stack memory references. Attempt to
23 reduce the number of stack adjustments by back-propagating across
24 the memory references.
26 This is intended primarily for use with targets that do not define
27 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
28 targets that define PREFERRED_STACK_BOUNDARY more aligned than
29 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
30 (e.g. x86 fp regs) which would ordinarily have to be implemented
31 as a sub/mov pair due to restrictions in calls.c.
33 Propagation stops when any of the insns that need adjusting are
34 (a) no longer valid because we've exceeded their range, (b) a
35 non-trivial push instruction, or (c) a call instruction.
37 Restriction B is based on the assumption that push instructions
38 are smaller or faster. If a port really wants to remove all
39 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
40 one exception that is made is for an add immediately followed
45 #include "coretypes.h"
49 #include "insn-config.h"
53 #include "hard-reg-set.h"
57 #include "basic-block.h"
63 #include "tree-pass.h"
66 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
67 #ifdef STACK_GROWS_DOWNWARD
68 #undef STACK_GROWS_DOWNWARD
69 #define STACK_GROWS_DOWNWARD 1
71 #define STACK_GROWS_DOWNWARD 0
74 /* This structure records stack memory references between stack adjusting
79 HOST_WIDE_INT sp_offset
;
81 struct csa_memlist
*next
;
84 static int stack_memref_p (rtx
);
85 static rtx
single_set_for_csa (rtx
);
86 static void free_csa_memlist (struct csa_memlist
*);
87 static struct csa_memlist
*record_one_stack_memref (rtx
, rtx
*,
88 struct csa_memlist
*);
89 static int try_apply_stack_adjustment (rtx
, struct csa_memlist
*,
90 HOST_WIDE_INT
, HOST_WIDE_INT
);
91 static void combine_stack_adjustments_for_block (basic_block
);
92 static int record_stack_memrefs (rtx
*, void *);
95 /* Main entry point for stack adjustment combination. */
98 combine_stack_adjustments (void)
103 combine_stack_adjustments_for_block (bb
);
106 /* Recognize a MEM of the form (sp) or (plus sp const). */
109 stack_memref_p (rtx x
)
115 if (x
== stack_pointer_rtx
)
117 if (GET_CODE (x
) == PLUS
118 && XEXP (x
, 0) == stack_pointer_rtx
119 && GET_CODE (XEXP (x
, 1)) == CONST_INT
)
125 /* Recognize either normal single_set or the hack in i386.md for
126 tying fp and sp adjustments. */
129 single_set_for_csa (rtx insn
)
132 rtx tmp
= single_set (insn
);
136 if (!NONJUMP_INSN_P (insn
)
137 || GET_CODE (PATTERN (insn
)) != PARALLEL
)
140 tmp
= PATTERN (insn
);
141 if (GET_CODE (XVECEXP (tmp
, 0, 0)) != SET
)
144 for (i
= 1; i
< XVECLEN (tmp
, 0); ++i
)
146 rtx this_rtx
= XVECEXP (tmp
, 0, i
);
148 /* The special case is allowing a no-op set. */
149 if (GET_CODE (this_rtx
) == SET
150 && SET_SRC (this_rtx
) == SET_DEST (this_rtx
))
152 else if (GET_CODE (this_rtx
) != CLOBBER
153 && GET_CODE (this_rtx
) != USE
)
157 return XVECEXP (tmp
, 0, 0);
160 /* Free the list of csa_memlist nodes. */
163 free_csa_memlist (struct csa_memlist
*memlist
)
165 struct csa_memlist
*next
;
166 for (; memlist
; memlist
= next
)
168 next
= memlist
->next
;
173 /* Create a new csa_memlist node from the given memory reference.
174 It is already known that the memory is stack_memref_p. */
176 static struct csa_memlist
*
177 record_one_stack_memref (rtx insn
, rtx
*mem
, struct csa_memlist
*next_memlist
)
179 struct csa_memlist
*ml
;
181 ml
= XNEW (struct csa_memlist
);
183 if (XEXP (*mem
, 0) == stack_pointer_rtx
)
186 ml
->sp_offset
= INTVAL (XEXP (XEXP (*mem
, 0), 1));
190 ml
->next
= next_memlist
;
195 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
196 as each of the memories in MEMLIST. Return true on success. */
199 try_apply_stack_adjustment (rtx insn
, struct csa_memlist
*memlist
, HOST_WIDE_INT new_adjust
,
202 struct csa_memlist
*ml
;
205 set
= single_set_for_csa (insn
);
206 validate_change (insn
, &XEXP (SET_SRC (set
), 1), GEN_INT (new_adjust
), 1);
208 for (ml
= memlist
; ml
; ml
= ml
->next
)
211 replace_equiv_address_nv (*ml
->mem
,
212 plus_constant (stack_pointer_rtx
,
213 ml
->sp_offset
- delta
)), 1);
215 if (apply_change_group ())
217 /* Succeeded. Update our knowledge of the memory references. */
218 for (ml
= memlist
; ml
; ml
= ml
->next
)
219 ml
->sp_offset
-= delta
;
227 /* Called via for_each_rtx and used to record all stack memory references in
228 the insn and discard all other stack pointer references. */
229 struct record_stack_memrefs_data
232 struct csa_memlist
*memlist
;
236 record_stack_memrefs (rtx
*xp
, void *data
)
239 struct record_stack_memrefs_data
*d
=
240 (struct record_stack_memrefs_data
*) data
;
243 switch (GET_CODE (x
))
246 if (!reg_mentioned_p (stack_pointer_rtx
, x
))
248 /* We are not able to handle correctly all possible memrefs containing
249 stack pointer, so this check is necessary. */
250 if (stack_memref_p (x
))
252 d
->memlist
= record_one_stack_memref (d
->insn
, xp
, d
->memlist
);
257 /* ??? We want be able to handle non-memory stack pointer
258 references later. For now just discard all insns referring to
259 stack pointer outside mem expressions. We would probably
260 want to teach validate_replace to simplify expressions first.
262 We can't just compare with STACK_POINTER_RTX because the
263 reference to the stack pointer might be in some other mode.
264 In particular, an explicit clobber in an asm statement will
265 result in a QImode clobber. */
266 if (REGNO (x
) == STACK_POINTER_REGNUM
)
275 /* Adjust or create REG_FRAME_RELATED_EXPR note when merging a stack
276 adjustment into a frame related insn. */
279 adjust_frame_related_expr (rtx last_sp_set
, rtx insn
,
280 HOST_WIDE_INT this_adjust
)
282 rtx note
= find_reg_note (last_sp_set
, REG_FRAME_RELATED_EXPR
, NULL_RTX
);
283 rtx new_expr
= NULL_RTX
;
285 if (note
== NULL_RTX
&& RTX_FRAME_RELATED_P (insn
))
289 && GET_CODE (XEXP (note
, 0)) == SEQUENCE
290 && XVECLEN (XEXP (note
, 0), 0) >= 2)
292 rtx expr
= XEXP (note
, 0);
293 rtx last
= XVECEXP (expr
, 0, XVECLEN (expr
, 0) - 1);
296 if (GET_CODE (last
) == SET
297 && RTX_FRAME_RELATED_P (last
) == RTX_FRAME_RELATED_P (insn
)
298 && SET_DEST (last
) == stack_pointer_rtx
299 && GET_CODE (SET_SRC (last
)) == PLUS
300 && XEXP (SET_SRC (last
), 0) == stack_pointer_rtx
301 && GET_CODE (XEXP (SET_SRC (last
), 1)) == CONST_INT
)
303 XEXP (SET_SRC (last
), 1)
304 = GEN_INT (INTVAL (XEXP (SET_SRC (last
), 1)) + this_adjust
);
308 new_expr
= gen_rtx_SEQUENCE (VOIDmode
,
309 rtvec_alloc (XVECLEN (expr
, 0) + 1));
310 for (i
= 0; i
< XVECLEN (expr
, 0); i
++)
311 XVECEXP (new_expr
, 0, i
) = XVECEXP (expr
, 0, i
);
315 new_expr
= gen_rtx_SEQUENCE (VOIDmode
, rtvec_alloc (2));
317 XVECEXP (new_expr
, 0, 0) = XEXP (note
, 0);
320 rtx expr
= copy_rtx (single_set_for_csa (last_sp_set
));
322 XEXP (SET_SRC (expr
), 1)
323 = GEN_INT (INTVAL (XEXP (SET_SRC (expr
), 1)) - this_adjust
);
324 RTX_FRAME_RELATED_P (expr
) = 1;
325 XVECEXP (new_expr
, 0, 0) = expr
;
329 XVECEXP (new_expr
, 0, XVECLEN (new_expr
, 0) - 1)
330 = copy_rtx (single_set_for_csa (insn
));
331 RTX_FRAME_RELATED_P (XVECEXP (new_expr
, 0, XVECLEN (new_expr
, 0) - 1))
332 = RTX_FRAME_RELATED_P (insn
);
334 XEXP (note
, 0) = new_expr
;
336 add_reg_note (last_sp_set
, REG_FRAME_RELATED_EXPR
, new_expr
);
339 /* Subroutine of combine_stack_adjustments, called for each basic block. */
342 combine_stack_adjustments_for_block (basic_block bb
)
344 HOST_WIDE_INT last_sp_adjust
= 0;
345 rtx last_sp_set
= NULL_RTX
;
346 struct csa_memlist
*memlist
= NULL
;
348 struct record_stack_memrefs_data data
;
349 bool end_of_block
= false;
351 for (insn
= BB_HEAD (bb
); !end_of_block
; insn
= next
)
353 end_of_block
= insn
== BB_END (bb
);
354 next
= NEXT_INSN (insn
);
359 set
= single_set_for_csa (insn
);
362 rtx dest
= SET_DEST (set
);
363 rtx src
= SET_SRC (set
);
365 /* Find constant additions to the stack pointer. */
366 if (dest
== stack_pointer_rtx
367 && GET_CODE (src
) == PLUS
368 && XEXP (src
, 0) == stack_pointer_rtx
369 && GET_CODE (XEXP (src
, 1)) == CONST_INT
)
371 HOST_WIDE_INT this_adjust
= INTVAL (XEXP (src
, 1));
373 /* If we've not seen an adjustment previously, record
374 it now and continue. */
378 last_sp_adjust
= this_adjust
;
382 /* If not all recorded memrefs can be adjusted, or the
383 adjustment is now too large for a constant addition,
384 we cannot merge the two stack adjustments.
386 Also we need to be careful to not move stack pointer
387 such that we create stack accesses outside the allocated
388 area. We can combine an allocation into the first insn,
389 or a deallocation into the second insn. We can not
390 combine an allocation followed by a deallocation.
392 The only somewhat frequent occurrence of the later is when
393 a function allocates a stack frame but does not use it.
394 For this case, we would need to analyze rtl stream to be
395 sure that allocated area is really unused. This means not
396 only checking the memory references, but also all registers
397 or global memory references possibly containing a stack
400 Perhaps the best way to address this problem is to teach
401 gcc not to allocate stack for objects never used. */
403 /* Combine an allocation into the first instruction. */
404 if (STACK_GROWS_DOWNWARD
? this_adjust
<= 0 : this_adjust
>= 0)
406 if (try_apply_stack_adjustment (last_sp_set
, memlist
,
407 last_sp_adjust
+ this_adjust
,
410 if (RTX_FRAME_RELATED_P (last_sp_set
))
411 adjust_frame_related_expr (last_sp_set
, insn
,
415 last_sp_adjust
+= this_adjust
;
420 /* Otherwise we have a deallocation. Do not combine with
421 a previous allocation. Combine into the second insn. */
422 else if (STACK_GROWS_DOWNWARD
423 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
425 if (try_apply_stack_adjustment (insn
, memlist
,
426 last_sp_adjust
+ this_adjust
,
430 delete_insn (last_sp_set
);
432 last_sp_adjust
+= this_adjust
;
433 free_csa_memlist (memlist
);
439 /* Combination failed. Restart processing from here. If
440 deallocation+allocation conspired to cancel, we can
441 delete the old deallocation insn. */
442 if (last_sp_set
&& last_sp_adjust
== 0)
443 delete_insn (last_sp_set
);
444 free_csa_memlist (memlist
);
447 last_sp_adjust
= this_adjust
;
451 /* Find a predecrement of exactly the previous adjustment and
452 turn it into a direct store. Obviously we can't do this if
453 there were any intervening uses of the stack pointer. */
456 && ((GET_CODE (XEXP (dest
, 0)) == PRE_DEC
458 == (HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
))))
459 || (GET_CODE (XEXP (dest
, 0)) == PRE_MODIFY
460 && GET_CODE (XEXP (XEXP (dest
, 0), 1)) == PLUS
461 && XEXP (XEXP (XEXP (dest
, 0), 1), 0) == stack_pointer_rtx
462 && (GET_CODE (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
464 && (INTVAL (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
465 == -last_sp_adjust
)))
466 && XEXP (XEXP (dest
, 0), 0) == stack_pointer_rtx
467 && ! reg_mentioned_p (stack_pointer_rtx
, src
)
468 && memory_address_p (GET_MODE (dest
), stack_pointer_rtx
)
469 && validate_change (insn
, &SET_DEST (set
),
470 replace_equiv_address (dest
,
474 delete_insn (last_sp_set
);
475 free_csa_memlist (memlist
);
477 last_sp_set
= NULL_RTX
;
484 data
.memlist
= memlist
;
485 if (!CALL_P (insn
) && last_sp_set
486 && !for_each_rtx (&PATTERN (insn
), record_stack_memrefs
, &data
))
488 memlist
= data
.memlist
;
491 memlist
= data
.memlist
;
493 /* Otherwise, we were not able to process the instruction.
494 Do not continue collecting data across such a one. */
497 || reg_mentioned_p (stack_pointer_rtx
, PATTERN (insn
))))
499 if (last_sp_set
&& last_sp_adjust
== 0)
500 delete_insn (last_sp_set
);
501 free_csa_memlist (memlist
);
503 last_sp_set
= NULL_RTX
;
508 if (last_sp_set
&& last_sp_adjust
== 0)
509 delete_insn (last_sp_set
);
512 free_csa_memlist (memlist
);
517 gate_handle_stack_adjustments (void)
519 return (optimize
> 0);
523 rest_of_handle_stack_adjustments (void)
525 cleanup_cfg (flag_crossjumping
? CLEANUP_CROSSJUMP
: 0);
527 /* This is kind of a heuristic. We need to run combine_stack_adjustments
528 even for machines with possibly nonzero RETURN_POPS_ARGS
529 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
530 push instructions will have popping returns. */
531 #ifndef PUSH_ROUNDING
532 if (!ACCUMULATE_OUTGOING_ARGS
)
535 df_note_add_problem ();
537 combine_stack_adjustments ();
542 struct rtl_opt_pass pass_stack_adjustments
=
547 gate_handle_stack_adjustments
, /* gate */
548 rest_of_handle_stack_adjustments
, /* execute */
551 0, /* static_pass_number */
553 0, /* properties_required */
554 0, /* properties_provided */
555 0, /* properties_destroyed */
556 0, /* todo_flags_start */
557 TODO_df_finish
| TODO_verify_rtl_sharing
|
559 TODO_ggc_collect
, /* todo_flags_finish */