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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [combine-stack-adj.c] - Blame information for rev 684

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 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
   2010 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
 
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
/* Subroutine of combine_stack_adjustments, called for each basic block.  */
324
 
325
static void
326
combine_stack_adjustments_for_block (basic_block bb)
327
{
328
  HOST_WIDE_INT last_sp_adjust = 0;
329
  rtx last_sp_set = NULL_RTX;
330
  struct csa_reflist *reflist = NULL;
331
  rtx insn, next, set;
332
  struct record_stack_refs_data data;
333
  bool end_of_block = false;
334
 
335
  for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
336
    {
337
      end_of_block = insn == BB_END (bb);
338
      next = NEXT_INSN (insn);
339
 
340
      if (! INSN_P (insn))
341
        continue;
342
 
343
      set = single_set_for_csa (insn);
344
      if (set)
345
        {
346
          rtx dest = SET_DEST (set);
347
          rtx src = SET_SRC (set);
348
 
349
          /* Find constant additions to the stack pointer.  */
350
          if (dest == stack_pointer_rtx
351
              && GET_CODE (src) == PLUS
352
              && XEXP (src, 0) == stack_pointer_rtx
353
              && CONST_INT_P (XEXP (src, 1)))
354
            {
355
              HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
356
 
357
              /* If we've not seen an adjustment previously, record
358
                 it now and continue.  */
359
              if (! last_sp_set)
360
                {
361
                  last_sp_set = insn;
362
                  last_sp_adjust = this_adjust;
363
                  continue;
364
                }
365
 
366
              /* If not all recorded refs can be adjusted, or the
367
                 adjustment is now too large for a constant addition,
368
                 we cannot merge the two stack adjustments.
369
 
370
                 Also we need to be careful to not move stack pointer
371
                 such that we create stack accesses outside the allocated
372
                 area.  We can combine an allocation into the first insn,
373
                 or a deallocation into the second insn.  We can not
374
                 combine an allocation followed by a deallocation.
375
 
376
                 The only somewhat frequent occurrence of the later is when
377
                 a function allocates a stack frame but does not use it.
378
                 For this case, we would need to analyze rtl stream to be
379
                 sure that allocated area is really unused.  This means not
380
                 only checking the memory references, but also all registers
381
                 or global memory references possibly containing a stack
382
                 frame address.
383
 
384
                 Perhaps the best way to address this problem is to teach
385
                 gcc not to allocate stack for objects never used.  */
386
 
387
              /* Combine an allocation into the first instruction.  */
388
              if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
389
                {
390
                  if (try_apply_stack_adjustment (last_sp_set, reflist,
391
                                                  last_sp_adjust + this_adjust,
392
                                                  this_adjust))
393
                    {
394
                      maybe_move_args_size_note (last_sp_set, insn, false);
395
 
396
                      /* It worked!  */
397
                      delete_insn (insn);
398
                      last_sp_adjust += this_adjust;
399
                      continue;
400
                    }
401
                }
402
 
403
              /* Otherwise we have a deallocation.  Do not combine with
404
                 a previous allocation.  Combine into the second insn.  */
405
              else if (STACK_GROWS_DOWNWARD
406
                       ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
407
                {
408
                  if (try_apply_stack_adjustment (insn, reflist,
409
                                                  last_sp_adjust + this_adjust,
410
                                                  -last_sp_adjust))
411
                    {
412
                      maybe_move_args_size_note (insn, last_sp_set, true);
413
 
414
                      /* It worked!  */
415
                      delete_insn (last_sp_set);
416
                      last_sp_set = insn;
417
                      last_sp_adjust += this_adjust;
418
                      free_csa_reflist (reflist);
419
                      reflist = NULL;
420
                      continue;
421
                    }
422
                }
423
 
424
              /* Combination failed.  Restart processing from here.  If
425
                 deallocation+allocation conspired to cancel, we can
426
                 delete the old deallocation insn.  */
427
              if (last_sp_set && last_sp_adjust == 0)
428
                delete_insn (last_sp_set);
429
              free_csa_reflist (reflist);
430
              reflist = NULL;
431
              last_sp_set = insn;
432
              last_sp_adjust = this_adjust;
433
              continue;
434
            }
435
 
436
          /* Find a store with pre-(dec|inc)rement or pre-modify of exactly
437
             the previous adjustment and turn it into a simple store.  This
438
             is equivalent to anticipating the stack adjustment so this must
439
             be an allocation.  */
440
          if (MEM_P (dest)
441
              && ((STACK_GROWS_DOWNWARD
442
                   ? (GET_CODE (XEXP (dest, 0)) == PRE_DEC
443
                      && last_sp_adjust
444
                         == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest)))
445
                   : (GET_CODE (XEXP (dest, 0)) == PRE_INC
446
                      && last_sp_adjust
447
                         == -(HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
448
                  || ((STACK_GROWS_DOWNWARD
449
                       ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
450
                      && GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
451
                      && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
452
                      && XEXP (XEXP (XEXP (dest, 0), 1), 0)
453
                         == stack_pointer_rtx
454
                      && GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
455
                         == CONST_INT
456
                      && INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
457
                         == -last_sp_adjust))
458
              && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
459
              && !reg_mentioned_p (stack_pointer_rtx, src)
460
              && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
461
              && try_apply_stack_adjustment (insn, reflist, 0,
462
                                             -last_sp_adjust))
463
            {
464
              delete_insn (last_sp_set);
465
              free_csa_reflist (reflist);
466
              reflist = NULL;
467
              last_sp_set = NULL_RTX;
468
              last_sp_adjust = 0;
469
              continue;
470
            }
471
        }
472
 
473
      data.insn = insn;
474
      data.reflist = reflist;
475
      if (!CALL_P (insn) && last_sp_set
476
          && !for_each_rtx (&PATTERN (insn), record_stack_refs, &data))
477
        {
478
           reflist = data.reflist;
479
           continue;
480
        }
481
      reflist = data.reflist;
482
 
483
      /* Otherwise, we were not able to process the instruction.
484
         Do not continue collecting data across such a one.  */
485
      if (last_sp_set
486
          && (CALL_P (insn)
487
              || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
488
        {
489
          if (last_sp_set && last_sp_adjust == 0)
490
            delete_insn (last_sp_set);
491
          free_csa_reflist (reflist);
492
          reflist = NULL;
493
          last_sp_set = NULL_RTX;
494
          last_sp_adjust = 0;
495
        }
496
    }
497
 
498
  if (last_sp_set && last_sp_adjust == 0)
499
    delete_insn (last_sp_set);
500
 
501
  if (reflist)
502
    free_csa_reflist (reflist);
503
}
504
 
505
 
506
static bool
507
gate_handle_stack_adjustments (void)
508
{
509
  return flag_combine_stack_adjustments;
510
}
511
 
512
static unsigned int
513
rest_of_handle_stack_adjustments (void)
514
{
515
  cleanup_cfg (flag_crossjumping ? CLEANUP_CROSSJUMP : 0);
516
 
517
  /* This is kind of a heuristic.  We need to run combine_stack_adjustments
518
     even for machines with possibly nonzero TARGET_RETURN_POPS_ARGS
519
     and ACCUMULATE_OUTGOING_ARGS.  We expect that only ports having
520
     push instructions will have popping returns.  */
521
#ifndef PUSH_ROUNDING
522
  if (!ACCUMULATE_OUTGOING_ARGS)
523
#endif
524
    {
525
      df_note_add_problem ();
526
      df_analyze ();
527
      combine_stack_adjustments ();
528
    }
529
  return 0;
530
}
531
 
532
struct rtl_opt_pass pass_stack_adjustments =
533
{
534
 {
535
  RTL_PASS,
536
  "csa",                                /* name */
537
  gate_handle_stack_adjustments,        /* gate */
538
  rest_of_handle_stack_adjustments,     /* execute */
539
  NULL,                                 /* sub */
540
  NULL,                                 /* next */
541
  0,                                    /* static_pass_number */
542
  TV_COMBINE_STACK_ADJUST,              /* tv_id */
543
  0,                                    /* properties_required */
544
  0,                                    /* properties_provided */
545
  0,                                    /* properties_destroyed */
546
  0,                                    /* todo_flags_start */
547
  TODO_df_finish | TODO_verify_rtl_sharing |
548
  TODO_ggc_collect,                     /* todo_flags_finish */
549
 }
550
};

powered by: WebSVN 2.1.0

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