Update change log
[platform/upstream/gcc48.git] / gcc / combine-stack-adj.c
1 /* Combine stack adjustments.
2    Copyright (C) 1987-2013 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>.  */
19
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.
23
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.
30
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.
34
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.  */
40
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
60 \f
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
68
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.  */
72
73 struct csa_reflist
74 {
75   HOST_WIDE_INT sp_offset;
76   rtx insn, *ref;
77   struct csa_reflist *next;
78 };
79
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 *);
89
90
91 /* Main entry point for stack adjustment combination.  */
92
93 static void
94 combine_stack_adjustments (void)
95 {
96   basic_block bb;
97
98   FOR_EACH_BB (bb)
99     combine_stack_adjustments_for_block (bb);
100 }
101
102 /* Recognize a MEM of the form (sp) or (plus sp const).  */
103
104 static int
105 stack_memref_p (rtx x)
106 {
107   if (!MEM_P (x))
108     return 0;
109   x = XEXP (x, 0);
110
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;
117
118   return 0;
119 }
120
121 /* Recognize either normal single_set or the hack in i386.md for
122    tying fp and sp adjustments.  */
123
124 static rtx
125 single_set_for_csa (rtx insn)
126 {
127   int i;
128   rtx tmp = single_set (insn);
129   if (tmp)
130     return tmp;
131
132   if (!NONJUMP_INSN_P (insn)
133       || GET_CODE (PATTERN (insn)) != PARALLEL)
134     return NULL_RTX;
135
136   tmp = PATTERN (insn);
137   if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
138     return NULL_RTX;
139
140   for (i = 1; i < XVECLEN (tmp, 0); ++i)
141     {
142       rtx this_rtx = XVECEXP (tmp, 0, i);
143
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))
147         ;
148       else if (GET_CODE (this_rtx) != CLOBBER
149                && GET_CODE (this_rtx) != USE)
150         return NULL_RTX;
151     }
152
153   return XVECEXP (tmp, 0, 0);
154 }
155
156 /* Free the list of csa_reflist nodes.  */
157
158 static void
159 free_csa_reflist (struct csa_reflist *reflist)
160 {
161   struct csa_reflist *next;
162   for (; reflist ; reflist = next)
163     {
164       next = reflist->next;
165       free (reflist);
166     }
167 }
168
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.  */
172
173 static struct csa_reflist *
174 record_one_stack_ref (rtx insn, rtx *ref, struct csa_reflist *next_reflist)
175 {
176   struct csa_reflist *ml;
177
178   ml = XNEW (struct csa_reflist);
179
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));
184
185   ml->insn = insn;
186   ml->ref = ref;
187   ml->next = next_reflist;
188
189   return ml;
190 }
191
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.  */
195
196 static int
197 try_apply_stack_adjustment (rtx insn, struct csa_reflist *reflist,
198                             HOST_WIDE_INT new_adjust, HOST_WIDE_INT delta)
199 {
200   struct csa_reflist *ml;
201   rtx set;
202
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),
207                      1);
208   else
209     validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
210
211   for (ml = reflist; ml ; ml = ml->next)
212     {
213       rtx new_addr = plus_constant (Pmode, stack_pointer_rtx,
214                                     ml->sp_offset - delta);
215       rtx new_val;
216
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);
225     }
226
227   if (apply_change_group ())
228     {
229       /* Succeeded.  Update our knowledge of the stack references.  */
230       for (ml = reflist; ml ; ml = ml->next)
231         ml->sp_offset -= delta;
232
233       return 1;
234     }
235   else
236     return 0;
237 }
238
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
242 {
243   rtx insn;
244   struct csa_reflist *reflist;
245 };
246
247 static int
248 record_stack_refs (rtx *xp, void *data)
249 {
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))
256     {
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))
263         {
264           d->reflist = record_one_stack_ref (d->insn, xp, d->reflist);
265           return -1;
266         }
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.
274
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.
279
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)
283         {
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;
288         }
289       break;
290     default:
291       break;
292     }
293   return 0;
294 }
295
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.  */
298
299 static void
300 maybe_move_args_size_note (rtx last, rtx insn, bool after)
301 {
302   rtx note, last_note;
303
304   note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX);
305   if (note == NULL)
306     return;
307
308   last_note = find_reg_note (last, REG_ARGS_SIZE, NULL_RTX);
309   if (last_note)
310     {
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);
315     }
316   else
317     add_reg_note (last, REG_ARGS_SIZE, XEXP (note, 0));
318 }
319
320 /* Return the next (or previous) active insn within BB.  */
321
322 static rtx
323 prev_active_insn_bb (basic_block bb, rtx insn)
324 {
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;
331 }
332
333 static rtx
334 next_active_insn_bb (basic_block bb, rtx insn)
335 {
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;
342 }
343
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.  */
346
347 static void
348 force_move_args_size_note (basic_block bb, rtx prev, rtx insn)
349 {
350   rtx note, test, next_candidate, prev_candidate;
351
352   /* If PREV exists, tail-call to the logic in the other function.  */
353   if (prev)
354     {
355       maybe_move_args_size_note (prev, insn, false);
356       return;
357     }
358
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;
363
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;
367
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.  */
374
375   test = insn;
376   while ((test = next_active_insn_bb (bb, test)) != NULL)
377     {
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;
386     }
387
388   test = insn;
389   while ((test = prev_active_insn_bb (bb, test)) != NULL)
390     {
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)
395         {
396           XEXP (tnote, 0) = XEXP (note, 0);
397           return;
398         }
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;
404     }
405
406   if (prev_candidate)
407     test = prev_candidate;
408   else if (next_candidate)
409     test = next_candidate;
410   else
411     {
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);
418     }
419   add_reg_note (test, REG_ARGS_SIZE, XEXP (note, 0));
420 }
421
422 /* Subroutine of combine_stack_adjustments, called for each basic block.  */
423
424 static void
425 combine_stack_adjustments_for_block (basic_block bb)
426 {
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;
434
435   for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
436     {
437       end_of_block = insn == BB_END (bb);
438       next = NEXT_INSN (insn);
439
440       if (! INSN_P (insn))
441         continue;
442
443       set = single_set_for_csa (insn);
444       if (set)
445         {
446           rtx dest = SET_DEST (set);
447           rtx src = SET_SRC (set);
448
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)))
454             {
455               HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
456
457               /* If we've not seen an adjustment previously, record
458                  it now and continue.  */
459               if (! last_sp_set)
460                 {
461                   last_sp_set = insn;
462                   last_sp_adjust = this_adjust;
463                   continue;
464                 }
465
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.
469
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.
475
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.
483
484                  Perhaps the best way to address this problem is to teach
485                  gcc not to allocate stack for objects never used.  */
486
487               /* Combine an allocation into the first instruction.  */
488               if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
489                 {
490                   if (try_apply_stack_adjustment (last_sp_set, reflist,
491                                                   last_sp_adjust + this_adjust,
492                                                   this_adjust))
493                     {
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;
499                     }
500                 }
501
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)
506                 {
507                   if (try_apply_stack_adjustment (insn, reflist,
508                                                   last_sp_adjust + this_adjust,
509                                                   -last_sp_adjust))
510                     {
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;
519                     }
520                 }
521
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)
526                 {
527                   if (last_sp_adjust == 0)
528                     {
529                       maybe_move_args_size_note (insn, last_sp_set, true);
530                       delete_insn (last_sp_set);
531                     }
532                   else
533                     last2_sp_set = last_sp_set;
534                 }
535               free_csa_reflist (reflist);
536               reflist = NULL;
537               last_sp_set = insn;
538               last_sp_adjust = this_adjust;
539               continue;
540             }
541
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))
569             {
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;
580             }
581         }
582
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))
587         {
588            reflist = data.reflist;
589            continue;
590         }
591       reflist = data.reflist;
592
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))))
598         {
599           if (last_sp_set && last_sp_adjust == 0)
600             {
601               force_move_args_size_note (bb, last2_sp_set, last_sp_set);
602               delete_insn (last_sp_set);
603             }
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;
609         }
610     }
611
612   if (last_sp_set && last_sp_adjust == 0)
613     {
614       force_move_args_size_note (bb, last2_sp_set, last_sp_set);
615       delete_insn (last_sp_set);
616     }
617
618   if (reflist)
619     free_csa_reflist (reflist);
620 }
621 \f
622
623 static bool
624 gate_handle_stack_adjustments (void)
625 {
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;
635 }
636
637 static unsigned int
638 rest_of_handle_stack_adjustments (void)
639 {
640   df_note_add_problem ();
641   df_analyze ();
642   combine_stack_adjustments ();
643   return 0;
644 }
645
646 struct rtl_opt_pass pass_stack_adjustments =
647 {
648  {
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 |
663   TODO_ggc_collect,                     /* todo_flags_finish */
664  }
665 };