2013-05-30 Ed Smith-Rowland <3dw4rd@verizon.net>
[official-gcc.git] / gcc / combine-stack-adj.c
blob7392b92b3f5fec76bd0c70fdabb2330d2fbdc8d2
1 /* Combine stack adjustments.
2 Copyright (C) 1987-2013 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
9 version.
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
14 for more details.
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
39 by a push. */
41 #include "config.h"
42 #include "system.h"
43 #include "coretypes.h"
44 #include "tm.h"
45 #include "rtl.h"
46 #include "tm_p.h"
47 #include "insn-config.h"
48 #include "recog.h"
49 #include "regs.h"
50 #include "hard-reg-set.h"
51 #include "flags.h"
52 #include "function.h"
53 #include "expr.h"
54 #include "basic-block.h"
55 #include "df.h"
56 #include "except.h"
57 #include "reload.h"
58 #include "tree-pass.h"
61 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
62 #ifdef STACK_GROWS_DOWNWARD
63 #undef STACK_GROWS_DOWNWARD
64 #define STACK_GROWS_DOWNWARD 1
65 #else
66 #define STACK_GROWS_DOWNWARD 0
67 #endif
69 /* This structure records two kinds of stack references between stack
70 adjusting instructions: stack references in memory addresses for
71 regular insns and all stack references for debug insns. */
73 struct csa_reflist
75 HOST_WIDE_INT sp_offset;
76 rtx insn, *ref;
77 struct csa_reflist *next;
80 static int stack_memref_p (rtx);
81 static rtx single_set_for_csa (rtx);
82 static void free_csa_reflist (struct csa_reflist *);
83 static struct csa_reflist *record_one_stack_ref (rtx, rtx *,
84 struct csa_reflist *);
85 static int try_apply_stack_adjustment (rtx, struct csa_reflist *,
86 HOST_WIDE_INT, HOST_WIDE_INT);
87 static void combine_stack_adjustments_for_block (basic_block);
88 static int record_stack_refs (rtx *, void *);
91 /* Main entry point for stack adjustment combination. */
93 static void
94 combine_stack_adjustments (void)
96 basic_block bb;
98 FOR_EACH_BB (bb)
99 combine_stack_adjustments_for_block (bb);
102 /* Recognize a MEM of the form (sp) or (plus sp const). */
104 static int
105 stack_memref_p (rtx x)
107 if (!MEM_P (x))
108 return 0;
109 x = XEXP (x, 0);
111 if (x == stack_pointer_rtx)
112 return 1;
113 if (GET_CODE (x) == PLUS
114 && XEXP (x, 0) == stack_pointer_rtx
115 && CONST_INT_P (XEXP (x, 1)))
116 return 1;
118 return 0;
121 /* Recognize either normal single_set or the hack in i386.md for
122 tying fp and sp adjustments. */
124 static rtx
125 single_set_for_csa (rtx insn)
127 int i;
128 rtx tmp = single_set (insn);
129 if (tmp)
130 return tmp;
132 if (!NONJUMP_INSN_P (insn)
133 || GET_CODE (PATTERN (insn)) != PARALLEL)
134 return NULL_RTX;
136 tmp = PATTERN (insn);
137 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
138 return NULL_RTX;
140 for (i = 1; i < XVECLEN (tmp, 0); ++i)
142 rtx this_rtx = XVECEXP (tmp, 0, i);
144 /* The special case is allowing a no-op set. */
145 if (GET_CODE (this_rtx) == SET
146 && SET_SRC (this_rtx) == SET_DEST (this_rtx))
148 else if (GET_CODE (this_rtx) != CLOBBER
149 && GET_CODE (this_rtx) != USE)
150 return NULL_RTX;
153 return XVECEXP (tmp, 0, 0);
156 /* Free the list of csa_reflist nodes. */
158 static void
159 free_csa_reflist (struct csa_reflist *reflist)
161 struct csa_reflist *next;
162 for (; reflist ; reflist = next)
164 next = reflist->next;
165 free (reflist);
169 /* Create a new csa_reflist node from the given stack reference.
170 It is already known that the reference is either a MEM satisfying the
171 predicate stack_memref_p or a REG representing the stack pointer. */
173 static struct csa_reflist *
174 record_one_stack_ref (rtx insn, rtx *ref, struct csa_reflist *next_reflist)
176 struct csa_reflist *ml;
178 ml = XNEW (struct csa_reflist);
180 if (REG_P (*ref) || XEXP (*ref, 0) == stack_pointer_rtx)
181 ml->sp_offset = 0;
182 else
183 ml->sp_offset = INTVAL (XEXP (XEXP (*ref, 0), 1));
185 ml->insn = insn;
186 ml->ref = ref;
187 ml->next = next_reflist;
189 return ml;
192 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
193 as each of the memories and stack references in REFLIST. Return true
194 on success. */
196 static int
197 try_apply_stack_adjustment (rtx insn, struct csa_reflist *reflist,
198 HOST_WIDE_INT new_adjust, HOST_WIDE_INT delta)
200 struct csa_reflist *ml;
201 rtx set;
203 set = single_set_for_csa (insn);
204 if (MEM_P (SET_DEST (set)))
205 validate_change (insn, &SET_DEST (set),
206 replace_equiv_address (SET_DEST (set), stack_pointer_rtx),
208 else
209 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
211 for (ml = reflist; ml ; ml = ml->next)
213 rtx new_addr = plus_constant (Pmode, stack_pointer_rtx,
214 ml->sp_offset - delta);
215 rtx new_val;
217 if (MEM_P (*ml->ref))
218 new_val = replace_equiv_address_nv (*ml->ref, new_addr);
219 else if (GET_MODE (*ml->ref) == GET_MODE (stack_pointer_rtx))
220 new_val = new_addr;
221 else
222 new_val = lowpart_subreg (GET_MODE (*ml->ref), new_addr,
223 GET_MODE (new_addr));
224 validate_change (ml->insn, ml->ref, new_val, 1);
227 if (apply_change_group ())
229 /* Succeeded. Update our knowledge of the stack references. */
230 for (ml = reflist; ml ; ml = ml->next)
231 ml->sp_offset -= delta;
233 return 1;
235 else
236 return 0;
239 /* Called via for_each_rtx and used to record all stack memory and other
240 references in the insn and discard all other stack pointer references. */
241 struct record_stack_refs_data
243 rtx insn;
244 struct csa_reflist *reflist;
247 static int
248 record_stack_refs (rtx *xp, void *data)
250 rtx x = *xp;
251 struct record_stack_refs_data *d =
252 (struct record_stack_refs_data *) data;
253 if (!x)
254 return 0;
255 switch (GET_CODE (x))
257 case MEM:
258 if (!reg_mentioned_p (stack_pointer_rtx, x))
259 return -1;
260 /* We are not able to handle correctly all possible memrefs containing
261 stack pointer, so this check is necessary. */
262 if (stack_memref_p (x))
264 d->reflist = record_one_stack_ref (d->insn, xp, d->reflist);
265 return -1;
267 /* Try harder for DEBUG_INSNs, handle e.g. (mem (mem (sp + 16) + 4). */
268 return !DEBUG_INSN_P (d->insn);
269 case REG:
270 /* ??? We want be able to handle non-memory stack pointer
271 references later. For now just discard all insns referring to
272 stack pointer outside mem expressions. We would probably
273 want to teach validate_replace to simplify expressions first.
275 We can't just compare with STACK_POINTER_RTX because the
276 reference to the stack pointer might be in some other mode.
277 In particular, an explicit clobber in an asm statement will
278 result in a QImode clobber.
280 In DEBUG_INSNs, we want to replace all occurrences, otherwise
281 they will cause -fcompare-debug failures. */
282 if (REGNO (x) == STACK_POINTER_REGNUM)
284 if (!DEBUG_INSN_P (d->insn))
285 return 1;
286 d->reflist = record_one_stack_ref (d->insn, xp, d->reflist);
287 return -1;
289 break;
290 default:
291 break;
293 return 0;
296 /* If INSN has a REG_ARGS_SIZE note, move it to LAST.
297 AFTER is true iff LAST follows INSN in the instruction stream. */
299 static void
300 maybe_move_args_size_note (rtx last, rtx insn, bool after)
302 rtx note, last_note;
304 note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX);
305 if (note == NULL)
306 return;
308 last_note = find_reg_note (last, REG_ARGS_SIZE, NULL_RTX);
309 if (last_note)
311 /* The ARGS_SIZE notes are *not* cumulative. They represent an
312 absolute value, and the "most recent" note wins. */
313 if (!after)
314 XEXP (last_note, 0) = XEXP (note, 0);
316 else
317 add_reg_note (last, REG_ARGS_SIZE, XEXP (note, 0));
320 /* Return the next (or previous) active insn within BB. */
322 static rtx
323 prev_active_insn_bb (basic_block bb, rtx insn)
325 for (insn = PREV_INSN (insn);
326 insn != PREV_INSN (BB_HEAD (bb));
327 insn = PREV_INSN (insn))
328 if (active_insn_p (insn))
329 return insn;
330 return NULL_RTX;
333 static rtx
334 next_active_insn_bb (basic_block bb, rtx insn)
336 for (insn = NEXT_INSN (insn);
337 insn != NEXT_INSN (BB_END (bb));
338 insn = NEXT_INSN (insn))
339 if (active_insn_p (insn))
340 return insn;
341 return NULL_RTX;
344 /* If INSN has a REG_ARGS_SIZE note, if possible move it to PREV. Otherwise
345 search for a nearby candidate within BB where we can stick the note. */
347 static void
348 force_move_args_size_note (basic_block bb, rtx prev, rtx insn)
350 rtx note, test, next_candidate, prev_candidate;
352 /* If PREV exists, tail-call to the logic in the other function. */
353 if (prev)
355 maybe_move_args_size_note (prev, insn, false);
356 return;
359 /* First, make sure there's anything that needs doing. */
360 note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX);
361 if (note == NULL)
362 return;
364 /* We need to find a spot between the previous and next exception points
365 where we can place the note and "properly" deallocate the arguments. */
366 next_candidate = prev_candidate = NULL;
368 /* It is often the case that we have insns in the order:
369 call
370 add sp (previous deallocation)
371 sub sp (align for next arglist)
372 push arg
373 and the add/sub cancel. Therefore we begin by searching forward. */
375 test = insn;
376 while ((test = next_active_insn_bb (bb, test)) != NULL)
378 /* Found an existing note: nothing to do. */
379 if (find_reg_note (test, REG_ARGS_SIZE, NULL_RTX))
380 return;
381 /* Found something that affects unwinding. Stop searching. */
382 if (CALL_P (test) || !insn_nothrow_p (test))
383 break;
384 if (next_candidate == NULL)
385 next_candidate = test;
388 test = insn;
389 while ((test = prev_active_insn_bb (bb, test)) != NULL)
391 rtx tnote;
392 /* Found a place that seems logical to adjust the stack. */
393 tnote = find_reg_note (test, REG_ARGS_SIZE, NULL_RTX);
394 if (tnote)
396 XEXP (tnote, 0) = XEXP (note, 0);
397 return;
399 if (prev_candidate == NULL)
400 prev_candidate = test;
401 /* Found something that affects unwinding. Stop searching. */
402 if (CALL_P (test) || !insn_nothrow_p (test))
403 break;
406 if (prev_candidate)
407 test = prev_candidate;
408 else if (next_candidate)
409 test = next_candidate;
410 else
412 /* ??? We *must* have a place, lest we ICE on the lost adjustment.
413 Options are: dummy clobber insn, nop, or prevent the removal of
414 the sp += 0 insn. */
415 /* TODO: Find another way to indicate to the dwarf2 code that we
416 have not in fact lost an adjustment. */
417 test = emit_insn_before (gen_rtx_CLOBBER (VOIDmode, const0_rtx), insn);
419 add_reg_note (test, REG_ARGS_SIZE, XEXP (note, 0));
422 /* Subroutine of combine_stack_adjustments, called for each basic block. */
424 static void
425 combine_stack_adjustments_for_block (basic_block bb)
427 HOST_WIDE_INT last_sp_adjust = 0;
428 rtx last_sp_set = NULL_RTX;
429 rtx last2_sp_set = NULL_RTX;
430 struct csa_reflist *reflist = NULL;
431 rtx insn, next, set;
432 struct record_stack_refs_data data;
433 bool end_of_block = false;
435 for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
437 end_of_block = insn == BB_END (bb);
438 next = NEXT_INSN (insn);
440 if (! INSN_P (insn))
441 continue;
443 set = single_set_for_csa (insn);
444 if (set)
446 rtx dest = SET_DEST (set);
447 rtx src = SET_SRC (set);
449 /* Find constant additions to the stack pointer. */
450 if (dest == stack_pointer_rtx
451 && GET_CODE (src) == PLUS
452 && XEXP (src, 0) == stack_pointer_rtx
453 && CONST_INT_P (XEXP (src, 1)))
455 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
457 /* If we've not seen an adjustment previously, record
458 it now and continue. */
459 if (! last_sp_set)
461 last_sp_set = insn;
462 last_sp_adjust = this_adjust;
463 continue;
466 /* If not all recorded refs can be adjusted, or the
467 adjustment is now too large for a constant addition,
468 we cannot merge the two stack adjustments.
470 Also we need to be careful to not move stack pointer
471 such that we create stack accesses outside the allocated
472 area. We can combine an allocation into the first insn,
473 or a deallocation into the second insn. We can not
474 combine an allocation followed by a deallocation.
476 The only somewhat frequent occurrence of the later is when
477 a function allocates a stack frame but does not use it.
478 For this case, we would need to analyze rtl stream to be
479 sure that allocated area is really unused. This means not
480 only checking the memory references, but also all registers
481 or global memory references possibly containing a stack
482 frame address.
484 Perhaps the best way to address this problem is to teach
485 gcc not to allocate stack for objects never used. */
487 /* Combine an allocation into the first instruction. */
488 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
490 if (try_apply_stack_adjustment (last_sp_set, reflist,
491 last_sp_adjust + this_adjust,
492 this_adjust))
494 /* It worked! */
495 maybe_move_args_size_note (last_sp_set, insn, false);
496 delete_insn (insn);
497 last_sp_adjust += this_adjust;
498 continue;
502 /* Otherwise we have a deallocation. Do not combine with
503 a previous allocation. Combine into the second insn. */
504 else if (STACK_GROWS_DOWNWARD
505 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
507 if (try_apply_stack_adjustment (insn, reflist,
508 last_sp_adjust + this_adjust,
509 -last_sp_adjust))
511 /* It worked! */
512 maybe_move_args_size_note (insn, last_sp_set, true);
513 delete_insn (last_sp_set);
514 last_sp_set = insn;
515 last_sp_adjust += this_adjust;
516 free_csa_reflist (reflist);
517 reflist = NULL;
518 continue;
522 /* Combination failed. Restart processing from here. If
523 deallocation+allocation conspired to cancel, we can
524 delete the old deallocation insn. */
525 if (last_sp_set)
527 if (last_sp_adjust == 0)
529 maybe_move_args_size_note (insn, last_sp_set, true);
530 delete_insn (last_sp_set);
532 else
533 last2_sp_set = last_sp_set;
535 free_csa_reflist (reflist);
536 reflist = NULL;
537 last_sp_set = insn;
538 last_sp_adjust = this_adjust;
539 continue;
542 /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
543 the previous adjustment and turn it into a simple store. This
544 is equivalent to anticipating the stack adjustment so this must
545 be an allocation. */
546 if (MEM_P (dest)
547 && ((STACK_GROWS_DOWNWARD
548 ? (GET_CODE (XEXP (dest, 0)) == PRE_DEC
549 && last_sp_adjust
550 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest)))
551 : (GET_CODE (XEXP (dest, 0)) == PRE_INC
552 && last_sp_adjust
553 == -(HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
554 || ((STACK_GROWS_DOWNWARD
555 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
556 && GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
557 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
558 && XEXP (XEXP (XEXP (dest, 0), 1), 0)
559 == stack_pointer_rtx
560 && GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
561 == CONST_INT
562 && INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
563 == -last_sp_adjust))
564 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
565 && !reg_mentioned_p (stack_pointer_rtx, src)
566 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
567 && try_apply_stack_adjustment (insn, reflist, 0,
568 -last_sp_adjust))
570 if (last2_sp_set)
571 maybe_move_args_size_note (last2_sp_set, last_sp_set, false);
572 else
573 maybe_move_args_size_note (insn, last_sp_set, true);
574 delete_insn (last_sp_set);
575 free_csa_reflist (reflist);
576 reflist = NULL;
577 last_sp_set = NULL_RTX;
578 last_sp_adjust = 0;
579 continue;
583 data.insn = insn;
584 data.reflist = reflist;
585 if (!CALL_P (insn) && last_sp_set
586 && !for_each_rtx (&PATTERN (insn), record_stack_refs, &data))
588 reflist = data.reflist;
589 continue;
591 reflist = data.reflist;
593 /* Otherwise, we were not able to process the instruction.
594 Do not continue collecting data across such a one. */
595 if (last_sp_set
596 && (CALL_P (insn)
597 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
599 if (last_sp_set && last_sp_adjust == 0)
601 force_move_args_size_note (bb, last2_sp_set, last_sp_set);
602 delete_insn (last_sp_set);
604 free_csa_reflist (reflist);
605 reflist = NULL;
606 last2_sp_set = NULL_RTX;
607 last_sp_set = NULL_RTX;
608 last_sp_adjust = 0;
612 if (last_sp_set && last_sp_adjust == 0)
614 force_move_args_size_note (bb, last2_sp_set, last_sp_set);
615 delete_insn (last_sp_set);
618 if (reflist)
619 free_csa_reflist (reflist);
623 static bool
624 gate_handle_stack_adjustments (void)
626 /* This is kind of a heuristic. We need to run combine_stack_adjustments
627 even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS
628 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
629 push instructions will have popping returns. */
630 #ifndef PUSH_ROUNDING
631 if (ACCUMULATE_OUTGOING_ARGS)
632 return false;
633 #endif
634 return flag_combine_stack_adjustments;
637 static unsigned int
638 rest_of_handle_stack_adjustments (void)
640 df_note_add_problem ();
641 df_analyze ();
642 combine_stack_adjustments ();
643 return 0;
646 struct rtl_opt_pass pass_stack_adjustments =
649 RTL_PASS,
650 "csa", /* name */
651 OPTGROUP_NONE, /* optinfo_flags */
652 gate_handle_stack_adjustments, /* gate */
653 rest_of_handle_stack_adjustments, /* execute */
654 NULL, /* sub */
655 NULL, /* next */
656 0, /* static_pass_number */
657 TV_COMBINE_STACK_ADJUST, /* tv_id */
658 0, /* properties_required */
659 0, /* properties_provided */
660 0, /* properties_destroyed */
661 0, /* todo_flags_start */
662 TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */