forked from illumos/gcc
/
reload1.c
8951 lines (7713 loc) · 287 KB
/
reload1.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
/* Reload pseudo regs into hard regs for insns that require hard regs.
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
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 "machmode.h"
#include "hard-reg-set.h"
#include "rtl.h"
#include "tm_p.h"
#include "obstack.h"
#include "insn-config.h"
#include "flags.h"
#include "function.h"
#include "expr.h"
#include "optabs.h"
#include "regs.h"
#include "addresses.h"
#include "basic-block.h"
#include "reload.h"
#include "recog.h"
#include "output.h"
#include "real.h"
#include "toplev.h"
#include "except.h"
#include "tree.h"
#include "ira.h"
#include "df.h"
#include "target.h"
#include "emit-rtl.h"
/* This file contains the reload pass of the compiler, which is
run after register allocation has been done. It checks that
each insn is valid (operands required to be in registers really
are in registers of the proper class) and fixes up invalid ones
by copying values temporarily into registers for the insns
that need them.
The results of register allocation are described by the vector
reg_renumber; the insns still contain pseudo regs, but reg_renumber
can be used to find which hard reg, if any, a pseudo reg is in.
The technique we always use is to free up a few hard regs that are
called ``reload regs'', and for each place where a pseudo reg
must be in a hard reg, copy it temporarily into one of the reload regs.
Reload regs are allocated locally for every instruction that needs
reloads. When there are pseudos which are allocated to a register that
has been chosen as a reload reg, such pseudos must be ``spilled''.
This means that they go to other hard regs, or to stack slots if no other
available hard regs can be found. Spilling can invalidate more
insns, requiring additional need for reloads, so we must keep checking
until the process stabilizes.
For machines with different classes of registers, we must keep track
of the register class needed for each reload, and make sure that
we allocate enough reload registers of each class.
The file reload.c contains the code that checks one insn for
validity and reports the reloads that it needs. This file
is in charge of scanning the entire rtl code, accumulating the
reload needs, spilling, assigning reload registers to use for
fixing up each insn, and generating the new insns to copy values
into the reload registers. */
/* During reload_as_needed, element N contains a REG rtx for the hard reg
into which reg N has been reloaded (perhaps for a previous insn). */
static rtx *reg_last_reload_reg;
/* Elt N nonzero if reg_last_reload_reg[N] has been set in this insn
for an output reload that stores into reg N. */
static regset_head reg_has_output_reload;
/* Indicates which hard regs are reload-registers for an output reload
in the current insn. */
static HARD_REG_SET reg_is_output_reload;
/* Element N is the constant value to which pseudo reg N is equivalent,
or zero if pseudo reg N is not equivalent to a constant.
find_reloads looks at this in order to replace pseudo reg N
with the constant it stands for. */
rtx *reg_equiv_constant;
/* Element N is an invariant value to which pseudo reg N is equivalent.
eliminate_regs_in_insn uses this to replace pseudos in particular
contexts. */
rtx *reg_equiv_invariant;
/* Element N is a memory location to which pseudo reg N is equivalent,
prior to any register elimination (such as frame pointer to stack
pointer). Depending on whether or not it is a valid address, this value
is transferred to either reg_equiv_address or reg_equiv_mem. */
rtx *reg_equiv_memory_loc;
/* We allocate reg_equiv_memory_loc inside a varray so that the garbage
collector can keep track of what is inside. */
VEC(rtx,gc) *reg_equiv_memory_loc_vec;
/* Element N is the address of stack slot to which pseudo reg N is equivalent.
This is used when the address is not valid as a memory address
(because its displacement is too big for the machine.) */
rtx *reg_equiv_address;
/* Element N is the memory slot to which pseudo reg N is equivalent,
or zero if pseudo reg N is not equivalent to a memory slot. */
rtx *reg_equiv_mem;
/* Element N is an EXPR_LIST of REG_EQUIVs containing MEMs with
alternate representations of the location of pseudo reg N. */
rtx *reg_equiv_alt_mem_list;
/* Widest width in which each pseudo reg is referred to (via subreg). */
static unsigned int *reg_max_ref_width;
/* Element N is the list of insns that initialized reg N from its equivalent
constant or memory slot. */
rtx *reg_equiv_init;
int reg_equiv_init_size;
/* Vector to remember old contents of reg_renumber before spilling. */
static short *reg_old_renumber;
/* During reload_as_needed, element N contains the last pseudo regno reloaded
into hard register N. If that pseudo reg occupied more than one register,
reg_reloaded_contents points to that pseudo for each spill register in
use; all of these must remain set for an inheritance to occur. */
static int reg_reloaded_contents[FIRST_PSEUDO_REGISTER];
/* During reload_as_needed, element N contains the insn for which
hard register N was last used. Its contents are significant only
when reg_reloaded_valid is set for this register. */
static rtx reg_reloaded_insn[FIRST_PSEUDO_REGISTER];
/* Indicate if reg_reloaded_insn / reg_reloaded_contents is valid. */
static HARD_REG_SET reg_reloaded_valid;
/* Indicate if the register was dead at the end of the reload.
This is only valid if reg_reloaded_contents is set and valid. */
static HARD_REG_SET reg_reloaded_dead;
/* Indicate whether the register's current value is one that is not
safe to retain across a call, even for registers that are normally
call-saved. This is only meaningful for members of reg_reloaded_valid. */
static HARD_REG_SET reg_reloaded_call_part_clobbered;
/* Number of spill-regs so far; number of valid elements of spill_regs. */
static int n_spills;
/* In parallel with spill_regs, contains REG rtx's for those regs.
Holds the last rtx used for any given reg, or 0 if it has never
been used for spilling yet. This rtx is reused, provided it has
the proper mode. */
static rtx spill_reg_rtx[FIRST_PSEUDO_REGISTER];
/* In parallel with spill_regs, contains nonzero for a spill reg
that was stored after the last time it was used.
The precise value is the insn generated to do the store. */
static rtx spill_reg_store[FIRST_PSEUDO_REGISTER];
/* This is the register that was stored with spill_reg_store. This is a
copy of reload_out / reload_out_reg when the value was stored; if
reload_out is a MEM, spill_reg_stored_to will be set to reload_out_reg. */
static rtx spill_reg_stored_to[FIRST_PSEUDO_REGISTER];
/* This table is the inverse mapping of spill_regs:
indexed by hard reg number,
it contains the position of that reg in spill_regs,
or -1 for something that is not in spill_regs.
?!? This is no longer accurate. */
static short spill_reg_order[FIRST_PSEUDO_REGISTER];
/* This reg set indicates registers that can't be used as spill registers for
the currently processed insn. These are the hard registers which are live
during the insn, but not allocated to pseudos, as well as fixed
registers. */
static HARD_REG_SET bad_spill_regs;
/* These are the hard registers that can't be used as spill register for any
insn. This includes registers used for user variables and registers that
we can't eliminate. A register that appears in this set also can't be used
to retry register allocation. */
static HARD_REG_SET bad_spill_regs_global;
/* Describes order of use of registers for reloading
of spilled pseudo-registers. `n_spills' is the number of
elements that are actually valid; new ones are added at the end.
Both spill_regs and spill_reg_order are used on two occasions:
once during find_reload_regs, where they keep track of the spill registers
for a single insn, but also during reload_as_needed where they show all
the registers ever used by reload. For the latter case, the information
is calculated during finish_spills. */
static short spill_regs[FIRST_PSEUDO_REGISTER];
/* This vector of reg sets indicates, for each pseudo, which hard registers
may not be used for retrying global allocation because the register was
formerly spilled from one of them. If we allowed reallocating a pseudo to
a register that it was already allocated to, reload might not
terminate. */
static HARD_REG_SET *pseudo_previous_regs;
/* This vector of reg sets indicates, for each pseudo, which hard
registers may not be used for retrying global allocation because they
are used as spill registers during one of the insns in which the
pseudo is live. */
static HARD_REG_SET *pseudo_forbidden_regs;
/* All hard regs that have been used as spill registers for any insn are
marked in this set. */
static HARD_REG_SET used_spill_regs;
/* Index of last register assigned as a spill register. We allocate in
a round-robin fashion. */
static int last_spill_reg;
/* Nonzero if indirect addressing is supported on the machine; this means
that spilling (REG n) does not require reloading it into a register in
order to do (MEM (REG n)) or (MEM (PLUS (REG n) (CONST_INT c))). The
value indicates the level of indirect addressing supported, e.g., two
means that (MEM (MEM (REG n))) is also valid if (REG n) does not get
a hard register. */
static char spill_indirect_levels;
/* Nonzero if indirect addressing is supported when the innermost MEM is
of the form (MEM (SYMBOL_REF sym)). It is assumed that the level to
which these are valid is the same as spill_indirect_levels, above. */
char indirect_symref_ok;
/* Nonzero if an address (plus (reg frame_pointer) (reg ...)) is valid. */
char double_reg_address_ok;
/* Record the stack slot for each spilled hard register. */
static rtx spill_stack_slot[FIRST_PSEUDO_REGISTER];
/* Width allocated so far for that stack slot. */
static unsigned int spill_stack_slot_width[FIRST_PSEUDO_REGISTER];
/* Record which pseudos needed to be spilled. */
static regset_head spilled_pseudos;
/* Record which pseudos changed their allocation in finish_spills. */
static regset_head changed_allocation_pseudos;
/* Used for communication between order_regs_for_reload and count_pseudo.
Used to avoid counting one pseudo twice. */
static regset_head pseudos_counted;
/* First uid used by insns created by reload in this function.
Used in find_equiv_reg. */
int reload_first_uid;
/* Flag set by local-alloc or global-alloc if anything is live in
a call-clobbered reg across calls. */
int caller_save_needed;
/* Set to 1 while reload_as_needed is operating.
Required by some machines to handle any generated moves differently. */
int reload_in_progress = 0;
/* These arrays record the insn_code of insns that may be needed to
perform input and output reloads of special objects. They provide a
place to pass a scratch register. */
enum insn_code reload_in_optab[NUM_MACHINE_MODES];
enum insn_code reload_out_optab[NUM_MACHINE_MODES];
/* This obstack is used for allocation of rtl during register elimination.
The allocated storage can be freed once find_reloads has processed the
insn. */
static struct obstack reload_obstack;
/* Points to the beginning of the reload_obstack. All insn_chain structures
are allocated first. */
static char *reload_startobj;
/* The point after all insn_chain structures. Used to quickly deallocate
memory allocated in copy_reloads during calculate_needs_all_insns. */
static char *reload_firstobj;
/* This points before all local rtl generated by register elimination.
Used to quickly free all memory after processing one insn. */
static char *reload_insn_firstobj;
/* List of insn_chain instructions, one for every insn that reload needs to
examine. */
struct insn_chain *reload_insn_chain;
/* List of all insns needing reloads. */
static struct insn_chain *insns_need_reload;
/* This structure is used to record information about register eliminations.
Each array entry describes one possible way of eliminating a register
in favor of another. If there is more than one way of eliminating a
particular register, the most preferred should be specified first. */
struct elim_table
{
int from; /* Register number to be eliminated. */
int to; /* Register number used as replacement. */
HOST_WIDE_INT initial_offset; /* Initial difference between values. */
int can_eliminate; /* Nonzero if this elimination can be done. */
int can_eliminate_previous; /* Value of CAN_ELIMINATE in previous scan over
insns made by reload. */
HOST_WIDE_INT offset; /* Current offset between the two regs. */
HOST_WIDE_INT previous_offset;/* Offset at end of previous insn. */
int ref_outside_mem; /* "to" has been referenced outside a MEM. */
rtx from_rtx; /* REG rtx for the register to be eliminated.
We cannot simply compare the number since
we might then spuriously replace a hard
register corresponding to a pseudo
assigned to the reg to be eliminated. */
rtx to_rtx; /* REG rtx for the replacement. */
};
static struct elim_table *reg_eliminate = 0;
/* This is an intermediate structure to initialize the table. It has
exactly the members provided by ELIMINABLE_REGS. */
static const struct elim_table_1
{
const int from;
const int to;
} reg_eliminate_1[] =
/* If a set of eliminable registers was specified, define the table from it.
Otherwise, default to the normal case of the frame pointer being
replaced by the stack pointer. */
#ifdef ELIMINABLE_REGS
ELIMINABLE_REGS;
#else
{{ FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM}};
#endif
#define NUM_ELIMINABLE_REGS ARRAY_SIZE (reg_eliminate_1)
/* Record the number of pending eliminations that have an offset not equal
to their initial offset. If nonzero, we use a new copy of each
replacement result in any insns encountered. */
int num_not_at_initial_offset;
/* Count the number of registers that we may be able to eliminate. */
static int num_eliminable;
/* And the number of registers that are equivalent to a constant that
can be eliminated to frame_pointer / arg_pointer + constant. */
static int num_eliminable_invariants;
/* For each label, we record the offset of each elimination. If we reach
a label by more than one path and an offset differs, we cannot do the
elimination. This information is indexed by the difference of the
number of the label and the first label number. We can't offset the
pointer itself as this can cause problems on machines with segmented
memory. The first table is an array of flags that records whether we
have yet encountered a label and the second table is an array of arrays,
one entry in the latter array for each elimination. */
static int first_label_num;
static char *offsets_known_at;
static HOST_WIDE_INT (*offsets_at)[NUM_ELIMINABLE_REGS];
/* Number of labels in the current function. */
static int num_labels;
static void replace_pseudos_in (rtx *, enum machine_mode, rtx);
static void maybe_fix_stack_asms (void);
static void copy_reloads (struct insn_chain *);
static void calculate_needs_all_insns (int);
static int find_reg (struct insn_chain *, int);
static void find_reload_regs (struct insn_chain *);
static void select_reload_regs (void);
static void delete_caller_save_insns (void);
static void spill_failure (rtx, enum reg_class);
static void count_spilled_pseudo (int, int, int);
static void delete_dead_insn (rtx);
static void alter_reg (int, int, bool);
static void set_label_offsets (rtx, rtx, int);
static void check_eliminable_occurrences (rtx);
static void elimination_effects (rtx, enum machine_mode);
static int eliminate_regs_in_insn (rtx, int);
static void update_eliminable_offsets (void);
static void mark_not_eliminable (rtx, const_rtx, void *);
static void set_initial_elim_offsets (void);
static bool verify_initial_elim_offsets (void);
static void set_initial_label_offsets (void);
static void set_offsets_for_label (rtx);
static void init_elim_table (void);
static void update_eliminables (HARD_REG_SET *);
static void spill_hard_reg (unsigned int, int);
static int finish_spills (int);
static void scan_paradoxical_subregs (rtx);
static void count_pseudo (int);
static void order_regs_for_reload (struct insn_chain *);
static void reload_as_needed (int);
static void forget_old_reloads_1 (rtx, const_rtx, void *);
static void forget_marked_reloads (regset);
static int reload_reg_class_lower (const void *, const void *);
static void mark_reload_reg_in_use (unsigned int, int, enum reload_type,
enum machine_mode);
static void clear_reload_reg_in_use (unsigned int, int, enum reload_type,
enum machine_mode);
static int reload_reg_free_p (unsigned int, int, enum reload_type);
static int reload_reg_free_for_value_p (int, int, int, enum reload_type,
rtx, rtx, int, int);
static int free_for_value_p (int, enum machine_mode, int, enum reload_type,
rtx, rtx, int, int);
static int reload_reg_reaches_end_p (unsigned int, int, enum reload_type);
static int allocate_reload_reg (struct insn_chain *, int, int);
static int conflicts_with_override (rtx);
static void failed_reload (rtx, int);
static int set_reload_reg (int, int);
static void choose_reload_regs_init (struct insn_chain *, rtx *);
static void choose_reload_regs (struct insn_chain *);
static void merge_assigned_reloads (rtx);
static void emit_input_reload_insns (struct insn_chain *, struct reload *,
rtx, int);
static void emit_output_reload_insns (struct insn_chain *, struct reload *,
int);
static void do_input_reload (struct insn_chain *, struct reload *, int);
static void do_output_reload (struct insn_chain *, struct reload *, int);
static void emit_reload_insns (struct insn_chain *);
static void delete_output_reload (rtx, int, int, rtx);
static void delete_address_reloads (rtx, rtx);
static void delete_address_reloads_1 (rtx, rtx, rtx);
static rtx inc_for_reload (rtx, rtx, rtx, int);
#ifdef AUTO_INC_DEC
static void add_auto_inc_notes (rtx, rtx);
#endif
static void copy_eh_notes (rtx, rtx);
static void substitute (rtx *, const_rtx, rtx);
static bool gen_reload_chain_without_interm_reg_p (int, int);
static int reloads_conflict (int, int);
static rtx gen_reload (rtx, rtx, int, enum reload_type);
static rtx emit_insn_if_valid_for_reload (rtx);
/* Initialize the reload pass. This is called at the beginning of compilation
and may be called again if the target is reinitialized. */
void
init_reload (void)
{
int i;
/* Often (MEM (REG n)) is still valid even if (REG n) is put on the stack.
Set spill_indirect_levels to the number of levels such addressing is
permitted, zero if it is not permitted at all. */
rtx tem
= gen_rtx_MEM (Pmode,
gen_rtx_PLUS (Pmode,
gen_rtx_REG (Pmode,
LAST_VIRTUAL_REGISTER + 1),
GEN_INT (4)));
spill_indirect_levels = 0;
while (memory_address_p (QImode, tem))
{
spill_indirect_levels++;
tem = gen_rtx_MEM (Pmode, tem);
}
/* See if indirect addressing is valid for (MEM (SYMBOL_REF ...)). */
tem = gen_rtx_MEM (Pmode, gen_rtx_SYMBOL_REF (Pmode, "foo"));
indirect_symref_ok = memory_address_p (QImode, tem);
/* See if reg+reg is a valid (and offsettable) address. */
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
{
tem = gen_rtx_PLUS (Pmode,
gen_rtx_REG (Pmode, HARD_FRAME_POINTER_REGNUM),
gen_rtx_REG (Pmode, i));
/* This way, we make sure that reg+reg is an offsettable address. */
tem = plus_constant (tem, 4);
if (memory_address_p (QImode, tem))
{
double_reg_address_ok = 1;
break;
}
}
/* Initialize obstack for our rtl allocation. */
gcc_obstack_init (&reload_obstack);
reload_startobj = XOBNEWVAR (&reload_obstack, char, 0);
INIT_REG_SET (&spilled_pseudos);
INIT_REG_SET (&changed_allocation_pseudos);
INIT_REG_SET (&pseudos_counted);
}
/* List of insn chains that are currently unused. */
static struct insn_chain *unused_insn_chains = 0;
/* Allocate an empty insn_chain structure. */
struct insn_chain *
new_insn_chain (void)
{
struct insn_chain *c;
if (unused_insn_chains == 0)
{
c = XOBNEW (&reload_obstack, struct insn_chain);
INIT_REG_SET (&c->live_throughout);
INIT_REG_SET (&c->dead_or_set);
}
else
{
c = unused_insn_chains;
unused_insn_chains = c->next;
}
c->is_caller_save_insn = 0;
c->need_operand_change = 0;
c->need_reload = 0;
c->need_elim = 0;
return c;
}
/* Small utility function to set all regs in hard reg set TO which are
allocated to pseudos in regset FROM. */
void
compute_use_by_pseudos (HARD_REG_SET *to, regset from)
{
unsigned int regno;
reg_set_iterator rsi;
EXECUTE_IF_SET_IN_REG_SET (from, FIRST_PSEUDO_REGISTER, regno, rsi)
{
int r = reg_renumber[regno];
if (r < 0)
{
/* reload_combine uses the information from DF_LIVE_IN,
which might still contain registers that have not
actually been allocated since they have an
equivalence. */
gcc_assert (ira_conflicts_p || reload_completed);
}
else
add_to_hard_reg_set (to, PSEUDO_REGNO_MODE (regno), r);
}
}
/* Replace all pseudos found in LOC with their corresponding
equivalences. */
static void
replace_pseudos_in (rtx *loc, enum machine_mode mem_mode, rtx usage)
{
rtx x = *loc;
enum rtx_code code;
const char *fmt;
int i, j;
if (! x)
return;
code = GET_CODE (x);
if (code == REG)
{
unsigned int regno = REGNO (x);
if (regno < FIRST_PSEUDO_REGISTER)
return;
x = eliminate_regs (x, mem_mode, usage);
if (x != *loc)
{
*loc = x;
replace_pseudos_in (loc, mem_mode, usage);
return;
}
if (reg_equiv_constant[regno])
*loc = reg_equiv_constant[regno];
else if (reg_equiv_mem[regno])
*loc = reg_equiv_mem[regno];
else if (reg_equiv_address[regno])
*loc = gen_rtx_MEM (GET_MODE (x), reg_equiv_address[regno]);
else
{
gcc_assert (!REG_P (regno_reg_rtx[regno])
|| REGNO (regno_reg_rtx[regno]) != regno);
*loc = regno_reg_rtx[regno];
}
return;
}
else if (code == MEM)
{
replace_pseudos_in (& XEXP (x, 0), GET_MODE (x), usage);
return;
}
/* Process each of our operands recursively. */
fmt = GET_RTX_FORMAT (code);
for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
if (*fmt == 'e')
replace_pseudos_in (&XEXP (x, i), mem_mode, usage);
else if (*fmt == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
replace_pseudos_in (& XVECEXP (x, i, j), mem_mode, usage);
}
/* Determine if the current function has an exception receiver block
that reaches the exit block via non-exceptional edges */
static bool
has_nonexceptional_receiver (void)
{
edge e;
edge_iterator ei;
basic_block *tos, *worklist, bb;
/* If we're not optimizing, then just err on the safe side. */
if (!optimize)
return true;
/* First determine which blocks can reach exit via normal paths. */
tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1);
FOR_EACH_BB (bb)
bb->flags &= ~BB_REACHABLE;
/* Place the exit block on our worklist. */
EXIT_BLOCK_PTR->flags |= BB_REACHABLE;
*tos++ = EXIT_BLOCK_PTR;
/* Iterate: find everything reachable from what we've already seen. */
while (tos != worklist)
{
bb = *--tos;
FOR_EACH_EDGE (e, ei, bb->preds)
if (!(e->flags & EDGE_ABNORMAL))
{
basic_block src = e->src;
if (!(src->flags & BB_REACHABLE))
{
src->flags |= BB_REACHABLE;
*tos++ = src;
}
}
}
free (worklist);
/* Now see if there's a reachable block with an exceptional incoming
edge. */
FOR_EACH_BB (bb)
if (bb->flags & BB_REACHABLE)
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->flags & EDGE_ABNORMAL)
return true;
/* No exceptional block reached exit unexceptionally. */
return false;
}
/* Global variables used by reload and its subroutines. */
/* Set during calculate_needs if an insn needs register elimination. */
static int something_needs_elimination;
/* Set during calculate_needs if an insn needs an operand changed. */
static int something_needs_operands_changed;
/* Nonzero means we couldn't get enough spill regs. */
static int failure;
/* Temporary array of pseudo-register number. */
static int *temp_pseudo_reg_arr;
/* Main entry point for the reload pass.
FIRST is the first insn of the function being compiled.
GLOBAL nonzero means we were called from global_alloc
and should attempt to reallocate any pseudoregs that we
displace from hard regs we will use for reloads.
If GLOBAL is zero, we do not have enough information to do that,
so any pseudo reg that is spilled must go to the stack.
Return value is nonzero if reload failed
and we must not do any more for this function. */
int
reload (rtx first, int global)
{
int i, n;
rtx insn;
struct elim_table *ep;
basic_block bb;
/* Make sure even insns with volatile mem refs are recognizable. */
init_recog ();
failure = 0;
reload_firstobj = XOBNEWVAR (&reload_obstack, char, 0);
/* Make sure that the last insn in the chain
is not something that needs reloading. */
emit_note (NOTE_INSN_DELETED);
/* Enable find_equiv_reg to distinguish insns made by reload. */
reload_first_uid = get_max_uid ();
#ifdef SECONDARY_MEMORY_NEEDED
/* Initialize the secondary memory table. */
clear_secondary_mem ();
#endif
/* We don't have a stack slot for any spill reg yet. */
memset (spill_stack_slot, 0, sizeof spill_stack_slot);
memset (spill_stack_slot_width, 0, sizeof spill_stack_slot_width);
/* Initialize the save area information for caller-save, in case some
are needed. */
init_save_areas ();
/* Compute which hard registers are now in use
as homes for pseudo registers.
This is done here rather than (eg) in global_alloc
because this point is reached even if not optimizing. */
for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
mark_home_live (i);
/* A function that has a nonlocal label that can reach the exit
block via non-exceptional paths must save all call-saved
registers. */
if (cfun->has_nonlocal_label
&& has_nonexceptional_receiver ())
crtl->saves_all_registers = 1;
if (crtl->saves_all_registers)
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i))
df_set_regs_ever_live (i, true);
/* Find all the pseudo registers that didn't get hard regs
but do have known equivalent constants or memory slots.
These include parameters (known equivalent to parameter slots)
and cse'd or loop-moved constant memory addresses.
Record constant equivalents in reg_equiv_constant
so they will be substituted by find_reloads.
Record memory equivalents in reg_mem_equiv so they can
be substituted eventually by altering the REG-rtx's. */
reg_equiv_constant = XCNEWVEC (rtx, max_regno);
reg_equiv_invariant = XCNEWVEC (rtx, max_regno);
reg_equiv_mem = XCNEWVEC (rtx, max_regno);
reg_equiv_alt_mem_list = XCNEWVEC (rtx, max_regno);
reg_equiv_address = XCNEWVEC (rtx, max_regno);
reg_max_ref_width = XCNEWVEC (unsigned int, max_regno);
reg_old_renumber = XCNEWVEC (short, max_regno);
memcpy (reg_old_renumber, reg_renumber, max_regno * sizeof (short));
pseudo_forbidden_regs = XNEWVEC (HARD_REG_SET, max_regno);
pseudo_previous_regs = XCNEWVEC (HARD_REG_SET, max_regno);
CLEAR_HARD_REG_SET (bad_spill_regs_global);
/* Look for REG_EQUIV notes; record what each pseudo is equivalent
to. Also find all paradoxical subregs and find largest such for
each pseudo. */
num_eliminable_invariants = 0;
for (insn = first; insn; insn = NEXT_INSN (insn))
{
rtx set = single_set (insn);
/* We may introduce USEs that we want to remove at the end, so
we'll mark them with QImode. Make sure there are no
previously-marked insns left by say regmove. */
if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == USE
&& GET_MODE (insn) != VOIDmode)
PUT_MODE (insn, VOIDmode);
if (INSN_P (insn))
scan_paradoxical_subregs (PATTERN (insn));
if (set != 0 && REG_P (SET_DEST (set)))
{
rtx note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
rtx x;
if (! note)
continue;
i = REGNO (SET_DEST (set));
x = XEXP (note, 0);
if (i <= LAST_VIRTUAL_REGISTER)
continue;
if (! function_invariant_p (x)
|| ! flag_pic
/* A function invariant is often CONSTANT_P but may
include a register. We promise to only pass
CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
|| (CONSTANT_P (x)
&& LEGITIMATE_PIC_OPERAND_P (x)))
{
/* It can happen that a REG_EQUIV note contains a MEM
that is not a legitimate memory operand. As later
stages of reload assume that all addresses found
in the reg_equiv_* arrays were originally legitimate,
we ignore such REG_EQUIV notes. */
if (memory_operand (x, VOIDmode))
{
/* Always unshare the equivalence, so we can
substitute into this insn without touching the
equivalence. */
reg_equiv_memory_loc[i] = copy_rtx (x);
}
else if (function_invariant_p (x))
{
if (GET_CODE (x) == PLUS)
{
/* This is PLUS of frame pointer and a constant,
and might be shared. Unshare it. */
reg_equiv_invariant[i] = copy_rtx (x);
num_eliminable_invariants++;
}
else if (x == frame_pointer_rtx || x == arg_pointer_rtx)
{
reg_equiv_invariant[i] = x;
num_eliminable_invariants++;
}
else if (LEGITIMATE_CONSTANT_P (x))
reg_equiv_constant[i] = x;
else
{
reg_equiv_memory_loc[i]
= force_const_mem (GET_MODE (SET_DEST (set)), x);
if (! reg_equiv_memory_loc[i])
reg_equiv_init[i] = NULL_RTX;
}
}
else
{
reg_equiv_init[i] = NULL_RTX;
continue;
}
}
else
reg_equiv_init[i] = NULL_RTX;
}
}
if (dump_file)
for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
if (reg_equiv_init[i])
{
fprintf (dump_file, "init_insns for %u: ", i);
print_inline_rtx (dump_file, reg_equiv_init[i], 20);
fprintf (dump_file, "\n");
}
init_elim_table ();
first_label_num = get_first_label_num ();
num_labels = max_label_num () - first_label_num;
/* Allocate the tables used to store offset information at labels. */
/* We used to use alloca here, but the size of what it would try to
allocate would occasionally cause it to exceed the stack limit and
cause a core dump. */
offsets_known_at = XNEWVEC (char, num_labels);
offsets_at = (HOST_WIDE_INT (*)[NUM_ELIMINABLE_REGS]) xmalloc (num_labels * NUM_ELIMINABLE_REGS * sizeof (HOST_WIDE_INT));
/* Alter each pseudo-reg rtx to contain its hard reg number. Assign
stack slots to the pseudos that lack hard regs or equivalents.
Do not touch virtual registers. */
temp_pseudo_reg_arr = XNEWVEC (int, max_regno - LAST_VIRTUAL_REGISTER - 1);
for (n = 0, i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
temp_pseudo_reg_arr[n++] = i;
if (ira_conflicts_p)
/* Ask IRA to order pseudo-registers for better stack slot
sharing. */
ira_sort_regnos_for_alter_reg (temp_pseudo_reg_arr, n, reg_max_ref_width);
for (i = 0; i < n; i++)
alter_reg (temp_pseudo_reg_arr[i], -1, false);
/* If we have some registers we think can be eliminated, scan all insns to
see if there is an insn that sets one of these registers to something
other than itself plus a constant. If so, the register cannot be
eliminated. Doing this scan here eliminates an extra pass through the
main reload loop in the most common case where register elimination
cannot be done. */
for (insn = first; insn && num_eliminable; insn = NEXT_INSN (insn))
if (INSN_P (insn))
note_stores (PATTERN (insn), mark_not_eliminable, NULL);
maybe_fix_stack_asms ();
insns_need_reload = 0;
something_needs_elimination = 0;
/* Initialize to -1, which means take the first spill register. */
last_spill_reg = -1;
/* Spill any hard regs that we know we can't eliminate. */
CLEAR_HARD_REG_SET (used_spill_regs);
/* There can be multiple ways to eliminate a register;
they should be listed adjacently.
Elimination for any register fails only if all possible ways fail. */
for (ep = reg_eliminate; ep < ®_eliminate[NUM_ELIMINABLE_REGS]; )
{
int from = ep->from;
int can_eliminate = 0;
do
{
can_eliminate |= ep->can_eliminate;
ep++;
}
while (ep < ®_eliminate[NUM_ELIMINABLE_REGS] && ep->from == from);
if (! can_eliminate)
spill_hard_reg (from, 1);
}
#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
if (frame_pointer_needed)
spill_hard_reg (HARD_FRAME_POINTER_REGNUM, 1);
#endif
finish_spills (global);
/* From now on, we may need to generate moves differently. We may also
allow modifications of insns which cause them to not be recognized.
Any such modifications will be cleaned up during reload itself. */
reload_in_progress = 1;
/* This loop scans the entire function each go-round
and repeats until one repetition spills no additional hard regs. */
for (;;)
{
int something_changed;
int did_spill;
HOST_WIDE_INT starting_frame_size;
starting_frame_size = get_frame_size ();
set_initial_elim_offsets ();
set_initial_label_offsets ();
/* For each pseudo register that has an equivalent location defined,
try to eliminate any eliminable registers (such as the frame pointer)
assuming initial offsets for the replacement register, which
is the normal case.
If the resulting location is directly addressable, substitute
the MEM we just got directly for the old REG.
If it is not addressable but is a constant or the sum of a hard reg
and constant, it is probably not addressable because the constant is
out of range, in that case record the address; we will generate
hairy code to compute the address in a register each time it is
needed. Similarly if it is a hard register, but one that is not
valid as an address register.
If the location is not addressable, but does not have one of the
above forms, assign a stack slot. We have to do this to avoid the
potential of producing lots of reloads if, e.g., a location involves
a pseudo that didn't get a hard register and has an equivalent memory
location that also involves a pseudo that didn't get a hard register.
Perhaps at some point we will improve reload_when_needed handling
so this problem goes away. But that's very hairy. */
for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
if (reg_renumber[i] < 0 && reg_equiv_memory_loc[i])
{
rtx x = eliminate_regs (reg_equiv_memory_loc[i], 0, NULL_RTX);