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"
60 #include "dominance.h"
63 #include "basic-block.h"
67 #include "tree-pass.h"
71 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
72 #ifdef STACK_GROWS_DOWNWARD
73 #undef STACK_GROWS_DOWNWARD
74 #define STACK_GROWS_DOWNWARD 1
76 #define STACK_GROWS_DOWNWARD 0
79 /* This structure records two kinds of stack references between stack
80 adjusting instructions: stack references in memory addresses for
81 regular insns and all stack references for debug insns. */
85 HOST_WIDE_INT sp_offset
;
88 struct csa_reflist
*next
;
91 static int stack_memref_p (rtx
);
92 static rtx
single_set_for_csa (rtx_insn
*);
93 static void free_csa_reflist (struct csa_reflist
*);
94 static struct csa_reflist
*record_one_stack_ref (rtx_insn
*, rtx
*,
95 struct csa_reflist
*);
96 static int try_apply_stack_adjustment (rtx_insn
*, struct csa_reflist
*,
97 HOST_WIDE_INT
, HOST_WIDE_INT
);
98 static void combine_stack_adjustments_for_block (basic_block
);
101 /* Main entry point for stack adjustment combination. */
104 combine_stack_adjustments (void)
108 FOR_EACH_BB_FN (bb
, cfun
)
109 combine_stack_adjustments_for_block (bb
);
112 /* Recognize a MEM of the form (sp) or (plus sp const). */
115 stack_memref_p (rtx x
)
121 if (x
== stack_pointer_rtx
)
123 if (GET_CODE (x
) == PLUS
124 && XEXP (x
, 0) == stack_pointer_rtx
125 && CONST_INT_P (XEXP (x
, 1)))
131 /* Recognize either normal single_set or the hack in i386.md for
132 tying fp and sp adjustments. */
135 single_set_for_csa (rtx_insn
*insn
)
138 rtx tmp
= single_set (insn
);
142 if (!NONJUMP_INSN_P (insn
)
143 || GET_CODE (PATTERN (insn
)) != PARALLEL
)
146 tmp
= PATTERN (insn
);
147 if (GET_CODE (XVECEXP (tmp
, 0, 0)) != SET
)
150 for (i
= 1; i
< XVECLEN (tmp
, 0); ++i
)
152 rtx this_rtx
= XVECEXP (tmp
, 0, i
);
154 /* The special case is allowing a no-op set. */
155 if (GET_CODE (this_rtx
) == SET
156 && SET_SRC (this_rtx
) == SET_DEST (this_rtx
))
158 else if (GET_CODE (this_rtx
) != CLOBBER
159 && GET_CODE (this_rtx
) != USE
)
163 return XVECEXP (tmp
, 0, 0);
166 /* Free the list of csa_reflist nodes. */
169 free_csa_reflist (struct csa_reflist
*reflist
)
171 struct csa_reflist
*next
;
172 for (; reflist
; reflist
= next
)
174 next
= reflist
->next
;
179 /* Create a new csa_reflist node from the given stack reference.
180 It is already known that the reference is either a MEM satisfying the
181 predicate stack_memref_p or a REG representing the stack pointer. */
183 static struct csa_reflist
*
184 record_one_stack_ref (rtx_insn
*insn
, rtx
*ref
, struct csa_reflist
*next_reflist
)
186 struct csa_reflist
*ml
;
188 ml
= XNEW (struct csa_reflist
);
190 if (REG_P (*ref
) || XEXP (*ref
, 0) == stack_pointer_rtx
)
193 ml
->sp_offset
= INTVAL (XEXP (XEXP (*ref
, 0), 1));
197 ml
->next
= next_reflist
;
202 /* We only know how to adjust the CFA; no other frame-related changes
203 may appear in any insn to be deleted. */
206 no_unhandled_cfa (rtx_insn
*insn
)
208 if (!RTX_FRAME_RELATED_P (insn
))
211 /* No CFA notes at all is a legacy interpretation like
212 FRAME_RELATED_EXPR, and is context sensitive within
213 the prologue state machine. We can't handle that here. */
214 bool has_cfa_adjust
= false;
216 for (rtx link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
217 switch (REG_NOTE_KIND (link
))
221 case REG_CFA_ADJUST_CFA
:
222 has_cfa_adjust
= true;
225 case REG_FRAME_RELATED_EXPR
:
226 case REG_CFA_DEF_CFA
:
228 case REG_CFA_REGISTER
:
229 case REG_CFA_EXPRESSION
:
230 case REG_CFA_RESTORE
:
231 case REG_CFA_SET_VDRAP
:
232 case REG_CFA_WINDOW_SAVE
:
233 case REG_CFA_FLUSH_QUEUE
:
237 return has_cfa_adjust
;
240 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
241 as each of the memories and stack references in REFLIST. Return true
245 try_apply_stack_adjustment (rtx_insn
*insn
, struct csa_reflist
*reflist
,
246 HOST_WIDE_INT new_adjust
, HOST_WIDE_INT delta
)
248 struct csa_reflist
*ml
;
251 set
= single_set_for_csa (insn
);
252 if (MEM_P (SET_DEST (set
)))
253 validate_change (insn
, &SET_DEST (set
),
254 replace_equiv_address (SET_DEST (set
), stack_pointer_rtx
),
257 validate_change (insn
, &XEXP (SET_SRC (set
), 1), GEN_INT (new_adjust
), 1);
259 for (ml
= reflist
; ml
; ml
= ml
->next
)
261 rtx new_addr
= plus_constant (Pmode
, stack_pointer_rtx
,
262 ml
->sp_offset
- delta
);
265 if (MEM_P (*ml
->ref
))
266 new_val
= replace_equiv_address_nv (*ml
->ref
, new_addr
);
267 else if (GET_MODE (*ml
->ref
) == GET_MODE (stack_pointer_rtx
))
270 new_val
= lowpart_subreg (GET_MODE (*ml
->ref
), new_addr
,
271 GET_MODE (new_addr
));
272 validate_change (ml
->insn
, ml
->ref
, new_val
, 1);
275 if (apply_change_group ())
277 /* Succeeded. Update our knowledge of the stack references. */
278 for (ml
= reflist
; ml
; ml
= ml
->next
)
279 ml
->sp_offset
-= delta
;
287 /* For non-debug insns, record all stack memory references in INSN
288 and return true if there were no other (unrecorded) references to the
289 stack pointer. For debug insns, record all stack references regardless
290 of context and unconditionally return true. */
293 record_stack_refs (rtx_insn
*insn
, struct csa_reflist
**reflist
)
295 subrtx_ptr_iterator::array_type array
;
296 FOR_EACH_SUBRTX_PTR (iter
, array
, &PATTERN (insn
), NONCONST
)
300 switch (GET_CODE (x
))
303 if (!reg_mentioned_p (stack_pointer_rtx
, x
))
304 iter
.skip_subrtxes ();
305 /* We are not able to handle correctly all possible memrefs
306 containing stack pointer, so this check is necessary. */
307 else if (stack_memref_p (x
))
309 *reflist
= record_one_stack_ref (insn
, loc
, *reflist
);
310 iter
.skip_subrtxes ();
312 /* Try harder for DEBUG_INSNs, handle e.g.
313 (mem (mem (sp + 16) + 4). */
314 else if (!DEBUG_INSN_P (insn
))
319 /* ??? We want be able to handle non-memory stack pointer
320 references later. For now just discard all insns referring to
321 stack pointer outside mem expressions. We would probably
322 want to teach validate_replace to simplify expressions first.
324 We can't just compare with STACK_POINTER_RTX because the
325 reference to the stack pointer might be in some other mode.
326 In particular, an explicit clobber in an asm statement will
327 result in a QImode clobber.
329 In DEBUG_INSNs, we want to replace all occurrences, otherwise
330 they will cause -fcompare-debug failures. */
331 if (REGNO (x
) == STACK_POINTER_REGNUM
)
333 if (!DEBUG_INSN_P (insn
))
335 *reflist
= record_one_stack_ref (insn
, loc
, *reflist
);
346 /* If INSN has a REG_ARGS_SIZE note, move it to LAST.
347 AFTER is true iff LAST follows INSN in the instruction stream. */
350 maybe_move_args_size_note (rtx_insn
*last
, rtx_insn
*insn
, bool after
)
354 note
= find_reg_note (insn
, REG_ARGS_SIZE
, NULL_RTX
);
358 last_note
= find_reg_note (last
, REG_ARGS_SIZE
, NULL_RTX
);
361 /* The ARGS_SIZE notes are *not* cumulative. They represent an
362 absolute value, and the "most recent" note wins. */
364 XEXP (last_note
, 0) = XEXP (note
, 0);
367 add_reg_note (last
, REG_ARGS_SIZE
, XEXP (note
, 0));
370 /* Merge any REG_CFA_ADJUST_CFA note from SRC into DST.
371 AFTER is true iff DST follows SRC in the instruction stream. */
374 maybe_merge_cfa_adjust (rtx_insn
*dst
, rtx_insn
*src
, bool after
)
376 rtx snote
= NULL
, dnote
= NULL
;
380 if (RTX_FRAME_RELATED_P (src
))
381 snote
= find_reg_note (src
, REG_CFA_ADJUST_CFA
, NULL_RTX
);
384 sexp
= XEXP (snote
, 0);
386 if (RTX_FRAME_RELATED_P (dst
))
387 dnote
= find_reg_note (dst
, REG_CFA_ADJUST_CFA
, NULL_RTX
);
390 add_reg_note (dst
, REG_CFA_ADJUST_CFA
, sexp
);
393 dexp
= XEXP (dnote
, 0);
395 gcc_assert (GET_CODE (sexp
) == SET
);
396 gcc_assert (GET_CODE (dexp
) == SET
);
399 exp1
= dexp
, exp2
= sexp
;
401 exp1
= sexp
, exp2
= dexp
;
403 SET_SRC (exp1
) = simplify_replace_rtx (SET_SRC (exp1
), SET_DEST (exp2
),
405 XEXP (dnote
, 0) = exp1
;
408 /* Return the next (or previous) active insn within BB. */
411 prev_active_insn_bb (basic_block bb
, rtx_insn
*insn
)
413 for (insn
= PREV_INSN (insn
);
414 insn
!= PREV_INSN (BB_HEAD (bb
));
415 insn
= PREV_INSN (insn
))
416 if (active_insn_p (insn
))
422 next_active_insn_bb (basic_block bb
, rtx_insn
*insn
)
424 for (insn
= NEXT_INSN (insn
);
425 insn
!= NEXT_INSN (BB_END (bb
));
426 insn
= NEXT_INSN (insn
))
427 if (active_insn_p (insn
))
432 /* If INSN has a REG_ARGS_SIZE note, if possible move it to PREV. Otherwise
433 search for a nearby candidate within BB where we can stick the note. */
436 force_move_args_size_note (basic_block bb
, rtx_insn
*prev
, rtx_insn
*insn
)
439 rtx_insn
*test
, *next_candidate
, *prev_candidate
;
441 /* If PREV exists, tail-call to the logic in the other function. */
444 maybe_move_args_size_note (prev
, insn
, false);
448 /* First, make sure there's anything that needs doing. */
449 note
= find_reg_note (insn
, REG_ARGS_SIZE
, NULL_RTX
);
453 /* We need to find a spot between the previous and next exception points
454 where we can place the note and "properly" deallocate the arguments. */
455 next_candidate
= prev_candidate
= NULL
;
457 /* It is often the case that we have insns in the order:
459 add sp (previous deallocation)
460 sub sp (align for next arglist)
462 and the add/sub cancel. Therefore we begin by searching forward. */
465 while ((test
= next_active_insn_bb (bb
, test
)) != NULL
)
467 /* Found an existing note: nothing to do. */
468 if (find_reg_note (test
, REG_ARGS_SIZE
, NULL_RTX
))
470 /* Found something that affects unwinding. Stop searching. */
471 if (CALL_P (test
) || !insn_nothrow_p (test
))
473 if (next_candidate
== NULL
)
474 next_candidate
= test
;
478 while ((test
= prev_active_insn_bb (bb
, test
)) != NULL
)
481 /* Found a place that seems logical to adjust the stack. */
482 tnote
= find_reg_note (test
, REG_ARGS_SIZE
, NULL_RTX
);
485 XEXP (tnote
, 0) = XEXP (note
, 0);
488 if (prev_candidate
== NULL
)
489 prev_candidate
= test
;
490 /* Found something that affects unwinding. Stop searching. */
491 if (CALL_P (test
) || !insn_nothrow_p (test
))
496 test
= prev_candidate
;
497 else if (next_candidate
)
498 test
= next_candidate
;
501 /* ??? We *must* have a place, lest we ICE on the lost adjustment.
502 Options are: dummy clobber insn, nop, or prevent the removal of
504 /* TODO: Find another way to indicate to the dwarf2 code that we
505 have not in fact lost an adjustment. */
506 test
= emit_insn_before (gen_rtx_CLOBBER (VOIDmode
, const0_rtx
), insn
);
508 add_reg_note (test
, REG_ARGS_SIZE
, XEXP (note
, 0));
511 /* Subroutine of combine_stack_adjustments, called for each basic block. */
514 combine_stack_adjustments_for_block (basic_block bb
)
516 HOST_WIDE_INT last_sp_adjust
= 0;
517 rtx_insn
*last_sp_set
= NULL
;
518 rtx_insn
*last2_sp_set
= NULL
;
519 struct csa_reflist
*reflist
= NULL
;
520 rtx_insn
*insn
, *next
;
522 bool end_of_block
= false;
524 for (insn
= BB_HEAD (bb
); !end_of_block
; insn
= next
)
526 end_of_block
= insn
== BB_END (bb
);
527 next
= NEXT_INSN (insn
);
532 set
= single_set_for_csa (insn
);
535 rtx dest
= SET_DEST (set
);
536 rtx src
= SET_SRC (set
);
538 /* Find constant additions to the stack pointer. */
539 if (dest
== stack_pointer_rtx
540 && GET_CODE (src
) == PLUS
541 && XEXP (src
, 0) == stack_pointer_rtx
542 && CONST_INT_P (XEXP (src
, 1)))
544 HOST_WIDE_INT this_adjust
= INTVAL (XEXP (src
, 1));
546 /* If we've not seen an adjustment previously, record
547 it now and continue. */
551 last_sp_adjust
= this_adjust
;
555 /* If not all recorded refs can be adjusted, or the
556 adjustment is now too large for a constant addition,
557 we cannot merge the two stack adjustments.
559 Also we need to be careful to not move stack pointer
560 such that we create stack accesses outside the allocated
561 area. We can combine an allocation into the first insn,
562 or a deallocation into the second insn. We can not
563 combine an allocation followed by a deallocation.
565 The only somewhat frequent occurrence of the later is when
566 a function allocates a stack frame but does not use it.
567 For this case, we would need to analyze rtl stream to be
568 sure that allocated area is really unused. This means not
569 only checking the memory references, but also all registers
570 or global memory references possibly containing a stack
573 Perhaps the best way to address this problem is to teach
574 gcc not to allocate stack for objects never used. */
576 /* Combine an allocation into the first instruction. */
577 if (STACK_GROWS_DOWNWARD
? this_adjust
<= 0 : this_adjust
>= 0)
579 if (no_unhandled_cfa (insn
)
580 && try_apply_stack_adjustment (last_sp_set
, reflist
,
586 maybe_move_args_size_note (last_sp_set
, insn
, false);
587 maybe_merge_cfa_adjust (last_sp_set
, insn
, false);
589 last_sp_adjust
+= this_adjust
;
594 /* Otherwise we have a deallocation. Do not combine with
595 a previous allocation. Combine into the second insn. */
596 else if (STACK_GROWS_DOWNWARD
597 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
599 if (no_unhandled_cfa (last_sp_set
)
600 && try_apply_stack_adjustment (insn
, reflist
,
606 maybe_move_args_size_note (insn
, last_sp_set
, true);
607 maybe_merge_cfa_adjust (insn
, last_sp_set
, true);
608 delete_insn (last_sp_set
);
610 last_sp_adjust
+= this_adjust
;
611 free_csa_reflist (reflist
);
617 /* Combination failed. Restart processing from here. If
618 deallocation+allocation conspired to cancel, we can
619 delete the old deallocation insn. */
622 if (last_sp_adjust
== 0 && no_unhandled_cfa (last_sp_set
))
624 maybe_move_args_size_note (insn
, last_sp_set
, true);
625 maybe_merge_cfa_adjust (insn
, last_sp_set
, true);
626 delete_insn (last_sp_set
);
629 last2_sp_set
= last_sp_set
;
631 free_csa_reflist (reflist
);
634 last_sp_adjust
= this_adjust
;
638 /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
639 the previous adjustment and turn it into a simple store. This
640 is equivalent to anticipating the stack adjustment so this must
643 && ((STACK_GROWS_DOWNWARD
644 ? (GET_CODE (XEXP (dest
, 0)) == PRE_DEC
646 == (HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
)))
647 : (GET_CODE (XEXP (dest
, 0)) == PRE_INC
649 == -(HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
))))
650 || ((STACK_GROWS_DOWNWARD
651 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
652 && GET_CODE (XEXP (dest
, 0)) == PRE_MODIFY
653 && GET_CODE (XEXP (XEXP (dest
, 0), 1)) == PLUS
654 && XEXP (XEXP (XEXP (dest
, 0), 1), 0)
656 && GET_CODE (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
658 && INTVAL (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
660 && XEXP (XEXP (dest
, 0), 0) == stack_pointer_rtx
661 && !reg_mentioned_p (stack_pointer_rtx
, src
)
662 && memory_address_p (GET_MODE (dest
), stack_pointer_rtx
)
663 && try_apply_stack_adjustment (insn
, reflist
, 0,
667 maybe_move_args_size_note (last2_sp_set
, last_sp_set
, false);
669 maybe_move_args_size_note (insn
, last_sp_set
, true);
670 delete_insn (last_sp_set
);
671 free_csa_reflist (reflist
);
679 if (!CALL_P (insn
) && last_sp_set
680 && record_stack_refs (insn
, &reflist
))
683 /* Otherwise, we were not able to process the instruction.
684 Do not continue collecting data across such a one. */
687 || reg_mentioned_p (stack_pointer_rtx
, PATTERN (insn
))))
689 if (last_sp_set
&& last_sp_adjust
== 0)
691 force_move_args_size_note (bb
, last2_sp_set
, last_sp_set
);
692 delete_insn (last_sp_set
);
694 free_csa_reflist (reflist
);
702 if (last_sp_set
&& last_sp_adjust
== 0)
704 force_move_args_size_note (bb
, last2_sp_set
, last_sp_set
);
705 delete_insn (last_sp_set
);
709 free_csa_reflist (reflist
);
713 rest_of_handle_stack_adjustments (void)
715 df_note_add_problem ();
717 combine_stack_adjustments ();
723 const pass_data pass_data_stack_adjustments
=
727 OPTGROUP_NONE
, /* optinfo_flags */
728 TV_COMBINE_STACK_ADJUST
, /* tv_id */
729 0, /* properties_required */
730 0, /* properties_provided */
731 0, /* properties_destroyed */
732 0, /* todo_flags_start */
733 TODO_df_finish
, /* todo_flags_finish */
736 class pass_stack_adjustments
: public rtl_opt_pass
739 pass_stack_adjustments (gcc::context
*ctxt
)
740 : rtl_opt_pass (pass_data_stack_adjustments
, ctxt
)
743 /* opt_pass methods: */
744 virtual bool gate (function
*);
745 virtual unsigned int execute (function
*)
747 return rest_of_handle_stack_adjustments ();
750 }; // class pass_stack_adjustments
753 pass_stack_adjustments::gate (function
*)
755 /* This is kind of a heuristic. We need to run combine_stack_adjustments
756 even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS
757 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
758 push instructions will have popping returns. */
759 #ifndef PUSH_ROUNDING
760 if (ACCUMULATE_OUTGOING_ARGS
)
763 return flag_combine_stack_adjustments
;
769 make_pass_stack_adjustments (gcc::context
*ctxt
)
771 return new pass_stack_adjustments (ctxt
);