OSDN Git Service

/cp
[pf3gnuchains/gcc-fork.git] / gcc / combine-stack-adj.c
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, 2012 Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
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.
12
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.
17
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/>.  */
21
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.
25
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.
32
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.
36
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.  */
42
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"
63
64 \f
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
72
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.  */
76
77 struct csa_reflist
78 {
79   HOST_WIDE_INT sp_offset;
80   rtx insn, *ref;
81   struct csa_reflist *next;
82 };
83
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 *);
93
94
95 /* Main entry point for stack adjustment combination.  */
96
97 static void
98 combine_stack_adjustments (void)
99 {
100   basic_block bb;
101
102   FOR_EACH_BB (bb)
103     combine_stack_adjustments_for_block (bb);
104 }
105
106 /* Recognize a MEM of the form (sp) or (plus sp const).  */
107
108 static int
109 stack_memref_p (rtx x)
110 {
111   if (!MEM_P (x))
112     return 0;
113   x = XEXP (x, 0);
114
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;
121
122   return 0;
123 }
124
125 /* Recognize either normal single_set or the hack in i386.md for
126    tying fp and sp adjustments.  */
127
128 static rtx
129 single_set_for_csa (rtx insn)
130 {
131   int i;
132   rtx tmp = single_set (insn);
133   if (tmp)
134     return tmp;
135
136   if (!NONJUMP_INSN_P (insn)
137       || GET_CODE (PATTERN (insn)) != PARALLEL)
138     return NULL_RTX;
139
140   tmp = PATTERN (insn);
141   if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
142     return NULL_RTX;
143
144   for (i = 1; i < XVECLEN (tmp, 0); ++i)
145     {
146       rtx this_rtx = XVECEXP (tmp, 0, i);
147
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))
151         ;
152       else if (GET_CODE (this_rtx) != CLOBBER
153                && GET_CODE (this_rtx) != USE)
154         return NULL_RTX;
155     }
156
157   return XVECEXP (tmp, 0, 0);
158 }
159
160 /* Free the list of csa_reflist nodes.  */
161
162 static void
163 free_csa_reflist (struct csa_reflist *reflist)
164 {
165   struct csa_reflist *next;
166   for (; reflist ; reflist = next)
167     {
168       next = reflist->next;
169       free (reflist);
170     }
171 }
172
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.  */
176
177 static struct csa_reflist *
178 record_one_stack_ref (rtx insn, rtx *ref, struct csa_reflist *next_reflist)
179 {
180   struct csa_reflist *ml;
181
182   ml = XNEW (struct csa_reflist);
183
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));
188
189   ml->insn = insn;
190   ml->ref = ref;
191   ml->next = next_reflist;
192
193   return ml;
194 }
195
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.  */
199
200 static int
201 try_apply_stack_adjustment (rtx insn, struct csa_reflist *reflist,
202                             HOST_WIDE_INT new_adjust, HOST_WIDE_INT delta)
203 {
204   struct csa_reflist *ml;
205   rtx set;
206
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),
211                      1);
212   else
213     validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
214
215   for (ml = reflist; ml ; ml = ml->next)
216     {
217       rtx new_addr = plus_constant (stack_pointer_rtx, ml->sp_offset - delta);
218       rtx new_val;
219
220       if (MEM_P (*ml->ref))
221         new_val = replace_equiv_address_nv (*ml->ref, new_addr);
222       else if (GET_MODE (*ml->ref) == GET_MODE (stack_pointer_rtx))
223         new_val = new_addr;
224       else
225         new_val = lowpart_subreg (GET_MODE (*ml->ref), new_addr,
226                                   GET_MODE (new_addr));
227       validate_change (ml->insn, ml->ref, new_val, 1);
228     }
229
230   if (apply_change_group ())
231     {
232       /* Succeeded.  Update our knowledge of the stack references.  */
233       for (ml = reflist; ml ; ml = ml->next)
234         ml->sp_offset -= delta;
235
236       return 1;
237     }
238   else
239     return 0;
240 }
241
242 /* Called via for_each_rtx and used to record all stack memory and other
243    references in the insn and discard all other stack pointer references.  */
244 struct record_stack_refs_data
245 {
246   rtx insn;
247   struct csa_reflist *reflist;
248 };
249
250 static int
251 record_stack_refs (rtx *xp, void *data)
252 {
253   rtx x = *xp;
254   struct record_stack_refs_data *d =
255     (struct record_stack_refs_data *) data;
256   if (!x)
257     return 0;
258   switch (GET_CODE (x))
259     {
260     case MEM:
261       if (!reg_mentioned_p (stack_pointer_rtx, x))
262         return -1;
263       /* We are not able to handle correctly all possible memrefs containing
264          stack pointer, so this check is necessary.  */
265       if (stack_memref_p (x))
266         {
267           d->reflist = record_one_stack_ref (d->insn, xp, d->reflist);
268           return -1;
269         }
270       /* Try harder for DEBUG_INSNs, handle e.g. (mem (mem (sp + 16) + 4).  */
271       return !DEBUG_INSN_P (d->insn);
272     case REG:
273       /* ??? We want be able to handle non-memory stack pointer
274          references later.  For now just discard all insns referring to
275          stack pointer outside mem expressions.  We would probably
276          want to teach validate_replace to simplify expressions first.
277
278          We can't just compare with STACK_POINTER_RTX because the
279          reference to the stack pointer might be in some other mode.
280          In particular, an explicit clobber in an asm statement will
281          result in a QImode clobber.
282
283          In DEBUG_INSNs, we want to replace all occurrences, otherwise
284          they will cause -fcompare-debug failures.  */
285       if (REGNO (x) == STACK_POINTER_REGNUM)
286         {
287           if (!DEBUG_INSN_P (d->insn))
288             return 1;
289           d->reflist = record_one_stack_ref (d->insn, xp, d->reflist);
290           return -1;
291         }
292       break;
293     default:
294       break;
295     }
296   return 0;
297 }
298
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.  */
301
302 static void
303 maybe_move_args_size_note (rtx last, rtx insn, bool after)
304 {
305   rtx note, last_note;
306
307   note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX);
308   if (note == NULL)
309     return;
310
311   last_note = find_reg_note (last, REG_ARGS_SIZE, NULL_RTX);
312   if (last_note)
313     {
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);
318     }
319   else
320     add_reg_note (last, REG_ARGS_SIZE, XEXP (note, 0));
321 }
322
323 /* Return the next (or previous) active insn within BB.  */
324
325 static rtx
326 prev_active_insn_bb (basic_block bb, rtx insn)
327 {
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_RTX;
334 }
335
336 static rtx
337 next_active_insn_bb (basic_block bb, rtx insn)
338 {
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_RTX;
345 }
346
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.  */
349
350 static void
351 force_move_args_size_note (basic_block bb, rtx prev, rtx insn)
352 {
353   rtx note, test, next_candidate, prev_candidate;
354
355   /* If PREV exists, tail-call to the logic in the other function.  */
356   if (prev)
357     {
358       maybe_move_args_size_note (prev, insn, false);
359       return;
360     }
361
362   /* First, make sure there's anything that needs doing.  */
363   note = find_reg_note (insn, REG_ARGS_SIZE, NULL_RTX);
364   if (note == NULL)
365     return;
366
367   /* We need to find a spot between the previous and next exception points
368      where we can place the note and "properly" deallocate the arguments.  */
369   next_candidate = prev_candidate = NULL;
370
371   /* It is often the case that we have insns in the order:
372         call
373         add sp (previous deallocation)
374         sub sp (align for next arglist)
375         push arg
376      and the add/sub cancel.  Therefore we begin by searching forward.  */
377
378   test = insn;
379   while ((test = next_active_insn_bb (bb, test)) != NULL)
380     {
381       /* Found an existing note: nothing to do.  */
382       if (find_reg_note (test, REG_ARGS_SIZE, NULL_RTX))
383         return;
384       /* Found something that affects unwinding.  Stop searching.  */
385       if (CALL_P (test) || !insn_nothrow_p (test))
386         break;
387       if (next_candidate == NULL)
388         next_candidate = test;
389     }
390
391   test = insn;
392   while ((test = prev_active_insn_bb (bb, test)) != NULL)
393     {
394       rtx tnote;
395       /* Found a place that seems logical to adjust the stack.  */
396       tnote = find_reg_note (test, REG_ARGS_SIZE, NULL_RTX);
397       if (tnote)
398         {
399           XEXP (tnote, 0) = XEXP (note, 0);
400           return;
401         }
402       if (prev_candidate == NULL)
403         prev_candidate = test;
404       /* Found something that affects unwinding.  Stop searching.  */
405       if (CALL_P (test) || !insn_nothrow_p (test))
406         break;
407     }
408
409   if (prev_candidate)
410     test = prev_candidate;
411   else if (next_candidate)
412     test = next_candidate;
413   else
414     {
415       /* ??? We *must* have a place, lest we ICE on the lost adjustment.
416          Options are: dummy clobber insn, nop, or prevent the removal of
417          the sp += 0 insn.  */
418       /* TODO: Find another way to indicate to the dwarf2 code that we
419          have not in fact lost an adjustment.  */
420       test = emit_insn_before (gen_rtx_CLOBBER (VOIDmode, const0_rtx), insn);
421     }
422   add_reg_note (test, REG_ARGS_SIZE, XEXP (note, 0));
423 }
424
425 /* Subroutine of combine_stack_adjustments, called for each basic block.  */
426
427 static void
428 combine_stack_adjustments_for_block (basic_block bb)
429 {
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;
437
438   for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
439     {
440       end_of_block = insn == BB_END (bb);
441       next = NEXT_INSN (insn);
442
443       if (! INSN_P (insn))
444         continue;
445
446       set = single_set_for_csa (insn);
447       if (set)
448         {
449           rtx dest = SET_DEST (set);
450           rtx src = SET_SRC (set);
451
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)))
457             {
458               HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
459
460               /* If we've not seen an adjustment previously, record
461                  it now and continue.  */
462               if (! last_sp_set)
463                 {
464                   last_sp_set = insn;
465                   last_sp_adjust = this_adjust;
466                   continue;
467                 }
468
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.
472
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.
478
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.
486
487                  Perhaps the best way to address this problem is to teach
488                  gcc not to allocate stack for objects never used.  */
489
490               /* Combine an allocation into the first instruction.  */
491               if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
492                 {
493                   if (try_apply_stack_adjustment (last_sp_set, reflist,
494                                                   last_sp_adjust + this_adjust,
495                                                   this_adjust))
496                     {
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;
502                     }
503                 }
504
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)
509                 {
510                   if (try_apply_stack_adjustment (insn, reflist,
511                                                   last_sp_adjust + this_adjust,
512                                                   -last_sp_adjust))
513                     {
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;
522                     }
523                 }
524
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)
529                 {
530                   if (last_sp_adjust == 0)
531                     {
532                       maybe_move_args_size_note (insn, last_sp_set, true);
533                       delete_insn (last_sp_set);
534                     }
535                   else
536                     last2_sp_set = last_sp_set;
537                 }
538               free_csa_reflist (reflist);
539               reflist = NULL;
540               last_sp_set = insn;
541               last_sp_adjust = this_adjust;
542               continue;
543             }
544
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))
572             {
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;
583             }
584         }
585
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))
590         {
591            reflist = data.reflist;
592            continue;
593         }
594       reflist = data.reflist;
595
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))))
601         {
602           if (last_sp_set && last_sp_adjust == 0)
603             {
604               force_move_args_size_note (bb, last2_sp_set, last_sp_set);
605               delete_insn (last_sp_set);
606             }
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;
612         }
613     }
614
615   if (last_sp_set && last_sp_adjust == 0)
616     {
617       force_move_args_size_note (bb, last2_sp_set, last_sp_set);
618       delete_insn (last_sp_set);
619     }
620
621   if (reflist)
622     free_csa_reflist (reflist);
623 }
624 \f
625
626 static bool
627 gate_handle_stack_adjustments (void)
628 {
629   return flag_combine_stack_adjustments;
630 }
631
632 static unsigned int
633 rest_of_handle_stack_adjustments (void)
634 {
635   cleanup_cfg (flag_crossjumping ? CLEANUP_CROSSJUMP : 0);
636
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
644     {
645       df_note_add_problem ();
646       df_analyze ();
647       combine_stack_adjustments ();
648     }
649   return 0;
650 }
651
652 struct rtl_opt_pass pass_stack_adjustments =
653 {
654  {
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 */
669  }
670 };