forked from illumos/gcc
-
Notifications
You must be signed in to change notification settings - Fork 1
/
cselib.c
2379 lines (2002 loc) · 62.6 KB
/
cselib.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/* Common subexpression elimination library for GNU compiler.
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "tm_p.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
#include "insn-config.h"
#include "recog.h"
#include "function.h"
#include "emit-rtl.h"
#include "toplev.h"
#include "output.h"
#include "ggc.h"
#include "hashtab.h"
#include "tree-pass.h"
#include "cselib.h"
#include "params.h"
#include "alloc-pool.h"
#include "target.h"
#include "bitmap.h"
static bool cselib_record_memory;
static bool cselib_preserve_constants;
static int entry_and_rtx_equal_p (const void *, const void *);
static hashval_t get_value_hash (const void *);
static struct elt_list *new_elt_list (struct elt_list *, cselib_val *);
static struct elt_loc_list *new_elt_loc_list (struct elt_loc_list *, rtx);
static void unchain_one_value (cselib_val *);
static void unchain_one_elt_list (struct elt_list **);
static void unchain_one_elt_loc_list (struct elt_loc_list **);
static int discard_useless_locs (void **, void *);
static int discard_useless_values (void **, void *);
static void remove_useless_values (void);
static unsigned int cselib_hash_rtx (rtx, int);
static cselib_val *new_cselib_val (unsigned int, enum machine_mode, rtx);
static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
static cselib_val *cselib_lookup_mem (rtx, int);
static void cselib_invalidate_regno (unsigned int, enum machine_mode);
static void cselib_invalidate_mem (rtx);
static void cselib_record_set (rtx, cselib_val *, cselib_val *);
static void cselib_record_sets (rtx);
struct expand_value_data
{
bitmap regs_active;
cselib_expand_callback callback;
void *callback_arg;
bool dummy;
};
static rtx cselib_expand_value_rtx_1 (rtx, struct expand_value_data *, int);
/* There are three ways in which cselib can look up an rtx:
- for a REG, the reg_values table (which is indexed by regno) is used
- for a MEM, we recursively look up its address and then follow the
addr_list of that value
- for everything else, we compute a hash value and go through the hash
table. Since different rtx's can still have the same hash value,
this involves walking the table entries for a given value and comparing
the locations of the entries with the rtx we are looking up. */
/* A table that enables us to look up elts by their value. */
static htab_t cselib_hash_table;
/* This is a global so we don't have to pass this through every function.
It is used in new_elt_loc_list to set SETTING_INSN. */
static rtx cselib_current_insn;
/* The unique id that the next create value will take. */
static unsigned int next_uid;
/* The number of registers we had when the varrays were last resized. */
static unsigned int cselib_nregs;
/* Count values without known locations, or with only locations that
wouldn't have been known except for debug insns. Whenever this
grows too big, we remove these useless values from the table.
Counting values with only debug values is a bit tricky. We don't
want to increment n_useless_values when we create a value for a
debug insn, for this would get n_useless_values out of sync, but we
want increment it if all locs in the list that were ever referenced
in nondebug insns are removed from the list.
In the general case, once we do that, we'd have to stop accepting
nondebug expressions in the loc list, to avoid having two values
equivalent that, without debug insns, would have been made into
separate values. However, because debug insns never introduce
equivalences themselves (no assignments), the only means for
growing loc lists is through nondebug assignments. If the locs
also happen to be referenced in debug insns, it will work just fine.
A consequence of this is that there's at most one debug-only loc in
each loc list. If we keep it in the first entry, testing whether
we have a debug-only loc list takes O(1).
Furthermore, since any additional entry in a loc list containing a
debug loc would have to come from an assignment (nondebug) that
references both the initial debug loc and the newly-equivalent loc,
the initial debug loc would be promoted to a nondebug loc, and the
loc list would not contain debug locs any more.
So the only case we have to be careful with in order to keep
n_useless_values in sync between debug and nondebug compilations is
to avoid incrementing n_useless_values when removing the single loc
from a value that turns out to not appear outside debug values. We
increment n_useless_debug_values instead, and leave such values
alone until, for other reasons, we garbage-collect useless
values. */
static int n_useless_values;
static int n_useless_debug_values;
/* Count values whose locs have been taken exclusively from debug
insns for the entire life of the value. */
static int n_debug_values;
/* Number of useless values before we remove them from the hash table. */
#define MAX_USELESS_VALUES 32
/* This table maps from register number to values. It does not
contain pointers to cselib_val structures, but rather elt_lists.
The purpose is to be able to refer to the same register in
different modes. The first element of the list defines the mode in
which the register was set; if the mode is unknown or the value is
no longer valid in that mode, ELT will be NULL for the first
element. */
static struct elt_list **reg_values;
static unsigned int reg_values_size;
#define REG_VALUES(i) reg_values[i]
/* The largest number of hard regs used by any entry added to the
REG_VALUES table. Cleared on each cselib_clear_table() invocation. */
static unsigned int max_value_regs;
/* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
in cselib_clear_table() for fast emptying. */
static unsigned int *used_regs;
static unsigned int n_used_regs;
/* We pass this to cselib_invalidate_mem to invalidate all of
memory for a non-const call instruction. */
static GTY(()) rtx callmem;
/* Set by discard_useless_locs if it deleted the last location of any
value. */
static int values_became_useless;
/* Used as stop element of the containing_mem list so we can check
presence in the list by checking the next pointer. */
static cselib_val dummy_val;
/* If non-NULL, value of the eliminated arg_pointer_rtx or frame_pointer_rtx
that is constant through the whole function and should never be
eliminated. */
static cselib_val *cfa_base_preserved_val;
static unsigned int cfa_base_preserved_regno;
/* Used to list all values that contain memory reference.
May or may not contain the useless values - the list is compacted
each time memory is invalidated. */
static cselib_val *first_containing_mem = &dummy_val;
static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool;
/* If nonnull, cselib will call this function before freeing useless
VALUEs. A VALUE is deemed useless if its "locs" field is null. */
void (*cselib_discard_hook) (cselib_val *);
/* If nonnull, cselib will call this function before recording sets or
even clobbering outputs of INSN. All the recorded sets will be
represented in the array sets[n_sets]. new_val_min can be used to
tell whether values present in sets are introduced by this
instruction. */
void (*cselib_record_sets_hook) (rtx insn, struct cselib_set *sets,
int n_sets);
#define PRESERVED_VALUE_P(RTX) \
(RTL_FLAG_CHECK1("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)
/* Allocate a struct elt_list and fill in its two elements with the
arguments. */
static inline struct elt_list *
new_elt_list (struct elt_list *next, cselib_val *elt)
{
struct elt_list *el;
el = (struct elt_list *) pool_alloc (elt_list_pool);
el->next = next;
el->elt = elt;
return el;
}
/* Allocate a struct elt_loc_list and fill in its two elements with the
arguments. */
static inline struct elt_loc_list *
new_elt_loc_list (struct elt_loc_list *next, rtx loc)
{
struct elt_loc_list *el;
el = (struct elt_loc_list *) pool_alloc (elt_loc_list_pool);
el->next = next;
el->loc = loc;
el->setting_insn = cselib_current_insn;
gcc_assert (!next || !next->setting_insn
|| !DEBUG_INSN_P (next->setting_insn));
/* If we're creating the first loc in a debug insn context, we've
just created a debug value. Count it. */
if (!next && cselib_current_insn && DEBUG_INSN_P (cselib_current_insn))
n_debug_values++;
return el;
}
/* Promote loc L to a nondebug cselib_current_insn if L is marked as
originating from a debug insn, maintaining the debug values
count. */
static inline void
promote_debug_loc (struct elt_loc_list *l)
{
if (l->setting_insn && DEBUG_INSN_P (l->setting_insn)
&& (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
{
n_debug_values--;
l->setting_insn = cselib_current_insn;
gcc_assert (!l->next);
}
}
/* The elt_list at *PL is no longer needed. Unchain it and free its
storage. */
static inline void
unchain_one_elt_list (struct elt_list **pl)
{
struct elt_list *l = *pl;
*pl = l->next;
pool_free (elt_list_pool, l);
}
/* Likewise for elt_loc_lists. */
static void
unchain_one_elt_loc_list (struct elt_loc_list **pl)
{
struct elt_loc_list *l = *pl;
*pl = l->next;
pool_free (elt_loc_list_pool, l);
}
/* Likewise for cselib_vals. This also frees the addr_list associated with
V. */
static void
unchain_one_value (cselib_val *v)
{
while (v->addr_list)
unchain_one_elt_list (&v->addr_list);
pool_free (cselib_val_pool, v);
}
/* Remove all entries from the hash table. Also used during
initialization. */
void
cselib_clear_table (void)
{
cselib_reset_table (1);
}
/* Remove from hash table all VALUEs except constants. */
static int
preserve_only_constants (void **x, void *info ATTRIBUTE_UNUSED)
{
cselib_val *v = (cselib_val *)*x;
if (v->locs != NULL
&& v->locs->next == NULL)
{
if (CONSTANT_P (v->locs->loc)
&& (GET_CODE (v->locs->loc) != CONST
|| !references_value_p (v->locs->loc, 0)))
return 1;
if (cfa_base_preserved_val)
{
if (v == cfa_base_preserved_val)
return 1;
if (GET_CODE (v->locs->loc) == PLUS
&& CONST_INT_P (XEXP (v->locs->loc, 1))
&& XEXP (v->locs->loc, 0) == cfa_base_preserved_val->val_rtx)
return 1;
}
}
htab_clear_slot (cselib_hash_table, x);
return 1;
}
/* Remove all entries from the hash table, arranging for the next
value to be numbered NUM. */
void
cselib_reset_table (unsigned int num)
{
unsigned int i;
max_value_regs = 0;
if (cfa_base_preserved_val)
{
unsigned int regno = cfa_base_preserved_regno;
unsigned int new_used_regs = 0;
for (i = 0; i < n_used_regs; i++)
if (used_regs[i] == regno)
{
new_used_regs = 1;
continue;
}
else
REG_VALUES (used_regs[i]) = 0;
gcc_assert (new_used_regs == 1);
n_used_regs = new_used_regs;
used_regs[0] = regno;
max_value_regs
= hard_regno_nregs[regno][GET_MODE (cfa_base_preserved_val->locs->loc)];
}
else
{
for (i = 0; i < n_used_regs; i++)
REG_VALUES (used_regs[i]) = 0;
n_used_regs = 0;
}
if (cselib_preserve_constants)
htab_traverse (cselib_hash_table, preserve_only_constants, NULL);
else
htab_empty (cselib_hash_table);
n_useless_values = 0;
n_useless_debug_values = 0;
n_debug_values = 0;
next_uid = num;
first_containing_mem = &dummy_val;
}
/* Return the number of the next value that will be generated. */
unsigned int
cselib_get_next_uid (void)
{
return next_uid;
}
/* The equality test for our hash table. The first argument ENTRY is a table
element (i.e. a cselib_val), while the second arg X is an rtx. We know
that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
CONST of an appropriate mode. */
static int
entry_and_rtx_equal_p (const void *entry, const void *x_arg)
{
struct elt_loc_list *l;
const cselib_val *const v = (const cselib_val *) entry;
rtx x = CONST_CAST_RTX ((const_rtx)x_arg);
enum machine_mode mode = GET_MODE (x);
gcc_assert (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED
&& (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE));
if (mode != GET_MODE (v->val_rtx))
return 0;
/* Unwrap X if necessary. */
if (GET_CODE (x) == CONST
&& (CONST_INT_P (XEXP (x, 0))
|| GET_CODE (XEXP (x, 0)) == CONST_FIXED
|| GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))
x = XEXP (x, 0);
/* We don't guarantee that distinct rtx's have different hash values,
so we need to do a comparison. */
for (l = v->locs; l; l = l->next)
if (rtx_equal_for_cselib_p (l->loc, x))
{
promote_debug_loc (l);
return 1;
}
return 0;
}
/* The hash function for our hash table. The value is always computed with
cselib_hash_rtx when adding an element; this function just extracts the
hash value from a cselib_val structure. */
static hashval_t
get_value_hash (const void *entry)
{
const cselib_val *const v = (const cselib_val *) entry;
return v->hash;
}
/* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
only return true for values which point to a cselib_val whose value
element has been set to zero, which implies the cselib_val will be
removed. */
int
references_value_p (const_rtx x, int only_useless)
{
const enum rtx_code code = GET_CODE (x);
const char *fmt = GET_RTX_FORMAT (code);
int i, j;
if (GET_CODE (x) == VALUE
&& (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
return 1;
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
return 1;
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
if (references_value_p (XVECEXP (x, i, j), only_useless))
return 1;
}
return 0;
}
/* For all locations found in X, delete locations that reference useless
values (i.e. values without any location). Called through
htab_traverse. */
static int
discard_useless_locs (void **x, void *info ATTRIBUTE_UNUSED)
{
cselib_val *v = (cselib_val *)*x;
struct elt_loc_list **p = &v->locs;
bool had_locs = v->locs != NULL;
rtx setting_insn = v->locs ? v->locs->setting_insn : NULL;
while (*p)
{
if (references_value_p ((*p)->loc, 1))
unchain_one_elt_loc_list (p);
else
p = &(*p)->next;
}
if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
{
if (setting_insn && DEBUG_INSN_P (setting_insn))
n_useless_debug_values++;
else
n_useless_values++;
values_became_useless = 1;
}
return 1;
}
/* If X is a value with no locations, remove it from the hashtable. */
static int
discard_useless_values (void **x, void *info ATTRIBUTE_UNUSED)
{
cselib_val *v = (cselib_val *)*x;
if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
{
if (cselib_discard_hook)
cselib_discard_hook (v);
CSELIB_VAL_PTR (v->val_rtx) = NULL;
htab_clear_slot (cselib_hash_table, x);
unchain_one_value (v);
n_useless_values--;
}
return 1;
}
/* Clean out useless values (i.e. those which no longer have locations
associated with them) from the hash table. */
static void
remove_useless_values (void)
{
cselib_val **p, *v;
/* First pass: eliminate locations that reference the value. That in
turn can make more values useless. */
do
{
values_became_useless = 0;
htab_traverse (cselib_hash_table, discard_useless_locs, 0);
}
while (values_became_useless);
/* Second pass: actually remove the values. */
p = &first_containing_mem;
for (v = *p; v != &dummy_val; v = v->next_containing_mem)
if (v->locs)
{
*p = v;
p = &(*p)->next_containing_mem;
}
*p = &dummy_val;
n_useless_values += n_useless_debug_values;
n_debug_values -= n_useless_debug_values;
n_useless_debug_values = 0;
htab_traverse (cselib_hash_table, discard_useless_values, 0);
gcc_assert (!n_useless_values);
}
/* Arrange for a value to not be removed from the hash table even if
it becomes useless. */
void
cselib_preserve_value (cselib_val *v)
{
PRESERVED_VALUE_P (v->val_rtx) = 1;
}
/* Test whether a value is preserved. */
bool
cselib_preserved_value_p (cselib_val *v)
{
return PRESERVED_VALUE_P (v->val_rtx);
}
/* Arrange for a REG value to be assumed constant through the whole function,
never invalidated and preserved across cselib_reset_table calls. */
void
cselib_preserve_cfa_base_value (cselib_val *v, unsigned int regno)
{
if (cselib_preserve_constants
&& v->locs
&& REG_P (v->locs->loc))
{
cfa_base_preserved_val = v;
cfa_base_preserved_regno = regno;
}
}
/* Clean all non-constant expressions in the hash table, but retain
their values. */
void
cselib_preserve_only_values (void)
{
int i;
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
cselib_invalidate_regno (i, reg_raw_mode[i]);
cselib_invalidate_mem (callmem);
remove_useless_values ();
gcc_assert (first_containing_mem == &dummy_val);
}
/* Return the mode in which a register was last set. If X is not a
register, return its mode. If the mode in which the register was
set is not known, or the value was already clobbered, return
VOIDmode. */
enum machine_mode
cselib_reg_set_mode (const_rtx x)
{
if (!REG_P (x))
return GET_MODE (x);
if (REG_VALUES (REGNO (x)) == NULL
|| REG_VALUES (REGNO (x))->elt == NULL)
return VOIDmode;
return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx);
}
/* Return nonzero if we can prove that X and Y contain the same value, taking
our gathered information into account. */
int
rtx_equal_for_cselib_p (rtx x, rtx y)
{
enum rtx_code code;
const char *fmt;
int i;
if (REG_P (x) || MEM_P (x))
{
cselib_val *e = cselib_lookup (x, GET_MODE (x), 0);
if (e)
x = e->val_rtx;
}
if (REG_P (y) || MEM_P (y))
{
cselib_val *e = cselib_lookup (y, GET_MODE (y), 0);
if (e)
y = e->val_rtx;
}
if (x == y)
return 1;
if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
if (GET_CODE (x) == VALUE)
{
cselib_val *e = CSELIB_VAL_PTR (x);
struct elt_loc_list *l;
for (l = e->locs; l; l = l->next)
{
rtx t = l->loc;
/* Avoid infinite recursion. */
if (REG_P (t) || MEM_P (t))
continue;
else if (rtx_equal_for_cselib_p (t, y))
return 1;
}
return 0;
}
if (GET_CODE (y) == VALUE)
{
cselib_val *e = CSELIB_VAL_PTR (y);
struct elt_loc_list *l;
for (l = e->locs; l; l = l->next)
{
rtx t = l->loc;
if (REG_P (t) || MEM_P (t))
continue;
else if (rtx_equal_for_cselib_p (x, t))
return 1;
}
return 0;
}
if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
return 0;
/* These won't be handled correctly by the code below. */
switch (GET_CODE (x))
{
case CONST_DOUBLE:
case CONST_FIXED:
case DEBUG_EXPR:
return 0;
case LABEL_REF:
return XEXP (x, 0) == XEXP (y, 0);
default:
break;
}
code = GET_CODE (x);
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
int j;
switch (fmt[i])
{
case 'w':
if (XWINT (x, i) != XWINT (y, i))
return 0;
break;
case 'n':
case 'i':
if (XINT (x, i) != XINT (y, i))
return 0;
break;
case 'V':
case 'E':
/* Two vectors must have the same length. */
if (XVECLEN (x, i) != XVECLEN (y, i))
return 0;
/* And the corresponding elements must match. */
for (j = 0; j < XVECLEN (x, i); j++)
if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
XVECEXP (y, i, j)))
return 0;
break;
case 'e':
if (i == 1
&& targetm.commutative_p (x, UNKNOWN)
&& rtx_equal_for_cselib_p (XEXP (x, 1), XEXP (y, 0))
&& rtx_equal_for_cselib_p (XEXP (x, 0), XEXP (y, 1)))
return 1;
if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
return 0;
break;
case 'S':
case 's':
if (strcmp (XSTR (x, i), XSTR (y, i)))
return 0;
break;
case 'u':
/* These are just backpointers, so they don't matter. */
break;
case '0':
case 't':
break;
/* It is believed that rtx's at this level will never
contain anything but integers and other rtx's,
except for within LABEL_REFs and SYMBOL_REFs. */
default:
gcc_unreachable ();
}
}
return 1;
}
/* We need to pass down the mode of constants through the hash table
functions. For that purpose, wrap them in a CONST of the appropriate
mode. */
static rtx
wrap_constant (enum machine_mode mode, rtx x)
{
if (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED
&& (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode))
return x;
gcc_assert (mode != VOIDmode);
return gen_rtx_CONST (mode, x);
}
/* Hash an rtx. Return 0 if we couldn't hash the rtx.
For registers and memory locations, we look up their cselib_val structure
and return its VALUE element.
Possible reasons for return 0 are: the object is volatile, or we couldn't
find a register or memory location in the table and CREATE is zero. If
CREATE is nonzero, table elts are created for regs and mem.
N.B. this hash function returns the same hash value for RTXes that
differ only in the order of operands, thus it is suitable for comparisons
that take commutativity into account.
If we wanted to also support associative rules, we'd have to use a different
strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
We used to have a MODE argument for hashing for CONST_INTs, but that
didn't make sense, since it caused spurious hash differences between
(set (reg:SI 1) (const_int))
(plus:SI (reg:SI 2) (reg:SI 1))
and
(plus:SI (reg:SI 2) (const_int))
If the mode is important in any context, it must be checked specifically
in a comparison anyway, since relying on hash differences is unsafe. */
static unsigned int
cselib_hash_rtx (rtx x, int create)
{
cselib_val *e;
int i, j;
enum rtx_code code;
const char *fmt;
unsigned int hash = 0;
code = GET_CODE (x);
hash += (unsigned) code + (unsigned) GET_MODE (x);
switch (code)
{
case MEM:
case REG:
e = cselib_lookup (x, GET_MODE (x), create);
if (! e)
return 0;
return e->hash;
case DEBUG_EXPR:
hash += ((unsigned) DEBUG_EXPR << 7)
+ DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x));
return hash ? hash : (unsigned int) DEBUG_EXPR;
case CONST_INT:
hash += ((unsigned) CONST_INT << 7) + INTVAL (x);
return hash ? hash : (unsigned int) CONST_INT;
case CONST_DOUBLE:
/* This is like the general case, except that it only counts
the integers representing the constant. */
hash += (unsigned) code + (unsigned) GET_MODE (x);
if (GET_MODE (x) != VOIDmode)
hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
else
hash += ((unsigned) CONST_DOUBLE_LOW (x)
+ (unsigned) CONST_DOUBLE_HIGH (x));
return hash ? hash : (unsigned int) CONST_DOUBLE;
case CONST_FIXED:
hash += (unsigned int) code + (unsigned int) GET_MODE (x);
hash += fixed_hash (CONST_FIXED_VALUE (x));
return hash ? hash : (unsigned int) CONST_FIXED;
case CONST_VECTOR:
{
int units;
rtx elt;
units = CONST_VECTOR_NUNITS (x);
for (i = 0; i < units; ++i)
{
elt = CONST_VECTOR_ELT (x, i);
hash += cselib_hash_rtx (elt, 0);
}
return hash;
}
/* Assume there is only one rtx object for any given label. */
case LABEL_REF:
/* We don't hash on the address of the CODE_LABEL to avoid bootstrap
differences and differences between each stage's debugging dumps. */
hash += (((unsigned int) LABEL_REF << 7)
+ CODE_LABEL_NUMBER (XEXP (x, 0)));
return hash ? hash : (unsigned int) LABEL_REF;
case SYMBOL_REF:
{
/* Don't hash on the symbol's address to avoid bootstrap differences.
Different hash values may cause expressions to be recorded in
different orders and thus different registers to be used in the
final assembler. This also avoids differences in the dump files
between various stages. */
unsigned int h = 0;
const unsigned char *p = (const unsigned char *) XSTR (x, 0);
while (*p)
h += (h << 7) + *p++; /* ??? revisit */
hash += ((unsigned int) SYMBOL_REF << 7) + h;
return hash ? hash : (unsigned int) SYMBOL_REF;
}
case PRE_DEC:
case PRE_INC:
case POST_DEC:
case POST_INC:
case POST_MODIFY:
case PRE_MODIFY:
case PC:
case CC0:
case CALL:
case UNSPEC_VOLATILE:
return 0;
case ASM_OPERANDS:
if (MEM_VOLATILE_P (x))
return 0;
break;
default:
break;
}
i = GET_RTX_LENGTH (code) - 1;
fmt = GET_RTX_FORMAT (code);
for (; i >= 0; i--)
{
switch (fmt[i])
{
case 'e':
{
rtx tem = XEXP (x, i);
unsigned int tem_hash = cselib_hash_rtx (tem, create);
if (tem_hash == 0)
return 0;
hash += tem_hash;
}
break;
case 'E':
for (j = 0; j < XVECLEN (x, i); j++)
{
unsigned int tem_hash
= cselib_hash_rtx (XVECEXP (x, i, j), create);
if (tem_hash == 0)
return 0;
hash += tem_hash;
}
break;
case 's':
{
const unsigned char *p = (const unsigned char *) XSTR (x, i);
if (p)
while (*p)
hash += *p++;
break;
}
case 'i':
hash += XINT (x, i);
break;
case '0':
case 't':
/* unused */
break;
default:
gcc_unreachable ();
}
}
return hash ? hash : 1 + (unsigned int) GET_CODE (x);
}
/* Create a new value structure for VALUE and initialize it. The mode of the
value is MODE. */
static inline cselib_val *
new_cselib_val (unsigned int hash, enum machine_mode mode, rtx x)
{
cselib_val *e = (cselib_val *) pool_alloc (cselib_val_pool);
gcc_assert (hash);
gcc_assert (next_uid);
e->hash = hash;
e->uid = next_uid++;
/* We use an alloc pool to allocate this RTL construct because it
accounts for about 8% of the overall memory usage. We know
precisely when we can have VALUE RTXen (when cselib is active)
so we don't need to put them in garbage collected memory.
??? Why should a VALUE be an RTX in the first place? */
e->val_rtx = (rtx) pool_alloc (value_pool);
memset (e->val_rtx, 0, RTX_HDR_SIZE);
PUT_CODE (e->val_rtx, VALUE);
PUT_MODE (e->val_rtx, mode);
CSELIB_VAL_PTR (e->val_rtx) = e;
e->addr_list = 0;
e->locs = 0;