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 two kinds of stack references between stack
75 adjusting instructions: stack references in memory addresses for
76 regular insns and all stack references for debug insns. */
80 HOST_WIDE_INT sp_offset
;
82 struct csa_reflist
*next
;
85 static int stack_memref_p (rtx
);
86 static rtx
single_set_for_csa (rtx
);
87 static void free_csa_reflist (struct csa_reflist
*);
88 static struct csa_reflist
*record_one_stack_ref (rtx
, rtx
*,
89 struct csa_reflist
*);
90 static int try_apply_stack_adjustment (rtx
, struct csa_reflist
*,
91 HOST_WIDE_INT
, HOST_WIDE_INT
);
92 static void combine_stack_adjustments_for_block (basic_block
);
93 static int record_stack_refs (rtx
*, void *);
96 /* Main entry point for stack adjustment combination. */
99 combine_stack_adjustments (void)
104 combine_stack_adjustments_for_block (bb
);
107 /* Recognize a MEM of the form (sp) or (plus sp const). */
110 stack_memref_p (rtx x
)
116 if (x
== stack_pointer_rtx
)
118 if (GET_CODE (x
) == PLUS
119 && XEXP (x
, 0) == stack_pointer_rtx
120 && CONST_INT_P (XEXP (x
, 1)))
126 /* Recognize either normal single_set or the hack in i386.md for
127 tying fp and sp adjustments. */
130 single_set_for_csa (rtx insn
)
133 rtx tmp
= single_set (insn
);
137 if (!NONJUMP_INSN_P (insn
)
138 || GET_CODE (PATTERN (insn
)) != PARALLEL
)
141 tmp
= PATTERN (insn
);
142 if (GET_CODE (XVECEXP (tmp
, 0, 0)) != SET
)
145 for (i
= 1; i
< XVECLEN (tmp
, 0); ++i
)
147 rtx this_rtx
= XVECEXP (tmp
, 0, i
);
149 /* The special case is allowing a no-op set. */
150 if (GET_CODE (this_rtx
) == SET
151 && SET_SRC (this_rtx
) == SET_DEST (this_rtx
))
153 else if (GET_CODE (this_rtx
) != CLOBBER
154 && GET_CODE (this_rtx
) != USE
)
158 return XVECEXP (tmp
, 0, 0);
161 /* Free the list of csa_reflist nodes. */
164 free_csa_reflist (struct csa_reflist
*reflist
)
166 struct csa_reflist
*next
;
167 for (; reflist
; reflist
= next
)
169 next
= reflist
->next
;
174 /* Create a new csa_reflist node from the given stack reference.
175 It is already known that the reference is either a MEM satisfying the
176 predicate stack_memref_p or a REG representing the stack pointer. */
178 static struct csa_reflist
*
179 record_one_stack_ref (rtx insn
, rtx
*ref
, struct csa_reflist
*next_reflist
)
181 struct csa_reflist
*ml
;
183 ml
= XNEW (struct csa_reflist
);
185 if (REG_P (*ref
) || XEXP (*ref
, 0) == stack_pointer_rtx
)
188 ml
->sp_offset
= INTVAL (XEXP (XEXP (*ref
, 0), 1));
192 ml
->next
= next_reflist
;
197 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
198 as each of the memories and stack references in REFLIST. Return true
202 try_apply_stack_adjustment (rtx insn
, struct csa_reflist
*reflist
,
203 HOST_WIDE_INT new_adjust
, HOST_WIDE_INT delta
)
205 struct csa_reflist
*ml
;
208 set
= single_set_for_csa (insn
);
209 if (MEM_P (SET_DEST (set
)))
210 validate_change (insn
, &SET_DEST (set
),
211 replace_equiv_address (SET_DEST (set
), stack_pointer_rtx
),
214 validate_change (insn
, &XEXP (SET_SRC (set
), 1), GEN_INT (new_adjust
), 1);
216 for (ml
= reflist
; ml
; ml
= ml
->next
)
218 rtx new_addr
= plus_constant (stack_pointer_rtx
, ml
->sp_offset
- delta
);
221 if (MEM_P (*ml
->ref
))
222 new_val
= replace_equiv_address_nv (*ml
->ref
, new_addr
);
223 else if (GET_MODE (*ml
->ref
) == GET_MODE (stack_pointer_rtx
))
226 new_val
= lowpart_subreg (GET_MODE (*ml
->ref
), new_addr
,
227 GET_MODE (new_addr
));
228 validate_change (ml
->insn
, ml
->ref
, new_val
, 1);
231 if (apply_change_group ())
233 /* Succeeded. Update our knowledge of the stack references. */
234 for (ml
= reflist
; ml
; ml
= ml
->next
)
235 ml
->sp_offset
-= delta
;
243 /* Called via for_each_rtx and used to record all stack memory and other
244 references in the insn and discard all other stack pointer references. */
245 struct record_stack_refs_data
248 struct csa_reflist
*reflist
;
252 record_stack_refs (rtx
*xp
, void *data
)
255 struct record_stack_refs_data
*d
=
256 (struct record_stack_refs_data
*) data
;
259 switch (GET_CODE (x
))
262 if (!reg_mentioned_p (stack_pointer_rtx
, x
))
264 /* We are not able to handle correctly all possible memrefs containing
265 stack pointer, so this check is necessary. */
266 if (stack_memref_p (x
))
268 d
->reflist
= record_one_stack_ref (d
->insn
, xp
, d
->reflist
);
271 /* Try harder for DEBUG_INSNs, handle e.g. (mem (mem (sp + 16) + 4). */
272 return !DEBUG_INSN_P (d
->insn
);
274 /* ??? We want be able to handle non-memory stack pointer
275 references later. For now just discard all insns referring to
276 stack pointer outside mem expressions. We would probably
277 want to teach validate_replace to simplify expressions first.
279 We can't just compare with STACK_POINTER_RTX because the
280 reference to the stack pointer might be in some other mode.
281 In particular, an explicit clobber in an asm statement will
282 result in a QImode clobber.
284 In DEBUG_INSNs, we want to replace all occurrences, otherwise
285 they will cause -fcompare-debug failures. */
286 if (REGNO (x
) == STACK_POINTER_REGNUM
)
288 if (!DEBUG_INSN_P (d
->insn
))
290 d
->reflist
= record_one_stack_ref (d
->insn
, xp
, d
->reflist
);
300 /* Adjust or create REG_FRAME_RELATED_EXPR note when merging a stack
301 adjustment into a frame related insn. */
304 adjust_frame_related_expr (rtx last_sp_set
, rtx insn
,
305 HOST_WIDE_INT this_adjust
)
307 rtx note
= find_reg_note (last_sp_set
, REG_FRAME_RELATED_EXPR
, NULL_RTX
);
308 rtx new_expr
= NULL_RTX
;
310 if (note
== NULL_RTX
&& RTX_FRAME_RELATED_P (insn
))
314 && GET_CODE (XEXP (note
, 0)) == SEQUENCE
315 && XVECLEN (XEXP (note
, 0), 0) >= 2)
317 rtx expr
= XEXP (note
, 0);
318 rtx last
= XVECEXP (expr
, 0, XVECLEN (expr
, 0) - 1);
321 if (GET_CODE (last
) == SET
322 && RTX_FRAME_RELATED_P (last
) == RTX_FRAME_RELATED_P (insn
)
323 && SET_DEST (last
) == stack_pointer_rtx
324 && GET_CODE (SET_SRC (last
)) == PLUS
325 && XEXP (SET_SRC (last
), 0) == stack_pointer_rtx
326 && CONST_INT_P (XEXP (SET_SRC (last
), 1)))
328 XEXP (SET_SRC (last
), 1)
329 = GEN_INT (INTVAL (XEXP (SET_SRC (last
), 1)) + this_adjust
);
333 new_expr
= gen_rtx_SEQUENCE (VOIDmode
,
334 rtvec_alloc (XVECLEN (expr
, 0) + 1));
335 for (i
= 0; i
< XVECLEN (expr
, 0); i
++)
336 XVECEXP (new_expr
, 0, i
) = XVECEXP (expr
, 0, i
);
340 new_expr
= gen_rtx_SEQUENCE (VOIDmode
, rtvec_alloc (2));
342 XVECEXP (new_expr
, 0, 0) = XEXP (note
, 0);
345 rtx expr
= copy_rtx (single_set_for_csa (last_sp_set
));
347 XEXP (SET_SRC (expr
), 1)
348 = GEN_INT (INTVAL (XEXP (SET_SRC (expr
), 1)) - this_adjust
);
349 RTX_FRAME_RELATED_P (expr
) = 1;
350 XVECEXP (new_expr
, 0, 0) = expr
;
354 XVECEXP (new_expr
, 0, XVECLEN (new_expr
, 0) - 1)
355 = copy_rtx (single_set_for_csa (insn
));
356 RTX_FRAME_RELATED_P (XVECEXP (new_expr
, 0, XVECLEN (new_expr
, 0) - 1))
357 = RTX_FRAME_RELATED_P (insn
);
359 XEXP (note
, 0) = new_expr
;
361 add_reg_note (last_sp_set
, REG_FRAME_RELATED_EXPR
, new_expr
);
364 /* Subroutine of combine_stack_adjustments, called for each basic block. */
367 combine_stack_adjustments_for_block (basic_block bb
)
369 HOST_WIDE_INT last_sp_adjust
= 0;
370 rtx last_sp_set
= NULL_RTX
;
371 struct csa_reflist
*reflist
= NULL
;
373 struct record_stack_refs_data data
;
374 bool end_of_block
= false;
376 for (insn
= BB_HEAD (bb
); !end_of_block
; insn
= next
)
378 end_of_block
= insn
== BB_END (bb
);
379 next
= NEXT_INSN (insn
);
384 set
= single_set_for_csa (insn
);
387 rtx dest
= SET_DEST (set
);
388 rtx src
= SET_SRC (set
);
390 /* Find constant additions to the stack pointer. */
391 if (dest
== stack_pointer_rtx
392 && GET_CODE (src
) == PLUS
393 && XEXP (src
, 0) == stack_pointer_rtx
394 && CONST_INT_P (XEXP (src
, 1)))
396 HOST_WIDE_INT this_adjust
= INTVAL (XEXP (src
, 1));
398 /* If we've not seen an adjustment previously, record
399 it now and continue. */
403 last_sp_adjust
= this_adjust
;
407 /* If not all recorded refs can be adjusted, or the
408 adjustment is now too large for a constant addition,
409 we cannot merge the two stack adjustments.
411 Also we need to be careful to not move stack pointer
412 such that we create stack accesses outside the allocated
413 area. We can combine an allocation into the first insn,
414 or a deallocation into the second insn. We can not
415 combine an allocation followed by a deallocation.
417 The only somewhat frequent occurrence of the later is when
418 a function allocates a stack frame but does not use it.
419 For this case, we would need to analyze rtl stream to be
420 sure that allocated area is really unused. This means not
421 only checking the memory references, but also all registers
422 or global memory references possibly containing a stack
425 Perhaps the best way to address this problem is to teach
426 gcc not to allocate stack for objects never used. */
428 /* Combine an allocation into the first instruction. */
429 if (STACK_GROWS_DOWNWARD
? this_adjust
<= 0 : this_adjust
>= 0)
431 if (try_apply_stack_adjustment (last_sp_set
, reflist
,
432 last_sp_adjust
+ this_adjust
,
435 if (RTX_FRAME_RELATED_P (last_sp_set
))
436 adjust_frame_related_expr (last_sp_set
, insn
,
440 last_sp_adjust
+= this_adjust
;
445 /* Otherwise we have a deallocation. Do not combine with
446 a previous allocation. Combine into the second insn. */
447 else if (STACK_GROWS_DOWNWARD
448 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
450 if (try_apply_stack_adjustment (insn
, reflist
,
451 last_sp_adjust
+ this_adjust
,
455 delete_insn (last_sp_set
);
457 last_sp_adjust
+= this_adjust
;
458 free_csa_reflist (reflist
);
464 /* Combination failed. Restart processing from here. If
465 deallocation+allocation conspired to cancel, we can
466 delete the old deallocation insn. */
467 if (last_sp_set
&& last_sp_adjust
== 0)
468 delete_insn (last_sp_set
);
469 free_csa_reflist (reflist
);
472 last_sp_adjust
= this_adjust
;
476 /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
477 the previous adjustment and turn it into a simple store. This
478 is equivalent to anticipating the stack adjustment so this must
481 && ((STACK_GROWS_DOWNWARD
482 ? (GET_CODE (XEXP (dest
, 0)) == PRE_DEC
484 == (HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
)))
485 : (GET_CODE (XEXP (dest
, 0)) == PRE_INC
487 == -(HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
))))
488 || ((STACK_GROWS_DOWNWARD
489 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
490 && GET_CODE (XEXP (dest
, 0)) == PRE_MODIFY
491 && GET_CODE (XEXP (XEXP (dest
, 0), 1)) == PLUS
492 && XEXP (XEXP (XEXP (dest
, 0), 1), 0)
494 && GET_CODE (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
496 && INTVAL (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
498 && XEXP (XEXP (dest
, 0), 0) == stack_pointer_rtx
499 && !reg_mentioned_p (stack_pointer_rtx
, src
)
500 && memory_address_p (GET_MODE (dest
), stack_pointer_rtx
)
501 && try_apply_stack_adjustment (insn
, reflist
, 0,
504 delete_insn (last_sp_set
);
505 free_csa_reflist (reflist
);
507 last_sp_set
= NULL_RTX
;
514 data
.reflist
= reflist
;
515 if (!CALL_P (insn
) && last_sp_set
516 && !for_each_rtx (&PATTERN (insn
), record_stack_refs
, &data
))
518 reflist
= data
.reflist
;
521 reflist
= data
.reflist
;
523 /* Otherwise, we were not able to process the instruction.
524 Do not continue collecting data across such a one. */
527 || reg_mentioned_p (stack_pointer_rtx
, PATTERN (insn
))))
529 if (last_sp_set
&& last_sp_adjust
== 0)
530 delete_insn (last_sp_set
);
531 free_csa_reflist (reflist
);
533 last_sp_set
= NULL_RTX
;
538 if (last_sp_set
&& last_sp_adjust
== 0)
539 delete_insn (last_sp_set
);
542 free_csa_reflist (reflist
);
547 gate_handle_stack_adjustments (void)
549 return (optimize
> 0);
553 rest_of_handle_stack_adjustments (void)
555 cleanup_cfg (flag_crossjumping
? CLEANUP_CROSSJUMP
: 0);
557 /* This is kind of a heuristic. We need to run combine_stack_adjustments
558 even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS
559 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
560 push instructions will have popping returns. */
561 #ifndef PUSH_ROUNDING
562 if (!ACCUMULATE_OUTGOING_ARGS
)
565 df_note_add_problem ();
567 combine_stack_adjustments ();
572 struct rtl_opt_pass pass_stack_adjustments
=
577 gate_handle_stack_adjustments
, /* gate */
578 rest_of_handle_stack_adjustments
, /* execute */
581 0, /* static_pass_number */
582 TV_COMBINE_STACK_ADJUST
, /* tv_id */
583 0, /* properties_required */
584 0, /* properties_provided */
585 0, /* properties_destroyed */
586 0, /* todo_flags_start */
587 TODO_df_finish
| TODO_verify_rtl_sharing
|
589 TODO_ggc_collect
, /* todo_flags_finish */