Concretize gimple_cond_set_{lhs|rhs}
[official-gcc.git] / gcc / combine-stack-adj.c
blobaebdf87d80752e927e457da1a88eac3afa09cf77
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
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"
59 #include "rtl-iter.h"
62 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
63 #ifdef STACK_GROWS_DOWNWARD
64 #undef STACK_GROWS_DOWNWARD
65 #define STACK_GROWS_DOWNWARD 1
66 #else
67 #define STACK_GROWS_DOWNWARD 0
68 #endif
70 /* This structure records two kinds of stack references between stack
71 adjusting instructions: stack references in memory addresses for
72 regular insns and all stack references for debug insns. */
74 struct csa_reflist
76 HOST_WIDE_INT sp_offset;
77 rtx_insn *insn;
78 rtx *ref;
79 struct csa_reflist *next;
82 static int stack_memref_p (rtx);
83 static rtx single_set_for_csa (rtx_insn *);
84 static void free_csa_reflist (struct csa_reflist *);
85 static struct csa_reflist *record_one_stack_ref (rtx_insn *, rtx *,
86 struct csa_reflist *);
87 static int try_apply_stack_adjustment (rtx_insn *, struct csa_reflist *,
88 HOST_WIDE_INT, HOST_WIDE_INT);
89 static void combine_stack_adjustments_for_block (basic_block);
92 /* Main entry point for stack adjustment combination. */
94 static void
95 combine_stack_adjustments (void)
97 basic_block bb;
99 FOR_EACH_BB_FN (bb, cfun)
100 combine_stack_adjustments_for_block (bb);
103 /* Recognize a MEM of the form (sp) or (plus sp const). */
105 static int
106 stack_memref_p (rtx x)
108 if (!MEM_P (x))
109 return 0;
110 x = XEXP (x, 0);
112 if (x == stack_pointer_rtx)
113 return 1;
114 if (GET_CODE (x) == PLUS
115 && XEXP (x, 0) == stack_pointer_rtx
116 && CONST_INT_P (XEXP (x, 1)))
117 return 1;
119 return 0;
122 /* Recognize either normal single_set or the hack in i386.md for
123 tying fp and sp adjustments. */
125 static rtx
126 single_set_for_csa (rtx_insn *insn)
128 int i;
129 rtx tmp = single_set (insn);
130 if (tmp)
131 return tmp;
133 if (!NONJUMP_INSN_P (insn)
134 || GET_CODE (PATTERN (insn)) != PARALLEL)
135 return NULL_RTX;
137 tmp = PATTERN (insn);
138 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
139 return NULL_RTX;
141 for (i = 1; i < XVECLEN (tmp, 0); ++i)
143 rtx this_rtx = XVECEXP (tmp, 0, i);
145 /* The special case is allowing a no-op set. */
146 if (GET_CODE (this_rtx) == SET
147 && SET_SRC (this_rtx) == SET_DEST (this_rtx))
149 else if (GET_CODE (this_rtx) != CLOBBER
150 && GET_CODE (this_rtx) != USE)
151 return NULL_RTX;
154 return XVECEXP (tmp, 0, 0);
157 /* Free the list of csa_reflist nodes. */
159 static void
160 free_csa_reflist (struct csa_reflist *reflist)
162 struct csa_reflist *next;
163 for (; reflist ; reflist = next)
165 next = reflist->next;
166 free (reflist);
170 /* Create a new csa_reflist node from the given stack reference.
171 It is already known that the reference is either a MEM satisfying the
172 predicate stack_memref_p or a REG representing the stack pointer. */
174 static struct csa_reflist *
175 record_one_stack_ref (rtx_insn *insn, rtx *ref, struct csa_reflist *next_reflist)
177 struct csa_reflist *ml;
179 ml = XNEW (struct csa_reflist);
181 if (REG_P (*ref) || XEXP (*ref, 0) == stack_pointer_rtx)
182 ml->sp_offset = 0;
183 else
184 ml->sp_offset = INTVAL (XEXP (XEXP (*ref, 0), 1));
186 ml->insn = insn;
187 ml->ref = ref;
188 ml->next = next_reflist;
190 return ml;
193 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
194 as each of the memories and stack references in REFLIST. Return true
195 on success. */
197 static int
198 try_apply_stack_adjustment (rtx_insn *insn, struct csa_reflist *reflist,
199 HOST_WIDE_INT new_adjust, HOST_WIDE_INT delta)
201 struct csa_reflist *ml;
202 rtx set;
204 set = single_set_for_csa (insn);
205 if (MEM_P (SET_DEST (set)))
206 validate_change (insn, &SET_DEST (set),
207 replace_equiv_address (SET_DEST (set), stack_pointer_rtx),
209 else
210 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
212 for (ml = reflist; ml ; ml = ml->next)
214 rtx new_addr = plus_constant (Pmode, stack_pointer_rtx,
215 ml->sp_offset - delta);
216 rtx new_val;
218 if (MEM_P (*ml->ref))
219 new_val = replace_equiv_address_nv (*ml->ref, new_addr);
220 else if (GET_MODE (*ml->ref) == GET_MODE (stack_pointer_rtx))
221 new_val = new_addr;
222 else
223 new_val = lowpart_subreg (GET_MODE (*ml->ref), new_addr,
224 GET_MODE (new_addr));
225 validate_change (ml->insn, ml->ref, new_val, 1);
228 if (apply_change_group ())
230 /* Succeeded. Update our knowledge of the stack references. */
231 for (ml = reflist; ml ; ml = ml->next)
232 ml->sp_offset -= delta;
234 return 1;
236 else
237 return 0;
240 /* For non-debug insns, record all stack memory references in INSN
241 and return true if there were no other (unrecorded) references to the
242 stack pointer. For debug insns, record all stack references regardless
243 of context and unconditionally return true. */
245 static bool
246 record_stack_refs (rtx_insn *insn, struct csa_reflist **reflist)
248 subrtx_ptr_iterator::array_type array;
249 FOR_EACH_SUBRTX_PTR (iter, array, &PATTERN (insn), NONCONST)
251 rtx *loc = *iter;
252 rtx x = *loc;
253 switch (GET_CODE (x))
255 case MEM:
256 if (!reg_mentioned_p (stack_pointer_rtx, x))
257 iter.skip_subrtxes ();
258 /* We are not able to handle correctly all possible memrefs
259 containing stack pointer, so this check is necessary. */
260 else if (stack_memref_p (x))
262 *reflist = record_one_stack_ref (insn, loc, *reflist);
263 iter.skip_subrtxes ();
265 /* Try harder for DEBUG_INSNs, handle e.g.
266 (mem (mem (sp + 16) + 4). */
267 else if (!DEBUG_INSN_P (insn))
268 return false;
269 break;
271 case REG:
272 /* ??? We want be able to handle non-memory stack pointer
273 references later. For now just discard all insns referring to
274 stack pointer outside mem expressions. We would probably
275 want to teach validate_replace to simplify expressions first.
277 We can't just compare with STACK_POINTER_RTX because the
278 reference to the stack pointer might be in some other mode.
279 In particular, an explicit clobber in an asm statement will
280 result in a QImode clobber.
282 In DEBUG_INSNs, we want to replace all occurrences, otherwise
283 they will cause -fcompare-debug failures. */
284 if (REGNO (x) == STACK_POINTER_REGNUM)
286 if (!DEBUG_INSN_P (insn))
287 return false;
288 *reflist = record_one_stack_ref (insn, loc, *reflist);
290 break;
292 default:
293 break;
296 return true;
299 /* If INSN has a REG_ARGS_SIZE note, move it to LAST.
300 AFTER is true iff LAST follows INSN in the instruction stream. */
302 static void
303 maybe_move_args_size_note (rtx_insn *last, rtx_insn *insn, bool after)
305 rtx note, last_note;
307 note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX);
308 if (note == NULL)
309 return;
311 last_note = find_reg_note (last, REG_ARGS_SIZE, NULL_RTX);
312 if (last_note)
314 /* The ARGS_SIZE notes are *not* cumulative. They represent an
315 absolute value, and the "most recent" note wins. */
316 if (!after)
317 XEXP (last_note, 0) = XEXP (note, 0);
319 else
320 add_reg_note (last, REG_ARGS_SIZE, XEXP (note, 0));
323 /* Return the next (or previous) active insn within BB. */
325 static rtx_insn *
326 prev_active_insn_bb (basic_block bb, rtx_insn *insn)
328 for (insn = PREV_INSN (insn);
329 insn != PREV_INSN (BB_HEAD (bb));
330 insn = PREV_INSN (insn))
331 if (active_insn_p (insn))
332 return insn;
333 return NULL;
336 static rtx_insn *
337 next_active_insn_bb (basic_block bb, rtx_insn *insn)
339 for (insn = NEXT_INSN (insn);
340 insn != NEXT_INSN (BB_END (bb));
341 insn = NEXT_INSN (insn))
342 if (active_insn_p (insn))
343 return insn;
344 return NULL;
347 /* If INSN has a REG_ARGS_SIZE note, if possible move it to PREV. Otherwise
348 search for a nearby candidate within BB where we can stick the note. */
350 static void
351 force_move_args_size_note (basic_block bb, rtx_insn *prev, rtx_insn *insn)
353 rtx note;
354 rtx_insn *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. */
419 /* TODO: Find another way to indicate to the dwarf2 code that we
420 have not in fact lost an adjustment. */
421 test = emit_insn_before (gen_rtx_CLOBBER (VOIDmode, const0_rtx), insn);
423 add_reg_note (test, REG_ARGS_SIZE, XEXP (note, 0));
426 /* Subroutine of combine_stack_adjustments, called for each basic block. */
428 static void
429 combine_stack_adjustments_for_block (basic_block bb)
431 HOST_WIDE_INT last_sp_adjust = 0;
432 rtx_insn *last_sp_set = NULL;
433 rtx_insn *last2_sp_set = NULL;
434 struct csa_reflist *reflist = NULL;
435 rtx_insn *insn, *next;
436 rtx set;
437 bool end_of_block = false;
439 for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
441 end_of_block = insn == BB_END (bb);
442 next = NEXT_INSN (insn);
444 if (! INSN_P (insn))
445 continue;
447 set = single_set_for_csa (insn);
448 if (set)
450 rtx dest = SET_DEST (set);
451 rtx src = SET_SRC (set);
453 /* Find constant additions to the stack pointer. */
454 if (dest == stack_pointer_rtx
455 && GET_CODE (src) == PLUS
456 && XEXP (src, 0) == stack_pointer_rtx
457 && CONST_INT_P (XEXP (src, 1)))
459 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
461 /* If we've not seen an adjustment previously, record
462 it now and continue. */
463 if (! last_sp_set)
465 last_sp_set = insn;
466 last_sp_adjust = this_adjust;
467 continue;
470 /* If not all recorded refs can be adjusted, or the
471 adjustment is now too large for a constant addition,
472 we cannot merge the two stack adjustments.
474 Also we need to be careful to not move stack pointer
475 such that we create stack accesses outside the allocated
476 area. We can combine an allocation into the first insn,
477 or a deallocation into the second insn. We can not
478 combine an allocation followed by a deallocation.
480 The only somewhat frequent occurrence of the later is when
481 a function allocates a stack frame but does not use it.
482 For this case, we would need to analyze rtl stream to be
483 sure that allocated area is really unused. This means not
484 only checking the memory references, but also all registers
485 or global memory references possibly containing a stack
486 frame address.
488 Perhaps the best way to address this problem is to teach
489 gcc not to allocate stack for objects never used. */
491 /* Combine an allocation into the first instruction. */
492 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
494 if (try_apply_stack_adjustment (last_sp_set, reflist,
495 last_sp_adjust + this_adjust,
496 this_adjust))
498 /* It worked! */
499 maybe_move_args_size_note (last_sp_set, insn, false);
500 delete_insn (insn);
501 last_sp_adjust += this_adjust;
502 continue;
506 /* Otherwise we have a deallocation. Do not combine with
507 a previous allocation. Combine into the second insn. */
508 else if (STACK_GROWS_DOWNWARD
509 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
511 if (try_apply_stack_adjustment (insn, reflist,
512 last_sp_adjust + this_adjust,
513 -last_sp_adjust))
515 /* It worked! */
516 maybe_move_args_size_note (insn, last_sp_set, true);
517 delete_insn (last_sp_set);
518 last_sp_set = insn;
519 last_sp_adjust += this_adjust;
520 free_csa_reflist (reflist);
521 reflist = NULL;
522 continue;
526 /* Combination failed. Restart processing from here. If
527 deallocation+allocation conspired to cancel, we can
528 delete the old deallocation insn. */
529 if (last_sp_set)
531 if (last_sp_adjust == 0)
533 maybe_move_args_size_note (insn, last_sp_set, true);
534 delete_insn (last_sp_set);
536 else
537 last2_sp_set = last_sp_set;
539 free_csa_reflist (reflist);
540 reflist = NULL;
541 last_sp_set = insn;
542 last_sp_adjust = this_adjust;
543 continue;
546 /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
547 the previous adjustment and turn it into a simple store. This
548 is equivalent to anticipating the stack adjustment so this must
549 be an allocation. */
550 if (MEM_P (dest)
551 && ((STACK_GROWS_DOWNWARD
552 ? (GET_CODE (XEXP (dest, 0)) == PRE_DEC
553 && last_sp_adjust
554 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest)))
555 : (GET_CODE (XEXP (dest, 0)) == PRE_INC
556 && last_sp_adjust
557 == -(HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
558 || ((STACK_GROWS_DOWNWARD
559 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
560 && GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
561 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
562 && XEXP (XEXP (XEXP (dest, 0), 1), 0)
563 == stack_pointer_rtx
564 && GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
565 == CONST_INT
566 && INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
567 == -last_sp_adjust))
568 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
569 && !reg_mentioned_p (stack_pointer_rtx, src)
570 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
571 && try_apply_stack_adjustment (insn, reflist, 0,
572 -last_sp_adjust))
574 if (last2_sp_set)
575 maybe_move_args_size_note (last2_sp_set, last_sp_set, false);
576 else
577 maybe_move_args_size_note (insn, last_sp_set, true);
578 delete_insn (last_sp_set);
579 free_csa_reflist (reflist);
580 reflist = NULL;
581 last_sp_set = NULL;
582 last_sp_adjust = 0;
583 continue;
587 if (!CALL_P (insn) && last_sp_set
588 && record_stack_refs (insn, &reflist))
589 continue;
591 /* Otherwise, we were not able to process the instruction.
592 Do not continue collecting data across such a one. */
593 if (last_sp_set
594 && (CALL_P (insn)
595 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
597 if (last_sp_set && last_sp_adjust == 0)
599 force_move_args_size_note (bb, last2_sp_set, last_sp_set);
600 delete_insn (last_sp_set);
602 free_csa_reflist (reflist);
603 reflist = NULL;
604 last2_sp_set = NULL;
605 last_sp_set = NULL;
606 last_sp_adjust = 0;
610 if (last_sp_set && last_sp_adjust == 0)
612 force_move_args_size_note (bb, last2_sp_set, last_sp_set);
613 delete_insn (last_sp_set);
616 if (reflist)
617 free_csa_reflist (reflist);
620 static unsigned int
621 rest_of_handle_stack_adjustments (void)
623 df_note_add_problem ();
624 df_analyze ();
625 combine_stack_adjustments ();
626 return 0;
629 namespace {
631 const pass_data pass_data_stack_adjustments =
633 RTL_PASS, /* type */
634 "csa", /* name */
635 OPTGROUP_NONE, /* optinfo_flags */
636 TV_COMBINE_STACK_ADJUST, /* tv_id */
637 0, /* properties_required */
638 0, /* properties_provided */
639 0, /* properties_destroyed */
640 0, /* todo_flags_start */
641 TODO_df_finish, /* todo_flags_finish */
644 class pass_stack_adjustments : public rtl_opt_pass
646 public:
647 pass_stack_adjustments (gcc::context *ctxt)
648 : rtl_opt_pass (pass_data_stack_adjustments, ctxt)
651 /* opt_pass methods: */
652 virtual bool gate (function *);
653 virtual unsigned int execute (function *)
655 return rest_of_handle_stack_adjustments ();
658 }; // class pass_stack_adjustments
660 bool
661 pass_stack_adjustments::gate (function *)
663 /* This is kind of a heuristic. We need to run combine_stack_adjustments
664 even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS
665 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
666 push instructions will have popping returns. */
667 #ifndef PUSH_ROUNDING
668 if (ACCUMULATE_OUTGOING_ARGS)
669 return false;
670 #endif
671 return flag_combine_stack_adjustments;
674 } // anon namespace
676 rtl_opt_pass *
677 make_pass_stack_adjustments (gcc::context *ctxt)
679 return new pass_stack_adjustments (ctxt);