1 /* Combine stack adjustments.
2 Copyright (C) 1987-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
20 /* Track stack adjustments and stack memory references. Attempt to
21 reduce the number of stack adjustments by back-propagating across
22 the memory references.
24 This is intended primarily for use with targets that do not define
25 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
26 targets that define PREFERRED_STACK_BOUNDARY more aligned than
27 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
28 (e.g. x86 fp regs) which would ordinarily have to be implemented
29 as a sub/mov pair due to restrictions in calls.c.
31 Propagation stops when any of the insns that need adjusting are
32 (a) no longer valid because we've exceeded their range, (b) a
33 non-trivial push instruction, or (c) a call instruction.
35 Restriction B is based on the assumption that push instructions
36 are smaller or faster. If a port really wants to remove all
37 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
38 one exception that is made is for an add immediately followed
43 #include "coretypes.h"
47 #include "insn-config.h"
50 #include "hard-reg-set.h"
59 #include "basic-block.h"
63 #include "tree-pass.h"
67 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
68 #ifdef STACK_GROWS_DOWNWARD
69 #undef STACK_GROWS_DOWNWARD
70 #define STACK_GROWS_DOWNWARD 1
72 #define STACK_GROWS_DOWNWARD 0
75 /* This structure records two kinds of stack references between stack
76 adjusting instructions: stack references in memory addresses for
77 regular insns and all stack references for debug insns. */
81 HOST_WIDE_INT sp_offset
;
84 struct csa_reflist
*next
;
87 static int stack_memref_p (rtx
);
88 static rtx
single_set_for_csa (rtx_insn
*);
89 static void free_csa_reflist (struct csa_reflist
*);
90 static struct csa_reflist
*record_one_stack_ref (rtx_insn
*, rtx
*,
91 struct csa_reflist
*);
92 static int try_apply_stack_adjustment (rtx_insn
*, struct csa_reflist
*,
93 HOST_WIDE_INT
, HOST_WIDE_INT
);
94 static void combine_stack_adjustments_for_block (basic_block
);
97 /* Main entry point for stack adjustment combination. */
100 combine_stack_adjustments (void)
104 FOR_EACH_BB_FN (bb
, cfun
)
105 combine_stack_adjustments_for_block (bb
);
108 /* Recognize a MEM of the form (sp) or (plus sp const). */
111 stack_memref_p (rtx x
)
117 if (x
== stack_pointer_rtx
)
119 if (GET_CODE (x
) == PLUS
120 && XEXP (x
, 0) == stack_pointer_rtx
121 && CONST_INT_P (XEXP (x
, 1)))
127 /* Recognize either normal single_set or the hack in i386.md for
128 tying fp and sp adjustments. */
131 single_set_for_csa (rtx_insn
*insn
)
134 rtx tmp
= single_set (insn
);
138 if (!NONJUMP_INSN_P (insn
)
139 || GET_CODE (PATTERN (insn
)) != PARALLEL
)
142 tmp
= PATTERN (insn
);
143 if (GET_CODE (XVECEXP (tmp
, 0, 0)) != SET
)
146 for (i
= 1; i
< XVECLEN (tmp
, 0); ++i
)
148 rtx this_rtx
= XVECEXP (tmp
, 0, i
);
150 /* The special case is allowing a no-op set. */
151 if (GET_CODE (this_rtx
) == SET
152 && SET_SRC (this_rtx
) == SET_DEST (this_rtx
))
154 else if (GET_CODE (this_rtx
) != CLOBBER
155 && GET_CODE (this_rtx
) != USE
)
159 return XVECEXP (tmp
, 0, 0);
162 /* Free the list of csa_reflist nodes. */
165 free_csa_reflist (struct csa_reflist
*reflist
)
167 struct csa_reflist
*next
;
168 for (; reflist
; reflist
= next
)
170 next
= reflist
->next
;
175 /* Create a new csa_reflist node from the given stack reference.
176 It is already known that the reference is either a MEM satisfying the
177 predicate stack_memref_p or a REG representing the stack pointer. */
179 static struct csa_reflist
*
180 record_one_stack_ref (rtx_insn
*insn
, rtx
*ref
, struct csa_reflist
*next_reflist
)
182 struct csa_reflist
*ml
;
184 ml
= XNEW (struct csa_reflist
);
186 if (REG_P (*ref
) || XEXP (*ref
, 0) == stack_pointer_rtx
)
189 ml
->sp_offset
= INTVAL (XEXP (XEXP (*ref
, 0), 1));
193 ml
->next
= next_reflist
;
198 /* We only know how to adjust the CFA; no other frame-related changes
199 may appear in any insn to be deleted. */
202 no_unhandled_cfa (rtx_insn
*insn
)
204 if (!RTX_FRAME_RELATED_P (insn
))
207 /* No CFA notes at all is a legacy interpretation like
208 FRAME_RELATED_EXPR, and is context sensitive within
209 the prologue state machine. We can't handle that here. */
210 bool has_cfa_adjust
= false;
212 for (rtx link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
213 switch (REG_NOTE_KIND (link
))
217 case REG_CFA_ADJUST_CFA
:
218 has_cfa_adjust
= true;
221 case REG_FRAME_RELATED_EXPR
:
222 case REG_CFA_DEF_CFA
:
224 case REG_CFA_REGISTER
:
225 case REG_CFA_EXPRESSION
:
226 case REG_CFA_RESTORE
:
227 case REG_CFA_SET_VDRAP
:
228 case REG_CFA_WINDOW_SAVE
:
229 case REG_CFA_FLUSH_QUEUE
:
233 return has_cfa_adjust
;
236 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
237 as each of the memories and stack references in REFLIST. Return true
241 try_apply_stack_adjustment (rtx_insn
*insn
, struct csa_reflist
*reflist
,
242 HOST_WIDE_INT new_adjust
, HOST_WIDE_INT delta
)
244 struct csa_reflist
*ml
;
247 set
= single_set_for_csa (insn
);
248 if (MEM_P (SET_DEST (set
)))
249 validate_change (insn
, &SET_DEST (set
),
250 replace_equiv_address (SET_DEST (set
), stack_pointer_rtx
),
253 validate_change (insn
, &XEXP (SET_SRC (set
), 1), GEN_INT (new_adjust
), 1);
255 for (ml
= reflist
; ml
; ml
= ml
->next
)
257 rtx new_addr
= plus_constant (Pmode
, stack_pointer_rtx
,
258 ml
->sp_offset
- delta
);
261 if (MEM_P (*ml
->ref
))
262 new_val
= replace_equiv_address_nv (*ml
->ref
, new_addr
);
263 else if (GET_MODE (*ml
->ref
) == GET_MODE (stack_pointer_rtx
))
266 new_val
= lowpart_subreg (GET_MODE (*ml
->ref
), new_addr
,
267 GET_MODE (new_addr
));
268 validate_change (ml
->insn
, ml
->ref
, new_val
, 1);
271 if (apply_change_group ())
273 /* Succeeded. Update our knowledge of the stack references. */
274 for (ml
= reflist
; ml
; ml
= ml
->next
)
275 ml
->sp_offset
-= delta
;
283 /* For non-debug insns, record all stack memory references in INSN
284 and return true if there were no other (unrecorded) references to the
285 stack pointer. For debug insns, record all stack references regardless
286 of context and unconditionally return true. */
289 record_stack_refs (rtx_insn
*insn
, struct csa_reflist
**reflist
)
291 subrtx_ptr_iterator::array_type array
;
292 FOR_EACH_SUBRTX_PTR (iter
, array
, &PATTERN (insn
), NONCONST
)
296 switch (GET_CODE (x
))
299 if (!reg_mentioned_p (stack_pointer_rtx
, x
))
300 iter
.skip_subrtxes ();
301 /* We are not able to handle correctly all possible memrefs
302 containing stack pointer, so this check is necessary. */
303 else if (stack_memref_p (x
))
305 *reflist
= record_one_stack_ref (insn
, loc
, *reflist
);
306 iter
.skip_subrtxes ();
308 /* Try harder for DEBUG_INSNs, handle e.g.
309 (mem (mem (sp + 16) + 4). */
310 else if (!DEBUG_INSN_P (insn
))
315 /* ??? We want be able to handle non-memory stack pointer
316 references later. For now just discard all insns referring to
317 stack pointer outside mem expressions. We would probably
318 want to teach validate_replace to simplify expressions first.
320 We can't just compare with STACK_POINTER_RTX because the
321 reference to the stack pointer might be in some other mode.
322 In particular, an explicit clobber in an asm statement will
323 result in a QImode clobber.
325 In DEBUG_INSNs, we want to replace all occurrences, otherwise
326 they will cause -fcompare-debug failures. */
327 if (REGNO (x
) == STACK_POINTER_REGNUM
)
329 if (!DEBUG_INSN_P (insn
))
331 *reflist
= record_one_stack_ref (insn
, loc
, *reflist
);
342 /* If INSN has a REG_ARGS_SIZE note, move it to LAST.
343 AFTER is true iff LAST follows INSN in the instruction stream. */
346 maybe_move_args_size_note (rtx_insn
*last
, rtx_insn
*insn
, bool after
)
350 note
= find_reg_note (insn
, REG_ARGS_SIZE
, NULL_RTX
);
354 last_note
= find_reg_note (last
, REG_ARGS_SIZE
, NULL_RTX
);
357 /* The ARGS_SIZE notes are *not* cumulative. They represent an
358 absolute value, and the "most recent" note wins. */
360 XEXP (last_note
, 0) = XEXP (note
, 0);
363 add_reg_note (last
, REG_ARGS_SIZE
, XEXP (note
, 0));
366 /* Merge any REG_CFA_ADJUST_CFA note from SRC into DST.
367 AFTER is true iff DST follows SRC in the instruction stream. */
370 maybe_merge_cfa_adjust (rtx_insn
*dst
, rtx_insn
*src
, bool after
)
372 rtx snote
= NULL
, dnote
= NULL
;
376 if (RTX_FRAME_RELATED_P (src
))
377 snote
= find_reg_note (src
, REG_CFA_ADJUST_CFA
, NULL_RTX
);
380 sexp
= XEXP (snote
, 0);
382 if (RTX_FRAME_RELATED_P (dst
))
383 dnote
= find_reg_note (dst
, REG_CFA_ADJUST_CFA
, NULL_RTX
);
386 add_reg_note (dst
, REG_CFA_ADJUST_CFA
, sexp
);
389 dexp
= XEXP (dnote
, 0);
391 gcc_assert (GET_CODE (sexp
) == SET
);
392 gcc_assert (GET_CODE (dexp
) == SET
);
395 exp1
= dexp
, exp2
= sexp
;
397 exp1
= sexp
, exp2
= dexp
;
399 SET_SRC (exp1
) = simplify_replace_rtx (SET_SRC (exp1
), SET_DEST (exp2
),
401 XEXP (dnote
, 0) = exp1
;
404 /* Return the next (or previous) active insn within BB. */
407 prev_active_insn_bb (basic_block bb
, rtx_insn
*insn
)
409 for (insn
= PREV_INSN (insn
);
410 insn
!= PREV_INSN (BB_HEAD (bb
));
411 insn
= PREV_INSN (insn
))
412 if (active_insn_p (insn
))
418 next_active_insn_bb (basic_block bb
, rtx_insn
*insn
)
420 for (insn
= NEXT_INSN (insn
);
421 insn
!= NEXT_INSN (BB_END (bb
));
422 insn
= NEXT_INSN (insn
))
423 if (active_insn_p (insn
))
428 /* If INSN has a REG_ARGS_SIZE note, if possible move it to PREV. Otherwise
429 search for a nearby candidate within BB where we can stick the note. */
432 force_move_args_size_note (basic_block bb
, rtx_insn
*prev
, rtx_insn
*insn
)
435 rtx_insn
*test
, *next_candidate
, *prev_candidate
;
437 /* If PREV exists, tail-call to the logic in the other function. */
440 maybe_move_args_size_note (prev
, insn
, false);
444 /* First, make sure there's anything that needs doing. */
445 note
= find_reg_note (insn
, REG_ARGS_SIZE
, NULL_RTX
);
449 /* We need to find a spot between the previous and next exception points
450 where we can place the note and "properly" deallocate the arguments. */
451 next_candidate
= prev_candidate
= NULL
;
453 /* It is often the case that we have insns in the order:
455 add sp (previous deallocation)
456 sub sp (align for next arglist)
458 and the add/sub cancel. Therefore we begin by searching forward. */
461 while ((test
= next_active_insn_bb (bb
, test
)) != NULL
)
463 /* Found an existing note: nothing to do. */
464 if (find_reg_note (test
, REG_ARGS_SIZE
, NULL_RTX
))
466 /* Found something that affects unwinding. Stop searching. */
467 if (CALL_P (test
) || !insn_nothrow_p (test
))
469 if (next_candidate
== NULL
)
470 next_candidate
= test
;
474 while ((test
= prev_active_insn_bb (bb
, test
)) != NULL
)
477 /* Found a place that seems logical to adjust the stack. */
478 tnote
= find_reg_note (test
, REG_ARGS_SIZE
, NULL_RTX
);
481 XEXP (tnote
, 0) = XEXP (note
, 0);
484 if (prev_candidate
== NULL
)
485 prev_candidate
= test
;
486 /* Found something that affects unwinding. Stop searching. */
487 if (CALL_P (test
) || !insn_nothrow_p (test
))
492 test
= prev_candidate
;
493 else if (next_candidate
)
494 test
= next_candidate
;
497 /* ??? We *must* have a place, lest we ICE on the lost adjustment.
498 Options are: dummy clobber insn, nop, or prevent the removal of
500 /* TODO: Find another way to indicate to the dwarf2 code that we
501 have not in fact lost an adjustment. */
502 test
= emit_insn_before (gen_rtx_CLOBBER (VOIDmode
, const0_rtx
), insn
);
504 add_reg_note (test
, REG_ARGS_SIZE
, XEXP (note
, 0));
507 /* Subroutine of combine_stack_adjustments, called for each basic block. */
510 combine_stack_adjustments_for_block (basic_block bb
)
512 HOST_WIDE_INT last_sp_adjust
= 0;
513 rtx_insn
*last_sp_set
= NULL
;
514 rtx_insn
*last2_sp_set
= NULL
;
515 struct csa_reflist
*reflist
= NULL
;
516 rtx_insn
*insn
, *next
;
518 bool end_of_block
= false;
520 for (insn
= BB_HEAD (bb
); !end_of_block
; insn
= next
)
522 end_of_block
= insn
== BB_END (bb
);
523 next
= NEXT_INSN (insn
);
528 set
= single_set_for_csa (insn
);
531 rtx dest
= SET_DEST (set
);
532 rtx src
= SET_SRC (set
);
534 /* Find constant additions to the stack pointer. */
535 if (dest
== stack_pointer_rtx
536 && GET_CODE (src
) == PLUS
537 && XEXP (src
, 0) == stack_pointer_rtx
538 && CONST_INT_P (XEXP (src
, 1)))
540 HOST_WIDE_INT this_adjust
= INTVAL (XEXP (src
, 1));
542 /* If we've not seen an adjustment previously, record
543 it now and continue. */
547 last_sp_adjust
= this_adjust
;
551 /* If not all recorded refs can be adjusted, or the
552 adjustment is now too large for a constant addition,
553 we cannot merge the two stack adjustments.
555 Also we need to be careful to not move stack pointer
556 such that we create stack accesses outside the allocated
557 area. We can combine an allocation into the first insn,
558 or a deallocation into the second insn. We can not
559 combine an allocation followed by a deallocation.
561 The only somewhat frequent occurrence of the later is when
562 a function allocates a stack frame but does not use it.
563 For this case, we would need to analyze rtl stream to be
564 sure that allocated area is really unused. This means not
565 only checking the memory references, but also all registers
566 or global memory references possibly containing a stack
569 Perhaps the best way to address this problem is to teach
570 gcc not to allocate stack for objects never used. */
572 /* Combine an allocation into the first instruction. */
573 if (STACK_GROWS_DOWNWARD
? this_adjust
<= 0 : this_adjust
>= 0)
575 if (no_unhandled_cfa (insn
)
576 && try_apply_stack_adjustment (last_sp_set
, reflist
,
582 maybe_move_args_size_note (last_sp_set
, insn
, false);
583 maybe_merge_cfa_adjust (last_sp_set
, insn
, false);
585 last_sp_adjust
+= this_adjust
;
590 /* Otherwise we have a deallocation. Do not combine with
591 a previous allocation. Combine into the second insn. */
592 else if (STACK_GROWS_DOWNWARD
593 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
595 if (no_unhandled_cfa (last_sp_set
)
596 && try_apply_stack_adjustment (insn
, reflist
,
602 maybe_move_args_size_note (insn
, last_sp_set
, true);
603 maybe_merge_cfa_adjust (insn
, last_sp_set
, true);
604 delete_insn (last_sp_set
);
606 last_sp_adjust
+= this_adjust
;
607 free_csa_reflist (reflist
);
613 /* Combination failed. Restart processing from here. If
614 deallocation+allocation conspired to cancel, we can
615 delete the old deallocation insn. */
618 if (last_sp_adjust
== 0 && no_unhandled_cfa (last_sp_set
))
620 maybe_move_args_size_note (insn
, last_sp_set
, true);
621 maybe_merge_cfa_adjust (insn
, last_sp_set
, true);
622 delete_insn (last_sp_set
);
625 last2_sp_set
= last_sp_set
;
627 free_csa_reflist (reflist
);
630 last_sp_adjust
= this_adjust
;
634 /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
635 the previous adjustment and turn it into a simple store. This
636 is equivalent to anticipating the stack adjustment so this must
639 && ((STACK_GROWS_DOWNWARD
640 ? (GET_CODE (XEXP (dest
, 0)) == PRE_DEC
642 == (HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
)))
643 : (GET_CODE (XEXP (dest
, 0)) == PRE_INC
645 == -(HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
))))
646 || ((STACK_GROWS_DOWNWARD
647 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
648 && GET_CODE (XEXP (dest
, 0)) == PRE_MODIFY
649 && GET_CODE (XEXP (XEXP (dest
, 0), 1)) == PLUS
650 && XEXP (XEXP (XEXP (dest
, 0), 1), 0)
652 && GET_CODE (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
654 && INTVAL (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
656 && XEXP (XEXP (dest
, 0), 0) == stack_pointer_rtx
657 && !reg_mentioned_p (stack_pointer_rtx
, src
)
658 && memory_address_p (GET_MODE (dest
), stack_pointer_rtx
)
659 && try_apply_stack_adjustment (insn
, reflist
, 0,
663 maybe_move_args_size_note (last2_sp_set
, last_sp_set
, false);
665 maybe_move_args_size_note (insn
, last_sp_set
, true);
666 delete_insn (last_sp_set
);
667 free_csa_reflist (reflist
);
675 if (!CALL_P (insn
) && last_sp_set
676 && record_stack_refs (insn
, &reflist
))
679 /* Otherwise, we were not able to process the instruction.
680 Do not continue collecting data across such a one. */
683 || reg_mentioned_p (stack_pointer_rtx
, PATTERN (insn
))))
685 if (last_sp_set
&& last_sp_adjust
== 0)
687 force_move_args_size_note (bb
, last2_sp_set
, last_sp_set
);
688 delete_insn (last_sp_set
);
690 free_csa_reflist (reflist
);
698 if (last_sp_set
&& last_sp_adjust
== 0)
700 force_move_args_size_note (bb
, last2_sp_set
, last_sp_set
);
701 delete_insn (last_sp_set
);
705 free_csa_reflist (reflist
);
709 rest_of_handle_stack_adjustments (void)
711 df_note_add_problem ();
713 combine_stack_adjustments ();
719 const pass_data pass_data_stack_adjustments
=
723 OPTGROUP_NONE
, /* optinfo_flags */
724 TV_COMBINE_STACK_ADJUST
, /* tv_id */
725 0, /* properties_required */
726 0, /* properties_provided */
727 0, /* properties_destroyed */
728 0, /* todo_flags_start */
729 TODO_df_finish
, /* todo_flags_finish */
732 class pass_stack_adjustments
: public rtl_opt_pass
735 pass_stack_adjustments (gcc::context
*ctxt
)
736 : rtl_opt_pass (pass_data_stack_adjustments
, ctxt
)
739 /* opt_pass methods: */
740 virtual bool gate (function
*);
741 virtual unsigned int execute (function
*)
743 return rest_of_handle_stack_adjustments ();
746 }; // class pass_stack_adjustments
749 pass_stack_adjustments::gate (function
*)
751 /* This is kind of a heuristic. We need to run combine_stack_adjustments
752 even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS
753 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
754 push instructions will have popping returns. */
755 #ifndef PUSH_ROUNDING
756 if (ACCUMULATE_OUTGOING_ARGS
)
759 return flag_combine_stack_adjustments
;
765 make_pass_stack_adjustments (gcc::context
*ctxt
)
767 return new pass_stack_adjustments (ctxt
);