Mercurial > hg > CbC > CbC_gcc

comparison gcc/combine-stack-adj.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
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
4 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 "toplev.h"
61 #include "reload.h"
62 #include "timevar.h"
63 #include "tree-pass.h"
64
65
66 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
67 #ifdef STACK_GROWS_DOWNWARD
68 #undef STACK_GROWS_DOWNWARD
69 #define STACK_GROWS_DOWNWARD 1
70 #else
71 #define STACK_GROWS_DOWNWARD 0
72 #endif
73
74 /* This structure records stack memory references between stack adjusting
75 instructions. */
76
77 struct csa_memlist
78 {
79 HOST_WIDE_INT sp_offset;
80 rtx insn, *mem;
81 struct csa_memlist *next;
82 };
83
84 static int stack_memref_p (rtx);
85 static rtx single_set_for_csa (rtx);
86 static void free_csa_memlist (struct csa_memlist *);
87 static struct csa_memlist *record_one_stack_memref (rtx, rtx *,
88 struct csa_memlist *);
89 static int try_apply_stack_adjustment (rtx, struct csa_memlist *,
90 HOST_WIDE_INT, HOST_WIDE_INT);
91 static void combine_stack_adjustments_for_block (basic_block);
92 static int record_stack_memrefs (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 && GET_CODE (XEXP (x, 1)) == CONST_INT)
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_memlist nodes. */
161
162 static void
163 free_csa_memlist (struct csa_memlist *memlist)
164 {
165 struct csa_memlist *next;
166 for (; memlist ; memlist = next)
167 {
168 next = memlist->next;
169 free (memlist);
170 }
171 }
172
173 /* Create a new csa_memlist node from the given memory reference.
174 It is already known that the memory is stack_memref_p. */
175
176 static struct csa_memlist *
177 record_one_stack_memref (rtx insn, rtx *mem, struct csa_memlist *next_memlist)
178 {
179 struct csa_memlist *ml;
180
181 ml = XNEW (struct csa_memlist);
182
183 if (XEXP (*mem, 0) == stack_pointer_rtx)
184 ml->sp_offset = 0;
185 else
186 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
187
188 ml->insn = insn;
189 ml->mem = mem;
190 ml->next = next_memlist;
191
192 return ml;
193 }
194
195 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
196 as each of the memories in MEMLIST. Return true on success. */
197
198 static int
199 try_apply_stack_adjustment (rtx insn, struct csa_memlist *memlist, HOST_WIDE_INT new_adjust,
200 HOST_WIDE_INT delta)
201 {
202 struct csa_memlist *ml;
203 rtx set;
204
205 set = single_set_for_csa (insn);
206 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
207
208 for (ml = memlist; ml ; ml = ml->next)
209 validate_change
210 (ml->insn, ml->mem,
211 replace_equiv_address_nv (*ml->mem,
212 plus_constant (stack_pointer_rtx,
213 ml->sp_offset - delta)), 1);
214
215 if (apply_change_group ())
216 {
217 /* Succeeded. Update our knowledge of the memory references. */
218 for (ml = memlist; ml ; ml = ml->next)
219 ml->sp_offset -= delta;
220
221 return 1;
222 }
223 else
224 return 0;
225 }
226
227 /* Called via for_each_rtx and used to record all stack memory references in
228 the insn and discard all other stack pointer references. */
229 struct record_stack_memrefs_data
230 {
231 rtx insn;
232 struct csa_memlist *memlist;
233 };
234
235 static int
236 record_stack_memrefs (rtx *xp, void *data)
237 {
238 rtx x = *xp;
239 struct record_stack_memrefs_data *d =
240 (struct record_stack_memrefs_data *) data;
241 if (!x)
242 return 0;
243 switch (GET_CODE (x))
244 {
245 case MEM:
246 if (!reg_mentioned_p (stack_pointer_rtx, x))
247 return -1;
248 /* We are not able to handle correctly all possible memrefs containing
249 stack pointer, so this check is necessary. */
250 if (stack_memref_p (x))
251 {
252 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
253 return -1;
254 }
255 return 1;
256 case REG:
257 /* ??? We want be able to handle non-memory stack pointer
258 references later. For now just discard all insns referring to
259 stack pointer outside mem expressions. We would probably
260 want to teach validate_replace to simplify expressions first.
261
262 We can't just compare with STACK_POINTER_RTX because the
263 reference to the stack pointer might be in some other mode.
264 In particular, an explicit clobber in an asm statement will
265 result in a QImode clobber. */
266 if (REGNO (x) == STACK_POINTER_REGNUM)
267 return 1;
268 break;
269 default:
270 break;
271 }
272 return 0;
273 }
274
275 /* Adjust or create REG_FRAME_RELATED_EXPR note when merging a stack
276 adjustment into a frame related insn. */
277
278 static void
279 adjust_frame_related_expr (rtx last_sp_set, rtx insn,
280 HOST_WIDE_INT this_adjust)
281 {
282 rtx note = find_reg_note (last_sp_set, REG_FRAME_RELATED_EXPR, NULL_RTX);
283 rtx new_expr = NULL_RTX;
284
285 if (note == NULL_RTX && RTX_FRAME_RELATED_P (insn))
286 return;
287
288 if (note
289 && GET_CODE (XEXP (note, 0)) == SEQUENCE
290 && XVECLEN (XEXP (note, 0), 0) >= 2)
291 {
292 rtx expr = XEXP (note, 0);
293 rtx last = XVECEXP (expr, 0, XVECLEN (expr, 0) - 1);
294 int i;
295
296 if (GET_CODE (last) == SET
297 && RTX_FRAME_RELATED_P (last) == RTX_FRAME_RELATED_P (insn)
298 && SET_DEST (last) == stack_pointer_rtx
299 && GET_CODE (SET_SRC (last)) == PLUS
300 && XEXP (SET_SRC (last), 0) == stack_pointer_rtx
301 && GET_CODE (XEXP (SET_SRC (last), 1)) == CONST_INT)
302 {
303 XEXP (SET_SRC (last), 1)
304 = GEN_INT (INTVAL (XEXP (SET_SRC (last), 1)) + this_adjust);
305 return;
306 }
307
308 new_expr = gen_rtx_SEQUENCE (VOIDmode,
309 rtvec_alloc (XVECLEN (expr, 0) + 1));
310 for (i = 0; i < XVECLEN (expr, 0); i++)
311 XVECEXP (new_expr, 0, i) = XVECEXP (expr, 0, i);
312 }
313 else
314 {
315 new_expr = gen_rtx_SEQUENCE (VOIDmode, rtvec_alloc (2));
316 if (note)
317 XVECEXP (new_expr, 0, 0) = XEXP (note, 0);
318 else
319 {
320 rtx expr = copy_rtx (single_set_for_csa (last_sp_set));
321
322 XEXP (SET_SRC (expr), 1)
323 = GEN_INT (INTVAL (XEXP (SET_SRC (expr), 1)) - this_adjust);
324 RTX_FRAME_RELATED_P (expr) = 1;
325 XVECEXP (new_expr, 0, 0) = expr;
326 }
327 }
328
329 XVECEXP (new_expr, 0, XVECLEN (new_expr, 0) - 1)
330 = copy_rtx (single_set_for_csa (insn));
331 RTX_FRAME_RELATED_P (XVECEXP (new_expr, 0, XVECLEN (new_expr, 0) - 1))
332 = RTX_FRAME_RELATED_P (insn);
333 if (note)
334 XEXP (note, 0) = new_expr;
335 else
336 REG_NOTES (last_sp_set)
337 = gen_rtx_EXPR_LIST (REG_FRAME_RELATED_EXPR, new_expr,
338 REG_NOTES (last_sp_set));
339 }
340
341 /* Subroutine of combine_stack_adjustments, called for each basic block. */
342
343 static void
344 combine_stack_adjustments_for_block (basic_block bb)
345 {
346 HOST_WIDE_INT last_sp_adjust = 0;
347 rtx last_sp_set = NULL_RTX;
348 struct csa_memlist *memlist = NULL;
349 rtx insn, next, set;
350 struct record_stack_memrefs_data data;
351 bool end_of_block = false;
352
353 for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
354 {
355 end_of_block = insn == BB_END (bb);
356 next = NEXT_INSN (insn);
357
358 if (! INSN_P (insn))
359 continue;
360
361 set = single_set_for_csa (insn);
362 if (set)
363 {
364 rtx dest = SET_DEST (set);
365 rtx src = SET_SRC (set);
366
367 /* Find constant additions to the stack pointer. */
368 if (dest == stack_pointer_rtx
369 && GET_CODE (src) == PLUS
370 && XEXP (src, 0) == stack_pointer_rtx
371 && GET_CODE (XEXP (src, 1)) == CONST_INT)
372 {
373 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
374
375 /* If we've not seen an adjustment previously, record
376 it now and continue. */
377 if (! last_sp_set)
378 {
379 last_sp_set = insn;
380 last_sp_adjust = this_adjust;
381 continue;
382 }
383
384 /* If not all recorded memrefs can be adjusted, or the
385 adjustment is now too large for a constant addition,
386 we cannot merge the two stack adjustments.
387
388 Also we need to be careful to not move stack pointer
389 such that we create stack accesses outside the allocated
390 area. We can combine an allocation into the first insn,
391 or a deallocation into the second insn. We can not
392 combine an allocation followed by a deallocation.
393
394 The only somewhat frequent occurrence of the later is when
395 a function allocates a stack frame but does not use it.
396 For this case, we would need to analyze rtl stream to be
397 sure that allocated area is really unused. This means not
398 only checking the memory references, but also all registers
399 or global memory references possibly containing a stack
400 frame address.
401
402 Perhaps the best way to address this problem is to teach
403 gcc not to allocate stack for objects never used. */
404
405 /* Combine an allocation into the first instruction. */
406 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
407 {
408 if (try_apply_stack_adjustment (last_sp_set, memlist,
409 last_sp_adjust + this_adjust,
410 this_adjust))
411 {
412 if (RTX_FRAME_RELATED_P (last_sp_set))
413 adjust_frame_related_expr (last_sp_set, insn,
414 this_adjust);
415 /* It worked! */
416 delete_insn (insn);
417 last_sp_adjust += this_adjust;
418 continue;
419 }
420 }
421
422 /* Otherwise we have a deallocation. Do not combine with
423 a previous allocation. Combine into the second insn. */
424 else if (STACK_GROWS_DOWNWARD
425 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
426 {
427 if (try_apply_stack_adjustment (insn, memlist,
428 last_sp_adjust + this_adjust,
429 -last_sp_adjust))
430 {
431 /* It worked! */
432 delete_insn (last_sp_set);
433 last_sp_set = insn;
434 last_sp_adjust += this_adjust;
435 free_csa_memlist (memlist);
436 memlist = NULL;
437 continue;
438 }
439 }
440
441 /* Combination failed. Restart processing from here. If
442 deallocation+allocation conspired to cancel, we can
443 delete the old deallocation insn. */
444 if (last_sp_set && last_sp_adjust == 0)
445 delete_insn (last_sp_set);
446 free_csa_memlist (memlist);
447 memlist = NULL;
448 last_sp_set = insn;
449 last_sp_adjust = this_adjust;
450 continue;
451 }
452
453 /* Find a predecrement of exactly the previous adjustment and
454 turn it into a direct store. Obviously we can't do this if
455 there were any intervening uses of the stack pointer. */
456 if (memlist == NULL
457 && MEM_P (dest)
458 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
459 && (last_sp_adjust
460 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
461 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
462 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
463 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
464 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
465 == CONST_INT)
466 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
467 == -last_sp_adjust)))
468 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
469 && ! reg_mentioned_p (stack_pointer_rtx, src)
470 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
471 && validate_change (insn, &SET_DEST (set),
472 replace_equiv_address (dest,
473 stack_pointer_rtx),
474 0))
475 {
476 delete_insn (last_sp_set);
477 free_csa_memlist (memlist);
478 memlist = NULL;
479 last_sp_set = NULL_RTX;
480 last_sp_adjust = 0;
481 continue;
482 }
483 }
484
485 data.insn = insn;
486 data.memlist = memlist;
487 if (!CALL_P (insn) && last_sp_set
488 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
489 {
490 memlist = data.memlist;
491 continue;
492 }
493 memlist = data.memlist;
494
495 /* Otherwise, we were not able to process the instruction.
496 Do not continue collecting data across such a one. */
497 if (last_sp_set
498 && (CALL_P (insn)
499 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
500 {
501 if (last_sp_set && last_sp_adjust == 0)
502 delete_insn (last_sp_set);
503 free_csa_memlist (memlist);
504 memlist = NULL;
505 last_sp_set = NULL_RTX;
506 last_sp_adjust = 0;
507 }
508 }
509
510 if (last_sp_set && last_sp_adjust == 0)
511 delete_insn (last_sp_set);
512
513 if (memlist)
514 free_csa_memlist (memlist);
515 }
516
517
518 static bool
519 gate_handle_stack_adjustments (void)
520 {
521 return (optimize > 0);
522 }
523
524 static unsigned int
525 rest_of_handle_stack_adjustments (void)
526 {
527 cleanup_cfg (flag_crossjumping ? CLEANUP_CROSSJUMP : 0);
528
529 /* This is kind of a heuristic. We need to run combine_stack_adjustments
530 even for machines with possibly nonzero RETURN_POPS_ARGS
531 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
532 push instructions will have popping returns. */
533 #ifndef PUSH_ROUNDING
534 if (!ACCUMULATE_OUTGOING_ARGS)
535 #endif
536 {
537 df_note_add_problem ();
538 df_analyze ();
539 combine_stack_adjustments ();
540 }
541 return 0;
542 }
543
544 struct rtl_opt_pass pass_stack_adjustments =
545 {
546 {
547 RTL_PASS,
548 "csa", /* name */
549 gate_handle_stack_adjustments, /* gate */
550 rest_of_handle_stack_adjustments, /* execute */
551 NULL, /* sub */
552 NULL, /* next */
553 0, /* static_pass_number */
554 0, /* tv_id */
555 0, /* properties_required */
556 0, /* properties_provided */
557 0, /* properties_destroyed */
558 0, /* todo_flags_start */
559 TODO_df_finish | TODO_verify_rtl_sharing |
560 TODO_dump_func |
561 TODO_ggc_collect, /* todo_flags_finish */
562 }
563 };
564