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"
59 #include "statistics.h"
60 #include "double-int.h"
62 #include "fixed-value.h"
76 #include "dominance.h"
79 #include "basic-block.h"
83 #include "tree-pass.h"
87 /* This structure records two kinds of stack references between stack
88 adjusting instructions: stack references in memory addresses for
89 regular insns and all stack references for debug insns. */
93 HOST_WIDE_INT sp_offset
;
96 struct csa_reflist
*next
;
99 static int stack_memref_p (rtx
);
100 static rtx
single_set_for_csa (rtx_insn
*);
101 static void free_csa_reflist (struct csa_reflist
*);
102 static struct csa_reflist
*record_one_stack_ref (rtx_insn
*, rtx
*,
103 struct csa_reflist
*);
104 static int try_apply_stack_adjustment (rtx_insn
*, struct csa_reflist
*,
105 HOST_WIDE_INT
, HOST_WIDE_INT
);
106 static void combine_stack_adjustments_for_block (basic_block
);
109 /* Main entry point for stack adjustment combination. */
112 combine_stack_adjustments (void)
116 FOR_EACH_BB_FN (bb
, cfun
)
117 combine_stack_adjustments_for_block (bb
);
120 /* Recognize a MEM of the form (sp) or (plus sp const). */
123 stack_memref_p (rtx x
)
129 if (x
== stack_pointer_rtx
)
131 if (GET_CODE (x
) == PLUS
132 && XEXP (x
, 0) == stack_pointer_rtx
133 && CONST_INT_P (XEXP (x
, 1)))
139 /* Recognize either normal single_set or the hack in i386.md for
140 tying fp and sp adjustments. */
143 single_set_for_csa (rtx_insn
*insn
)
146 rtx tmp
= single_set (insn
);
150 if (!NONJUMP_INSN_P (insn
)
151 || GET_CODE (PATTERN (insn
)) != PARALLEL
)
154 tmp
= PATTERN (insn
);
155 if (GET_CODE (XVECEXP (tmp
, 0, 0)) != SET
)
158 for (i
= 1; i
< XVECLEN (tmp
, 0); ++i
)
160 rtx this_rtx
= XVECEXP (tmp
, 0, i
);
162 /* The special case is allowing a no-op set. */
163 if (GET_CODE (this_rtx
) == SET
164 && SET_SRC (this_rtx
) == SET_DEST (this_rtx
))
166 else if (GET_CODE (this_rtx
) != CLOBBER
167 && GET_CODE (this_rtx
) != USE
)
171 return XVECEXP (tmp
, 0, 0);
174 /* Free the list of csa_reflist nodes. */
177 free_csa_reflist (struct csa_reflist
*reflist
)
179 struct csa_reflist
*next
;
180 for (; reflist
; reflist
= next
)
182 next
= reflist
->next
;
187 /* Create a new csa_reflist node from the given stack reference.
188 It is already known that the reference is either a MEM satisfying the
189 predicate stack_memref_p or a REG representing the stack pointer. */
191 static struct csa_reflist
*
192 record_one_stack_ref (rtx_insn
*insn
, rtx
*ref
, struct csa_reflist
*next_reflist
)
194 struct csa_reflist
*ml
;
196 ml
= XNEW (struct csa_reflist
);
198 if (REG_P (*ref
) || XEXP (*ref
, 0) == stack_pointer_rtx
)
201 ml
->sp_offset
= INTVAL (XEXP (XEXP (*ref
, 0), 1));
205 ml
->next
= next_reflist
;
210 /* We only know how to adjust the CFA; no other frame-related changes
211 may appear in any insn to be deleted. */
214 no_unhandled_cfa (rtx_insn
*insn
)
216 if (!RTX_FRAME_RELATED_P (insn
))
219 /* No CFA notes at all is a legacy interpretation like
220 FRAME_RELATED_EXPR, and is context sensitive within
221 the prologue state machine. We can't handle that here. */
222 bool has_cfa_adjust
= false;
224 for (rtx link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
225 switch (REG_NOTE_KIND (link
))
229 case REG_CFA_ADJUST_CFA
:
230 has_cfa_adjust
= true;
233 case REG_FRAME_RELATED_EXPR
:
234 case REG_CFA_DEF_CFA
:
236 case REG_CFA_REGISTER
:
237 case REG_CFA_EXPRESSION
:
238 case REG_CFA_RESTORE
:
239 case REG_CFA_SET_VDRAP
:
240 case REG_CFA_WINDOW_SAVE
:
241 case REG_CFA_FLUSH_QUEUE
:
245 return has_cfa_adjust
;
248 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
249 as each of the memories and stack references in REFLIST. Return true
253 try_apply_stack_adjustment (rtx_insn
*insn
, struct csa_reflist
*reflist
,
254 HOST_WIDE_INT new_adjust
, HOST_WIDE_INT delta
)
256 struct csa_reflist
*ml
;
259 set
= single_set_for_csa (insn
);
260 if (MEM_P (SET_DEST (set
)))
261 validate_change (insn
, &SET_DEST (set
),
262 replace_equiv_address (SET_DEST (set
), stack_pointer_rtx
),
265 validate_change (insn
, &XEXP (SET_SRC (set
), 1), GEN_INT (new_adjust
), 1);
267 for (ml
= reflist
; ml
; ml
= ml
->next
)
269 rtx new_addr
= plus_constant (Pmode
, stack_pointer_rtx
,
270 ml
->sp_offset
- delta
);
273 if (MEM_P (*ml
->ref
))
274 new_val
= replace_equiv_address_nv (*ml
->ref
, new_addr
);
275 else if (GET_MODE (*ml
->ref
) == GET_MODE (stack_pointer_rtx
))
278 new_val
= lowpart_subreg (GET_MODE (*ml
->ref
), new_addr
,
279 GET_MODE (new_addr
));
280 validate_change (ml
->insn
, ml
->ref
, new_val
, 1);
283 if (apply_change_group ())
285 /* Succeeded. Update our knowledge of the stack references. */
286 for (ml
= reflist
; ml
; ml
= ml
->next
)
287 ml
->sp_offset
-= delta
;
295 /* For non-debug insns, record all stack memory references in INSN
296 and return true if there were no other (unrecorded) references to the
297 stack pointer. For debug insns, record all stack references regardless
298 of context and unconditionally return true. */
301 record_stack_refs (rtx_insn
*insn
, struct csa_reflist
**reflist
)
303 subrtx_ptr_iterator::array_type array
;
304 FOR_EACH_SUBRTX_PTR (iter
, array
, &PATTERN (insn
), NONCONST
)
308 switch (GET_CODE (x
))
311 if (!reg_mentioned_p (stack_pointer_rtx
, x
))
312 iter
.skip_subrtxes ();
313 /* We are not able to handle correctly all possible memrefs
314 containing stack pointer, so this check is necessary. */
315 else if (stack_memref_p (x
))
317 *reflist
= record_one_stack_ref (insn
, loc
, *reflist
);
318 iter
.skip_subrtxes ();
320 /* Try harder for DEBUG_INSNs, handle e.g.
321 (mem (mem (sp + 16) + 4). */
322 else if (!DEBUG_INSN_P (insn
))
327 /* ??? We want be able to handle non-memory stack pointer
328 references later. For now just discard all insns referring to
329 stack pointer outside mem expressions. We would probably
330 want to teach validate_replace to simplify expressions first.
332 We can't just compare with STACK_POINTER_RTX because the
333 reference to the stack pointer might be in some other mode.
334 In particular, an explicit clobber in an asm statement will
335 result in a QImode clobber.
337 In DEBUG_INSNs, we want to replace all occurrences, otherwise
338 they will cause -fcompare-debug failures. */
339 if (REGNO (x
) == STACK_POINTER_REGNUM
)
341 if (!DEBUG_INSN_P (insn
))
343 *reflist
= record_one_stack_ref (insn
, loc
, *reflist
);
354 /* If INSN has a REG_ARGS_SIZE note, move it to LAST.
355 AFTER is true iff LAST follows INSN in the instruction stream. */
358 maybe_move_args_size_note (rtx_insn
*last
, rtx_insn
*insn
, bool after
)
362 note
= find_reg_note (insn
, REG_ARGS_SIZE
, NULL_RTX
);
366 last_note
= find_reg_note (last
, REG_ARGS_SIZE
, NULL_RTX
);
369 /* The ARGS_SIZE notes are *not* cumulative. They represent an
370 absolute value, and the "most recent" note wins. */
372 XEXP (last_note
, 0) = XEXP (note
, 0);
375 add_reg_note (last
, REG_ARGS_SIZE
, XEXP (note
, 0));
378 /* Merge any REG_CFA_ADJUST_CFA note from SRC into DST.
379 AFTER is true iff DST follows SRC in the instruction stream. */
382 maybe_merge_cfa_adjust (rtx_insn
*dst
, rtx_insn
*src
, bool after
)
384 rtx snote
= NULL
, dnote
= NULL
;
388 if (RTX_FRAME_RELATED_P (src
))
389 snote
= find_reg_note (src
, REG_CFA_ADJUST_CFA
, NULL_RTX
);
392 sexp
= XEXP (snote
, 0);
394 if (RTX_FRAME_RELATED_P (dst
))
395 dnote
= find_reg_note (dst
, REG_CFA_ADJUST_CFA
, NULL_RTX
);
398 add_reg_note (dst
, REG_CFA_ADJUST_CFA
, sexp
);
401 dexp
= XEXP (dnote
, 0);
403 gcc_assert (GET_CODE (sexp
) == SET
);
404 gcc_assert (GET_CODE (dexp
) == SET
);
407 exp1
= dexp
, exp2
= sexp
;
409 exp1
= sexp
, exp2
= dexp
;
411 SET_SRC (exp1
) = simplify_replace_rtx (SET_SRC (exp1
), SET_DEST (exp2
),
413 XEXP (dnote
, 0) = exp1
;
416 /* Return the next (or previous) active insn within BB. */
419 prev_active_insn_bb (basic_block bb
, rtx_insn
*insn
)
421 for (insn
= PREV_INSN (insn
);
422 insn
!= PREV_INSN (BB_HEAD (bb
));
423 insn
= PREV_INSN (insn
))
424 if (active_insn_p (insn
))
430 next_active_insn_bb (basic_block bb
, rtx_insn
*insn
)
432 for (insn
= NEXT_INSN (insn
);
433 insn
!= NEXT_INSN (BB_END (bb
));
434 insn
= NEXT_INSN (insn
))
435 if (active_insn_p (insn
))
440 /* If INSN has a REG_ARGS_SIZE note, if possible move it to PREV. Otherwise
441 search for a nearby candidate within BB where we can stick the note. */
444 force_move_args_size_note (basic_block bb
, rtx_insn
*prev
, rtx_insn
*insn
)
447 rtx_insn
*test
, *next_candidate
, *prev_candidate
;
449 /* If PREV exists, tail-call to the logic in the other function. */
452 maybe_move_args_size_note (prev
, insn
, false);
456 /* First, make sure there's anything that needs doing. */
457 note
= find_reg_note (insn
, REG_ARGS_SIZE
, NULL_RTX
);
461 /* We need to find a spot between the previous and next exception points
462 where we can place the note and "properly" deallocate the arguments. */
463 next_candidate
= prev_candidate
= NULL
;
465 /* It is often the case that we have insns in the order:
467 add sp (previous deallocation)
468 sub sp (align for next arglist)
470 and the add/sub cancel. Therefore we begin by searching forward. */
473 while ((test
= next_active_insn_bb (bb
, test
)) != NULL
)
475 /* Found an existing note: nothing to do. */
476 if (find_reg_note (test
, REG_ARGS_SIZE
, NULL_RTX
))
478 /* Found something that affects unwinding. Stop searching. */
479 if (CALL_P (test
) || !insn_nothrow_p (test
))
481 if (next_candidate
== NULL
)
482 next_candidate
= test
;
486 while ((test
= prev_active_insn_bb (bb
, test
)) != NULL
)
489 /* Found a place that seems logical to adjust the stack. */
490 tnote
= find_reg_note (test
, REG_ARGS_SIZE
, NULL_RTX
);
493 XEXP (tnote
, 0) = XEXP (note
, 0);
496 if (prev_candidate
== NULL
)
497 prev_candidate
= test
;
498 /* Found something that affects unwinding. Stop searching. */
499 if (CALL_P (test
) || !insn_nothrow_p (test
))
504 test
= prev_candidate
;
505 else if (next_candidate
)
506 test
= next_candidate
;
509 /* ??? We *must* have a place, lest we ICE on the lost adjustment.
510 Options are: dummy clobber insn, nop, or prevent the removal of
512 /* TODO: Find another way to indicate to the dwarf2 code that we
513 have not in fact lost an adjustment. */
514 test
= emit_insn_before (gen_rtx_CLOBBER (VOIDmode
, const0_rtx
), insn
);
516 add_reg_note (test
, REG_ARGS_SIZE
, XEXP (note
, 0));
519 /* Subroutine of combine_stack_adjustments, called for each basic block. */
522 combine_stack_adjustments_for_block (basic_block bb
)
524 HOST_WIDE_INT last_sp_adjust
= 0;
525 rtx_insn
*last_sp_set
= NULL
;
526 rtx_insn
*last2_sp_set
= NULL
;
527 struct csa_reflist
*reflist
= NULL
;
528 rtx_insn
*insn
, *next
;
530 bool end_of_block
= false;
532 for (insn
= BB_HEAD (bb
); !end_of_block
; insn
= next
)
534 end_of_block
= insn
== BB_END (bb
);
535 next
= NEXT_INSN (insn
);
540 set
= single_set_for_csa (insn
);
543 rtx dest
= SET_DEST (set
);
544 rtx src
= SET_SRC (set
);
546 /* Find constant additions to the stack pointer. */
547 if (dest
== stack_pointer_rtx
548 && GET_CODE (src
) == PLUS
549 && XEXP (src
, 0) == stack_pointer_rtx
550 && CONST_INT_P (XEXP (src
, 1)))
552 HOST_WIDE_INT this_adjust
= INTVAL (XEXP (src
, 1));
554 /* If we've not seen an adjustment previously, record
555 it now and continue. */
559 last_sp_adjust
= this_adjust
;
563 /* If not all recorded refs can be adjusted, or the
564 adjustment is now too large for a constant addition,
565 we cannot merge the two stack adjustments.
567 Also we need to be careful to not move stack pointer
568 such that we create stack accesses outside the allocated
569 area. We can combine an allocation into the first insn,
570 or a deallocation into the second insn. We can not
571 combine an allocation followed by a deallocation.
573 The only somewhat frequent occurrence of the later is when
574 a function allocates a stack frame but does not use it.
575 For this case, we would need to analyze rtl stream to be
576 sure that allocated area is really unused. This means not
577 only checking the memory references, but also all registers
578 or global memory references possibly containing a stack
581 Perhaps the best way to address this problem is to teach
582 gcc not to allocate stack for objects never used. */
584 /* Combine an allocation into the first instruction. */
585 if (STACK_GROWS_DOWNWARD
? this_adjust
<= 0 : this_adjust
>= 0)
587 if (no_unhandled_cfa (insn
)
588 && try_apply_stack_adjustment (last_sp_set
, reflist
,
594 maybe_move_args_size_note (last_sp_set
, insn
, false);
595 maybe_merge_cfa_adjust (last_sp_set
, insn
, false);
597 last_sp_adjust
+= this_adjust
;
602 /* Otherwise we have a deallocation. Do not combine with
603 a previous allocation. Combine into the second insn. */
604 else if (STACK_GROWS_DOWNWARD
605 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
607 if (no_unhandled_cfa (last_sp_set
)
608 && try_apply_stack_adjustment (insn
, reflist
,
614 maybe_move_args_size_note (insn
, last_sp_set
, true);
615 maybe_merge_cfa_adjust (insn
, last_sp_set
, true);
616 delete_insn (last_sp_set
);
618 last_sp_adjust
+= this_adjust
;
619 free_csa_reflist (reflist
);
625 /* Combination failed. Restart processing from here. If
626 deallocation+allocation conspired to cancel, we can
627 delete the old deallocation insn. */
630 if (last_sp_adjust
== 0 && no_unhandled_cfa (last_sp_set
))
632 maybe_move_args_size_note (insn
, last_sp_set
, true);
633 maybe_merge_cfa_adjust (insn
, last_sp_set
, true);
634 delete_insn (last_sp_set
);
637 last2_sp_set
= last_sp_set
;
639 free_csa_reflist (reflist
);
642 last_sp_adjust
= this_adjust
;
646 /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
647 the previous adjustment and turn it into a simple store. This
648 is equivalent to anticipating the stack adjustment so this must
651 && ((STACK_GROWS_DOWNWARD
652 ? (GET_CODE (XEXP (dest
, 0)) == PRE_DEC
654 == (HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
)))
655 : (GET_CODE (XEXP (dest
, 0)) == PRE_INC
657 == -(HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
))))
658 || ((STACK_GROWS_DOWNWARD
659 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
660 && GET_CODE (XEXP (dest
, 0)) == PRE_MODIFY
661 && GET_CODE (XEXP (XEXP (dest
, 0), 1)) == PLUS
662 && XEXP (XEXP (XEXP (dest
, 0), 1), 0)
664 && GET_CODE (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
666 && INTVAL (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
668 && XEXP (XEXP (dest
, 0), 0) == stack_pointer_rtx
669 && !reg_mentioned_p (stack_pointer_rtx
, src
)
670 && memory_address_p (GET_MODE (dest
), stack_pointer_rtx
)
671 && try_apply_stack_adjustment (insn
, reflist
, 0,
675 maybe_move_args_size_note (last2_sp_set
, last_sp_set
, false);
677 maybe_move_args_size_note (insn
, last_sp_set
, true);
678 delete_insn (last_sp_set
);
679 free_csa_reflist (reflist
);
687 if (!CALL_P (insn
) && last_sp_set
688 && record_stack_refs (insn
, &reflist
))
691 /* Otherwise, we were not able to process the instruction.
692 Do not continue collecting data across such a one. */
695 || reg_mentioned_p (stack_pointer_rtx
, PATTERN (insn
))))
697 if (last_sp_set
&& last_sp_adjust
== 0)
699 force_move_args_size_note (bb
, last2_sp_set
, last_sp_set
);
700 delete_insn (last_sp_set
);
702 free_csa_reflist (reflist
);
710 if (last_sp_set
&& last_sp_adjust
== 0)
712 force_move_args_size_note (bb
, last2_sp_set
, last_sp_set
);
713 delete_insn (last_sp_set
);
717 free_csa_reflist (reflist
);
721 rest_of_handle_stack_adjustments (void)
723 df_note_add_problem ();
725 combine_stack_adjustments ();
731 const pass_data pass_data_stack_adjustments
=
735 OPTGROUP_NONE
, /* optinfo_flags */
736 TV_COMBINE_STACK_ADJUST
, /* tv_id */
737 0, /* properties_required */
738 0, /* properties_provided */
739 0, /* properties_destroyed */
740 0, /* todo_flags_start */
741 TODO_df_finish
, /* todo_flags_finish */
744 class pass_stack_adjustments
: public rtl_opt_pass
747 pass_stack_adjustments (gcc::context
*ctxt
)
748 : rtl_opt_pass (pass_data_stack_adjustments
, ctxt
)
751 /* opt_pass methods: */
752 virtual bool gate (function
*);
753 virtual unsigned int execute (function
*)
755 return rest_of_handle_stack_adjustments ();
758 }; // class pass_stack_adjustments
761 pass_stack_adjustments::gate (function
*)
763 /* This is kind of a heuristic. We need to run combine_stack_adjustments
764 even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS
765 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
766 push instructions will have popping returns. */
767 #ifndef PUSH_ROUNDING
768 if (ACCUMULATE_OUTGOING_ARGS
)
771 return flag_combine_stack_adjustments
;
777 make_pass_stack_adjustments (gcc::context
*ctxt
)
779 return new pass_stack_adjustments (ctxt
);