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"
65 #include "dominance.h"
68 #include "basic-block.h"
72 #include "tree-pass.h"
76 /* This structure records two kinds of stack references between stack
77 adjusting instructions: stack references in memory addresses for
78 regular insns and all stack references for debug insns. */
82 HOST_WIDE_INT sp_offset
;
85 struct csa_reflist
*next
;
88 static int stack_memref_p (rtx
);
89 static rtx
single_set_for_csa (rtx_insn
*);
90 static void free_csa_reflist (struct csa_reflist
*);
91 static struct csa_reflist
*record_one_stack_ref (rtx_insn
*, rtx
*,
92 struct csa_reflist
*);
93 static int try_apply_stack_adjustment (rtx_insn
*, struct csa_reflist
*,
94 HOST_WIDE_INT
, HOST_WIDE_INT
);
95 static void combine_stack_adjustments_for_block (basic_block
);
98 /* Main entry point for stack adjustment combination. */
101 combine_stack_adjustments (void)
105 FOR_EACH_BB_FN (bb
, cfun
)
106 combine_stack_adjustments_for_block (bb
);
109 /* Recognize a MEM of the form (sp) or (plus sp const). */
112 stack_memref_p (rtx x
)
118 if (x
== stack_pointer_rtx
)
120 if (GET_CODE (x
) == PLUS
121 && XEXP (x
, 0) == stack_pointer_rtx
122 && CONST_INT_P (XEXP (x
, 1)))
128 /* Recognize either normal single_set or the hack in i386.md for
129 tying fp and sp adjustments. */
132 single_set_for_csa (rtx_insn
*insn
)
135 rtx tmp
= single_set (insn
);
139 if (!NONJUMP_INSN_P (insn
)
140 || GET_CODE (PATTERN (insn
)) != PARALLEL
)
143 tmp
= PATTERN (insn
);
144 if (GET_CODE (XVECEXP (tmp
, 0, 0)) != SET
)
147 for (i
= 1; i
< XVECLEN (tmp
, 0); ++i
)
149 rtx this_rtx
= XVECEXP (tmp
, 0, i
);
151 /* The special case is allowing a no-op set. */
152 if (GET_CODE (this_rtx
) == SET
153 && SET_SRC (this_rtx
) == SET_DEST (this_rtx
))
155 else if (GET_CODE (this_rtx
) != CLOBBER
156 && GET_CODE (this_rtx
) != USE
)
160 return XVECEXP (tmp
, 0, 0);
163 /* Free the list of csa_reflist nodes. */
166 free_csa_reflist (struct csa_reflist
*reflist
)
168 struct csa_reflist
*next
;
169 for (; reflist
; reflist
= next
)
171 next
= reflist
->next
;
176 /* Create a new csa_reflist node from the given stack reference.
177 It is already known that the reference is either a MEM satisfying the
178 predicate stack_memref_p or a REG representing the stack pointer. */
180 static struct csa_reflist
*
181 record_one_stack_ref (rtx_insn
*insn
, rtx
*ref
, struct csa_reflist
*next_reflist
)
183 struct csa_reflist
*ml
;
185 ml
= XNEW (struct csa_reflist
);
187 if (REG_P (*ref
) || XEXP (*ref
, 0) == stack_pointer_rtx
)
190 ml
->sp_offset
= INTVAL (XEXP (XEXP (*ref
, 0), 1));
194 ml
->next
= next_reflist
;
199 /* We only know how to adjust the CFA; no other frame-related changes
200 may appear in any insn to be deleted. */
203 no_unhandled_cfa (rtx_insn
*insn
)
205 if (!RTX_FRAME_RELATED_P (insn
))
208 /* No CFA notes at all is a legacy interpretation like
209 FRAME_RELATED_EXPR, and is context sensitive within
210 the prologue state machine. We can't handle that here. */
211 bool has_cfa_adjust
= false;
213 for (rtx link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
214 switch (REG_NOTE_KIND (link
))
218 case REG_CFA_ADJUST_CFA
:
219 has_cfa_adjust
= true;
222 case REG_FRAME_RELATED_EXPR
:
223 case REG_CFA_DEF_CFA
:
225 case REG_CFA_REGISTER
:
226 case REG_CFA_EXPRESSION
:
227 case REG_CFA_RESTORE
:
228 case REG_CFA_SET_VDRAP
:
229 case REG_CFA_WINDOW_SAVE
:
230 case REG_CFA_FLUSH_QUEUE
:
234 return has_cfa_adjust
;
237 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
238 as each of the memories and stack references in REFLIST. Return true
242 try_apply_stack_adjustment (rtx_insn
*insn
, struct csa_reflist
*reflist
,
243 HOST_WIDE_INT new_adjust
, HOST_WIDE_INT delta
)
245 struct csa_reflist
*ml
;
248 set
= single_set_for_csa (insn
);
249 if (MEM_P (SET_DEST (set
)))
250 validate_change (insn
, &SET_DEST (set
),
251 replace_equiv_address (SET_DEST (set
), stack_pointer_rtx
),
254 validate_change (insn
, &XEXP (SET_SRC (set
), 1), GEN_INT (new_adjust
), 1);
256 for (ml
= reflist
; ml
; ml
= ml
->next
)
258 rtx new_addr
= plus_constant (Pmode
, stack_pointer_rtx
,
259 ml
->sp_offset
- delta
);
262 if (MEM_P (*ml
->ref
))
263 new_val
= replace_equiv_address_nv (*ml
->ref
, new_addr
);
264 else if (GET_MODE (*ml
->ref
) == GET_MODE (stack_pointer_rtx
))
267 new_val
= lowpart_subreg (GET_MODE (*ml
->ref
), new_addr
,
268 GET_MODE (new_addr
));
269 validate_change (ml
->insn
, ml
->ref
, new_val
, 1);
272 if (apply_change_group ())
274 /* Succeeded. Update our knowledge of the stack references. */
275 for (ml
= reflist
; ml
; ml
= ml
->next
)
276 ml
->sp_offset
-= delta
;
284 /* For non-debug insns, record all stack memory references in INSN
285 and return true if there were no other (unrecorded) references to the
286 stack pointer. For debug insns, record all stack references regardless
287 of context and unconditionally return true. */
290 record_stack_refs (rtx_insn
*insn
, struct csa_reflist
**reflist
)
292 subrtx_ptr_iterator::array_type array
;
293 FOR_EACH_SUBRTX_PTR (iter
, array
, &PATTERN (insn
), NONCONST
)
297 switch (GET_CODE (x
))
300 if (!reg_mentioned_p (stack_pointer_rtx
, x
))
301 iter
.skip_subrtxes ();
302 /* We are not able to handle correctly all possible memrefs
303 containing stack pointer, so this check is necessary. */
304 else if (stack_memref_p (x
))
306 *reflist
= record_one_stack_ref (insn
, loc
, *reflist
);
307 iter
.skip_subrtxes ();
309 /* Try harder for DEBUG_INSNs, handle e.g.
310 (mem (mem (sp + 16) + 4). */
311 else if (!DEBUG_INSN_P (insn
))
316 /* ??? We want be able to handle non-memory stack pointer
317 references later. For now just discard all insns referring to
318 stack pointer outside mem expressions. We would probably
319 want to teach validate_replace to simplify expressions first.
321 We can't just compare with STACK_POINTER_RTX because the
322 reference to the stack pointer might be in some other mode.
323 In particular, an explicit clobber in an asm statement will
324 result in a QImode clobber.
326 In DEBUG_INSNs, we want to replace all occurrences, otherwise
327 they will cause -fcompare-debug failures. */
328 if (REGNO (x
) == STACK_POINTER_REGNUM
)
330 if (!DEBUG_INSN_P (insn
))
332 *reflist
= record_one_stack_ref (insn
, loc
, *reflist
);
343 /* If INSN has a REG_ARGS_SIZE note, move it to LAST.
344 AFTER is true iff LAST follows INSN in the instruction stream. */
347 maybe_move_args_size_note (rtx_insn
*last
, rtx_insn
*insn
, bool after
)
351 note
= find_reg_note (insn
, REG_ARGS_SIZE
, NULL_RTX
);
355 last_note
= find_reg_note (last
, REG_ARGS_SIZE
, NULL_RTX
);
358 /* The ARGS_SIZE notes are *not* cumulative. They represent an
359 absolute value, and the "most recent" note wins. */
361 XEXP (last_note
, 0) = XEXP (note
, 0);
364 add_reg_note (last
, REG_ARGS_SIZE
, XEXP (note
, 0));
367 /* Merge any REG_CFA_ADJUST_CFA note from SRC into DST.
368 AFTER is true iff DST follows SRC in the instruction stream. */
371 maybe_merge_cfa_adjust (rtx_insn
*dst
, rtx_insn
*src
, bool after
)
373 rtx snote
= NULL
, dnote
= NULL
;
377 if (RTX_FRAME_RELATED_P (src
))
378 snote
= find_reg_note (src
, REG_CFA_ADJUST_CFA
, NULL_RTX
);
381 sexp
= XEXP (snote
, 0);
383 if (RTX_FRAME_RELATED_P (dst
))
384 dnote
= find_reg_note (dst
, REG_CFA_ADJUST_CFA
, NULL_RTX
);
387 add_reg_note (dst
, REG_CFA_ADJUST_CFA
, sexp
);
390 dexp
= XEXP (dnote
, 0);
392 gcc_assert (GET_CODE (sexp
) == SET
);
393 gcc_assert (GET_CODE (dexp
) == SET
);
396 exp1
= dexp
, exp2
= sexp
;
398 exp1
= sexp
, exp2
= dexp
;
400 SET_SRC (exp1
) = simplify_replace_rtx (SET_SRC (exp1
), SET_DEST (exp2
),
402 XEXP (dnote
, 0) = exp1
;
405 /* Return the next (or previous) active insn within BB. */
408 prev_active_insn_bb (basic_block bb
, rtx_insn
*insn
)
410 for (insn
= PREV_INSN (insn
);
411 insn
!= PREV_INSN (BB_HEAD (bb
));
412 insn
= PREV_INSN (insn
))
413 if (active_insn_p (insn
))
419 next_active_insn_bb (basic_block bb
, rtx_insn
*insn
)
421 for (insn
= NEXT_INSN (insn
);
422 insn
!= NEXT_INSN (BB_END (bb
));
423 insn
= NEXT_INSN (insn
))
424 if (active_insn_p (insn
))
429 /* If INSN has a REG_ARGS_SIZE note, if possible move it to PREV. Otherwise
430 search for a nearby candidate within BB where we can stick the note. */
433 force_move_args_size_note (basic_block bb
, rtx_insn
*prev
, rtx_insn
*insn
)
436 rtx_insn
*test
, *next_candidate
, *prev_candidate
;
438 /* If PREV exists, tail-call to the logic in the other function. */
441 maybe_move_args_size_note (prev
, insn
, false);
445 /* First, make sure there's anything that needs doing. */
446 note
= find_reg_note (insn
, REG_ARGS_SIZE
, NULL_RTX
);
450 /* We need to find a spot between the previous and next exception points
451 where we can place the note and "properly" deallocate the arguments. */
452 next_candidate
= prev_candidate
= NULL
;
454 /* It is often the case that we have insns in the order:
456 add sp (previous deallocation)
457 sub sp (align for next arglist)
459 and the add/sub cancel. Therefore we begin by searching forward. */
462 while ((test
= next_active_insn_bb (bb
, test
)) != NULL
)
464 /* Found an existing note: nothing to do. */
465 if (find_reg_note (test
, REG_ARGS_SIZE
, NULL_RTX
))
467 /* Found something that affects unwinding. Stop searching. */
468 if (CALL_P (test
) || !insn_nothrow_p (test
))
470 if (next_candidate
== NULL
)
471 next_candidate
= test
;
475 while ((test
= prev_active_insn_bb (bb
, test
)) != NULL
)
478 /* Found a place that seems logical to adjust the stack. */
479 tnote
= find_reg_note (test
, REG_ARGS_SIZE
, NULL_RTX
);
482 XEXP (tnote
, 0) = XEXP (note
, 0);
485 if (prev_candidate
== NULL
)
486 prev_candidate
= test
;
487 /* Found something that affects unwinding. Stop searching. */
488 if (CALL_P (test
) || !insn_nothrow_p (test
))
493 test
= prev_candidate
;
494 else if (next_candidate
)
495 test
= next_candidate
;
498 /* ??? We *must* have a place, lest we ICE on the lost adjustment.
499 Options are: dummy clobber insn, nop, or prevent the removal of
501 /* TODO: Find another way to indicate to the dwarf2 code that we
502 have not in fact lost an adjustment. */
503 test
= emit_insn_before (gen_rtx_CLOBBER (VOIDmode
, const0_rtx
), insn
);
505 add_reg_note (test
, REG_ARGS_SIZE
, XEXP (note
, 0));
508 /* Subroutine of combine_stack_adjustments, called for each basic block. */
511 combine_stack_adjustments_for_block (basic_block bb
)
513 HOST_WIDE_INT last_sp_adjust
= 0;
514 rtx_insn
*last_sp_set
= NULL
;
515 rtx_insn
*last2_sp_set
= NULL
;
516 struct csa_reflist
*reflist
= NULL
;
517 rtx_insn
*insn
, *next
;
519 bool end_of_block
= false;
521 for (insn
= BB_HEAD (bb
); !end_of_block
; insn
= next
)
523 end_of_block
= insn
== BB_END (bb
);
524 next
= NEXT_INSN (insn
);
529 set
= single_set_for_csa (insn
);
532 rtx dest
= SET_DEST (set
);
533 rtx src
= SET_SRC (set
);
535 /* Find constant additions to the stack pointer. */
536 if (dest
== stack_pointer_rtx
537 && GET_CODE (src
) == PLUS
538 && XEXP (src
, 0) == stack_pointer_rtx
539 && CONST_INT_P (XEXP (src
, 1)))
541 HOST_WIDE_INT this_adjust
= INTVAL (XEXP (src
, 1));
543 /* If we've not seen an adjustment previously, record
544 it now and continue. */
548 last_sp_adjust
= this_adjust
;
552 /* If not all recorded refs can be adjusted, or the
553 adjustment is now too large for a constant addition,
554 we cannot merge the two stack adjustments.
556 Also we need to be careful to not move stack pointer
557 such that we create stack accesses outside the allocated
558 area. We can combine an allocation into the first insn,
559 or a deallocation into the second insn. We can not
560 combine an allocation followed by a deallocation.
562 The only somewhat frequent occurrence of the later is when
563 a function allocates a stack frame but does not use it.
564 For this case, we would need to analyze rtl stream to be
565 sure that allocated area is really unused. This means not
566 only checking the memory references, but also all registers
567 or global memory references possibly containing a stack
570 Perhaps the best way to address this problem is to teach
571 gcc not to allocate stack for objects never used. */
573 /* Combine an allocation into the first instruction. */
574 if (STACK_GROWS_DOWNWARD
? this_adjust
<= 0 : this_adjust
>= 0)
576 if (no_unhandled_cfa (insn
)
577 && try_apply_stack_adjustment (last_sp_set
, reflist
,
583 maybe_move_args_size_note (last_sp_set
, insn
, false);
584 maybe_merge_cfa_adjust (last_sp_set
, insn
, false);
586 last_sp_adjust
+= this_adjust
;
591 /* Otherwise we have a deallocation. Do not combine with
592 a previous allocation. Combine into the second insn. */
593 else if (STACK_GROWS_DOWNWARD
594 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
596 if (no_unhandled_cfa (last_sp_set
)
597 && try_apply_stack_adjustment (insn
, reflist
,
603 maybe_move_args_size_note (insn
, last_sp_set
, true);
604 maybe_merge_cfa_adjust (insn
, last_sp_set
, true);
605 delete_insn (last_sp_set
);
607 last_sp_adjust
+= this_adjust
;
608 free_csa_reflist (reflist
);
614 /* Combination failed. Restart processing from here. If
615 deallocation+allocation conspired to cancel, we can
616 delete the old deallocation insn. */
619 if (last_sp_adjust
== 0 && no_unhandled_cfa (last_sp_set
))
621 maybe_move_args_size_note (insn
, last_sp_set
, true);
622 maybe_merge_cfa_adjust (insn
, last_sp_set
, true);
623 delete_insn (last_sp_set
);
626 last2_sp_set
= last_sp_set
;
628 free_csa_reflist (reflist
);
631 last_sp_adjust
= this_adjust
;
635 /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
636 the previous adjustment and turn it into a simple store. This
637 is equivalent to anticipating the stack adjustment so this must
640 && ((STACK_GROWS_DOWNWARD
641 ? (GET_CODE (XEXP (dest
, 0)) == PRE_DEC
643 == (HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
)))
644 : (GET_CODE (XEXP (dest
, 0)) == PRE_INC
646 == -(HOST_WIDE_INT
) GET_MODE_SIZE (GET_MODE (dest
))))
647 || ((STACK_GROWS_DOWNWARD
648 ? last_sp_adjust
>= 0 : last_sp_adjust
<= 0)
649 && GET_CODE (XEXP (dest
, 0)) == PRE_MODIFY
650 && GET_CODE (XEXP (XEXP (dest
, 0), 1)) == PLUS
651 && XEXP (XEXP (XEXP (dest
, 0), 1), 0)
653 && GET_CODE (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
655 && INTVAL (XEXP (XEXP (XEXP (dest
, 0), 1), 1))
657 && XEXP (XEXP (dest
, 0), 0) == stack_pointer_rtx
658 && !reg_mentioned_p (stack_pointer_rtx
, src
)
659 && memory_address_p (GET_MODE (dest
), stack_pointer_rtx
)
660 && try_apply_stack_adjustment (insn
, reflist
, 0,
664 maybe_move_args_size_note (last2_sp_set
, last_sp_set
, false);
666 maybe_move_args_size_note (insn
, last_sp_set
, true);
667 delete_insn (last_sp_set
);
668 free_csa_reflist (reflist
);
676 if (!CALL_P (insn
) && last_sp_set
677 && record_stack_refs (insn
, &reflist
))
680 /* Otherwise, we were not able to process the instruction.
681 Do not continue collecting data across such a one. */
684 || reg_mentioned_p (stack_pointer_rtx
, PATTERN (insn
))))
686 if (last_sp_set
&& last_sp_adjust
== 0)
688 force_move_args_size_note (bb
, last2_sp_set
, last_sp_set
);
689 delete_insn (last_sp_set
);
691 free_csa_reflist (reflist
);
699 if (last_sp_set
&& last_sp_adjust
== 0)
701 force_move_args_size_note (bb
, last2_sp_set
, last_sp_set
);
702 delete_insn (last_sp_set
);
706 free_csa_reflist (reflist
);
710 rest_of_handle_stack_adjustments (void)
712 df_note_add_problem ();
714 combine_stack_adjustments ();
720 const pass_data pass_data_stack_adjustments
=
724 OPTGROUP_NONE
, /* optinfo_flags */
725 TV_COMBINE_STACK_ADJUST
, /* tv_id */
726 0, /* properties_required */
727 0, /* properties_provided */
728 0, /* properties_destroyed */
729 0, /* todo_flags_start */
730 TODO_df_finish
, /* todo_flags_finish */
733 class pass_stack_adjustments
: public rtl_opt_pass
736 pass_stack_adjustments (gcc::context
*ctxt
)
737 : rtl_opt_pass (pass_data_stack_adjustments
, ctxt
)
740 /* opt_pass methods: */
741 virtual bool gate (function
*);
742 virtual unsigned int execute (function
*)
744 return rest_of_handle_stack_adjustments ();
747 }; // class pass_stack_adjustments
750 pass_stack_adjustments::gate (function
*)
752 /* This is kind of a heuristic. We need to run combine_stack_adjustments
753 even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS
754 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
755 push instructions will have popping returns. */
756 #ifndef PUSH_ROUNDING
757 if (ACCUMULATE_OUTGOING_ARGS
)
760 return flag_combine_stack_adjustments
;
766 make_pass_stack_adjustments (gcc::context
*ctxt
)
768 return new pass_stack_adjustments (ctxt
);