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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.2.2/] [gcc/] [cselib.c] - Blame information for rev 304

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Common subexpression elimination library for GNU compiler.
2
   Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3
   1999, 2000, 2001, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
 
26
#include "rtl.h"
27
#include "tm_p.h"
28
#include "regs.h"
29
#include "hard-reg-set.h"
30
#include "flags.h"
31
#include "real.h"
32
#include "insn-config.h"
33
#include "recog.h"
34
#include "function.h"
35
#include "emit-rtl.h"
36
#include "toplev.h"
37
#include "output.h"
38
#include "ggc.h"
39
#include "hashtab.h"
40
#include "cselib.h"
41
#include "params.h"
42
#include "alloc-pool.h"
43
#include "target.h"
44
 
45
static bool cselib_record_memory;
46
static int entry_and_rtx_equal_p (const void *, const void *);
47
static hashval_t get_value_hash (const void *);
48
static struct elt_list *new_elt_list (struct elt_list *, cselib_val *);
49
static struct elt_loc_list *new_elt_loc_list (struct elt_loc_list *, rtx);
50
static void unchain_one_value (cselib_val *);
51
static void unchain_one_elt_list (struct elt_list **);
52
static void unchain_one_elt_loc_list (struct elt_loc_list **);
53
static int discard_useless_locs (void **, void *);
54
static int discard_useless_values (void **, void *);
55
static void remove_useless_values (void);
56
static rtx wrap_constant (enum machine_mode, rtx);
57
static unsigned int cselib_hash_rtx (rtx, int);
58
static cselib_val *new_cselib_val (unsigned int, enum machine_mode);
59
static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
60
static cselib_val *cselib_lookup_mem (rtx, int);
61
static void cselib_invalidate_regno (unsigned int, enum machine_mode);
62
static void cselib_invalidate_mem (rtx);
63
static void cselib_record_set (rtx, cselib_val *, cselib_val *);
64
static void cselib_record_sets (rtx);
65
 
66
/* There are three ways in which cselib can look up an rtx:
67
   - for a REG, the reg_values table (which is indexed by regno) is used
68
   - for a MEM, we recursively look up its address and then follow the
69
     addr_list of that value
70
   - for everything else, we compute a hash value and go through the hash
71
     table.  Since different rtx's can still have the same hash value,
72
     this involves walking the table entries for a given value and comparing
73
     the locations of the entries with the rtx we are looking up.  */
74
 
75
/* A table that enables us to look up elts by their value.  */
76
static htab_t cselib_hash_table;
77
 
78
/* This is a global so we don't have to pass this through every function.
79
   It is used in new_elt_loc_list to set SETTING_INSN.  */
80
static rtx cselib_current_insn;
81
static bool cselib_current_insn_in_libcall;
82
 
83
/* Every new unknown value gets a unique number.  */
84
static unsigned int next_unknown_value;
85
 
86
/* The number of registers we had when the varrays were last resized.  */
87
static unsigned int cselib_nregs;
88
 
89
/* Count values without known locations.  Whenever this grows too big, we
90
   remove these useless values from the table.  */
91
static int n_useless_values;
92
 
93
/* Number of useless values before we remove them from the hash table.  */
94
#define MAX_USELESS_VALUES 32
95
 
96
/* This table maps from register number to values.  It does not
97
   contain pointers to cselib_val structures, but rather elt_lists.
98
   The purpose is to be able to refer to the same register in
99
   different modes.  The first element of the list defines the mode in
100
   which the register was set; if the mode is unknown or the value is
101
   no longer valid in that mode, ELT will be NULL for the first
102
   element.  */
103
static struct elt_list **reg_values;
104
static unsigned int reg_values_size;
105
#define REG_VALUES(i) reg_values[i]
106
 
107
/* The largest number of hard regs used by any entry added to the
108
   REG_VALUES table.  Cleared on each cselib_clear_table() invocation.  */
109
static unsigned int max_value_regs;
110
 
111
/* Here the set of indices I with REG_VALUES(I) != 0 is saved.  This is used
112
   in cselib_clear_table() for fast emptying.  */
113
static unsigned int *used_regs;
114
static unsigned int n_used_regs;
115
 
116
/* We pass this to cselib_invalidate_mem to invalidate all of
117
   memory for a non-const call instruction.  */
118
static GTY(()) rtx callmem;
119
 
120
/* Set by discard_useless_locs if it deleted the last location of any
121
   value.  */
122
static int values_became_useless;
123
 
124
/* Used as stop element of the containing_mem list so we can check
125
   presence in the list by checking the next pointer.  */
126
static cselib_val dummy_val;
127
 
128
/* Used to list all values that contain memory reference.
129
   May or may not contain the useless values - the list is compacted
130
   each time memory is invalidated.  */
131
static cselib_val *first_containing_mem = &dummy_val;
132
static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool;
133
 
134
 
135
/* Allocate a struct elt_list and fill in its two elements with the
136
   arguments.  */
137
 
138
static inline struct elt_list *
139
new_elt_list (struct elt_list *next, cselib_val *elt)
140
{
141
  struct elt_list *el;
142
  el = pool_alloc (elt_list_pool);
143
  el->next = next;
144
  el->elt = elt;
145
  return el;
146
}
147
 
148
/* Allocate a struct elt_loc_list and fill in its two elements with the
149
   arguments.  */
150
 
151
static inline struct elt_loc_list *
152
new_elt_loc_list (struct elt_loc_list *next, rtx loc)
153
{
154
  struct elt_loc_list *el;
155
  el = pool_alloc (elt_loc_list_pool);
156
  el->next = next;
157
  el->loc = loc;
158
  el->setting_insn = cselib_current_insn;
159
  el->in_libcall = cselib_current_insn_in_libcall;
160
  return el;
161
}
162
 
163
/* The elt_list at *PL is no longer needed.  Unchain it and free its
164
   storage.  */
165
 
166
static inline void
167
unchain_one_elt_list (struct elt_list **pl)
168
{
169
  struct elt_list *l = *pl;
170
 
171
  *pl = l->next;
172
  pool_free (elt_list_pool, l);
173
}
174
 
175
/* Likewise for elt_loc_lists.  */
176
 
177
static void
178
unchain_one_elt_loc_list (struct elt_loc_list **pl)
179
{
180
  struct elt_loc_list *l = *pl;
181
 
182
  *pl = l->next;
183
  pool_free (elt_loc_list_pool, l);
184
}
185
 
186
/* Likewise for cselib_vals.  This also frees the addr_list associated with
187
   V.  */
188
 
189
static void
190
unchain_one_value (cselib_val *v)
191
{
192
  while (v->addr_list)
193
    unchain_one_elt_list (&v->addr_list);
194
 
195
  pool_free (cselib_val_pool, v);
196
}
197
 
198
/* Remove all entries from the hash table.  Also used during
199
   initialization.  If CLEAR_ALL isn't set, then only clear the entries
200
   which are known to have been used.  */
201
 
202
void
203
cselib_clear_table (void)
204
{
205
  unsigned int i;
206
 
207
  for (i = 0; i < n_used_regs; i++)
208
    REG_VALUES (used_regs[i]) = 0;
209
 
210
  max_value_regs = 0;
211
 
212
  n_used_regs = 0;
213
 
214
  htab_empty (cselib_hash_table);
215
 
216
  n_useless_values = 0;
217
 
218
  next_unknown_value = 0;
219
 
220
  first_containing_mem = &dummy_val;
221
}
222
 
223
/* The equality test for our hash table.  The first argument ENTRY is a table
224
   element (i.e. a cselib_val), while the second arg X is an rtx.  We know
225
   that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
226
   CONST of an appropriate mode.  */
227
 
228
static int
229
entry_and_rtx_equal_p (const void *entry, const void *x_arg)
230
{
231
  struct elt_loc_list *l;
232
  const cselib_val *v = (const cselib_val *) entry;
233
  rtx x = (rtx) x_arg;
234
  enum machine_mode mode = GET_MODE (x);
235
 
236
  gcc_assert (GET_CODE (x) != CONST_INT
237
              && (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE));
238
 
239
  if (mode != GET_MODE (v->u.val_rtx))
240
    return 0;
241
 
242
  /* Unwrap X if necessary.  */
243
  if (GET_CODE (x) == CONST
244
      && (GET_CODE (XEXP (x, 0)) == CONST_INT
245
          || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))
246
    x = XEXP (x, 0);
247
 
248
  /* We don't guarantee that distinct rtx's have different hash values,
249
     so we need to do a comparison.  */
250
  for (l = v->locs; l; l = l->next)
251
    if (rtx_equal_for_cselib_p (l->loc, x))
252
      return 1;
253
 
254
  return 0;
255
}
256
 
257
/* The hash function for our hash table.  The value is always computed with
258
   cselib_hash_rtx when adding an element; this function just extracts the
259
   hash value from a cselib_val structure.  */
260
 
261
static hashval_t
262
get_value_hash (const void *entry)
263
{
264
  const cselib_val *v = (const cselib_val *) entry;
265
  return v->value;
266
}
267
 
268
/* Return true if X contains a VALUE rtx.  If ONLY_USELESS is set, we
269
   only return true for values which point to a cselib_val whose value
270
   element has been set to zero, which implies the cselib_val will be
271
   removed.  */
272
 
273
int
274
references_value_p (rtx x, int only_useless)
275
{
276
  enum rtx_code code = GET_CODE (x);
277
  const char *fmt = GET_RTX_FORMAT (code);
278
  int i, j;
279
 
280
  if (GET_CODE (x) == VALUE
281
      && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
282
    return 1;
283
 
284
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
285
    {
286
      if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
287
        return 1;
288
      else if (fmt[i] == 'E')
289
        for (j = 0; j < XVECLEN (x, i); j++)
290
          if (references_value_p (XVECEXP (x, i, j), only_useless))
291
            return 1;
292
    }
293
 
294
  return 0;
295
}
296
 
297
/* For all locations found in X, delete locations that reference useless
298
   values (i.e. values without any location).  Called through
299
   htab_traverse.  */
300
 
301
static int
302
discard_useless_locs (void **x, void *info ATTRIBUTE_UNUSED)
303
{
304
  cselib_val *v = (cselib_val *)*x;
305
  struct elt_loc_list **p = &v->locs;
306
  int had_locs = v->locs != 0;
307
 
308
  while (*p)
309
    {
310
      if (references_value_p ((*p)->loc, 1))
311
        unchain_one_elt_loc_list (p);
312
      else
313
        p = &(*p)->next;
314
    }
315
 
316
  if (had_locs && v->locs == 0)
317
    {
318
      n_useless_values++;
319
      values_became_useless = 1;
320
    }
321
  return 1;
322
}
323
 
324
/* If X is a value with no locations, remove it from the hashtable.  */
325
 
326
static int
327
discard_useless_values (void **x, void *info ATTRIBUTE_UNUSED)
328
{
329
  cselib_val *v = (cselib_val *)*x;
330
 
331
  if (v->locs == 0)
332
    {
333
      CSELIB_VAL_PTR (v->u.val_rtx) = NULL;
334
      htab_clear_slot (cselib_hash_table, x);
335
      unchain_one_value (v);
336
      n_useless_values--;
337
    }
338
 
339
  return 1;
340
}
341
 
342
/* Clean out useless values (i.e. those which no longer have locations
343
   associated with them) from the hash table.  */
344
 
345
static void
346
remove_useless_values (void)
347
{
348
  cselib_val **p, *v;
349
  /* First pass: eliminate locations that reference the value.  That in
350
     turn can make more values useless.  */
351
  do
352
    {
353
      values_became_useless = 0;
354
      htab_traverse (cselib_hash_table, discard_useless_locs, 0);
355
    }
356
  while (values_became_useless);
357
 
358
  /* Second pass: actually remove the values.  */
359
 
360
  p = &first_containing_mem;
361
  for (v = *p; v != &dummy_val; v = v->next_containing_mem)
362
    if (v->locs)
363
      {
364
        *p = v;
365
        p = &(*p)->next_containing_mem;
366
      }
367
  *p = &dummy_val;
368
 
369
  htab_traverse (cselib_hash_table, discard_useless_values, 0);
370
 
371
  gcc_assert (!n_useless_values);
372
}
373
 
374
/* Return the mode in which a register was last set.  If X is not a
375
   register, return its mode.  If the mode in which the register was
376
   set is not known, or the value was already clobbered, return
377
   VOIDmode.  */
378
 
379
enum machine_mode
380
cselib_reg_set_mode (rtx x)
381
{
382
  if (!REG_P (x))
383
    return GET_MODE (x);
384
 
385
  if (REG_VALUES (REGNO (x)) == NULL
386
      || REG_VALUES (REGNO (x))->elt == NULL)
387
    return VOIDmode;
388
 
389
  return GET_MODE (REG_VALUES (REGNO (x))->elt->u.val_rtx);
390
}
391
 
392
/* Return nonzero if we can prove that X and Y contain the same value, taking
393
   our gathered information into account.  */
394
 
395
int
396
rtx_equal_for_cselib_p (rtx x, rtx y)
397
{
398
  enum rtx_code code;
399
  const char *fmt;
400
  int i;
401
 
402
  if (REG_P (x) || MEM_P (x))
403
    {
404
      cselib_val *e = cselib_lookup (x, GET_MODE (x), 0);
405
 
406
      if (e)
407
        x = e->u.val_rtx;
408
    }
409
 
410
  if (REG_P (y) || MEM_P (y))
411
    {
412
      cselib_val *e = cselib_lookup (y, GET_MODE (y), 0);
413
 
414
      if (e)
415
        y = e->u.val_rtx;
416
    }
417
 
418
  if (x == y)
419
    return 1;
420
 
421
  if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
422
    return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
423
 
424
  if (GET_CODE (x) == VALUE)
425
    {
426
      cselib_val *e = CSELIB_VAL_PTR (x);
427
      struct elt_loc_list *l;
428
 
429
      for (l = e->locs; l; l = l->next)
430
        {
431
          rtx t = l->loc;
432
 
433
          /* Avoid infinite recursion.  */
434
          if (REG_P (t) || MEM_P (t))
435
            continue;
436
          else if (rtx_equal_for_cselib_p (t, y))
437
            return 1;
438
        }
439
 
440
      return 0;
441
    }
442
 
443
  if (GET_CODE (y) == VALUE)
444
    {
445
      cselib_val *e = CSELIB_VAL_PTR (y);
446
      struct elt_loc_list *l;
447
 
448
      for (l = e->locs; l; l = l->next)
449
        {
450
          rtx t = l->loc;
451
 
452
          if (REG_P (t) || MEM_P (t))
453
            continue;
454
          else if (rtx_equal_for_cselib_p (x, t))
455
            return 1;
456
        }
457
 
458
      return 0;
459
    }
460
 
461
  if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
462
    return 0;
463
 
464
  /* These won't be handled correctly by the code below.  */
465
  switch (GET_CODE (x))
466
    {
467
    case CONST_DOUBLE:
468
      return 0;
469
 
470
    case LABEL_REF:
471
      return XEXP (x, 0) == XEXP (y, 0);
472
 
473
    default:
474
      break;
475
    }
476
 
477
  code = GET_CODE (x);
478
  fmt = GET_RTX_FORMAT (code);
479
 
480
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
481
    {
482
      int j;
483
 
484
      switch (fmt[i])
485
        {
486
        case 'w':
487
          if (XWINT (x, i) != XWINT (y, i))
488
            return 0;
489
          break;
490
 
491
        case 'n':
492
        case 'i':
493
          if (XINT (x, i) != XINT (y, i))
494
            return 0;
495
          break;
496
 
497
        case 'V':
498
        case 'E':
499
          /* Two vectors must have the same length.  */
500
          if (XVECLEN (x, i) != XVECLEN (y, i))
501
            return 0;
502
 
503
          /* And the corresponding elements must match.  */
504
          for (j = 0; j < XVECLEN (x, i); j++)
505
            if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
506
                                          XVECEXP (y, i, j)))
507
              return 0;
508
          break;
509
 
510
        case 'e':
511
          if (i == 1
512
              && targetm.commutative_p (x, UNKNOWN)
513
              && rtx_equal_for_cselib_p (XEXP (x, 1), XEXP (y, 0))
514
              && rtx_equal_for_cselib_p (XEXP (x, 0), XEXP (y, 1)))
515
            return 1;
516
          if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
517
            return 0;
518
          break;
519
 
520
        case 'S':
521
        case 's':
522
          if (strcmp (XSTR (x, i), XSTR (y, i)))
523
            return 0;
524
          break;
525
 
526
        case 'u':
527
          /* These are just backpointers, so they don't matter.  */
528
          break;
529
 
530
        case '0':
531
        case 't':
532
          break;
533
 
534
          /* It is believed that rtx's at this level will never
535
             contain anything but integers and other rtx's,
536
             except for within LABEL_REFs and SYMBOL_REFs.  */
537
        default:
538
          gcc_unreachable ();
539
        }
540
    }
541
  return 1;
542
}
543
 
544
/* We need to pass down the mode of constants through the hash table
545
   functions.  For that purpose, wrap them in a CONST of the appropriate
546
   mode.  */
547
static rtx
548
wrap_constant (enum machine_mode mode, rtx x)
549
{
550
  if (GET_CODE (x) != CONST_INT
551
      && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode))
552
    return x;
553
  gcc_assert (mode != VOIDmode);
554
  return gen_rtx_CONST (mode, x);
555
}
556
 
557
/* Hash an rtx.  Return 0 if we couldn't hash the rtx.
558
   For registers and memory locations, we look up their cselib_val structure
559
   and return its VALUE element.
560
   Possible reasons for return 0 are: the object is volatile, or we couldn't
561
   find a register or memory location in the table and CREATE is zero.  If
562
   CREATE is nonzero, table elts are created for regs and mem.
563
   N.B. this hash function returns the same hash value for RTXes that
564
   differ only in the order of operands, thus it is suitable for comparisons
565
   that take commutativity into account.
566
   If we wanted to also support associative rules, we'd have to use a different
567
   strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
568
   We used to have a MODE argument for hashing for CONST_INTs, but that
569
   didn't make sense, since it caused spurious hash differences between
570
    (set (reg:SI 1) (const_int))
571
    (plus:SI (reg:SI 2) (reg:SI 1))
572
   and
573
    (plus:SI (reg:SI 2) (const_int))
574
   If the mode is important in any context, it must be checked specifically
575
   in a comparison anyway, since relying on hash differences is unsafe.  */
576
 
577
static unsigned int
578
cselib_hash_rtx (rtx x, int create)
579
{
580
  cselib_val *e;
581
  int i, j;
582
  enum rtx_code code;
583
  const char *fmt;
584
  unsigned int hash = 0;
585
 
586
  code = GET_CODE (x);
587
  hash += (unsigned) code + (unsigned) GET_MODE (x);
588
 
589
  switch (code)
590
    {
591
    case MEM:
592
    case REG:
593
      e = cselib_lookup (x, GET_MODE (x), create);
594
      if (! e)
595
        return 0;
596
 
597
      return e->value;
598
 
599
    case CONST_INT:
600
      hash += ((unsigned) CONST_INT << 7) + INTVAL (x);
601
      return hash ? hash : (unsigned int) CONST_INT;
602
 
603
    case CONST_DOUBLE:
604
      /* This is like the general case, except that it only counts
605
         the integers representing the constant.  */
606
      hash += (unsigned) code + (unsigned) GET_MODE (x);
607
      if (GET_MODE (x) != VOIDmode)
608
        hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
609
      else
610
        hash += ((unsigned) CONST_DOUBLE_LOW (x)
611
                 + (unsigned) CONST_DOUBLE_HIGH (x));
612
      return hash ? hash : (unsigned int) CONST_DOUBLE;
613
 
614
    case CONST_VECTOR:
615
      {
616
        int units;
617
        rtx elt;
618
 
619
        units = CONST_VECTOR_NUNITS (x);
620
 
621
        for (i = 0; i < units; ++i)
622
          {
623
            elt = CONST_VECTOR_ELT (x, i);
624
            hash += cselib_hash_rtx (elt, 0);
625
          }
626
 
627
        return hash;
628
      }
629
 
630
      /* Assume there is only one rtx object for any given label.  */
631
    case LABEL_REF:
632
      /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
633
         differences and differences between each stage's debugging dumps.  */
634
      hash += (((unsigned int) LABEL_REF << 7)
635
               + CODE_LABEL_NUMBER (XEXP (x, 0)));
636
      return hash ? hash : (unsigned int) LABEL_REF;
637
 
638
    case SYMBOL_REF:
639
      {
640
        /* Don't hash on the symbol's address to avoid bootstrap differences.
641
           Different hash values may cause expressions to be recorded in
642
           different orders and thus different registers to be used in the
643
           final assembler.  This also avoids differences in the dump files
644
           between various stages.  */
645
        unsigned int h = 0;
646
        const unsigned char *p = (const unsigned char *) XSTR (x, 0);
647
 
648
        while (*p)
649
          h += (h << 7) + *p++; /* ??? revisit */
650
 
651
        hash += ((unsigned int) SYMBOL_REF << 7) + h;
652
        return hash ? hash : (unsigned int) SYMBOL_REF;
653
      }
654
 
655
    case PRE_DEC:
656
    case PRE_INC:
657
    case POST_DEC:
658
    case POST_INC:
659
    case POST_MODIFY:
660
    case PRE_MODIFY:
661
    case PC:
662
    case CC0:
663
    case CALL:
664
    case UNSPEC_VOLATILE:
665
      return 0;
666
 
667
    case ASM_OPERANDS:
668
      if (MEM_VOLATILE_P (x))
669
        return 0;
670
 
671
      break;
672
 
673
    default:
674
      break;
675
    }
676
 
677
  i = GET_RTX_LENGTH (code) - 1;
678
  fmt = GET_RTX_FORMAT (code);
679
  for (; i >= 0; i--)
680
    {
681
      switch (fmt[i])
682
        {
683
        case 'e':
684
          {
685
            rtx tem = XEXP (x, i);
686
            unsigned int tem_hash = cselib_hash_rtx (tem, create);
687
 
688
            if (tem_hash == 0)
689
              return 0;
690
 
691
            hash += tem_hash;
692
          }
693
          break;
694
        case 'E':
695
          for (j = 0; j < XVECLEN (x, i); j++)
696
            {
697
              unsigned int tem_hash
698
                = cselib_hash_rtx (XVECEXP (x, i, j), create);
699
 
700
              if (tem_hash == 0)
701
                return 0;
702
 
703
              hash += tem_hash;
704
            }
705
          break;
706
 
707
        case 's':
708
          {
709
            const unsigned char *p = (const unsigned char *) XSTR (x, i);
710
 
711
            if (p)
712
              while (*p)
713
                hash += *p++;
714
            break;
715
          }
716
 
717
        case 'i':
718
          hash += XINT (x, i);
719
          break;
720
 
721
        case '0':
722
        case 't':
723
          /* unused */
724
          break;
725
 
726
        default:
727
          gcc_unreachable ();
728
        }
729
    }
730
 
731
  return hash ? hash : 1 + (unsigned int) GET_CODE (x);
732
}
733
 
734
/* Create a new value structure for VALUE and initialize it.  The mode of the
735
   value is MODE.  */
736
 
737
static inline cselib_val *
738
new_cselib_val (unsigned int value, enum machine_mode mode)
739
{
740
  cselib_val *e = pool_alloc (cselib_val_pool);
741
 
742
  gcc_assert (value);
743
 
744
  e->value = value;
745
  /* We use an alloc pool to allocate this RTL construct because it
746
     accounts for about 8% of the overall memory usage.  We know
747
     precisely when we can have VALUE RTXen (when cselib is active)
748
     so we don't need to put them in garbage collected memory.
749
     ??? Why should a VALUE be an RTX in the first place?  */
750
  e->u.val_rtx = pool_alloc (value_pool);
751
  memset (e->u.val_rtx, 0, RTX_HDR_SIZE);
752
  PUT_CODE (e->u.val_rtx, VALUE);
753
  PUT_MODE (e->u.val_rtx, mode);
754
  CSELIB_VAL_PTR (e->u.val_rtx) = e;
755
  e->addr_list = 0;
756
  e->locs = 0;
757
  e->next_containing_mem = 0;
758
  return e;
759
}
760
 
761
/* ADDR_ELT is a value that is used as address.  MEM_ELT is the value that
762
   contains the data at this address.  X is a MEM that represents the
763
   value.  Update the two value structures to represent this situation.  */
764
 
765
static void
766
add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
767
{
768
  struct elt_loc_list *l;
769
 
770
  /* Avoid duplicates.  */
771
  for (l = mem_elt->locs; l; l = l->next)
772
    if (MEM_P (l->loc)
773
        && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
774
      return;
775
 
776
  addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
777
  mem_elt->locs
778
    = new_elt_loc_list (mem_elt->locs,
779
                        replace_equiv_address_nv (x, addr_elt->u.val_rtx));
780
  if (mem_elt->next_containing_mem == NULL)
781
    {
782
      mem_elt->next_containing_mem = first_containing_mem;
783
      first_containing_mem = mem_elt;
784
    }
785
}
786
 
787
/* Subroutine of cselib_lookup.  Return a value for X, which is a MEM rtx.
788
   If CREATE, make a new one if we haven't seen it before.  */
789
 
790
static cselib_val *
791
cselib_lookup_mem (rtx x, int create)
792
{
793
  enum machine_mode mode = GET_MODE (x);
794
  void **slot;
795
  cselib_val *addr;
796
  cselib_val *mem_elt;
797
  struct elt_list *l;
798
 
799
  if (MEM_VOLATILE_P (x) || mode == BLKmode
800
      || !cselib_record_memory
801
      || (FLOAT_MODE_P (mode) && flag_float_store))
802
    return 0;
803
 
804
  /* Look up the value for the address.  */
805
  addr = cselib_lookup (XEXP (x, 0), mode, create);
806
  if (! addr)
807
    return 0;
808
 
809
  /* Find a value that describes a value of our mode at that address.  */
810
  for (l = addr->addr_list; l; l = l->next)
811
    if (GET_MODE (l->elt->u.val_rtx) == mode)
812
      return l->elt;
813
 
814
  if (! create)
815
    return 0;
816
 
817
  mem_elt = new_cselib_val (++next_unknown_value, mode);
818
  add_mem_for_addr (addr, mem_elt, x);
819
  slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
820
                                   mem_elt->value, INSERT);
821
  *slot = mem_elt;
822
  return mem_elt;
823
}
824
 
825
/* Walk rtx X and replace all occurrences of REG and MEM subexpressions
826
   with VALUE expressions.  This way, it becomes independent of changes
827
   to registers and memory.
828
   X isn't actually modified; if modifications are needed, new rtl is
829
   allocated.  However, the return value can share rtl with X.  */
830
 
831
rtx
832
cselib_subst_to_values (rtx x)
833
{
834
  enum rtx_code code = GET_CODE (x);
835
  const char *fmt = GET_RTX_FORMAT (code);
836
  cselib_val *e;
837
  struct elt_list *l;
838
  rtx copy = x;
839
  int i;
840
 
841
  switch (code)
842
    {
843
    case REG:
844
      l = REG_VALUES (REGNO (x));
845
      if (l && l->elt == NULL)
846
        l = l->next;
847
      for (; l; l = l->next)
848
        if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
849
          return l->elt->u.val_rtx;
850
 
851
      gcc_unreachable ();
852
 
853
    case MEM:
854
      e = cselib_lookup_mem (x, 0);
855
      if (! e)
856
        {
857
          /* This happens for autoincrements.  Assign a value that doesn't
858
             match any other.  */
859
          e = new_cselib_val (++next_unknown_value, GET_MODE (x));
860
        }
861
      return e->u.val_rtx;
862
 
863
    case CONST_DOUBLE:
864
    case CONST_VECTOR:
865
    case CONST_INT:
866
      return x;
867
 
868
    case POST_INC:
869
    case PRE_INC:
870
    case POST_DEC:
871
    case PRE_DEC:
872
    case POST_MODIFY:
873
    case PRE_MODIFY:
874
      e = new_cselib_val (++next_unknown_value, GET_MODE (x));
875
      return e->u.val_rtx;
876
 
877
    default:
878
      break;
879
    }
880
 
881
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
882
    {
883
      if (fmt[i] == 'e')
884
        {
885
          rtx t = cselib_subst_to_values (XEXP (x, i));
886
 
887
          if (t != XEXP (x, i) && x == copy)
888
            copy = shallow_copy_rtx (x);
889
 
890
          XEXP (copy, i) = t;
891
        }
892
      else if (fmt[i] == 'E')
893
        {
894
          int j, k;
895
 
896
          for (j = 0; j < XVECLEN (x, i); j++)
897
            {
898
              rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
899
 
900
              if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
901
                {
902
                  if (x == copy)
903
                    copy = shallow_copy_rtx (x);
904
 
905
                  XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
906
                  for (k = 0; k < j; k++)
907
                    XVECEXP (copy, i, k) = XVECEXP (x, i, k);
908
                }
909
 
910
              XVECEXP (copy, i, j) = t;
911
            }
912
        }
913
    }
914
 
915
  return copy;
916
}
917
 
918
/* Look up the rtl expression X in our tables and return the value it has.
919
   If CREATE is zero, we return NULL if we don't know the value.  Otherwise,
920
   we create a new one if possible, using mode MODE if X doesn't have a mode
921
   (i.e. because it's a constant).  */
922
 
923
cselib_val *
924
cselib_lookup (rtx x, enum machine_mode mode, int create)
925
{
926
  void **slot;
927
  cselib_val *e;
928
  unsigned int hashval;
929
 
930
  if (GET_MODE (x) != VOIDmode)
931
    mode = GET_MODE (x);
932
 
933
  if (GET_CODE (x) == VALUE)
934
    return CSELIB_VAL_PTR (x);
935
 
936
  if (REG_P (x))
937
    {
938
      struct elt_list *l;
939
      unsigned int i = REGNO (x);
940
 
941
      l = REG_VALUES (i);
942
      if (l && l->elt == NULL)
943
        l = l->next;
944
      for (; l; l = l->next)
945
        if (mode == GET_MODE (l->elt->u.val_rtx))
946
          return l->elt;
947
 
948
      if (! create)
949
        return 0;
950
 
951
      if (i < FIRST_PSEUDO_REGISTER)
952
        {
953
          unsigned int n = hard_regno_nregs[i][mode];
954
 
955
          if (n > max_value_regs)
956
            max_value_regs = n;
957
        }
958
 
959
      e = new_cselib_val (++next_unknown_value, GET_MODE (x));
960
      e->locs = new_elt_loc_list (e->locs, x);
961
      if (REG_VALUES (i) == 0)
962
        {
963
          /* Maintain the invariant that the first entry of
964
             REG_VALUES, if present, must be the value used to set the
965
             register, or NULL.  */
966
          used_regs[n_used_regs++] = i;
967
          REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
968
        }
969
      REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
970
      slot = htab_find_slot_with_hash (cselib_hash_table, x, e->value, INSERT);
971
      *slot = e;
972
      return e;
973
    }
974
 
975
  if (MEM_P (x))
976
    return cselib_lookup_mem (x, create);
977
 
978
  hashval = cselib_hash_rtx (x, create);
979
  /* Can't even create if hashing is not possible.  */
980
  if (! hashval)
981
    return 0;
982
 
983
  slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
984
                                   hashval, create ? INSERT : NO_INSERT);
985
  if (slot == 0)
986
    return 0;
987
 
988
  e = (cselib_val *) *slot;
989
  if (e)
990
    return e;
991
 
992
  e = new_cselib_val (hashval, mode);
993
 
994
  /* We have to fill the slot before calling cselib_subst_to_values:
995
     the hash table is inconsistent until we do so, and
996
     cselib_subst_to_values will need to do lookups.  */
997
  *slot = (void *) e;
998
  e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
999
  return e;
1000
}
1001
 
1002
/* Invalidate any entries in reg_values that overlap REGNO.  This is called
1003
   if REGNO is changing.  MODE is the mode of the assignment to REGNO, which
1004
   is used to determine how many hard registers are being changed.  If MODE
1005
   is VOIDmode, then only REGNO is being changed; this is used when
1006
   invalidating call clobbered registers across a call.  */
1007
 
1008
static void
1009
cselib_invalidate_regno (unsigned int regno, enum machine_mode mode)
1010
{
1011
  unsigned int endregno;
1012
  unsigned int i;
1013
 
1014
  /* If we see pseudos after reload, something is _wrong_.  */
1015
  gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
1016
              || reg_renumber[regno] < 0);
1017
 
1018
  /* Determine the range of registers that must be invalidated.  For
1019
     pseudos, only REGNO is affected.  For hard regs, we must take MODE
1020
     into account, and we must also invalidate lower register numbers
1021
     if they contain values that overlap REGNO.  */
1022
  if (regno < FIRST_PSEUDO_REGISTER)
1023
    {
1024
      gcc_assert (mode != VOIDmode);
1025
 
1026
      if (regno < max_value_regs)
1027
        i = 0;
1028
      else
1029
        i = regno - max_value_regs;
1030
 
1031
      endregno = regno + hard_regno_nregs[regno][mode];
1032
    }
1033
  else
1034
    {
1035
      i = regno;
1036
      endregno = regno + 1;
1037
    }
1038
 
1039
  for (; i < endregno; i++)
1040
    {
1041
      struct elt_list **l = &REG_VALUES (i);
1042
 
1043
      /* Go through all known values for this reg; if it overlaps the range
1044
         we're invalidating, remove the value.  */
1045
      while (*l)
1046
        {
1047
          cselib_val *v = (*l)->elt;
1048
          struct elt_loc_list **p;
1049
          unsigned int this_last = i;
1050
 
1051
          if (i < FIRST_PSEUDO_REGISTER && v != NULL)
1052
            this_last += hard_regno_nregs[i][GET_MODE (v->u.val_rtx)] - 1;
1053
 
1054
          if (this_last < regno || v == NULL)
1055
            {
1056
              l = &(*l)->next;
1057
              continue;
1058
            }
1059
 
1060
          /* We have an overlap.  */
1061
          if (*l == REG_VALUES (i))
1062
            {
1063
              /* Maintain the invariant that the first entry of
1064
                 REG_VALUES, if present, must be the value used to set
1065
                 the register, or NULL.  This is also nice because
1066
                 then we won't push the same regno onto user_regs
1067
                 multiple times.  */
1068
              (*l)->elt = NULL;
1069
              l = &(*l)->next;
1070
            }
1071
          else
1072
            unchain_one_elt_list (l);
1073
 
1074
          /* Now, we clear the mapping from value to reg.  It must exist, so
1075
             this code will crash intentionally if it doesn't.  */
1076
          for (p = &v->locs; ; p = &(*p)->next)
1077
            {
1078
              rtx x = (*p)->loc;
1079
 
1080
              if (REG_P (x) && REGNO (x) == i)
1081
                {
1082
                  unchain_one_elt_loc_list (p);
1083
                  break;
1084
                }
1085
            }
1086
          if (v->locs == 0)
1087
            n_useless_values++;
1088
        }
1089
    }
1090
}
1091
 
1092
/* Return 1 if X has a value that can vary even between two
1093
   executions of the program.  0 means X can be compared reliably
1094
   against certain constants or near-constants.  */
1095
 
1096
static int
1097
cselib_rtx_varies_p (rtx x ATTRIBUTE_UNUSED, int from_alias ATTRIBUTE_UNUSED)
1098
{
1099
  /* We actually don't need to verify very hard.  This is because
1100
     if X has actually changed, we invalidate the memory anyway,
1101
     so assume that all common memory addresses are
1102
     invariant.  */
1103
  return 0;
1104
}
1105
 
1106
/* Invalidate any locations in the table which are changed because of a
1107
   store to MEM_RTX.  If this is called because of a non-const call
1108
   instruction, MEM_RTX is (mem:BLK const0_rtx).  */
1109
 
1110
static void
1111
cselib_invalidate_mem (rtx mem_rtx)
1112
{
1113
  cselib_val **vp, *v, *next;
1114
  int num_mems = 0;
1115
  rtx mem_addr;
1116
 
1117
  mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
1118
  mem_rtx = canon_rtx (mem_rtx);
1119
 
1120
  vp = &first_containing_mem;
1121
  for (v = *vp; v != &dummy_val; v = next)
1122
    {
1123
      bool has_mem = false;
1124
      struct elt_loc_list **p = &v->locs;
1125
      int had_locs = v->locs != 0;
1126
 
1127
      while (*p)
1128
        {
1129
          rtx x = (*p)->loc;
1130
          cselib_val *addr;
1131
          struct elt_list **mem_chain;
1132
 
1133
          /* MEMs may occur in locations only at the top level; below
1134
             that every MEM or REG is substituted by its VALUE.  */
1135
          if (!MEM_P (x))
1136
            {
1137
              p = &(*p)->next;
1138
              continue;
1139
            }
1140
          if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
1141
              && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
1142
                                          x, cselib_rtx_varies_p))
1143
            {
1144
              has_mem = true;
1145
              num_mems++;
1146
              p = &(*p)->next;
1147
              continue;
1148
            }
1149
 
1150
          /* This one overlaps.  */
1151
          /* We must have a mapping from this MEM's address to the
1152
             value (E).  Remove that, too.  */
1153
          addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
1154
          mem_chain = &addr->addr_list;
1155
          for (;;)
1156
            {
1157
              if ((*mem_chain)->elt == v)
1158
                {
1159
                  unchain_one_elt_list (mem_chain);
1160
                  break;
1161
                }
1162
 
1163
              mem_chain = &(*mem_chain)->next;
1164
            }
1165
 
1166
          unchain_one_elt_loc_list (p);
1167
        }
1168
 
1169
      if (had_locs && v->locs == 0)
1170
        n_useless_values++;
1171
 
1172
      next = v->next_containing_mem;
1173
      if (has_mem)
1174
        {
1175
          *vp = v;
1176
          vp = &(*vp)->next_containing_mem;
1177
        }
1178
      else
1179
        v->next_containing_mem = NULL;
1180
    }
1181
  *vp = &dummy_val;
1182
}
1183
 
1184
/* Invalidate DEST, which is being assigned to or clobbered.  */
1185
 
1186
void
1187
cselib_invalidate_rtx (rtx dest)
1188
{
1189
  while (GET_CODE (dest) == SUBREG
1190
         || GET_CODE (dest) == ZERO_EXTRACT
1191
         || GET_CODE (dest) == STRICT_LOW_PART)
1192
    dest = XEXP (dest, 0);
1193
 
1194
  if (REG_P (dest))
1195
    cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
1196
  else if (MEM_P (dest))
1197
    cselib_invalidate_mem (dest);
1198
 
1199
  /* Some machines don't define AUTO_INC_DEC, but they still use push
1200
     instructions.  We need to catch that case here in order to
1201
     invalidate the stack pointer correctly.  Note that invalidating
1202
     the stack pointer is different from invalidating DEST.  */
1203
  if (push_operand (dest, GET_MODE (dest)))
1204
    cselib_invalidate_rtx (stack_pointer_rtx);
1205
}
1206
 
1207
/* A wrapper for cselib_invalidate_rtx to be called via note_stores.  */
1208
 
1209
static void
1210
cselib_invalidate_rtx_note_stores (rtx dest, rtx ignore ATTRIBUTE_UNUSED,
1211
                                   void *data ATTRIBUTE_UNUSED)
1212
{
1213
  cselib_invalidate_rtx (dest);
1214
}
1215
 
1216
/* Record the result of a SET instruction.  DEST is being set; the source
1217
   contains the value described by SRC_ELT.  If DEST is a MEM, DEST_ADDR_ELT
1218
   describes its address.  */
1219
 
1220
static void
1221
cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
1222
{
1223
  int dreg = REG_P (dest) ? (int) REGNO (dest) : -1;
1224
 
1225
  if (src_elt == 0 || side_effects_p (dest))
1226
    return;
1227
 
1228
  if (dreg >= 0)
1229
    {
1230
      if (dreg < FIRST_PSEUDO_REGISTER)
1231
        {
1232
          unsigned int n = hard_regno_nregs[dreg][GET_MODE (dest)];
1233
 
1234
          if (n > max_value_regs)
1235
            max_value_regs = n;
1236
        }
1237
 
1238
      if (REG_VALUES (dreg) == 0)
1239
        {
1240
          used_regs[n_used_regs++] = dreg;
1241
          REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
1242
        }
1243
      else
1244
        {
1245
          /* The register should have been invalidated.  */
1246
          gcc_assert (REG_VALUES (dreg)->elt == 0);
1247
          REG_VALUES (dreg)->elt = src_elt;
1248
        }
1249
 
1250
      if (src_elt->locs == 0)
1251
        n_useless_values--;
1252
      src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
1253
    }
1254
  else if (MEM_P (dest) && dest_addr_elt != 0
1255
           && cselib_record_memory)
1256
    {
1257
      if (src_elt->locs == 0)
1258
        n_useless_values--;
1259
      add_mem_for_addr (dest_addr_elt, src_elt, dest);
1260
    }
1261
}
1262
 
1263
/* Describe a single set that is part of an insn.  */
1264
struct set
1265
{
1266
  rtx src;
1267
  rtx dest;
1268
  cselib_val *src_elt;
1269
  cselib_val *dest_addr_elt;
1270
};
1271
 
1272
/* There is no good way to determine how many elements there can be
1273
   in a PARALLEL.  Since it's fairly cheap, use a really large number.  */
1274
#define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1275
 
1276
/* Record the effects of any sets in INSN.  */
1277
static void
1278
cselib_record_sets (rtx insn)
1279
{
1280
  int n_sets = 0;
1281
  int i;
1282
  struct set sets[MAX_SETS];
1283
  rtx body = PATTERN (insn);
1284
  rtx cond = 0;
1285
 
1286
  body = PATTERN (insn);
1287
  if (GET_CODE (body) == COND_EXEC)
1288
    {
1289
      cond = COND_EXEC_TEST (body);
1290
      body = COND_EXEC_CODE (body);
1291
    }
1292
 
1293
  /* Find all sets.  */
1294
  if (GET_CODE (body) == SET)
1295
    {
1296
      sets[0].src = SET_SRC (body);
1297
      sets[0].dest = SET_DEST (body);
1298
      n_sets = 1;
1299
    }
1300
  else if (GET_CODE (body) == PARALLEL)
1301
    {
1302
      /* Look through the PARALLEL and record the values being
1303
         set, if possible.  Also handle any CLOBBERs.  */
1304
      for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
1305
        {
1306
          rtx x = XVECEXP (body, 0, i);
1307
 
1308
          if (GET_CODE (x) == SET)
1309
            {
1310
              sets[n_sets].src = SET_SRC (x);
1311
              sets[n_sets].dest = SET_DEST (x);
1312
              n_sets++;
1313
            }
1314
        }
1315
    }
1316
 
1317
  /* Look up the values that are read.  Do this before invalidating the
1318
     locations that are written.  */
1319
  for (i = 0; i < n_sets; i++)
1320
    {
1321
      rtx dest = sets[i].dest;
1322
 
1323
      /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1324
         the low part after invalidating any knowledge about larger modes.  */
1325
      if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
1326
        sets[i].dest = dest = XEXP (dest, 0);
1327
 
1328
      /* We don't know how to record anything but REG or MEM.  */
1329
      if (REG_P (dest)
1330
          || (MEM_P (dest) && cselib_record_memory))
1331
        {
1332
          rtx src = sets[i].src;
1333
          if (cond)
1334
            src = gen_rtx_IF_THEN_ELSE (GET_MODE (src), cond, src, dest);
1335
          sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1);
1336
          if (MEM_P (dest))
1337
            sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1);
1338
          else
1339
            sets[i].dest_addr_elt = 0;
1340
        }
1341
    }
1342
 
1343
  /* Invalidate all locations written by this insn.  Note that the elts we
1344
     looked up in the previous loop aren't affected, just some of their
1345
     locations may go away.  */
1346
  note_stores (body, cselib_invalidate_rtx_note_stores, NULL);
1347
 
1348
  /* If this is an asm, look for duplicate sets.  This can happen when the
1349
     user uses the same value as an output multiple times.  This is valid
1350
     if the outputs are not actually used thereafter.  Treat this case as
1351
     if the value isn't actually set.  We do this by smashing the destination
1352
     to pc_rtx, so that we won't record the value later.  */
1353
  if (n_sets >= 2 && asm_noperands (body) >= 0)
1354
    {
1355
      for (i = 0; i < n_sets; i++)
1356
        {
1357
          rtx dest = sets[i].dest;
1358
          if (REG_P (dest) || MEM_P (dest))
1359
            {
1360
              int j;
1361
              for (j = i + 1; j < n_sets; j++)
1362
                if (rtx_equal_p (dest, sets[j].dest))
1363
                  {
1364
                    sets[i].dest = pc_rtx;
1365
                    sets[j].dest = pc_rtx;
1366
                  }
1367
            }
1368
        }
1369
    }
1370
 
1371
  /* Now enter the equivalences in our tables.  */
1372
  for (i = 0; i < n_sets; i++)
1373
    {
1374
      rtx dest = sets[i].dest;
1375
      if (REG_P (dest)
1376
          || (MEM_P (dest) && cselib_record_memory))
1377
        cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
1378
    }
1379
}
1380
 
1381
/* Record the effects of INSN.  */
1382
 
1383
void
1384
cselib_process_insn (rtx insn)
1385
{
1386
  int i;
1387
  rtx x;
1388
 
1389
  if (find_reg_note (insn, REG_LIBCALL, NULL))
1390
    cselib_current_insn_in_libcall = true;
1391
  cselib_current_insn = insn;
1392
 
1393
  /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp.  */
1394
  if (LABEL_P (insn)
1395
      || (CALL_P (insn)
1396
          && find_reg_note (insn, REG_SETJMP, NULL))
1397
      || (NONJUMP_INSN_P (insn)
1398
          && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
1399
          && MEM_VOLATILE_P (PATTERN (insn))))
1400
    {
1401
      if (find_reg_note (insn, REG_RETVAL, NULL))
1402
        cselib_current_insn_in_libcall = false;
1403
      cselib_clear_table ();
1404
      return;
1405
    }
1406
 
1407
  if (! INSN_P (insn))
1408
    {
1409
      if (find_reg_note (insn, REG_RETVAL, NULL))
1410
        cselib_current_insn_in_libcall = false;
1411
      cselib_current_insn = 0;
1412
      return;
1413
    }
1414
 
1415
  /* If this is a call instruction, forget anything stored in a
1416
     call clobbered register, or, if this is not a const call, in
1417
     memory.  */
1418
  if (CALL_P (insn))
1419
    {
1420
      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1421
        if (call_used_regs[i]
1422
            || (REG_VALUES (i) && REG_VALUES (i)->elt
1423
                && HARD_REGNO_CALL_PART_CLOBBERED (i,
1424
                      GET_MODE (REG_VALUES (i)->elt->u.val_rtx))))
1425
          cselib_invalidate_regno (i, reg_raw_mode[i]);
1426
 
1427
      if (! CONST_OR_PURE_CALL_P (insn))
1428
        cselib_invalidate_mem (callmem);
1429
    }
1430
 
1431
  cselib_record_sets (insn);
1432
 
1433
#ifdef AUTO_INC_DEC
1434
  /* Clobber any registers which appear in REG_INC notes.  We
1435
     could keep track of the changes to their values, but it is
1436
     unlikely to help.  */
1437
  for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1438
    if (REG_NOTE_KIND (x) == REG_INC)
1439
      cselib_invalidate_rtx (XEXP (x, 0));
1440
#endif
1441
 
1442
  /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1443
     after we have processed the insn.  */
1444
  if (CALL_P (insn))
1445
    for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
1446
      if (GET_CODE (XEXP (x, 0)) == CLOBBER)
1447
        cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
1448
 
1449
  if (find_reg_note (insn, REG_RETVAL, NULL))
1450
    cselib_current_insn_in_libcall = false;
1451
  cselib_current_insn = 0;
1452
 
1453
  if (n_useless_values > MAX_USELESS_VALUES
1454
      /* remove_useless_values is linear in the hash table size.  Avoid
1455
         quadratic behaviour for very large hashtables with very few
1456
         useless elements.  */
1457
      && (unsigned int)n_useless_values > cselib_hash_table->n_elements / 4)
1458
    remove_useless_values ();
1459
}
1460
 
1461
/* Initialize cselib for one pass.  The caller must also call
1462
   init_alias_analysis.  */
1463
 
1464
void
1465
cselib_init (bool record_memory)
1466
{
1467
  elt_list_pool = create_alloc_pool ("elt_list",
1468
                                     sizeof (struct elt_list), 10);
1469
  elt_loc_list_pool = create_alloc_pool ("elt_loc_list",
1470
                                         sizeof (struct elt_loc_list), 10);
1471
  cselib_val_pool = create_alloc_pool ("cselib_val_list",
1472
                                       sizeof (cselib_val), 10);
1473
  value_pool = create_alloc_pool ("value", RTX_CODE_SIZE (VALUE), 100);
1474
  cselib_record_memory = record_memory;
1475
  /* This is only created once.  */
1476
  if (! callmem)
1477
    callmem = gen_rtx_MEM (BLKmode, const0_rtx);
1478
 
1479
  cselib_nregs = max_reg_num ();
1480
 
1481
  /* We preserve reg_values to allow expensive clearing of the whole thing.
1482
     Reallocate it however if it happens to be too large.  */
1483
  if (!reg_values || reg_values_size < cselib_nregs
1484
      || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
1485
    {
1486
      if (reg_values)
1487
        free (reg_values);
1488
      /* Some space for newly emit instructions so we don't end up
1489
         reallocating in between passes.  */
1490
      reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
1491
      reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
1492
    }
1493
  used_regs = XNEWVEC (unsigned int, cselib_nregs);
1494
  n_used_regs = 0;
1495
  cselib_hash_table = htab_create (31, get_value_hash,
1496
                                   entry_and_rtx_equal_p, NULL);
1497
  cselib_current_insn_in_libcall = false;
1498
}
1499
 
1500
/* Called when the current user is done with cselib.  */
1501
 
1502
void
1503
cselib_finish (void)
1504
{
1505
  free_alloc_pool (elt_list_pool);
1506
  free_alloc_pool (elt_loc_list_pool);
1507
  free_alloc_pool (cselib_val_pool);
1508
  free_alloc_pool (value_pool);
1509
  cselib_clear_table ();
1510
  htab_delete (cselib_hash_table);
1511
  free (used_regs);
1512
  used_regs = 0;
1513
  cselib_hash_table = 0;
1514
  n_useless_values = 0;
1515
  next_unknown_value = 0;
1516
}
1517
 
1518
#include "gt-cselib.h"

powered by: WebSVN 2.1.0

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