1 /* Combine stack adjustments.
2 Copyright (C) 1987-2015 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"
61 #include "dominance.h"
64 #include "basic-block.h"
68 #include "tree-pass.h"
72 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
73 #ifdef STACK_GROWS_DOWNWARD
74 #undef STACK_GROWS_DOWNWARD
75 #define STACK_GROWS_DOWNWARD 1
77 #define STACK_GROWS_DOWNWARD 0
80 /* This structure records two kinds of stack references between stack
81 adjusting instructions: stack references in memory addresses for
82 regular insns and all stack references for debug insns. */
86 HOST_WIDE_INT sp_offset
;
89 struct csa_reflist
*next
;
92 static int stack_memref_p (rtx
);
93 static rtx
single_set_for_csa (rtx_insn
*);
94 static void free_csa_reflist (struct csa_reflist
*);
95 static struct csa_reflist
*record_one_stack_ref (rtx_insn
*, rtx
*,
96 struct csa_reflist
*);
97 static int try_apply_stack_adjustment (rtx_insn
*, struct csa_reflist
*,
98 HOST_WIDE_INT
, HOST_WIDE_INT
);
99 static void combine_stack_adjustments_for_block (basic_block
);
102 /* Main entry point for stack adjustment combination. */
105 combine_stack_adjustments (void)
109 FOR_EACH_BB_FN (bb
, cfun
)
110 combine_stack_adjustments_for_block (bb
);
113 /* Recognize a MEM of the form (sp) or (plus sp const). */
116 stack_memref_p (rtx x
)
122 if (x
== stack_pointer_rtx
)
124 if (GET_CODE (x
) == PLUS
125 && XEXP (x
, 0) == stack_pointer_rtx
126 && CONST_INT_P (XEXP (x
, 1)))
132 /* Recognize either normal single_set or the hack in i386.md for
133 tying fp and sp adjustments. */
136 single_set_for_csa (rtx_insn
*insn
)
139 rtx tmp
= single_set (insn
);
143 if (!NONJUMP_INSN_P (insn
)
144 || GET_CODE (PATTERN (insn
)) != PARALLEL
)
147 tmp
= PATTERN (insn
);
148 if (GET_CODE (XVECEXP (tmp
, 0, 0)) != SET
)
151 for (i
= 1; i
< XVECLEN (tmp
, 0); ++i
)
153 rtx this_rtx
= XVECEXP (tmp
, 0, i
);
155 /* The special case is allowing a no-op set. */
156 if (GET_CODE (this_rtx
) == SET
157 && SET_SRC (this_rtx
) == SET_DEST (this_rtx
))
159 else if (GET_CODE (this_rtx
) != CLOBBER
160 && GET_CODE (this_rtx
) != USE
)
164 return XVECEXP (tmp
, 0, 0);
167 /* Free the list of csa_reflist nodes. */
170 free_csa_reflist (struct csa_reflist
*reflist
)
172 struct csa_reflist
*next
;
173 for (; reflist
; reflist
= next
)
175 next
= reflist
->next
;
180 /* Create a new csa_reflist node from the given stack reference.
181 It is already known that the reference is either a MEM satisfying the
182 predicate stack_memref_p or a REG representing the stack pointer. */
184 static struct csa_reflist
*
185 record_one_stack_ref (rtx_insn
*insn
, rtx
*ref
, struct csa_reflist
*next_reflist
)
187 struct csa_reflist
*ml
;
189 ml
= XNEW (struct csa_reflist
);
191 if (REG_P (*ref
) || XEXP (*ref
, 0) == stack_pointer_rtx
)
194 ml
->sp_offset
= INTVAL (XEXP (XEXP (*ref
, 0), 1));
198 ml
->next
= next_reflist
;
203 /* We only know how to adjust the CFA; no other frame-related changes
204 may appear in any insn to be deleted. */
207 no_unhandled_cfa (rtx_insn
*insn
)
209 if (!RTX_FRAME_RELATED_P (insn
))
212 /* No CFA notes at all is a legacy interpretation like
213 FRAME_RELATED_EXPR, and is context sensitive within
214 the prologue state machine. We can't handle that here. */
215 bool has_cfa_adjust
= false;
217 for (rtx link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
218 switch (REG_NOTE_KIND (link
))
222 case REG_CFA_ADJUST_CFA
:
223 has_cfa_adjust
= true;
226 case REG_FRAME_RELATED_EXPR
:
227 case REG_CFA_DEF_CFA
:
229 case REG_CFA_REGISTER
:
230 case REG_CFA_EXPRESSION
:
231 case REG_CFA_RESTORE
:
232 case REG_CFA_SET_VDRAP
:
233 case REG_CFA_WINDOW_SAVE
:
234 case REG_CFA_FLUSH_QUEUE
:
238 return has_cfa_adjust
;
241 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
242 as each of the memories and stack references in REFLIST. Return true
246 try_apply_stack_adjustment (rtx_insn
*insn
, struct csa_reflist
*reflist
,
247 HOST_WIDE_INT new_adjust
, HOST_WIDE_INT delta
)
249 struct csa_reflist
*ml
;
252 set
= single_set_for_csa (insn
);
253 if (MEM_P (SET_DEST (set
)))
254 validate_change (insn
, &SET_DEST (set
),
255 replace_equiv_address (SET_DEST (set
), stack_pointer_rtx
),
258 validate_change (insn
, &XEXP (SET_SRC (set
), 1), GEN_INT (new_adjust
), 1);
260 for (ml
= reflist
; ml
; ml
= ml
->next
)
262 rtx new_addr
= plus_constant (Pmode
, stack_pointer_rtx
,
263 ml
->sp_offset
- delta
);
266 if (MEM_P (*ml
->ref
))
267 new_val
= replace_equiv_address_nv (*ml
->ref
, new_addr
);
268 else if (GET_MODE (*ml
->ref
) == GET_MODE (stack_pointer_rtx
))
271 new_val
= lowpart_subreg (GET_MODE (*ml
->ref
), new_addr
,
272 GET_MODE (new_addr
));
273 validate_change (ml
->insn
, ml
->ref
, new_val
, 1);
276 if (apply_change_group ())
278 /* Succeeded. Update our knowledge of the stack references. */
279 for (ml
= reflist
; ml
; ml
= ml
->next
)
280 ml
->sp_offset
-= delta
;
288 /* For non-debug insns, record all stack memory references in INSN
289 and return true if there were no other (unrecorded) references to the
290 stack pointer. For debug insns, record all stack references regardless
291 of context and unconditionally return true. */
294 record_stack_refs (rtx_insn
*insn
, struct csa_reflist
**reflist
)
296 subrtx_ptr_iterator::array_type array
;
297 FOR_EACH_SUBRTX_PTR (iter
, array
, &PATTERN (insn
), NONCONST
)
301 switch (GET_CODE (x
))
304 if (!reg_mentioned_p (stack_pointer_rtx
, x
))
305 iter
.skip_subrtxes ();
306 /* We are not able to handle correctly all possible memrefs
307 containing stack pointer, so this check is necessary. */
308 else if (stack_memref_p (x
))
310 *reflist
= record_one_stack_ref (insn
, loc
, *reflist
);
311 iter
.skip_subrtxes ();
313 /* Try harder for DEBUG_INSNs, handle e.g.
314 (mem (mem (sp + 16) + 4). */
315 else if (!DEBUG_INSN_P (insn
))
320 /* ??? We want be able to handle non-memory stack pointer
321 references later. For now just discard all insns referring to
322 stack pointer outside mem expressions. We would probably
323 want to teach validate_replace to simplify expressions first.
325 We can't just compare with STACK_POINTER_RTX because the
326 reference to the stack pointer might be in some other mode.
327 In particular, an explicit clobber in an asm statement will
328 result in a QImode clobber.
330 In DEBUG_INSNs, we want to replace all occurrences, otherwise
331 they will cause -fcompare-debug failures. */
332 if (REGNO (x
) == STACK_POINTER_REGNUM
)
334 if (!DEBUG_INSN_P (insn
))
336 *reflist
= record_one_stack_ref (insn
, loc
, *reflist
);
347 /* If INSN has a REG_ARGS_SIZE note, move it to LAST.
348 AFTER is true iff LAST follows INSN in the instruction stream. */
351 maybe_move_args_size_note (rtx_insn
*last
, rtx_insn
*insn
, bool after
)
355 note
= find_reg_note (insn
, REG_ARGS_SIZE
, NULL_RTX
);
359 last_note
= find_reg_note (last
, REG_ARGS_SIZE
, NULL_RTX
);
362 /* The ARGS_SIZE notes are *not* cumulative. They represent an
363 absolute value, and the "most recent" note wins. */
365 XEXP (last_note
, 0) = XEXP (note
, 0);
368 add_reg_note (last
, REG_ARGS_SIZE
, XEXP (note
, 0));
371 /* Merge any REG_CFA_ADJUST_CFA note from SRC into DST.
372 AFTER is true iff DST follows SRC in the instruction stream. */
375 maybe_merge_cfa_adjust (rtx_insn
*dst
, rtx_insn
*src
, bool after
)
377 rtx snote
= NULL
, dnote
= NULL
;
381 if (RTX_FRAME_RELATED_P (src
))
382 snote
= find_reg_note (src
, REG_CFA_ADJUST_CFA
, NULL_RTX
);
385 sexp
= XEXP (snote
, 0);
387 if (RTX_FRAME_RELATED_P (dst
))
388 dnote
= find_reg_note (dst
, REG_CFA_ADJUST_CFA
, NULL_RTX
);
391 add_reg_note (dst
, REG_CFA_ADJUST_CFA
, sexp
);
394 dexp
= XEXP (dnote
, 0);
396 gcc_assert (GET_CODE (sexp
) == SET
);
397 gcc_assert (GET_CODE (dexp
) == SET
);
400 exp1
= dexp
, exp2
= sexp
;
402 exp1
= sexp
, exp2
= dexp
;
404 SET_SRC (exp1
) = simplify_replace_rtx (SET_SRC (exp1
), SET_DEST (exp2
),
406 XEXP (dnote
, 0) = exp1
;
409 /* Return the next (or previous) active insn within BB. */
412 prev_active_insn_bb (basic_block bb
, rtx_insn
*insn
)
414 for (insn
= PREV_INSN (insn
);
415 insn
!= PREV_INSN (BB_HEAD (bb
));
416 insn
= PREV_INSN (insn
))
417 if (active_insn_p (insn
))
423 next_active_insn_bb (basic_block bb
, rtx_insn
*insn
)
425 for (insn
= NEXT_INSN (insn
);
426 insn
!= NEXT_INSN (BB_END (bb
));
427 insn
= NEXT_INSN (insn
))
428 if (active_insn_p (insn
))
433 /* If INSN has a REG_ARGS_SIZE note, if possible move it to PREV. Otherwise
434 search for a nearby candidate within BB where we can stick the note. */
437 force_move_args_size_note (basic_block bb
, rtx_insn
*prev
, rtx_insn
*insn
)
440 rtx_insn
*test
, *next_candidate
, *prev_candidate
;
442 /* If PREV exists, tail-call to the logic in the other function. */
445 maybe_move_args_size_note (prev
, insn
, false);
449 /* First, make sure there's anything that needs doing. */
450 note
= find_reg_note (insn
, REG_ARGS_SIZE
, NULL_RTX
);
454 /* We need to find a spot between the previous and next exception points
455 where we can place the note and "properly" deallocate the arguments. */
456 next_candidate
= prev_candidate
= NULL
;
458 /* It is often the case that we have insns in the order:
460 add sp (previous deallocation)
461 sub sp (align for next arglist)
463 and the add/sub cancel. Therefore we begin by searching forward. */
466 while ((test
= next_active_insn_bb (bb
, test
)) != NULL
)
468 /* Found an existing note: nothing to do. */
469 if (find_reg_note (test
, REG_ARGS_SIZE
, NULL_RTX
))
471 /* Found something that affects unwinding. Stop searching. */
472 if (CALL_P (test
) || !insn_nothrow_p (test
))
474 if (next_candidate
== NULL
)
475 next_candidate
= test
;
479 while ((test
= prev_active_insn_bb (bb
, test
)) != NULL
)
482 /* Found a place that seems logical to adjust the stack. */
483 tnote
= find_reg_note (test
, REG_ARGS_SIZE
, NULL_RTX
);
486 XEXP (tnote
, 0) = XEXP (note
, 0);
489 if (prev_candidate
== NULL
)
490 prev_candidate
= test
;
491 /* Found something that affects unwinding. Stop searching. */
492 if (CALL_P (test
) || !insn_nothrow_p (test
))
497 test
= prev_candidate
;
498 else if (next_candidate
)
499 test
= next_candidate
;
502 /* ??? We *must* have a place, lest we ICE on the lost adjustment.
503 Options are: dummy clobber insn, nop, or prevent the removal of
505 /* TODO: Find another way to indicate to the dwarf2 code that we
506 have not in fact lost an adjustment. */
507 test
= emit_insn_before (gen_rtx_CLOBBER (VOIDmode
, const0_rtx
), insn
);
509 add_reg_note (test
, REG_ARGS_SIZE
, XEXP (note
, 0));
512 /* Subroutine of combine_stack_adjustments, called for each basic block. */
515 combine_stack_adjustments_for_block (basic_block bb
)
517 HOST_WIDE_INT last_sp_adjust
= 0;
518 rtx_insn
*last_sp_set
= NULL
;
519 rtx_insn
*last2_sp_set
= NULL
;
520 struct csa_reflist
*reflist
= NULL
;
521 rtx_insn
*insn
, *next
;
523 bool end_of_block
= false;
525 for (insn
= BB_HEAD (bb
); !end_of_block
; insn
= next
)
527 end_of_block
= insn
== BB_END (bb
);
528 next
= NEXT_INSN (insn
);
533 set
= single_set_for_csa (insn
);
536 rtx dest
= SET_DEST (set
);
537 rtx src
= SET_SRC (set
);
539 /* Find constant additions to the stack pointer. */
540 if (dest
== stack_pointer_rtx
541 && GET_CODE (src
) == PLUS
542 && XEXP (src
, 0) == stack_pointer_rtx
543 && CONST_INT_P (XEXP (src
, 1)))
545 HOST_WIDE_INT this_adjust
= INTVAL (XEXP (src
, 1));
547 /* If we've not seen an adjustment previously, record
548 it now and continue. */
552 last_sp_adjust
= this_adjust
;
556 /* If not all recorded refs can be adjusted, or the
557 adjustment is now too large for a constant addition,
558 we cannot merge the two stack adjustments.
560 Also we need to be careful to not move stack pointer
561 such that we create stack accesses outside the allocated
562 area. We can combine an allocation into the first insn,
563 or a deallocation into the second insn. We can not
564 combine an allocation followed by a deallocation.
566 The only somewhat frequent occurrence of the later is when
567 a function allocates a stack frame but does not use it.
568 For this case, we would need to analyze rtl stream to be
569 sure that allocated area is really unused. This means not
570 only checking the memory references, but also all registers
571 or global memory references possibly containing a stack
574 Perhaps the best way to address this problem is to teach
575 gcc not to allocate stack for objects never used. */
577 /* Combine an allocation into the first instruction. */
578 if (STACK_GROWS_DOWNWARD
? this_adjust
<= 0 : this_adjust
>= 0)
580 if (no_unhandled_cfa (insn
)
581 && try_apply_stack_adjustment (last_sp_set
, reflist
,
587 maybe_move_args_size_note (last_sp_set
, insn
, false);
588 maybe_merge_cfa_adjust (last_sp_set
, insn
, false);
590 last_sp_adjust
+= this_adjust
;
595 /* Otherwise we have a deallocation. Do not combine with
596 a previous allocation. Combine into the second insn. */
597 else if (STACK_GROWS_DOWNWARD
598 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
600 if (no_unhandled_cfa (last_sp_set
)
601 && try_apply_stack_adjustment (insn
, reflist
,
607 maybe_move_args_size_note (insn
, last_sp_set
, true);
608 maybe_merge_cfa_adjust (insn
, last_sp_set
, true);
609 delete_insn (last_sp_set
);
611 last_sp_adjust
+= this_adjust
;
612 free_csa_reflist (reflist
);
618 /* Combination failed. Restart processing from here. If
619 deallocation+allocation conspired to cancel, we can
620 delete the old deallocation insn. */
623 if (last_sp_adjust
== 0 && no_unhandled_cfa (last_sp_set
))
625 maybe_move_args_size_note (insn
, last_sp_set
, true);
626 maybe_merge_cfa_adjust (insn
, last_sp_set
, true);
627 delete_insn (last_sp_set
);
630 last2_sp_set
= last_sp_set
;
632 free_csa_reflist (reflist
);
635 last_sp_adjust
= this_adjust
;
639 /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
640 the previous adjustment and turn it into a simple store. This
641 is equivalent to anticipating the stack adjustment so this must
644 && ((STACK_GROWS_DOWNWARD
645 ? (GET_CODE (XEXP (dest
, 0)) == PRE_DEC
647 == (HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
)))
648 : (GET_CODE (XEXP (dest
, 0)) == PRE_INC
650 == -(HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
))))
651 || ((STACK_GROWS_DOWNWARD
652 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
653 && GET_CODE (XEXP (dest
, 0)) == PRE_MODIFY
654 && GET_CODE (XEXP (XEXP (dest
, 0), 1)) == PLUS
655 && XEXP (XEXP (XEXP (dest
, 0), 1), 0)
657 && GET_CODE (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
659 && INTVAL (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
661 && XEXP (XEXP (dest
, 0), 0) == stack_pointer_rtx
662 && !reg_mentioned_p (stack_pointer_rtx
, src
)
663 && memory_address_p (GET_MODE (dest
), stack_pointer_rtx
)
664 && try_apply_stack_adjustment (insn
, reflist
, 0,
668 maybe_move_args_size_note (last2_sp_set
, last_sp_set
, false);
670 maybe_move_args_size_note (insn
, last_sp_set
, true);
671 delete_insn (last_sp_set
);
672 free_csa_reflist (reflist
);
680 if (!CALL_P (insn
) && last_sp_set
681 && record_stack_refs (insn
, &reflist
))
684 /* Otherwise, we were not able to process the instruction.
685 Do not continue collecting data across such a one. */
688 || reg_mentioned_p (stack_pointer_rtx
, PATTERN (insn
))))
690 if (last_sp_set
&& last_sp_adjust
== 0)
692 force_move_args_size_note (bb
, last2_sp_set
, last_sp_set
);
693 delete_insn (last_sp_set
);
695 free_csa_reflist (reflist
);
703 if (last_sp_set
&& last_sp_adjust
== 0)
705 force_move_args_size_note (bb
, last2_sp_set
, last_sp_set
);
706 delete_insn (last_sp_set
);
710 free_csa_reflist (reflist
);
714 rest_of_handle_stack_adjustments (void)
716 df_note_add_problem ();
718 combine_stack_adjustments ();
724 const pass_data pass_data_stack_adjustments
=
728 OPTGROUP_NONE
, /* optinfo_flags */
729 TV_COMBINE_STACK_ADJUST
, /* tv_id */
730 0, /* properties_required */
731 0, /* properties_provided */
732 0, /* properties_destroyed */
733 0, /* todo_flags_start */
734 TODO_df_finish
, /* todo_flags_finish */
737 class pass_stack_adjustments
: public rtl_opt_pass
740 pass_stack_adjustments (gcc::context
*ctxt
)
741 : rtl_opt_pass (pass_data_stack_adjustments
, ctxt
)
744 /* opt_pass methods: */
745 virtual bool gate (function
*);
746 virtual unsigned int execute (function
*)
748 return rest_of_handle_stack_adjustments ();
751 }; // class pass_stack_adjustments
754 pass_stack_adjustments::gate (function
*)
756 /* This is kind of a heuristic. We need to run combine_stack_adjustments
757 even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS
758 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
759 push instructions will have popping returns. */
760 #ifndef PUSH_ROUNDING
761 if (ACCUMULATE_OUTGOING_ARGS
)
764 return flag_combine_stack_adjustments
;
770 make_pass_stack_adjustments (gcc::context
*ctxt
)
772 return new pass_stack_adjustments (ctxt
);