-
Notifications
You must be signed in to change notification settings - Fork 17
/
Copy pathcombine.c
1559 lines (1378 loc) · 47 KB
/
combine.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
/* Optimize by combining instructions for GNU compiler.
Copyright (C) 1987 Free Software Foundation, Inc.
This file is part of GNU CC.
GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY. No author or distributor
accepts responsibility to anyone for the consequences of using it
or for whether it serves any particular purpose or works at all,
unless he says so in writing. Refer to the GNU CC General Public
License for full details.
Everyone is granted permission to copy, modify and redistribute
GNU CC, but only under the conditions described in the
GNU CC General Public License. A copy of this license is
supposed to have been given to you along with GNU CC so you
can know your rights and responsibilities. It should be in a
file named COPYING. Among other things, the copyright notice
and this notice must be preserved on all copies. */
/* This module is essentially the "combiner" phase of the U. of Arizona
Portable Optimizer, but redone to work on our list-structured
representation for RTL instead of their string representation.
The LOG_LINKS of each insn identify the most recent assignment
to each REG used in the insn. It is a list of previous insns,
each of which contains a SET for a REG that is used in this insn
and not used or set in between. LOG_LINKs never cross basic blocks.
They were set up by the preceding pass (lifetime analysis).
We try to combine each pair of insns joined by a logical link.
We also try to combine triples of insns A, B and C when
C has a link back to B and B has a link back to A.
LOG_LINKS does not have links for use of the CC0. They don't
need to, because the insn that sets the CC0 is always immediately
before the insn that tests it. So we always regard a branch
insn as having a logical link to the preceding insn.
We check (with use_crosses_set_p) to avoid combining in such a way
as to move a computation to a place where its value would be different.
Combination is done by mathematically substituting the previous
insn(s) values for the regs they set into the expressions in
the later insns that refer to these regs. If the result is a valid insn
for our target machine, according to the machine description,
we install it, delete the earlier insns, and update the data flow
information (LOG_LINKS and REG_NOTES) for what we did.
To simplify substitution, we combine only when the earlier insn(s)
consist of only a single assignment. To simplify updating afterward,
we never combine when a subroutine call appears in the middle.
Since we do not represent assignments to CC0 explicitly except when that
is all an insn does, there is no LOG_LINKS entry in an insn that uses
the condition code for the insn that set the condition code.
Fortunately, these two insns must be consecutive.
Therefore, every JUMP_INSN is taken to have an implicit logical link
to the preceding insn. This is not quite right, since non-jumps can
also use the condition code; but in practice such insns would not
combine anyway. */
#include "config.h"
#include "rtl.h"
#include "regs.h"
#include "basic-block.h"
#include "insn-config.h"
#include "recog.h"
#define max(A,B) ((A) > (B) ? (A) : (B))
#define min(A,B) ((A) < (B) ? (A) : (B))
/* Number of attempts to combine instructions in this function. */
static int combine_attempts;
/* Number of attempts that got as far as substitution in this function. */
static int combine_merges;
/* Number of instructions combined with added SETs in this function. */
static int combine_extras;
/* Number of instructions combined in this function. */
static int combine_successes;
/* Totals over entire compilation. */
static int total_attempts, total_merges, total_extras, total_successes;
/* Vector mapping INSN_UIDs to cuids.
The cuids are like uids but increase monononically always.
Combine always uses cuids so that it can compare them.
But actually renumbering the uids, which we used to do,
proves to be a bad idea because it makes it hard to compare
the dumps produced by earlier passes with those from later passes. */
static short *uid_cuid;
/* Get the cuid of an insn. */
#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
/* Record last point of death of (hard or pseudo) register n. */
static rtx *reg_last_death;
/* Record last point of modification of (hard or pseudo) register n. */
static rtx *reg_last_set;
/* Record the cuid of the last insn that invalidated memory
(anything that writes memory, and subroutine calls). */
static int mem_last_set;
/* Record the cuid of the last CALL_INSN
so we can tell whether a potential combination crosses any calls. */
static int last_call_cuid;
/* When `subst' is called, this is the insn that is being modified
(by combining in a previous insn). The PATTERN of this insn
is still the old pattern partially modified and it should not be
looked at, but this may be used to examine the successors of the insn
to judge whether a simplification is valid. */
static rtx subst_insn;
/* Record one modification to rtl structure
to be undone by storing old_contents into *where. */
struct undo
{
rtx *where;
rtx old_contents;
};
/* Record a bunch of changes to be undone, up to MAX_UNDO of them.
num_undo says how many are currently recorded.
storage is nonzero if we must undo the allocation of new storage.
The value of storage is what to pass to obfree. */
#define MAX_UNDO 10
struct undobuf
{
int num_undo;
char *storage;
struct undo undo[MAX_UNDO];
};
static struct undobuf undobuf;
static void move_deaths ();
static void remove_death ();
static void record_dead_and_set_regs ();
int regno_dead_p ();
static int reg_set_in_range_p ();
static int use_crosses_set_p ();
static rtx subst ();
static void undo_all ();
static void add_links ();
static void add_incs ();
static int adjacent_insns_p ();
static rtx simplify_and_const_int ();
static rtx gen_lowpart_for_combine ();
static void simplify_set_cc0_and ();
/* Main entry point for combiner. F is the first insn of the function.
NREGS is the first unused pseudo-reg number. */
void
combine_instructions (f, nregs)
rtx f;
int nregs;
{
register rtx insn;
register int i;
register rtx links, nextlinks;
rtx prev;
combine_attempts = 0;
combine_merges = 0;
combine_extras = 0;
combine_successes = 0;
reg_last_death = (rtx *) alloca (nregs * sizeof (rtx));
reg_last_set = (rtx *) alloca (nregs * sizeof (rtx));
bzero (reg_last_death, nregs * sizeof (rtx));
bzero (reg_last_set, nregs * sizeof (rtx));
init_recog ();
/* Compute maximum uid value so uid_cuid can be allocated. */
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
if (INSN_UID (insn) > i)
i = INSN_UID (insn);
uid_cuid = (short *) alloca ((i + 1) * sizeof (short));
/* Compute the mapping from uids to cuids.
Cuids are numbers assigned to insns, like uids,
except that cuids increase monotonically through the code. */
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
INSN_CUID (insn) = ++i;
/* Now scan all the insns in forward order. */
last_call_cuid = 0;
mem_last_set = 0;
prev = 0;
for (insn = f; insn; insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == INSN
|| GET_CODE (insn) == CALL_INSN
|| GET_CODE (insn) == JUMP_INSN)
{
retry:
/* Try this insn with each insn it links back to. */
for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
if (try_combine (insn, XEXP (links, 0), 0))
goto retry;
/* Try each sequence of three linked insns ending with this one. */
for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
if (GET_CODE (XEXP (links, 0)) != NOTE)
for (nextlinks = LOG_LINKS (XEXP (links, 0)); nextlinks;
nextlinks = XEXP (nextlinks, 1))
if (try_combine (insn, XEXP (links, 0), XEXP (nextlinks, 0)))
goto retry;
/* Try to combine a jump insn that uses CC0
with a preceding insn that sets CC0, and maybe with its
logical predecessor as well.
This is how we make decrement-and-branch insns.
We need this special code because data flow connections
via CC0 do not get entered in LOG_LINKS. */
if (GET_CODE (insn) == JUMP_INSN
&& prev != 0
&& GET_CODE (prev) == INSN
&& GET_CODE (PATTERN (prev)) == SET
&& GET_CODE (SET_DEST (PATTERN (prev))) == CC0)
{
if (try_combine (insn, prev, 0))
goto retry;
if (GET_CODE (prev) != NOTE)
for (nextlinks = LOG_LINKS (prev); nextlinks;
nextlinks = XEXP (nextlinks, 1))
if (try_combine (insn, prev, XEXP (nextlinks, 0)))
goto retry;
}
#if 0
/* Turned off because on 68020 it takes four insns to make
something like (a[b / 32] & (1 << (31 - (b % 32)))) != 0
that could actually be optimized, and that's an unlikely piece of code. */
/* If an insn gets or sets a bit field, try combining it
with two different insns whose results it uses. */
if (GET_CODE (insn) == INSN
&& GET_CODE (PATTERN (insn)) == SET
&& (GET_CODE (SET_DEST (PATTERN (insn))) == ZERO_EXTRACT
|| GET_CODE (SET_DEST (PATTERN (insn))) == SIGN_EXTRACT
|| GET_CODE (SET_SRC (PATTERN (insn))) == ZERO_EXTRACT
|| GET_CODE (SET_SRC (PATTERN (insn))) == SIGN_EXTRACT))
{
for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
if (GET_CODE (XEXP (links, 0)) != NOTE)
for (nextlinks = XEXP (links, 1); nextlinks;
nextlinks = XEXP (nextlinks, 1))
if (try_combine (insn, XEXP (links, 0), XEXP (nextlinks, 0)))
goto retry;
}
#endif
record_dead_and_set_regs (insn);
prev = insn;
}
else if (GET_CODE (insn) != NOTE)
prev = 0;
}
total_attempts += combine_attempts;
total_merges += combine_merges;
total_extras += combine_extras;
total_successes += combine_successes;
}
/* Try to combine the insns I1 and I2 into I3.
Here I1 appears earlier than I2, which is earlier than I3.
I1 can be zero; then we combine just I2 into I3.
Return 1 if successful; if that happens, I1 and I2 are pseudo-deleted
by turning them into NOTEs, and I3 is modified.
Return 0 if the combination does not work. Then nothing is changed. */
static int
try_combine (i3, i2, i1)
register rtx i3, i2, i1;
{
register rtx newpat;
int added_sets_1 = 0;
int added_sets_2 = 0;
int total_sets;
int i2_is_used;
register rtx link;
int insn_code_number;
int recog_flags = 0;
rtx i2dest, i2src;
rtx i1dest, i1src;
combine_attempts++;
/* Don't combine with something already used up by combination. */
if (GET_CODE (i2) == NOTE
|| (i1 && GET_CODE (i1) == NOTE))
return 0;
/* Don't combine across a CALL_INSN, because that would possibly
change whether the life span of some REGs crosses calls or not,
and it is a pain to update that information. */
if (INSN_CUID (i2) < last_call_cuid
|| (i1 && INSN_CUID (i1) < last_call_cuid))
return 0;
/* Can combine only if previous insn is a SET of a REG, a SUBREG or CC0.
That REG must be either set or dead by the final instruction
(so that we can safely forget about setting it).
Also test use_crosses_set_p to make sure that the value
that is to be substituted for the register
does not use any registers whose values alter in between.
Do not try combining with moves from one register to another
since it is better to let them be tied by register allocation.
A set of a SUBREG is considered as if it were a set from
SUBREG. Thus, (SET (SUBREG:X (REG:Y...)) (something:X...))
is handled by substituting (SUBREG:Y (something:X...)) for (REG:Y...). */
if (GET_CODE (PATTERN (i2)) != SET)
return 0;
i2dest = SET_DEST (PATTERN (i2));
i2src = SET_SRC (PATTERN (i2));
if (GET_CODE (i2dest) == SUBREG)
{
i2dest = SUBREG_REG (i2dest);
i2src = gen_rtx (SUBREG, GET_MODE (i2dest), i2src, 0);
}
if (GET_CODE (i2dest) != CC0
&& (GET_CODE (i2dest) != REG
|| GET_CODE (i2src) == REG
|| use_crosses_set_p (i2src, INSN_CUID (i2))))
return 0;
if (i1 != 0)
{
if (GET_CODE (PATTERN (i1)) != SET)
return 0;
i1dest = SET_DEST (PATTERN (i1));
i1src = SET_SRC (PATTERN (i1));
if (GET_CODE (i1dest) == SUBREG)
{
i1dest = SUBREG_REG (i1dest);
i1src = gen_rtx (SUBREG, GET_MODE (i1dest), i1src, 0);
}
if (GET_CODE (i1dest) != CC0
&& (GET_CODE (i1dest) != REG
|| GET_CODE (i1src) == REG
|| use_crosses_set_p (i1src, INSN_CUID (i1))))
return 0;
}
/* If I1 or I2 contains an autoincrement or autodecrement,
make sure that register is not used between there and I3.
Also insist that I3 not be a jump; if it were one
and the incremented register were spilled, we would lose. */
for (link = REG_NOTES (i2); link; link = XEXP (link, 1))
if ((enum reg_note) GET_MODE (link) == REG_INC)
if (GET_CODE (i3) == JUMP_INSN
|| reg_used_between_p (XEXP (link, 0), i2, i3))
return 0;
if (i1)
for (link = REG_NOTES (i1); link; link = XEXP (link, 1))
if ((enum reg_note) GET_MODE (link) == REG_INC)
if (GET_CODE (i3) == JUMP_INSN
|| reg_used_between_p (XEXP (link, 0), i1, i3))
return 0;
/* See if the SETs in i1 or i2 need to be kept around in the merged
instruction: whenever the value set there is still needed past i3. */
added_sets_2 = (GET_CODE (i2dest) != CC0
&& ! dead_or_set_p (i3, i2dest));
if (i1)
added_sets_1 = ! (dead_or_set_p (i3, i1dest)
|| dead_or_set_p (i2, i1dest));
combine_merges++;
undobuf.num_undo = 0;
undobuf.storage = 0;
/* Substitute in the latest insn for the regs set by the earlier ones. */
subst_insn = i3;
newpat = subst (PATTERN (i3), i2dest, i2src);
/* Record whether i2's body now appears within i3's body. */
i2_is_used = undobuf.num_undo;
if (i1)
newpat = subst (newpat, i1dest, i1src);
if (GET_CODE (PATTERN (i3)) == SET
&& SET_DEST (PATTERN (i3)) == cc0_rtx
&& GET_CODE (SET_SRC (PATTERN (i3))) == AND
&& next_insn_tests_no_inequality (i3))
simplify_set_cc0_and (i3);
/* If the actions of the earler insns must be kept
in addition to substituting them into the latest one,
we must make a new PARALLEL for the latest insn
to hold additional the SETs. */
if (added_sets_1 || added_sets_2)
{
combine_extras++;
/* Arrange to free later what we allocate now
if we don't accept this combination. */
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
if (GET_CODE (newpat) == PARALLEL)
{
total_sets = XVECLEN (newpat, 0) + added_sets_1 + added_sets_2;
newpat = gen_rtx (PARALLEL, VOIDmode,
gen_rtvec_v (total_sets,
&XVECEXP (newpat, 0, 0)));
}
else
{
total_sets = 1 + added_sets_1 + added_sets_2;
newpat = gen_rtx (PARALLEL, VOIDmode,
gen_rtvec (total_sets, newpat));
}
if (added_sets_1)
{
XVECEXP (newpat, 0, --total_sets) = PATTERN (i1);
}
if (added_sets_2)
{
/* If there is no I1, use I2's body as is. */
if (i1 == 0
/* If I2 was stuck into I3, then anything within it has
already had I1 substituted into it when that was done to I3. */
|| i2_is_used)
{
XVECEXP (newpat, 0, --total_sets) = PATTERN (i2);
}
else
XVECEXP (newpat, 0, --total_sets)
= subst (PATTERN (i2), i1dest, i1src);
}
}
/* Is the result of combination a valid instruction? */
insn_code_number = recog (newpat, i3);
if (insn_code_number >= 0)
{
/* Yes. Install it. */
register int regno;
INSN_CODE (i3) = insn_code_number;
PATTERN (i3) = newpat;
/* Most REGs that previously died in I2 now die in I3. */
move_deaths (i2src, INSN_CUID (i2), i3);
if (GET_CODE (i2dest) == REG)
{
/* If the reg formerly set in I2 died only once and that was in I3,
zero its use count so it won't make `reload' do any work. */
regno = REGNO (i2dest);
if (! added_sets_2)
reg_n_sets[regno]--;
if (reg_n_sets[regno] == 0 && regno_dead_p (regno, i3))
reg_n_refs[regno] = 0;
/* If a ref to REGNO was substituted into I3 from I2,
then it still dies there if it previously did.
Otherwise either REGNO never did die in I3 so remove_death is safe
or this entire life of REGNO is gone so remove its death. */
if (!added_sets_2
&& ! reg_mentioned_p (i2dest, PATTERN (i3)))
remove_death (regno, i3);
}
/* The data flowing into I2 now flows into I3.
But we cannot always move I2's LOG_LINKS into I3,
since they must go to a setting of a REG from the
first use following. If I2 was the first use following a set,
I3 is now a use, but it is not the first use
if some instruction between I2 and I3 is also a use.
Here, for simplicity, we move the links only if
there are no real insns between I2 and I3. */
if (adjacent_insns_p (i2, i3))
add_links (i3, LOG_LINKS (i2));
/* Any registers previously autoincremented in I2
are now incremented in I3. */
add_incs (i3, REG_NOTES (i2));
/* Get rid of I2. */
LOG_LINKS (i2) = 0;
PUT_CODE (i2, NOTE);
NOTE_LINE_NUMBER (i2) = NOTE_INSN_DELETED;
NOTE_SOURCE_FILE (i2) = 0;
if (i1)
{
/* Likewise, merge the info from I1 and get rid of it. */
move_deaths (i1src, INSN_CUID (i1), i3);
if (GET_CODE (i1dest) == REG)
{
regno = REGNO (i1dest);
if (! added_sets_1)
reg_n_sets[regno]--;
if (reg_n_sets[regno] == 0 && regno_dead_p (regno, i3))
reg_n_refs[regno] = 0;
/* If a ref to REGNO was substituted into I3 from I1,
then it still dies there if it previously did.
Else either REGNO never did die in I3 so remove_death is safe
or this entire life of REGNO is gone so remove its death. */
if (! added_sets_1
&& ! reg_mentioned_p (i1dest, PATTERN (i3)))
remove_death (regno, i3);
}
if (adjacent_insns_p (i2, i3))
add_links (i3, LOG_LINKS (i1));
add_incs (i3, REG_NOTES (i1));
LOG_LINKS (i1) = 0;
PUT_CODE (i1, NOTE);
NOTE_LINE_NUMBER (i1) = NOTE_INSN_DELETED;
NOTE_SOURCE_FILE (i1) = 0;
}
combine_successes++;
return 1;
}
/* Failure: change I3 back the way it was. */
undo_all ();
return 0;
}
/* Undo all the modifications recorded in undobuf. */
static void
undo_all ()
{
register int i;
if (undobuf.num_undo > MAX_UNDO)
undobuf.num_undo = MAX_UNDO;
for (i = undobuf.num_undo - 1; i >= 0; i--)
*undobuf.undo[i].where = undobuf.undo[i].old_contents;
if (undobuf.storage)
obfree (undobuf.storage);
undobuf.num_undo = 0;
undobuf.storage = 0;
}
/* Throughout X, replace FROM with TO, and return the result.
The result is TO if X is FROM;
otherwise the result is X, but its contents may have been modified.
If they were modified, a record was made in undobuf so that
undo_all will (among other things) return X to its original state.
If the number of changes necessary is too much to record to undo,
the excess changes are not made, so the result is invalid.
The changes already made can still be undone.
undobuf.num_undo is incremented for such changes, so by testing that
the caller can tell whether the result is valid. */
static rtx
subst (x, from, to)
register rtx x, from, to;
{
register char *fmt;
register int len, i;
register enum rtx_code code;
/* THIS_TO is used to replace FROM if it appears exactly one
level down in X. Simplifications often work by changing
THIS_TO after observing that FROM appears in a specific way
one level down in X. Since only THIS_TO is changed, and TO
is left alone, further occurrences of FROM within the operands
of X are replaced normally. */
rtx this_to;
if (x == from)
return to;
code = GET_CODE (x);
this_to = to;
/* A little bit of algebraic simplification here. */
switch (code)
{
/* This case has no effect except to speed things up. */
case REG:
case CONST_INT:
case CONST:
case SYMBOL_REF:
case LABEL_REF:
case PC:
case CC0:
return x;
case NOT:
case NEG:
/* Don't let substitution introduce double-negatives. */
if (XEXP (x, 0) == from
&& GET_CODE (to) == code)
return XEXP (to, 0);
break;
case PLUS:
/* In (plus <foo> (ashift <bar> <n>))
change the shift to a multiply so we can recognize
scaled indexed addresses. */
if ((XEXP (x, 0) == from
|| XEXP (x, 1) == from)
&& GET_CODE (to) == ASHIFT
&& GET_CODE (XEXP (to, 1)) == CONST_INT)
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
this_to = gen_rtx (MULT, GET_MODE (to),
XEXP (to, 0),
gen_rtx (CONST_INT, VOIDmode,
1 << INTVAL (XEXP (to, 1))));
}
/* If we have something (putative index) being added to a sum,
associate it so that any constant term is outermost.
That's because that's the way indexed addresses are
now supposed to appear. */
if (((XEXP (x, 0) == from && GET_CODE (XEXP (x, 1)) == PLUS)
|| (XEXP (x, 1) == from && GET_CODE (XEXP (x, 0)) == PLUS))
||
((XEXP (x, 0) == from || XEXP (x, 1) == from)
&& GET_CODE (this_to) == PLUS))
{
rtx offset = 0, base, index;
if (GET_CODE (this_to) != PLUS)
{
index = this_to;
base = XEXP (x, 0) == from ? XEXP (x, 1) : XEXP (x, 0);
}
else
{
index = XEXP (x, 0) == from ? XEXP (x, 1) : XEXP (x, 0);
base = this_to;
}
if (CONSTANT_ADDRESS_P (XEXP (base, 0)))
{
offset = XEXP (base, 0);
base = XEXP (base, 1);
}
else if (CONSTANT_ADDRESS_P (XEXP (base, 1)))
{
offset = XEXP (base, 1);
base = XEXP (base, 0);
}
if (offset != 0)
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
return gen_rtx (PLUS, GET_MODE (index), offset,
gen_rtx (PLUS, GET_MODE (index),
index, base));
}
}
break;
case MINUS:
/* Can simplify (minus:VOIDmode (zero/sign_extend FOO) CONST)
(which is a compare instruction, not a subtract instruction)
to (minus FOO CONST) if CONST fits in FOO's mode
and we are only testing equality.
In fact, this is valid for zero_extend if what follows is an
unsigned comparison, and for sign_extend with a signed comparison. */
if (GET_MODE (x) == VOIDmode
&& XEXP (x, 0) == from
&& (GET_CODE (to) == ZERO_EXTEND || GET_CODE (to) == SIGN_EXTEND)
&& next_insn_tests_no_inequality (subst_insn)
&& GET_CODE (XEXP (x, 1)) == CONST_INT
&& ((unsigned) INTVAL (XEXP (x, 1))
< (1 << (BITS_PER_UNIT * GET_MODE_SIZE (GET_MODE (XEXP (to, 0)))))))
this_to = XEXP (to, 0);
break;
case EQ:
case NE:
/* If comparing a subreg against zero, discard the subreg. */
if (XEXP (x, 0) == from
&& GET_CODE (to) == SUBREG
&& SUBREG_WORD (to) == 0
&& XEXP (x, 1) == const0_rtx)
this_to = SUBREG_REG (to);
/* If comparing a ZERO_EXTRACT against zero,
canonicalize to a SIGN_EXTRACT,
since the two are equivalent here. */
if (XEXP (x, 0) == from
&& GET_CODE (this_to) == ZERO_EXTRACT
&& XEXP (x, 1) == const0_rtx)
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
this_to = gen_rtx (SIGN_EXTRACT, GET_MODE (this_to),
XEXP (this_to, 0), XEXP (this_to, 1),
XEXP (this_to, 2));
}
/* If we are putting (ASHIFT 1 x) into (EQ (AND ... y) 0),
arrange to return (EQ (SIGN_EXTRACT y 1 x) 0),
which is what jump-on-bit instructions are written with. */
else if (XEXP (x, 1) == const0_rtx
&& GET_CODE (XEXP (x, 0)) == AND
&& (XEXP (XEXP (x, 0), 0) == from
|| XEXP (XEXP (x, 0), 1) == from)
&& GET_CODE (this_to) == ASHIFT
&& XEXP (this_to, 0) == const1_rtx)
{
register rtx y = XEXP (XEXP (x, 0),
XEXP (XEXP (x, 0), 0) == from);
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
this_to = gen_rtx (SIGN_EXTRACT, GET_MODE (this_to),
y,
const1_rtx, XEXP (this_to, 1));
from = XEXP (x, 0);
}
break;
case ZERO_EXTEND:
if (XEXP (x, 0) == from
&& GET_CODE (to) == ZERO_EXTEND)
this_to = XEXP (to, 0);
/* Zero-extending the result of an and with a constant can be done
with a wider and. */
if (XEXP (x, 0) == from
&& GET_CODE (to) == AND
&& GET_CODE (XEXP (to, 1)) == CONST_INT
&& (GET_CODE (XEXP (to, 0)) == REG
|| offsetable_address_p (XEXP (to, 0)))
/* Avoid getting wrong result if the constant has high bits set
that are irrelevant in the narrow mode where it is being used. */
&& ((INTVAL (XEXP (to, 1))
& (-1 << (GET_MODE_SIZE (GET_MODE (to)) * BITS_PER_UNIT)))
== 0))
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
return gen_rtx (AND, GET_MODE (x),
gen_lowpart (GET_MODE (x), XEXP (to, 0)),
XEXP (to, 1));
}
break;
case SIGN_EXTEND:
if (XEXP (x, 0) == from
&& GET_CODE (to) == SIGN_EXTEND)
this_to = XEXP (to, 0);
/* Sign-extending the result of an and with a constant can be done
with a wider and, provided the high bit of the constant is 0. */
if (XEXP (x, 0) == from
&& GET_CODE (to) == AND
&& GET_CODE (XEXP (to, 1)) == CONST_INT
&& (GET_CODE (XEXP (to, 0)) == REG
|| offsetable_address_p (XEXP (to, 0)))
&& ((INTVAL (XEXP (to, 1))
& (-1 << (GET_MODE_SIZE (GET_MODE (to)) * BITS_PER_UNIT - 1)))
== 0))
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
return gen_rtx (AND, GET_MODE (x),
gen_lowpart (GET_MODE (x), XEXP (to, 0)),
XEXP (to, 1));
}
break;
case SET:
/* In (set (zero-extract <x> <1> <y>) (and <foo> <1>))
the `and' can be deleted. This can happen when storing a bit
that came from a set-flag insn followed by masking to one bit.
There is probably no need to optimize other field widths similarly
because on machines with bit-field insns `and' is not needed
to extract the fields. */
if (GET_CODE (XEXP (x, 0)) == ZERO_EXTRACT
&& XEXP (XEXP (x, 0), 1) == const1_rtx
&& XEXP (x, 1) == from
&& GET_CODE (to) == AND
&& XEXP (to, 1) == const1_rtx)
{
this_to = XEXP (to, 0);
}
break;
case AND:
if (GET_CODE (XEXP (x, 1)) == CONST_INT)
{
rtx tem = simplify_and_const_int (x, from, to);
if (tem)
return tem;
}
break;
case FLOAT:
/* (float (sign_extend <X>)) = (float <X>). */
if (XEXP (x, 0) == from
&& GET_CODE (to) == SIGN_EXTEND)
this_to = XEXP (to, 0);
break;
case ZERO_EXTRACT:
/* Extracting a single bit from the result of a shift:
see which bit it was before the shift and extract that directly. */
if (XEXP (x, 0) == from
&& (GET_CODE (to) == ASHIFTRT || GET_CODE (to) == LSHIFTRT
|| GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
&& GET_CODE (XEXP (to, 1)) == CONST_INT
&& XEXP (x, 1) == const1_rtx
&& GET_CODE (XEXP (x, 2)) == CONST_INT)
{
int shift = INTVAL (XEXP (to, 1));
int newpos;
if (GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
shift = - shift;
#ifdef BITS_BIG_ENDIAN
shift = - shift;
#endif
newpos = INTVAL (XEXP (x, 2)) + shift;
if (newpos >= 0 &&
newpos < BITS_PER_UNIT * GET_MODE_SIZE (GET_MODE (from)))
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
return gen_rtx (ZERO_EXTRACT, GET_MODE (x),
XEXP (to, 0), const1_rtx,
gen_rtx (CONST_INT, VOIDmode, newpos));
}
}
break;
case LSHIFTRT:
case ASHIFTRT:
case ROTATE:
case ROTATERT:
#ifdef SHIFT_COUNT_TRUNCATED
/* (lshift <X> (sign_extend <Y>)) = (lshift <X> <Y>) (most machines).
True for all kinds of shifts and also for zero_extend. */
if (XEXP (x, 1) == from
&& (GET_CODE (to) == SIGN_EXTEND
|| GET_CODE (to) == ZERO_EXTEND))
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
this_to = gen_rtx (SUBREG, GET_MODE (to), XEXP (to, 0), 0);
}
#endif
/* Two shifts in a row of same kind
in same direction with constant counts
may be combined. */
if (XEXP (x, 0) == from
&& GET_CODE (to) == GET_CODE (x)
&& GET_CODE (XEXP (x, 1)) == CONST_INT
&& GET_CODE (XEXP (to, 1)) == CONST_INT
&& INTVAL (XEXP (to, 1)) > 0
&& INTVAL (XEXP (x, 1)) > 0
&& (INTVAL (XEXP (x, 1)) + INTVAL (XEXP (to, 1))
< BITS_PER_UNIT * GET_MODE_SIZE (GET_MODE (x))))
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
return gen_rtx (GET_CODE (x), GET_MODE (x),
XEXP (to, 0),
gen_rtx (CONST_INT, VOIDmode,
INTVAL (XEXP (x, 1))
+ INTVAL (XEXP (to, 1))));
}
break;
case LSHIFT:
case ASHIFT:
#ifdef SHIFT_COUNT_TRUNCATED
/* (lshift <X> (sign_extend <Y>)) = (lshift <X> <Y>) (most machines).
True for all kinds of shifts and also for zero_extend. */
if (XEXP (x, 1) == from
&& (GET_CODE (to) == SIGN_EXTEND
|| GET_CODE (to) == ZERO_EXTEND))
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
this_to = gen_rtx (SUBREG, GET_MODE (to), XEXP (to, 0), 0);
}
#endif
/* (lshift (and (lshiftrt <foo> <X>) <Y>) <X>)
happens copying between bit fields in similar structures.
It can be replaced by one and instruction.
It does not matter whether the shifts are logical or arithmetic. */
if (GET_CODE (XEXP (x, 0)) == AND
&& GET_CODE (XEXP (x, 1)) == CONST_INT
&& INTVAL (XEXP (x, 1)) > 0
&& GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
&& XEXP (XEXP (x, 0), 0) == from
&& (GET_CODE (to) == LSHIFTRT
|| GET_CODE (to) == ASHIFTRT)
#if 0
/* I now believe this restriction is unnecessary.
The outer shift will discard those bits in any case, right? */
/* If inner shift is arithmetic, either it shifts left or
the bits it shifts the sign into are zeroed by the and. */
&& (INTVAL (XEXP (x, 1)) < 0
|| ((unsigned) INTVAL (XEXP (XEXP (x, 0), 1))
< 1 << (GET_MODE_BITSIZE (GET_MODE (x))
- INTVAL (XEXP (x, 0)))))
#endif
&& GET_CODE (XEXP (to, 1)) == CONST_INT
&& INTVAL (XEXP (x, 1)) == INTVAL (XEXP (to, 1)))
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
/* The constant in the new `and' is <Y> << <X>
but clear out all bits that don't belong in our mode. */
return gen_rtx (AND, GET_MODE (x), XEXP (to, 0),
gen_rtx (CONST_INT, VOIDmode,
(GET_MODE_MASK (GET_MODE (x))
& ((GET_MODE_MASK (GET_MODE (x))
& INTVAL (XEXP (XEXP (x, 0), 1)))
<< INTVAL (XEXP (x, 1))))));
}
/* Two shifts in a row in same direction with constant counts
may be combined. */
if (XEXP (x, 0) == from
&& (GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
&& GET_CODE (XEXP (x, 1)) == CONST_INT
&& GET_CODE (XEXP (to, 1)) == CONST_INT
&& INTVAL (XEXP (to, 1)) > 0
&& INTVAL (XEXP (x, 1)) > 0
&& (INTVAL (XEXP (x, 1)) + INTVAL (XEXP (to, 1))
< BITS_PER_UNIT * GET_MODE_SIZE (GET_MODE (x))))
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
return gen_rtx (GET_CODE (x), GET_MODE (x),
XEXP (to, 0),
gen_rtx (CONST_INT, VOIDmode,
INTVAL (XEXP (x, 1))
+ INTVAL (XEXP (to, 1))));
}
/* (ashift (ashiftrt <foo> <X>) <X>)
(or, on some machines, (ashift (ashift <foo> <-X>) <X>) instead)
happens if you divide by 2**N and then multiply by 2**N.
It can be replaced by one `and' instruction.
It does not matter whether the shifts are logical or arithmetic. */
if (GET_CODE (XEXP (x, 1)) == CONST_INT
&& INTVAL (XEXP (x, 1)) > 0
&& XEXP (x, 0) == from
&& (((GET_CODE (to) == LSHIFTRT || GET_CODE (to) == ASHIFTRT)
&& GET_CODE (XEXP (to, 1)) == CONST_INT
&& INTVAL (XEXP (x, 1)) == INTVAL (XEXP (to, 1)))
||
((GET_CODE (to) == LSHIFT || GET_CODE (to) == ASHIFT)
&& GET_CODE (XEXP (to, 1)) == CONST_INT
&& INTVAL (XEXP (x, 1)) == - INTVAL (XEXP (to, 1)))))
{
if (!undobuf.storage)
undobuf.storage = (char *) oballoc (0);
/* The constant in the new `and' is <Y> << <X>
but clear out all bits that don't belong in our mode. */
return gen_rtx (AND, GET_MODE (x), XEXP (to, 0),
gen_rtx (CONST_INT, VOIDmode,
(GET_MODE_MASK (GET_MODE (x))
& (GET_MODE_MASK (GET_MODE (x))
<< INTVAL (XEXP (x, 1))))));
}
}
len = GET_RTX_LENGTH (code);
fmt = GET_RTX_FORMAT (code);
/* Don't replace FROM where it is being stored in rather than used. */