OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [combine-stack-adj.c] - Blame information for rev 826

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* 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
   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 two kinds of stack references between stack
75
   adjusting instructions: stack references in memory addresses for
76
   regular insns and all stack references for debug insns.  */
77
 
78
struct csa_reflist
79
{
80
  HOST_WIDE_INT sp_offset;
81
  rtx insn, *ref;
82
  struct csa_reflist *next;
83
};
84
 
85
static int stack_memref_p (rtx);
86
static rtx single_set_for_csa (rtx);
87
static void free_csa_reflist (struct csa_reflist *);
88
static struct csa_reflist *record_one_stack_ref (rtx, rtx *,
89
                                                 struct csa_reflist *);
90
static int try_apply_stack_adjustment (rtx, struct csa_reflist *,
91
                                       HOST_WIDE_INT, HOST_WIDE_INT);
92
static void combine_stack_adjustments_for_block (basic_block);
93
static int record_stack_refs (rtx *, void *);
94
 
95
 
96
/* Main entry point for stack adjustment combination.  */
97
 
98
static void
99
combine_stack_adjustments (void)
100
{
101
  basic_block bb;
102
 
103
  FOR_EACH_BB (bb)
104
    combine_stack_adjustments_for_block (bb);
105
}
106
 
107
/* Recognize a MEM of the form (sp) or (plus sp const).  */
108
 
109
static int
110
stack_memref_p (rtx x)
111
{
112
  if (!MEM_P (x))
113
    return 0;
114
  x = XEXP (x, 0);
115
 
116
  if (x == stack_pointer_rtx)
117
    return 1;
118
  if (GET_CODE (x) == PLUS
119
      && XEXP (x, 0) == stack_pointer_rtx
120
      && CONST_INT_P (XEXP (x, 1)))
121
    return 1;
122
 
123
  return 0;
124
}
125
 
126
/* Recognize either normal single_set or the hack in i386.md for
127
   tying fp and sp adjustments.  */
128
 
129
static rtx
130
single_set_for_csa (rtx insn)
131
{
132
  int i;
133
  rtx tmp = single_set (insn);
134
  if (tmp)
135
    return tmp;
136
 
137
  if (!NONJUMP_INSN_P (insn)
138
      || GET_CODE (PATTERN (insn)) != PARALLEL)
139
    return NULL_RTX;
140
 
141
  tmp = PATTERN (insn);
142
  if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
143
    return NULL_RTX;
144
 
145
  for (i = 1; i < XVECLEN (tmp, 0); ++i)
146
    {
147
      rtx this_rtx = XVECEXP (tmp, 0, i);
148
 
149
      /* The special case is allowing a no-op set.  */
150
      if (GET_CODE (this_rtx) == SET
151
          && SET_SRC (this_rtx) == SET_DEST (this_rtx))
152
        ;
153
      else if (GET_CODE (this_rtx) != CLOBBER
154
               && GET_CODE (this_rtx) != USE)
155
        return NULL_RTX;
156
    }
157
 
158
  return XVECEXP (tmp, 0, 0);
159
}
160
 
161
/* Free the list of csa_reflist nodes.  */
162
 
163
static void
164
free_csa_reflist (struct csa_reflist *reflist)
165
{
166
  struct csa_reflist *next;
167
  for (; reflist ; reflist = next)
168
    {
169
      next = reflist->next;
170
      free (reflist);
171
    }
172
}
173
 
174
/* Create a new csa_reflist node from the given stack reference.
175
   It is already known that the reference is either a MEM satisfying the
176
   predicate stack_memref_p or a REG representing the stack pointer.  */
177
 
178
static struct csa_reflist *
179
record_one_stack_ref (rtx insn, rtx *ref, struct csa_reflist *next_reflist)
180
{
181
  struct csa_reflist *ml;
182
 
183
  ml = XNEW (struct csa_reflist);
184
 
185
  if (REG_P (*ref) || XEXP (*ref, 0) == stack_pointer_rtx)
186
    ml->sp_offset = 0;
187
  else
188
    ml->sp_offset = INTVAL (XEXP (XEXP (*ref, 0), 1));
189
 
190
  ml->insn = insn;
191
  ml->ref = ref;
192
  ml->next = next_reflist;
193
 
194
  return ml;
195
}
196
 
197
/* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
198
   as each of the memories and stack references in REFLIST.  Return true
199
   on success.  */
200
 
201
static int
202
try_apply_stack_adjustment (rtx insn, struct csa_reflist *reflist,
203
                            HOST_WIDE_INT new_adjust, HOST_WIDE_INT delta)
204
{
205
  struct csa_reflist *ml;
206
  rtx set;
207
 
208
  set = single_set_for_csa (insn);
209
  if (MEM_P (SET_DEST (set)))
210
    validate_change (insn, &SET_DEST (set),
211
                     replace_equiv_address (SET_DEST (set), stack_pointer_rtx),
212
                     1);
213
  else
214
    validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
215
 
216
  for (ml = reflist; ml ; ml = ml->next)
217
    {
218
      rtx new_addr = plus_constant (stack_pointer_rtx, ml->sp_offset - delta);
219
      rtx new_val;
220
 
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);
229
    }
230
 
231
  if (apply_change_group ())
232
    {
233
      /* Succeeded.  Update our knowledge of the stack references.  */
234
      for (ml = reflist; ml ; ml = ml->next)
235
        ml->sp_offset -= delta;
236
 
237
      return 1;
238
    }
239
  else
240
    return 0;
241
}
242
 
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
246
{
247
  rtx insn;
248
  struct csa_reflist *reflist;
249
};
250
 
251
static int
252
record_stack_refs (rtx *xp, void *data)
253
{
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))
260
    {
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))
267
        {
268
          d->reflist = record_one_stack_ref (d->insn, xp, d->reflist);
269
          return -1;
270
        }
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.
278
 
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.
283
 
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)
287
        {
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;
292
        }
293
      break;
294
    default:
295
      break;
296
    }
297
  return 0;
298
}
299
 
300
/* Adjust or create REG_FRAME_RELATED_EXPR note when merging a stack
301
   adjustment into a frame related insn.  */
302
 
303
static void
304
adjust_frame_related_expr (rtx last_sp_set, rtx insn,
305
                           HOST_WIDE_INT this_adjust)
306
{
307
  rtx note = find_reg_note (last_sp_set, REG_FRAME_RELATED_EXPR, NULL_RTX);
308
  rtx new_expr = NULL_RTX;
309
 
310
  if (note == NULL_RTX && RTX_FRAME_RELATED_P (insn))
311
    return;
312
 
313
  if (note
314
      && GET_CODE (XEXP (note, 0)) == SEQUENCE
315
      && XVECLEN (XEXP (note, 0), 0) >= 2)
316
    {
317
      rtx expr = XEXP (note, 0);
318
      rtx last = XVECEXP (expr, 0, XVECLEN (expr, 0) - 1);
319
      int i;
320
 
321
      if (GET_CODE (last) == SET
322
          && RTX_FRAME_RELATED_P (last) == RTX_FRAME_RELATED_P (insn)
323
          && SET_DEST (last) == stack_pointer_rtx
324
          && GET_CODE (SET_SRC (last)) == PLUS
325
          && XEXP (SET_SRC (last), 0) == stack_pointer_rtx
326
          && CONST_INT_P (XEXP (SET_SRC (last), 1)))
327
        {
328
          XEXP (SET_SRC (last), 1)
329
            = GEN_INT (INTVAL (XEXP (SET_SRC (last), 1)) + this_adjust);
330
          return;
331
        }
332
 
333
      new_expr = gen_rtx_SEQUENCE (VOIDmode,
334
                                   rtvec_alloc (XVECLEN (expr, 0) + 1));
335
      for (i = 0; i < XVECLEN (expr, 0); i++)
336
        XVECEXP (new_expr, 0, i) = XVECEXP (expr, 0, i);
337
    }
338
  else
339
    {
340
      new_expr = gen_rtx_SEQUENCE (VOIDmode, rtvec_alloc (2));
341
      if (note)
342
        XVECEXP (new_expr, 0, 0) = XEXP (note, 0);
343
      else
344
        {
345
          rtx expr = copy_rtx (single_set_for_csa (last_sp_set));
346
 
347
          XEXP (SET_SRC (expr), 1)
348
            = GEN_INT (INTVAL (XEXP (SET_SRC (expr), 1)) - this_adjust);
349
          RTX_FRAME_RELATED_P (expr) = 1;
350
          XVECEXP (new_expr, 0, 0) = expr;
351
        }
352
    }
353
 
354
  XVECEXP (new_expr, 0, XVECLEN (new_expr, 0) - 1)
355
    = copy_rtx (single_set_for_csa (insn));
356
  RTX_FRAME_RELATED_P (XVECEXP (new_expr, 0, XVECLEN (new_expr, 0) - 1))
357
    = RTX_FRAME_RELATED_P (insn);
358
  if (note)
359
    XEXP (note, 0) = new_expr;
360
  else
361
    add_reg_note (last_sp_set, REG_FRAME_RELATED_EXPR, new_expr);
362
}
363
 
364
/* Subroutine of combine_stack_adjustments, called for each basic block.  */
365
 
366
static void
367
combine_stack_adjustments_for_block (basic_block bb)
368
{
369
  HOST_WIDE_INT last_sp_adjust = 0;
370
  rtx last_sp_set = NULL_RTX;
371
  struct csa_reflist *reflist = NULL;
372
  rtx insn, next, set;
373
  struct record_stack_refs_data data;
374
  bool end_of_block = false;
375
 
376
  for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
377
    {
378
      end_of_block = insn == BB_END (bb);
379
      next = NEXT_INSN (insn);
380
 
381
      if (! INSN_P (insn))
382
        continue;
383
 
384
      set = single_set_for_csa (insn);
385
      if (set)
386
        {
387
          rtx dest = SET_DEST (set);
388
          rtx src = SET_SRC (set);
389
 
390
          /* Find constant additions to the stack pointer.  */
391
          if (dest == stack_pointer_rtx
392
              && GET_CODE (src) == PLUS
393
              && XEXP (src, 0) == stack_pointer_rtx
394
              && CONST_INT_P (XEXP (src, 1)))
395
            {
396
              HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
397
 
398
              /* If we've not seen an adjustment previously, record
399
                 it now and continue.  */
400
              if (! last_sp_set)
401
                {
402
                  last_sp_set = insn;
403
                  last_sp_adjust = this_adjust;
404
                  continue;
405
                }
406
 
407
              /* If not all recorded refs can be adjusted, or the
408
                 adjustment is now too large for a constant addition,
409
                 we cannot merge the two stack adjustments.
410
 
411
                 Also we need to be careful to not move stack pointer
412
                 such that we create stack accesses outside the allocated
413
                 area.  We can combine an allocation into the first insn,
414
                 or a deallocation into the second insn.  We can not
415
                 combine an allocation followed by a deallocation.
416
 
417
                 The only somewhat frequent occurrence of the later is when
418
                 a function allocates a stack frame but does not use it.
419
                 For this case, we would need to analyze rtl stream to be
420
                 sure that allocated area is really unused.  This means not
421
                 only checking the memory references, but also all registers
422
                 or global memory references possibly containing a stack
423
                 frame address.
424
 
425
                 Perhaps the best way to address this problem is to teach
426
                 gcc not to allocate stack for objects never used.  */
427
 
428
              /* Combine an allocation into the first instruction.  */
429
              if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
430
                {
431
                  if (try_apply_stack_adjustment (last_sp_set, reflist,
432
                                                  last_sp_adjust + this_adjust,
433
                                                  this_adjust))
434
                    {
435
                      if (RTX_FRAME_RELATED_P (last_sp_set))
436
                        adjust_frame_related_expr (last_sp_set, insn,
437
                                                   this_adjust);
438
                      /* It worked!  */
439
                      delete_insn (insn);
440
                      last_sp_adjust += this_adjust;
441
                      continue;
442
                    }
443
                }
444
 
445
              /* Otherwise we have a deallocation.  Do not combine with
446
                 a previous allocation.  Combine into the second insn.  */
447
              else if (STACK_GROWS_DOWNWARD
448
                       ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
449
                {
450
                  if (try_apply_stack_adjustment (insn, reflist,
451
                                                  last_sp_adjust + this_adjust,
452
                                                  -last_sp_adjust))
453
                    {
454
                      /* It worked!  */
455
                      delete_insn (last_sp_set);
456
                      last_sp_set = insn;
457
                      last_sp_adjust += this_adjust;
458
                      free_csa_reflist (reflist);
459
                      reflist = NULL;
460
                      continue;
461
                    }
462
                }
463
 
464
              /* Combination failed.  Restart processing from here.  If
465
                 deallocation+allocation conspired to cancel, we can
466
                 delete the old deallocation insn.  */
467
              if (last_sp_set && last_sp_adjust == 0)
468
                delete_insn (last_sp_set);
469
              free_csa_reflist (reflist);
470
              reflist = NULL;
471
              last_sp_set = insn;
472
              last_sp_adjust = this_adjust;
473
              continue;
474
            }
475
 
476
          /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
477
             the previous adjustment and turn it into a simple store.  This
478
             is equivalent to anticipating the stack adjustment so this must
479
             be an allocation.  */
480
          if (MEM_P (dest)
481
              && ((STACK_GROWS_DOWNWARD
482
                   ? (GET_CODE (XEXP (dest, 0)) == PRE_DEC
483
                      && last_sp_adjust
484
                         == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest)))
485
                   : (GET_CODE (XEXP (dest, 0)) == PRE_INC
486
                      && last_sp_adjust
487
                         == -(HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
488
                  || ((STACK_GROWS_DOWNWARD
489
                       ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
490
                      && GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
491
                      && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
492
                      && XEXP (XEXP (XEXP (dest, 0), 1), 0)
493
                         == stack_pointer_rtx
494
                      && GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
495
                         == CONST_INT
496
                      && INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
497
                         == -last_sp_adjust))
498
              && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
499
              && !reg_mentioned_p (stack_pointer_rtx, src)
500
              && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
501
              && try_apply_stack_adjustment (insn, reflist, 0,
502
                                             -last_sp_adjust))
503
            {
504
              delete_insn (last_sp_set);
505
              free_csa_reflist (reflist);
506
              reflist = NULL;
507
              last_sp_set = NULL_RTX;
508
              last_sp_adjust = 0;
509
              continue;
510
            }
511
        }
512
 
513
      data.insn = insn;
514
      data.reflist = reflist;
515
      if (!CALL_P (insn) && last_sp_set
516
          && !for_each_rtx (&PATTERN (insn), record_stack_refs, &data))
517
        {
518
           reflist = data.reflist;
519
           continue;
520
        }
521
      reflist = data.reflist;
522
 
523
      /* Otherwise, we were not able to process the instruction.
524
         Do not continue collecting data across such a one.  */
525
      if (last_sp_set
526
          && (CALL_P (insn)
527
              || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
528
        {
529
          if (last_sp_set && last_sp_adjust == 0)
530
            delete_insn (last_sp_set);
531
          free_csa_reflist (reflist);
532
          reflist = NULL;
533
          last_sp_set = NULL_RTX;
534
          last_sp_adjust = 0;
535
        }
536
    }
537
 
538
  if (last_sp_set && last_sp_adjust == 0)
539
    delete_insn (last_sp_set);
540
 
541
  if (reflist)
542
    free_csa_reflist (reflist);
543
}
544
 
545
 
546
static bool
547
gate_handle_stack_adjustments (void)
548
{
549
  return (optimize > 0);
550
}
551
 
552
static unsigned int
553
rest_of_handle_stack_adjustments (void)
554
{
555
  cleanup_cfg (flag_crossjumping ? CLEANUP_CROSSJUMP : 0);
556
 
557
  /* This is kind of a heuristic.  We need to run combine_stack_adjustments
558
     even for machines with possibly nonzero RETURN_POPS_ARGS
559
     and ACCUMULATE_OUTGOING_ARGS.  We expect that only ports having
560
     push instructions will have popping returns.  */
561
#ifndef PUSH_ROUNDING
562
  if (!ACCUMULATE_OUTGOING_ARGS)
563
#endif
564
    {
565
      df_note_add_problem ();
566
      df_analyze ();
567
      combine_stack_adjustments ();
568
    }
569
  return 0;
570
}
571
 
572
struct rtl_opt_pass pass_stack_adjustments =
573
{
574
 {
575
  RTL_PASS,
576
  "csa",                                /* name */
577
  gate_handle_stack_adjustments,        /* gate */
578
  rest_of_handle_stack_adjustments,     /* execute */
579
  NULL,                                 /* sub */
580
  NULL,                                 /* next */
581
  0,                                    /* static_pass_number */
582
  TV_COMBINE_STACK_ADJUST,              /* tv_id */
583
  0,                                    /* properties_required */
584
  0,                                    /* properties_provided */
585
  0,                                    /* properties_destroyed */
586
  0,                                    /* todo_flags_start */
587
  TODO_df_finish | TODO_verify_rtl_sharing |
588
  TODO_dump_func |
589
  TODO_ggc_collect,                     /* todo_flags_finish */
590
 }
591
};

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.