2012-05-17 Paolo Carlini <paolo.carlini@oracle.com>
[official-gcc.git] / gcc / combine-stack-adj.c
blob27aca85de38c598406a7d2d61fdb738ba37839bc
1 /* Combine stack adjustments.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
3 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
4 2010 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Track stack adjustments and stack memory references. Attempt to
23 reduce the number of stack adjustments by back-propagating across
24 the memory references.
26 This is intended primarily for use with targets that do not define
27 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
28 targets that define PREFERRED_STACK_BOUNDARY more aligned than
29 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
30 (e.g. x86 fp regs) which would ordinarily have to be implemented
31 as a sub/mov pair due to restrictions in calls.c.
33 Propagation stops when any of the insns that need adjusting are
34 (a) no longer valid because we've exceeded their range, (b) a
35 non-trivial push instruction, or (c) a call instruction.
37 Restriction B is based on the assumption that push instructions
38 are smaller or faster. If a port really wants to remove all
39 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
40 one exception that is made is for an add immediately followed
41 by a push. */
43 #include "config.h"
44 #include "system.h"
45 #include "coretypes.h"
46 #include "tm.h"
47 #include "rtl.h"
48 #include "tm_p.h"
49 #include "insn-config.h"
50 #include "recog.h"
51 #include "output.h"
52 #include "regs.h"
53 #include "hard-reg-set.h"
54 #include "flags.h"
55 #include "function.h"
56 #include "expr.h"
57 #include "basic-block.h"
58 #include "df.h"
59 #include "except.h"
60 #include "reload.h"
61 #include "timevar.h"
62 #include "tree-pass.h"
65 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
66 #ifdef STACK_GROWS_DOWNWARD
67 #undef STACK_GROWS_DOWNWARD
68 #define STACK_GROWS_DOWNWARD 1
69 #else
70 #define STACK_GROWS_DOWNWARD 0
71 #endif
73 /* This structure records two kinds of stack references between stack
74 adjusting instructions: stack references in memory addresses for
75 regular insns and all stack references for debug insns. */
77 struct csa_reflist
79 HOST_WIDE_INT sp_offset;
80 rtx insn, *ref;
81 struct csa_reflist *next;
84 static int stack_memref_p (rtx);
85 static rtx single_set_for_csa (rtx);
86 static void free_csa_reflist (struct csa_reflist *);
87 static struct csa_reflist *record_one_stack_ref (rtx, rtx *,
88 struct csa_reflist *);
89 static int try_apply_stack_adjustment (rtx, struct csa_reflist *,
90 HOST_WIDE_INT, HOST_WIDE_INT);
91 static void combine_stack_adjustments_for_block (basic_block);
92 static int record_stack_refs (rtx *, void *);
95 /* Main entry point for stack adjustment combination. */
97 static void
98 combine_stack_adjustments (void)
100 basic_block bb;
102 FOR_EACH_BB (bb)
103 combine_stack_adjustments_for_block (bb);
106 /* Recognize a MEM of the form (sp) or (plus sp const). */
108 static int
109 stack_memref_p (rtx x)
111 if (!MEM_P (x))
112 return 0;
113 x = XEXP (x, 0);
115 if (x == stack_pointer_rtx)
116 return 1;
117 if (GET_CODE (x) == PLUS
118 && XEXP (x, 0) == stack_pointer_rtx
119 && CONST_INT_P (XEXP (x, 1)))
120 return 1;
122 return 0;
125 /* Recognize either normal single_set or the hack in i386.md for
126 tying fp and sp adjustments. */
128 static rtx
129 single_set_for_csa (rtx insn)
131 int i;
132 rtx tmp = single_set (insn);
133 if (tmp)
134 return tmp;
136 if (!NONJUMP_INSN_P (insn)
137 || GET_CODE (PATTERN (insn)) != PARALLEL)
138 return NULL_RTX;
140 tmp = PATTERN (insn);
141 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
142 return NULL_RTX;
144 for (i = 1; i < XVECLEN (tmp, 0); ++i)
146 rtx this_rtx = XVECEXP (tmp, 0, i);
148 /* The special case is allowing a no-op set. */
149 if (GET_CODE (this_rtx) == SET
150 && SET_SRC (this_rtx) == SET_DEST (this_rtx))
152 else if (GET_CODE (this_rtx) != CLOBBER
153 && GET_CODE (this_rtx) != USE)
154 return NULL_RTX;
157 return XVECEXP (tmp, 0, 0);
160 /* Free the list of csa_reflist nodes. */
162 static void
163 free_csa_reflist (struct csa_reflist *reflist)
165 struct csa_reflist *next;
166 for (; reflist ; reflist = next)
168 next = reflist->next;
169 free (reflist);
173 /* Create a new csa_reflist node from the given stack reference.
174 It is already known that the reference is either a MEM satisfying the
175 predicate stack_memref_p or a REG representing the stack pointer. */
177 static struct csa_reflist *
178 record_one_stack_ref (rtx insn, rtx *ref, struct csa_reflist *next_reflist)
180 struct csa_reflist *ml;
182 ml = XNEW (struct csa_reflist);
184 if (REG_P (*ref) || XEXP (*ref, 0) == stack_pointer_rtx)
185 ml->sp_offset = 0;
186 else
187 ml->sp_offset = INTVAL (XEXP (XEXP (*ref, 0), 1));
189 ml->insn = insn;
190 ml->ref = ref;
191 ml->next = next_reflist;
193 return ml;
196 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
197 as each of the memories and stack references in REFLIST. Return true
198 on success. */
200 static int
201 try_apply_stack_adjustment (rtx insn, struct csa_reflist *reflist,
202 HOST_WIDE_INT new_adjust, HOST_WIDE_INT delta)
204 struct csa_reflist *ml;
205 rtx set;
207 set = single_set_for_csa (insn);
208 if (MEM_P (SET_DEST (set)))
209 validate_change (insn, &SET_DEST (set),
210 replace_equiv_address (SET_DEST (set), stack_pointer_rtx),
212 else
213 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
215 for (ml = reflist; ml ; ml = ml->next)
217 rtx new_addr = plus_constant (Pmode, stack_pointer_rtx,
218 ml->sp_offset - delta);
219 rtx new_val;
221 if (MEM_P (*ml->ref))
222 new_val = replace_equiv_address_nv (*ml->ref, new_addr);
223 else if (GET_MODE (*ml->ref) == GET_MODE (stack_pointer_rtx))
224 new_val = new_addr;
225 else
226 new_val = lowpart_subreg (GET_MODE (*ml->ref), new_addr,
227 GET_MODE (new_addr));
228 validate_change (ml->insn, ml->ref, new_val, 1);
231 if (apply_change_group ())
233 /* Succeeded. Update our knowledge of the stack references. */
234 for (ml = reflist; ml ; ml = ml->next)
235 ml->sp_offset -= delta;
237 return 1;
239 else
240 return 0;
243 /* Called via for_each_rtx and used to record all stack memory and other
244 references in the insn and discard all other stack pointer references. */
245 struct record_stack_refs_data
247 rtx insn;
248 struct csa_reflist *reflist;
251 static int
252 record_stack_refs (rtx *xp, void *data)
254 rtx x = *xp;
255 struct record_stack_refs_data *d =
256 (struct record_stack_refs_data *) data;
257 if (!x)
258 return 0;
259 switch (GET_CODE (x))
261 case MEM:
262 if (!reg_mentioned_p (stack_pointer_rtx, x))
263 return -1;
264 /* We are not able to handle correctly all possible memrefs containing
265 stack pointer, so this check is necessary. */
266 if (stack_memref_p (x))
268 d->reflist = record_one_stack_ref (d->insn, xp, d->reflist);
269 return -1;
271 /* Try harder for DEBUG_INSNs, handle e.g. (mem (mem (sp + 16) + 4). */
272 return !DEBUG_INSN_P (d->insn);
273 case REG:
274 /* ??? We want be able to handle non-memory stack pointer
275 references later. For now just discard all insns referring to
276 stack pointer outside mem expressions. We would probably
277 want to teach validate_replace to simplify expressions first.
279 We can't just compare with STACK_POINTER_RTX because the
280 reference to the stack pointer might be in some other mode.
281 In particular, an explicit clobber in an asm statement will
282 result in a QImode clobber.
284 In DEBUG_INSNs, we want to replace all occurrences, otherwise
285 they will cause -fcompare-debug failures. */
286 if (REGNO (x) == STACK_POINTER_REGNUM)
288 if (!DEBUG_INSN_P (d->insn))
289 return 1;
290 d->reflist = record_one_stack_ref (d->insn, xp, d->reflist);
291 return -1;
293 break;
294 default:
295 break;
297 return 0;
300 /* If INSN has a REG_ARGS_SIZE note, move it to LAST.
301 AFTER is true iff LAST follows INSN in the instruction stream. */
303 static void
304 maybe_move_args_size_note (rtx last, rtx insn, bool after)
306 rtx note, last_note;
308 note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX);
309 if (note == NULL)
310 return;
312 last_note = find_reg_note (last, REG_ARGS_SIZE, NULL_RTX);
313 if (last_note)
315 /* The ARGS_SIZE notes are *not* cumulative. They represent an
316 absolute value, and the "most recent" note wins. */
317 if (!after)
318 XEXP (last_note, 0) = XEXP (note, 0);
320 else
321 add_reg_note (last, REG_ARGS_SIZE, XEXP (note, 0));
324 /* Return the next (or previous) active insn within BB. */
326 static rtx
327 prev_active_insn_bb (basic_block bb, rtx insn)
329 for (insn = PREV_INSN (insn);
330 insn != PREV_INSN (BB_HEAD (bb));
331 insn = PREV_INSN (insn))
332 if (active_insn_p (insn))
333 return insn;
334 return NULL_RTX;
337 static rtx
338 next_active_insn_bb (basic_block bb, rtx insn)
340 for (insn = NEXT_INSN (insn);
341 insn != NEXT_INSN (BB_END (bb));
342 insn = NEXT_INSN (insn))
343 if (active_insn_p (insn))
344 return insn;
345 return NULL_RTX;
348 /* If INSN has a REG_ARGS_SIZE note, if possible move it to PREV. Otherwise
349 search for a nearby candidate within BB where we can stick the note. */
351 static void
352 force_move_args_size_note (basic_block bb, rtx prev, rtx insn)
354 rtx note, test, next_candidate, prev_candidate;
356 /* If PREV exists, tail-call to the logic in the other function. */
357 if (prev)
359 maybe_move_args_size_note (prev, insn, false);
360 return;
363 /* First, make sure there's anything that needs doing. */
364 note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX);
365 if (note == NULL)
366 return;
368 /* We need to find a spot between the previous and next exception points
369 where we can place the note and "properly" deallocate the arguments. */
370 next_candidate = prev_candidate = NULL;
372 /* It is often the case that we have insns in the order:
373 call
374 add sp (previous deallocation)
375 sub sp (align for next arglist)
376 push arg
377 and the add/sub cancel. Therefore we begin by searching forward. */
379 test = insn;
380 while ((test = next_active_insn_bb (bb, test)) != NULL)
382 /* Found an existing note: nothing to do. */
383 if (find_reg_note (test, REG_ARGS_SIZE, NULL_RTX))
384 return;
385 /* Found something that affects unwinding. Stop searching. */
386 if (CALL_P (test) || !insn_nothrow_p (test))
387 break;
388 if (next_candidate == NULL)
389 next_candidate = test;
392 test = insn;
393 while ((test = prev_active_insn_bb (bb, test)) != NULL)
395 rtx tnote;
396 /* Found a place that seems logical to adjust the stack. */
397 tnote = find_reg_note (test, REG_ARGS_SIZE, NULL_RTX);
398 if (tnote)
400 XEXP (tnote, 0) = XEXP (note, 0);
401 return;
403 if (prev_candidate == NULL)
404 prev_candidate = test;
405 /* Found something that affects unwinding. Stop searching. */
406 if (CALL_P (test) || !insn_nothrow_p (test))
407 break;
410 if (prev_candidate)
411 test = prev_candidate;
412 else if (next_candidate)
413 test = next_candidate;
414 else
416 /* ??? We *must* have a place, lest we ICE on the lost adjustment.
417 Options are: dummy clobber insn, nop, or prevent the removal of
418 the sp += 0 insn. Defer that decision until we can prove this
419 can actually happen. */
420 gcc_unreachable ();
422 add_reg_note (test, REG_ARGS_SIZE, XEXP (note, 0));
425 /* Subroutine of combine_stack_adjustments, called for each basic block. */
427 static void
428 combine_stack_adjustments_for_block (basic_block bb)
430 HOST_WIDE_INT last_sp_adjust = 0;
431 rtx last_sp_set = NULL_RTX;
432 rtx last2_sp_set = NULL_RTX;
433 struct csa_reflist *reflist = NULL;
434 rtx insn, next, set;
435 struct record_stack_refs_data data;
436 bool end_of_block = false;
438 for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
440 end_of_block = insn == BB_END (bb);
441 next = NEXT_INSN (insn);
443 if (! INSN_P (insn))
444 continue;
446 set = single_set_for_csa (insn);
447 if (set)
449 rtx dest = SET_DEST (set);
450 rtx src = SET_SRC (set);
452 /* Find constant additions to the stack pointer. */
453 if (dest == stack_pointer_rtx
454 && GET_CODE (src) == PLUS
455 && XEXP (src, 0) == stack_pointer_rtx
456 && CONST_INT_P (XEXP (src, 1)))
458 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
460 /* If we've not seen an adjustment previously, record
461 it now and continue. */
462 if (! last_sp_set)
464 last_sp_set = insn;
465 last_sp_adjust = this_adjust;
466 continue;
469 /* If not all recorded refs can be adjusted, or the
470 adjustment is now too large for a constant addition,
471 we cannot merge the two stack adjustments.
473 Also we need to be careful to not move stack pointer
474 such that we create stack accesses outside the allocated
475 area. We can combine an allocation into the first insn,
476 or a deallocation into the second insn. We can not
477 combine an allocation followed by a deallocation.
479 The only somewhat frequent occurrence of the later is when
480 a function allocates a stack frame but does not use it.
481 For this case, we would need to analyze rtl stream to be
482 sure that allocated area is really unused. This means not
483 only checking the memory references, but also all registers
484 or global memory references possibly containing a stack
485 frame address.
487 Perhaps the best way to address this problem is to teach
488 gcc not to allocate stack for objects never used. */
490 /* Combine an allocation into the first instruction. */
491 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
493 if (try_apply_stack_adjustment (last_sp_set, reflist,
494 last_sp_adjust + this_adjust,
495 this_adjust))
497 /* It worked! */
498 maybe_move_args_size_note (last_sp_set, insn, false);
499 delete_insn (insn);
500 last_sp_adjust += this_adjust;
501 continue;
505 /* Otherwise we have a deallocation. Do not combine with
506 a previous allocation. Combine into the second insn. */
507 else if (STACK_GROWS_DOWNWARD
508 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
510 if (try_apply_stack_adjustment (insn, reflist,
511 last_sp_adjust + this_adjust,
512 -last_sp_adjust))
514 /* It worked! */
515 maybe_move_args_size_note (insn, last_sp_set, true);
516 delete_insn (last_sp_set);
517 last_sp_set = insn;
518 last_sp_adjust += this_adjust;
519 free_csa_reflist (reflist);
520 reflist = NULL;
521 continue;
525 /* Combination failed. Restart processing from here. If
526 deallocation+allocation conspired to cancel, we can
527 delete the old deallocation insn. */
528 if (last_sp_set)
530 if (last_sp_adjust == 0)
532 maybe_move_args_size_note (insn, last_sp_set, true);
533 delete_insn (last_sp_set);
535 else
536 last2_sp_set = last_sp_set;
538 free_csa_reflist (reflist);
539 reflist = NULL;
540 last_sp_set = insn;
541 last_sp_adjust = this_adjust;
542 continue;
545 /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
546 the previous adjustment and turn it into a simple store. This
547 is equivalent to anticipating the stack adjustment so this must
548 be an allocation. */
549 if (MEM_P (dest)
550 && ((STACK_GROWS_DOWNWARD
551 ? (GET_CODE (XEXP (dest, 0)) == PRE_DEC
552 && last_sp_adjust
553 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest)))
554 : (GET_CODE (XEXP (dest, 0)) == PRE_INC
555 && last_sp_adjust
556 == -(HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
557 || ((STACK_GROWS_DOWNWARD
558 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
559 && GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
560 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
561 && XEXP (XEXP (XEXP (dest, 0), 1), 0)
562 == stack_pointer_rtx
563 && GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
564 == CONST_INT
565 && INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
566 == -last_sp_adjust))
567 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
568 && !reg_mentioned_p (stack_pointer_rtx, src)
569 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
570 && try_apply_stack_adjustment (insn, reflist, 0,
571 -last_sp_adjust))
573 if (last2_sp_set)
574 maybe_move_args_size_note (last2_sp_set, last_sp_set, false);
575 else
576 maybe_move_args_size_note (insn, last_sp_set, true);
577 delete_insn (last_sp_set);
578 free_csa_reflist (reflist);
579 reflist = NULL;
580 last_sp_set = NULL_RTX;
581 last_sp_adjust = 0;
582 continue;
586 data.insn = insn;
587 data.reflist = reflist;
588 if (!CALL_P (insn) && last_sp_set
589 && !for_each_rtx (&PATTERN (insn), record_stack_refs, &data))
591 reflist = data.reflist;
592 continue;
594 reflist = data.reflist;
596 /* Otherwise, we were not able to process the instruction.
597 Do not continue collecting data across such a one. */
598 if (last_sp_set
599 && (CALL_P (insn)
600 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
602 if (last_sp_set && last_sp_adjust == 0)
604 force_move_args_size_note (bb, last2_sp_set, last_sp_set);
605 delete_insn (last_sp_set);
607 free_csa_reflist (reflist);
608 reflist = NULL;
609 last2_sp_set = NULL_RTX;
610 last_sp_set = NULL_RTX;
611 last_sp_adjust = 0;
615 if (last_sp_set && last_sp_adjust == 0)
617 force_move_args_size_note (bb, last2_sp_set, last_sp_set);
618 delete_insn (last_sp_set);
621 if (reflist)
622 free_csa_reflist (reflist);
626 static bool
627 gate_handle_stack_adjustments (void)
629 return flag_combine_stack_adjustments;
632 static unsigned int
633 rest_of_handle_stack_adjustments (void)
635 cleanup_cfg (flag_crossjumping ? CLEANUP_CROSSJUMP : 0);
637 /* This is kind of a heuristic. We need to run combine_stack_adjustments
638 even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS
639 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
640 push instructions will have popping returns. */
641 #ifndef PUSH_ROUNDING
642 if (!ACCUMULATE_OUTGOING_ARGS)
643 #endif
645 df_note_add_problem ();
646 df_analyze ();
647 combine_stack_adjustments ();
649 return 0;
652 struct rtl_opt_pass pass_stack_adjustments =
655 RTL_PASS,
656 "csa", /* name */
657 gate_handle_stack_adjustments, /* gate */
658 rest_of_handle_stack_adjustments, /* execute */
659 NULL, /* sub */
660 NULL, /* next */
661 0, /* static_pass_number */
662 TV_COMBINE_STACK_ADJUST, /* tv_id */
663 0, /* properties_required */
664 0, /* properties_provided */
665 0, /* properties_destroyed */
666 0, /* todo_flags_start */
667 TODO_df_finish | TODO_verify_rtl_sharing |
668 TODO_ggc_collect, /* todo_flags_finish */