summaryrefslogtreecommitdiffstats
path: root/contrib/gcc/ra-build.c
blob: db2979a0120a912bb6fa29eaf3499fbbf96a3e51 (plain)
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
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
/* Graph coloring register allocator
   Copyright (C) 2001, 2002 Free Software Foundation, Inc.
   Contributed by Michael Matz <matz@suse.de>
   and Daniel Berlin <dan@cgsoftware.com>

   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 2, 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 COPYING.  If not, write to the Free Software
   Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */

#include "config.h"
#include "system.h"
#include "rtl.h"
#include "tm_p.h"
#include "insn-config.h"
#include "recog.h"
#include "reload.h"
#include "function.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "df.h"
#include "output.h"
#include "ggc.h"
#include "ra.h"

/* This file is part of the graph coloring register alloctor.
   It deals with building the interference graph.  When rebuilding
   the graph for a function after spilling, we rebuild only those
   parts needed, i.e. it works incrementally.

   The first part (the functions called from build_web_parts_and_conflicts()
   ) constructs a web_part for each pseudo register reference in the insn
   stream, then goes backward from each use, until it reaches defs for that
   pseudo.  While going back it remember seen defs for other registers as
   conflicts.  By connecting the uses and defs, which reach each other, webs
   (or live ranges) are built conceptually.

   The second part (make_webs() and childs) deals with converting that
   structure to the nodes and edges, on which our interference graph is
   built.  For each root web part constructed above, an instance of struct
   web is created.  For all subregs of pseudos, which matter for allocation,
   a subweb of the corresponding super web is built.  Finally all the
   conflicts noted in the first part (as bitmaps) are transformed into real
   edges.

   As part of that process the webs are also classified (their spill cost
   is calculated, and if they are spillable at all, and if not, for what
   reason; or if they are rematerializable), and move insns are collected,
   which are potentially coalescable.

   The top-level entry of this file (build_i_graph) puts it all together,
   and leaves us with a complete interference graph, which just has to
   be colored.  */


struct curr_use;

static unsigned HOST_WIDE_INT rtx_to_undefined PARAMS ((rtx));
static bitmap find_sub_conflicts PARAMS ((struct web_part *, unsigned int));
static bitmap get_sub_conflicts PARAMS ((struct web_part *, unsigned int));
static unsigned int undef_to_size_word PARAMS ((rtx, unsigned HOST_WIDE_INT *));
static bitmap undef_to_bitmap PARAMS ((struct web_part *,
				       unsigned HOST_WIDE_INT *));
static struct web_part * find_web_part_1 PARAMS ((struct web_part *));
static struct web_part * union_web_part_roots
				PARAMS ((struct web_part *, struct web_part *));
static int defuse_overlap_p_1 PARAMS ((rtx, struct curr_use *));
static int live_out_1 PARAMS ((struct df *, struct curr_use *, rtx));
static int live_out PARAMS ((struct df *, struct curr_use *, rtx));
static rtx live_in_edge PARAMS (( struct df *, struct curr_use *, edge));
static void live_in PARAMS ((struct df *, struct curr_use *, rtx));
static int copy_insn_p PARAMS ((rtx, rtx *, rtx *));
static void remember_move PARAMS ((rtx));
static void handle_asm_insn PARAMS ((struct df *, rtx));
static void prune_hardregs_for_mode PARAMS ((HARD_REG_SET *,
					     enum machine_mode));
static void init_one_web_common PARAMS ((struct web *, rtx));
static void init_one_web PARAMS ((struct web *, rtx));
static void reinit_one_web PARAMS ((struct web *, rtx));
static struct web * add_subweb PARAMS ((struct web *, rtx));
static struct web * add_subweb_2 PARAMS ((struct web *, unsigned int));
static void init_web_parts PARAMS ((struct df *));
static void copy_conflict_list PARAMS ((struct web *));
static void add_conflict_edge PARAMS ((struct web *, struct web *));
static void build_inverse_webs PARAMS ((struct web *));
static void copy_web PARAMS ((struct web *, struct web_link **));
static void compare_and_free_webs PARAMS ((struct web_link **));
static void init_webs_defs_uses PARAMS ((void));
static unsigned int parts_to_webs_1 PARAMS ((struct df *, struct web_link **,
					     struct df_link *));
static void parts_to_webs PARAMS ((struct df *));
static void reset_conflicts PARAMS ((void));
#if 0
static void check_conflict_numbers PARAMS ((void));
#endif
static void conflicts_between_webs PARAMS ((struct df *));
static void remember_web_was_spilled PARAMS ((struct web *));
static void detect_spill_temps PARAMS ((void));
static int contains_pseudo PARAMS ((rtx));
static int want_to_remat PARAMS ((rtx x));
static void detect_remat_webs PARAMS ((void));
static void determine_web_costs PARAMS ((void));
static void detect_webs_set_in_cond_jump PARAMS ((void));
static void make_webs PARAMS ((struct df *));
static void moves_to_webs PARAMS ((struct df *));
static void connect_rmw_web_parts PARAMS ((struct df *));
static void update_regnos_mentioned PARAMS ((void));
static void livethrough_conflicts_bb PARAMS ((basic_block));
static void init_bb_info PARAMS ((void));
static void free_bb_info PARAMS ((void));
static void build_web_parts_and_conflicts PARAMS ((struct df *));


/* A sbitmap of DF_REF_IDs of uses, which are live over an abnormal
   edge.  */
static sbitmap live_over_abnormal;

/* To cache if we already saw a certain edge while analyzing one
   use, we use a tick count incremented per use.  */
static unsigned int visited_pass;

/* A sbitmap of UIDs of move insns, which we already analyzed.  */
static sbitmap move_handled;

/* One such structed is allocated per insn, and traces for the currently
   analyzed use, which web part belongs to it, and how many bytes of
   it were still undefined when that insn was reached.  */
struct visit_trace
{
  struct web_part *wp;
  unsigned HOST_WIDE_INT undefined;
};
/* Indexed by UID.  */
static struct visit_trace *visit_trace;

/* Per basic block we have one such structure, used to speed up
   the backtracing of uses.  */
struct ra_bb_info
{
  /* The value of visited_pass, as the first insn of this BB was reached
     the last time.  If this equals the current visited_pass, then
     undefined is valid.  Otherwise not.  */
  unsigned int pass;
  /* The still undefined bytes at that time.  The use to which this is
     relative is the current use.  */
  unsigned HOST_WIDE_INT undefined;
  /* Bit regno is set, if that regno is mentioned in this BB as a def, or
     the source of a copy insn.  In these cases we can not skip the whole
     block if we reach it from the end.  */
  bitmap regnos_mentioned;
  /* If a use reaches the end of a BB, and that BB doesn't mention its
     regno, we skip the block, and remember the ID of that use
     as living throughout the whole block.  */
  bitmap live_throughout;
  /* The content of the aux field before placing a pointer to this
     structure there.  */
  void *old_aux;
};

/* We need a fast way to describe a certain part of a register.
   Therefore we put together the size and offset (in bytes) in one
   integer.  */
#define BL_TO_WORD(b, l) ((((b) & 0xFFFF) << 16) | ((l) & 0xFFFF))
#define BYTE_BEGIN(i) (((unsigned int)(i) >> 16) & 0xFFFF)
#define BYTE_LENGTH(i) ((unsigned int)(i) & 0xFFFF)

/* For a REG or SUBREG expression X return the size/offset pair
   as an integer.  */

unsigned int
rtx_to_bits (x)
     rtx x;
{
  unsigned int len, beg;
  len = GET_MODE_SIZE (GET_MODE (x));
  beg = (GET_CODE (x) == SUBREG) ? SUBREG_BYTE (x) : 0;
  return BL_TO_WORD (beg, len);
}

/* X is a REG or SUBREG rtx.  Return the bytes it touches as a bitmask.  */

static unsigned HOST_WIDE_INT
rtx_to_undefined (x)
     rtx x;
{
  unsigned int len, beg;
  unsigned HOST_WIDE_INT ret;
  len = GET_MODE_SIZE (GET_MODE (x));
  beg = (GET_CODE (x) == SUBREG) ? SUBREG_BYTE (x) : 0;
  ret = ~ ((unsigned HOST_WIDE_INT) 0);
  ret = (~(ret << len)) << beg;
  return ret;
}

/* We remember if we've analyzed an insn for being a move insn, and if yes
   between which operands.  */
struct copy_p_cache
{
  int seen;
  rtx source;
  rtx target;
};

/* On demand cache, for if insns are copy insns, and if yes, what
   source/target they have.  */
static struct copy_p_cache * copy_cache;

int *number_seen;

/* For INSN, return nonzero, if it's a move insn, we consider to coalesce
   later, and place the operands in *SOURCE and *TARGET, if they are
   not NULL.  */

static int
copy_insn_p (insn, source, target)
     rtx insn;
     rtx *source;
     rtx *target;
{
  rtx d, s;
  unsigned int d_regno, s_regno;
  int uid = INSN_UID (insn);

  if (!INSN_P (insn))
    abort ();

  /* First look, if we already saw this insn.  */
  if (copy_cache[uid].seen)
    {
      /* And if we saw it, if it's actually a copy insn.  */
      if (copy_cache[uid].seen == 1)
	{
	  if (source)
	    *source = copy_cache[uid].source;
	  if (target)
	    *target = copy_cache[uid].target;
	  return 1;
	}
      return 0;
    }

  /* Mark it as seen, but not being a copy insn.  */
  copy_cache[uid].seen = 2;
  insn = single_set (insn);
  if (!insn)
    return 0;
  d = SET_DEST (insn);
  s = SET_SRC (insn);

  /* We recognize moves between subreg's as copy insns.  This is used to avoid
     conflicts of those subwebs.  But they are currently _not_ used for
     coalescing (the check for this is in remember_move() below).  */
  while (GET_CODE (d) == STRICT_LOW_PART)
    d = XEXP (d, 0);
  if (GET_CODE (d) != REG
      && (GET_CODE (d) != SUBREG || GET_CODE (SUBREG_REG (d)) != REG))
    return 0;
  while (GET_CODE (s) == STRICT_LOW_PART)
    s = XEXP (s, 0);
  if (GET_CODE (s) != REG
      && (GET_CODE (s) != SUBREG || GET_CODE (SUBREG_REG (s)) != REG))
    return 0;

  s_regno = (unsigned) REGNO (GET_CODE (s) == SUBREG ? SUBREG_REG (s) : s);
  d_regno = (unsigned) REGNO (GET_CODE (d) == SUBREG ? SUBREG_REG (d) : d);

  /* Copies between hardregs are useless for us, as not coalesable anyway.  */
  if ((s_regno < FIRST_PSEUDO_REGISTER
       && d_regno < FIRST_PSEUDO_REGISTER)
      || s_regno >= max_normal_pseudo
      || d_regno >= max_normal_pseudo)
    return 0;

  if (source)
    *source = s;
  if (target)
    *target = d;

  /* Still mark it as seen, but as a copy insn this time.  */
  copy_cache[uid].seen = 1;
  copy_cache[uid].source = s;
  copy_cache[uid].target = d;
  return 1;
}

/* We build webs, as we process the conflicts.  For each use we go upward
   the insn stream, noting any defs as potentially conflicting with the
   current use.  We stop at defs of the current regno.  The conflicts are only
   potentially, because we may never reach a def, so this is an undefined use,
   which conflicts with nothing.  */


/* Given a web part WP, and the location of a reg part SIZE_WORD
   return the conflict bitmap for that reg part, or NULL if it doesn't
   exist yet in WP.  */

static bitmap
find_sub_conflicts (wp, size_word)
     struct web_part *wp;
     unsigned int size_word;
{
  struct tagged_conflict *cl;
  cl = wp->sub_conflicts;
  for (; cl; cl = cl->next)
    if (cl->size_word == size_word)
      return cl->conflicts;
  return NULL;
}

/* Similar to find_sub_conflicts(), but creates that bitmap, if it
   doesn't exist.  I.e. this never returns NULL.  */

static bitmap
get_sub_conflicts (wp, size_word)
     struct web_part *wp;
     unsigned int size_word;
{
  bitmap b = find_sub_conflicts (wp, size_word);
  if (!b)
    {
      struct tagged_conflict *cl =
	(struct tagged_conflict *) ra_alloc (sizeof *cl);
      cl->conflicts = BITMAP_XMALLOC ();
      cl->size_word = size_word;
      cl->next = wp->sub_conflicts;
      wp->sub_conflicts = cl;
      b = cl->conflicts;
    }
  return b;
}

/* Helper table for undef_to_size_word() below for small values
   of UNDEFINED.  Offsets and lengths are byte based.  */
static struct undef_table_s {
  unsigned int new_undef;
  /* size | (byte << 16)  */
  unsigned int size_word;
} const undef_table [] = {
  { 0, BL_TO_WORD (0, 0)}, /* 0 */
  { 0, BL_TO_WORD (0, 1)},
  { 0, BL_TO_WORD (1, 1)},
  { 0, BL_TO_WORD (0, 2)},
  { 0, BL_TO_WORD (2, 1)}, /* 4 */
  { 1, BL_TO_WORD (2, 1)},
  { 2, BL_TO_WORD (2, 1)},
  { 3, BL_TO_WORD (2, 1)},
  { 0, BL_TO_WORD (3, 1)}, /* 8 */
  { 1, BL_TO_WORD (3, 1)},
  { 2, BL_TO_WORD (3, 1)},
  { 3, BL_TO_WORD (3, 1)},
  { 0, BL_TO_WORD (2, 2)}, /* 12 */
  { 1, BL_TO_WORD (2, 2)},
  { 2, BL_TO_WORD (2, 2)},
  { 0, BL_TO_WORD (0, 4)}};

/* Interpret *UNDEFINED as bitmask where each bit corresponds to a byte.
   A set bit means an undefined byte.  Factor all undefined bytes into
   groups, and return a size/ofs pair of consecutive undefined bytes,
   but according to certain borders.  Clear out those bits corrsponding
   to bytes overlaid by that size/ofs pair.  REG is only used for
   the mode, to detect if it's a floating mode or not.

   For example:	*UNDEFINED	size+ofs	new *UNDEFINED
		 1111		4+0		  0
		 1100		2+2		  0
		 1101		2+2		  1
		 0001		1+0		  0
		10101		1+4		101

   */

static unsigned int
undef_to_size_word (reg, undefined)
     rtx reg;
     unsigned HOST_WIDE_INT *undefined;
{
  /* When only the lower four bits are possibly set, we use
     a fast lookup table.  */
  if (*undefined <= 15)
    {
      struct undef_table_s u;
      u = undef_table[*undefined];
      *undefined = u.new_undef;
      return u.size_word;
    }

  /* Otherwise we handle certain cases directly.  */
  switch (*undefined)
    {
      case 0x00f0 : *undefined = 0; return BL_TO_WORD (4, 4);
      case 0x00ff : *undefined = 0; return BL_TO_WORD (0, 8);
      case 0x0f00 : *undefined = 0; return BL_TO_WORD (8, 4);
      case 0x0ff0 : *undefined = 0xf0; return BL_TO_WORD (8, 4);
      case 0x0fff :
	if (INTEGRAL_MODE_P (GET_MODE (reg)))
	  { *undefined = 0xff; return BL_TO_WORD (8, 4); }
	else
	  { *undefined = 0; return BL_TO_WORD (0, 12); /* XFmode */ }
      case 0xf000 : *undefined = 0; return BL_TO_WORD (12, 4);
      case 0xff00 : *undefined = 0; return BL_TO_WORD (8, 8);
      case 0xfff0 : *undefined = 0xf0; return BL_TO_WORD (8, 8);
      case 0xffff : *undefined = 0; return BL_TO_WORD (0, 16);

      /* And if nothing matched fall back to the general solution.
	 For now unknown undefined bytes are converted to sequences
	 of maximal length 4 bytes.  We could make this larger if
	 necessary.  */
      default :
	{
	  unsigned HOST_WIDE_INT u = *undefined;
	  int word;
	  struct undef_table_s tab;
	  for (word = 0; (u & 15) == 0; word += 4)
	    u >>= 4;
	  u = u & 15;
	  tab = undef_table[u];
	  u = tab.new_undef;
	  u = (*undefined & ~((unsigned HOST_WIDE_INT)15 << word))
	      | (u << word);
	  *undefined = u;
	  /* Size remains the same, only the begin is moved up move bytes.  */
	  return tab.size_word + BL_TO_WORD (word, 0);
	}
	break;
    }
}

/* Put the above three functions together.  For a set of undefined bytes
   as bitmap *UNDEFINED, look for (create if necessary) and return the
   corresponding conflict bitmap.  Change *UNDEFINED to remove the bytes
   covered by the part for that bitmap.  */

static bitmap
undef_to_bitmap (wp, undefined)
     struct web_part *wp;
     unsigned HOST_WIDE_INT *undefined;
{
  unsigned int size_word = undef_to_size_word (DF_REF_REAL_REG (wp->ref),
					       undefined);
  return get_sub_conflicts (wp, size_word);
}

/* Returns the root of the web part P is a member of.  Additionally
   it compresses the path.  P may not be NULL.  */

static struct web_part *
find_web_part_1 (p)
     struct web_part *p;
{
  struct web_part *r = p;
  struct web_part *p_next;
  while (r->uplink)
    r = r->uplink;
  for (; p != r; p = p_next)
    {
      p_next = p->uplink;
      p->uplink = r;
    }
  return r;
}

/* Fast macro for the common case (WP either being the root itself, or
   the end of an already compressed path.  */

#define find_web_part(wp) ((! (wp)->uplink) ? (wp) \
  : (! (wp)->uplink->uplink) ? (wp)->uplink : find_web_part_1 (wp))

/* Unions together the parts R1 resp. R2 is a root of.
   All dynamic information associated with the parts (number of spanned insns
   and so on) is also merged.
   The root of the resulting (possibly larger) web part is returned.  */

static struct web_part *
union_web_part_roots (r1, r2)
     struct web_part *r1, *r2;
{
  if (r1 != r2)
    {
      /* The new root is the smaller (pointerwise) of both.  This is crucial
         to make the construction of webs from web parts work (so, when
	 scanning all parts, we see the roots before all it's childs).
         Additionally this ensures, that if the web has a def at all, than
         the root is a def (because all def parts are before use parts in the
	 web_parts[] array), or put another way, as soon, as the root of a
         web part is not a def, this is an uninitialized web part.  The
         way we construct the I-graph ensures, that if a web is initialized,
         then the first part we find (besides trivial 1 item parts) has a
         def.  */
      if (r1 > r2)
	{
	  struct web_part *h = r1;
	  r1 = r2;
	  r2 = h;
	}
      r2->uplink = r1;
      num_webs--;

      /* Now we merge the dynamic information of R1 and R2.  */
      r1->spanned_deaths += r2->spanned_deaths;

      if (!r1->sub_conflicts)
	r1->sub_conflicts = r2->sub_conflicts;
      else if (r2->sub_conflicts)
	/* We need to merge the conflict bitmaps from R2 into R1.  */
	{
	  struct tagged_conflict *cl1, *cl2;
	  /* First those from R2, which are also contained in R1.
	     We union the bitmaps, and free those from R2, resetting them
	     to 0.  */
	  for (cl1 = r1->sub_conflicts; cl1; cl1 = cl1->next)
	    for (cl2 = r2->sub_conflicts; cl2; cl2 = cl2->next)
	      if (cl1->size_word == cl2->size_word)
		{
		  bitmap_operation (cl1->conflicts, cl1->conflicts,
				    cl2->conflicts, BITMAP_IOR);
		  BITMAP_XFREE (cl2->conflicts);
		  cl2->conflicts = NULL;
		}
	  /* Now the conflict lists from R2 which weren't in R1.
	     We simply copy the entries from R2 into R1' list.  */
	  for (cl2 = r2->sub_conflicts; cl2;)
	    {
	      struct tagged_conflict *cl_next = cl2->next;
	      if (cl2->conflicts)
		{
		  cl2->next = r1->sub_conflicts;
		  r1->sub_conflicts = cl2;
		}
	      cl2 = cl_next;
	    }
	}
      r2->sub_conflicts = NULL;
      r1->crosses_call |= r2->crosses_call;
    }
  return r1;
}

/* Convenience macro, that is cabable of unioning also non-roots.  */
#define union_web_parts(p1, p2) \
  ((p1 == p2) ? find_web_part (p1) \
      : union_web_part_roots (find_web_part (p1), find_web_part (p2)))

/* Remember that we've handled a given move, so we don't reprocess it.  */

static void
remember_move (insn)
     rtx insn;
{
  if (!TEST_BIT (move_handled, INSN_UID (insn)))
    {
      rtx s, d;
      SET_BIT (move_handled, INSN_UID (insn));
      if (copy_insn_p (insn, &s, &d))
	{
	  /* Some sanity test for the copy insn.  */
	  struct df_link *slink = DF_INSN_USES (df, insn);
	  struct df_link *link = DF_INSN_DEFS (df, insn);
	  if (!link || !link->ref || !slink || !slink->ref)
	    abort ();
	  /* The following (link->next != 0) happens when a hardreg
	     is used in wider mode (REG:DI %eax).  Then df.* creates
	     a def/use for each hardreg contained therein.  We only
	     allow hardregs here.  */
	  if (link->next
	      && DF_REF_REGNO (link->next->ref) >= FIRST_PSEUDO_REGISTER)
	    abort ();
	}
      else
	abort ();
      /* XXX for now we don't remember move insns involving any subregs.
	 Those would be difficult to coalesce (we would need to implement
	 handling of all the subwebs in the allocator, including that such
	 subwebs could be source and target of coalesing).  */
      if (GET_CODE (s) == REG && GET_CODE (d) == REG)
	{
	  struct move *m = (struct move *) ra_calloc (sizeof (struct move));
	  struct move_list *ml;
	  m->insn = insn;
	  ml = (struct move_list *) ra_alloc (sizeof (struct move_list));
	  ml->move = m;
	  ml->next = wl_moves;
	  wl_moves = ml;
	}
    }
}

/* This describes the USE currently looked at in the main-loop in
   build_web_parts_and_conflicts().  */
struct curr_use {
  struct web_part *wp;
  /* This has a 1-bit for each byte in the USE, which is still undefined.  */
  unsigned HOST_WIDE_INT undefined;
  /* For easy access.  */
  unsigned int regno;
  rtx x;
  /* If some bits of this USE are live over an abnormal edge.  */
  unsigned int live_over_abnormal;
};

/* Returns nonzero iff rtx DEF and USE have bits in common (but see below).
   It is only called with DEF and USE being (reg:M a) or (subreg:M1 (reg:M2 a)
   x) rtx's.  Furthermore if it's a subreg rtx M1 is at least one word wide,
   and a is a multi-word pseudo.  If DEF or USE are hardregs, they are in
   word_mode, so we don't need to check for further hardregs which would result
   from wider references.  We are never called with paradoxical subregs.

   This returns:
   0 for no common bits,
   1 if DEF and USE exactly cover the same bytes,
   2 if the DEF only covers a part of the bits of USE
   3 if the DEF covers more than the bits of the USE, and
   4 if both are SUBREG's of different size, but have bytes in common.
   -1 is a special case, for when DEF and USE refer to the same regno, but
      have for other reasons no bits in common (can only happen with
      subregs refering to different words, or to words which already were
      defined for this USE).
   Furthermore it modifies use->undefined to clear the bits which get defined
   by DEF (only for cases with partial overlap).
   I.e. if bit 1 is set for the result != -1, the USE was completely covered,
   otherwise a test is needed to track the already defined bytes.  */

static int
defuse_overlap_p_1 (def, use)
     rtx def;
     struct curr_use *use;
{
  int mode = 0;
  if (def == use->x)
    return 1;
  if (!def)
    return 0;
  if (GET_CODE (def) == SUBREG)
    {
      if (REGNO (SUBREG_REG (def)) != use->regno)
	return 0;
      mode |= 1;
    }
  else if (REGNO (def) != use->regno)
    return 0;
  if (GET_CODE (use->x) == SUBREG)
    mode |= 2;
  switch (mode)
    {
      case 0: /* REG, REG */
	return 1;
      case 1: /* SUBREG, REG */
	{
	  unsigned HOST_WIDE_INT old_u = use->undefined;
	  use->undefined &= ~ rtx_to_undefined (def);
	  return (old_u != use->undefined) ? 2 : -1;
	}
      case 2: /* REG, SUBREG */
	return 3;
      case 3: /* SUBREG, SUBREG */
	if (GET_MODE_SIZE (GET_MODE (def)) == GET_MODE_SIZE (GET_MODE (use->x)))
	  /* If the size of both things is the same, the subreg's overlap
	     if they refer to the same word.  */
	  if (SUBREG_BYTE (def) == SUBREG_BYTE (use->x))
	    return 1;
	/* Now the more difficult part: the same regno is refered, but the
	   sizes of the references or the words differ.  E.g.
           (subreg:SI (reg:CDI a) 0) and (subreg:DI (reg:CDI a) 2) do not
	   overlap, wereas the latter overlaps with (subreg:SI (reg:CDI a) 3).
	   */
	{
	  unsigned HOST_WIDE_INT old_u;
	  int b1, e1, b2, e2;
	  unsigned int bl1, bl2;
	  bl1 = rtx_to_bits (def);
	  bl2 = rtx_to_bits (use->x);
	  b1 = BYTE_BEGIN (bl1);
	  b2 = BYTE_BEGIN (bl2);
	  e1 = b1 + BYTE_LENGTH (bl1) - 1;
	  e2 = b2 + BYTE_LENGTH (bl2) - 1;
	  if (b1 > e2 || b2 > e1)
	    return -1;
	  old_u = use->undefined;
	  use->undefined &= ~ rtx_to_undefined (def);
	  return (old_u != use->undefined) ? 4 : -1;
	}
      default:
        abort ();
    }
}

/* Macro for the common case of either def and use having the same rtx,
   or based on different regnos.  */
#define defuse_overlap_p(def, use) \
  ((def) == (use)->x ? 1 : \
     (REGNO (GET_CODE (def) == SUBREG \
	     ? SUBREG_REG (def) : def) != use->regno \
      ? 0 : defuse_overlap_p_1 (def, use)))


/* The use USE flows into INSN (backwards).  Determine INSNs effect on it,
   and return nonzero, if (parts of) that USE are also live before it.
   This also notes conflicts between the USE and all DEFS in that insn,
   and modifies the undefined bits of USE in case parts of it were set in
   this insn.  */

static int
live_out_1 (df, use, insn)
     struct df *df ATTRIBUTE_UNUSED;
     struct curr_use *use;
     rtx insn;
{
  int defined = 0;
  int uid = INSN_UID (insn);
  struct web_part *wp = use->wp;

  /* Mark, that this insn needs this webpart live.  */
  visit_trace[uid].wp = wp;
  visit_trace[uid].undefined = use->undefined;

  if (INSN_P (insn))
    {
      unsigned int source_regno = ~0;
      unsigned int regno = use->regno;
      unsigned HOST_WIDE_INT orig_undef = use->undefined;
      unsigned HOST_WIDE_INT final_undef = use->undefined;
      rtx s = NULL;
      unsigned int n, num_defs = insn_df[uid].num_defs;
      struct ref **defs = insn_df[uid].defs;

      /* We want to access the root webpart.  */
      wp = find_web_part (wp);
      if (GET_CODE (insn) == CALL_INSN)
	wp->crosses_call = 1;
      else if (copy_insn_p (insn, &s, NULL))
	source_regno = REGNO (GET_CODE (s) == SUBREG ? SUBREG_REG (s) : s);

      /* Look at all DEFS in this insn.  */
      for (n = 0; n < num_defs; n++)
	{
	  struct ref *ref = defs[n];
	  int lap;

	  /* Reset the undefined bits for each iteration, in case this
	     insn has more than one set, and one of them sets this regno.
	     But still the original undefined part conflicts with the other
	     sets.  */
	  use->undefined = orig_undef;
	  if ((lap = defuse_overlap_p (DF_REF_REG (ref), use)) != 0)
	    {
	      if (lap == -1)
		  /* Same regnos but non-overlapping or already defined bits,
		     so ignore this DEF, or better said make the yet undefined
		     part and this DEF conflicting.  */
		{
		  unsigned HOST_WIDE_INT undef;
		  undef = use->undefined;
		  while (undef)
		    bitmap_set_bit (undef_to_bitmap (wp, &undef),
				    DF_REF_ID (ref));
		  continue;
		}
	      if ((lap & 1) != 0)
		  /* The current DEF completely covers the USE, so we can
		     stop traversing the code looking for further DEFs.  */
		defined = 1;
	      else
		  /* We have a partial overlap.  */
		{
		  final_undef &= use->undefined;
		  if (final_undef == 0)
		    /* Now the USE is completely defined, which means, that
		       we can stop looking for former DEFs.  */
		    defined = 1;
		  /* If this is a partial overlap, which left some bits
		     in USE undefined, we normally would need to create
		     conflicts between that undefined part and the part of
		     this DEF which overlapped with some of the formerly
		     undefined bits.  We don't need to do this, because both
		     parts of this DEF (that which overlaps, and that which
		     doesn't) are written together in this one DEF, and can
		     not be colored in a way which would conflict with
		     the USE.  This is only true for partial overlap,
		     because only then the DEF and USE have bits in common,
		     which makes the DEF move, if the USE moves, making them
		     aligned.
		     If they have no bits in common (lap == -1), they are
		     really independent.  Therefore we there made a
		     conflict above.  */
		}
	      /* This is at least a partial overlap, so we need to union
		 the web parts.  */
	      wp = union_web_parts (wp, &web_parts[DF_REF_ID (ref)]);
	    }
	  else
	    {
	      /* The DEF and the USE don't overlap at all, different
		 regnos.  I.e. make conflicts between the undefined bits,
	         and that DEF.  */
	      unsigned HOST_WIDE_INT undef = use->undefined;

	      if (regno == source_regno)
		/* This triggers only, when this was a copy insn and the
		   source is at least a part of the USE currently looked at.
		   In this case only the bits of the USE conflict with the
		   DEF, which are not covered by the source of this copy
		   insn, and which are still undefined.  I.e. in the best
		   case (the whole reg being the source), _no_ conflicts
		   between that USE and this DEF (the target of the move)
		   are created by this insn (though they might be by
		   others).  This is a super case of the normal copy insn
		   only between full regs.  */
		{
		  undef &= ~ rtx_to_undefined (s);
		}
	      if (undef)
		{
		  /*struct web_part *cwp;
		    cwp = find_web_part (&web_parts[DF_REF_ID
		    (ref)]);*/

		  /* TODO: somehow instead of noting the ID of the LINK
		     use an ID nearer to the root webpart of that LINK.
		     We can't use the root itself, because we later use the
		     ID to look at the form (reg or subreg, and if yes,
		     which subreg) of this conflict.  This means, that we
		     need to remember in the root an ID for each form, and
		     maintaining this, when merging web parts.  This makes
		     the bitmaps smaller.  */
		  do
		    bitmap_set_bit (undef_to_bitmap (wp, &undef),
				    DF_REF_ID (ref));
		  while (undef);
		}
	    }
	}
      if (defined)
	use->undefined = 0;
      else
	{
	  /* If this insn doesn't completely define the USE, increment also
	     it's spanned deaths count (if this insn contains a death).  */
	  if (uid >= death_insns_max_uid)
	    abort ();
	  if (TEST_BIT (insns_with_deaths, uid))
	    wp->spanned_deaths++;
	  use->undefined = final_undef;
	}
    }

  return !defined;
}

/* Same as live_out_1() (actually calls it), but caches some information.
   E.g. if we reached this INSN with the current regno already, and the
   current undefined bits are a subset of those as we came here, we
   simply connect the web parts of the USE, and the one cached for this
   INSN, and additionally return zero, indicating we don't need to traverse
   this path any longer (all effect were already seen, as we first reached
   this insn).  */

static inline int
live_out (df, use, insn)
     struct df *df;
     struct curr_use *use;
     rtx insn;
{
  unsigned int uid = INSN_UID (insn);
  if (visit_trace[uid].wp
      && DF_REF_REGNO (visit_trace[uid].wp->ref) == use->regno
      && (use->undefined & ~visit_trace[uid].undefined) == 0)
    {
      union_web_parts (visit_trace[uid].wp, use->wp);
      /* Don't search any further, as we already were here with this regno.  */
      return 0;
    }
  else
    return live_out_1 (df, use, insn);
}

/* The current USE reached a basic block head.  The edge E is one
   of the predecessors edges.  This evaluates the effect of the predecessor
   block onto the USE, and returns the next insn, which should be looked at.
   This either is the last insn of that pred. block, or the first one.
   The latter happens, when the pred. block has no possible effect on the
   USE, except for conflicts.  In that case, it's remembered, that the USE
   is live over that whole block, and it's skipped.  Otherwise we simply
   continue with the last insn of the block.

   This also determines the effects of abnormal edges, and remembers
   which uses are live at the end of that basic block.  */

static rtx
live_in_edge (df, use, e)
     struct df *df;
     struct curr_use *use;
     edge e;
{
  struct ra_bb_info *info_pred;
  rtx next_insn;
  /* Call used hard regs die over an exception edge, ergo
     they don't reach the predecessor block, so ignore such
     uses.  And also don't set the live_over_abnormal flag
     for them.  */
  if ((e->flags & EDGE_EH) && use->regno < FIRST_PSEUDO_REGISTER
      && call_used_regs[use->regno])
    return NULL_RTX;
  if (e->flags & EDGE_ABNORMAL)
    use->live_over_abnormal = 1;
  bitmap_set_bit (live_at_end[e->src->index], DF_REF_ID (use->wp->ref));
  info_pred = (struct ra_bb_info *) e->src->aux;
  next_insn = e->src->end;

  /* If the last insn of the pred. block doesn't completely define the
     current use, we need to check the block.  */
  if (live_out (df, use, next_insn))
    {
      /* If the current regno isn't mentioned anywhere in the whole block,
	 and the complete use is still undefined...  */
      if (!bitmap_bit_p (info_pred->regnos_mentioned, use->regno)
	  && (rtx_to_undefined (use->x) & ~use->undefined) == 0)
	{
	  /* ...we can hop over the whole block and defer conflict
	     creation to later.  */
	  bitmap_set_bit (info_pred->live_throughout,
			  DF_REF_ID (use->wp->ref));
	  next_insn = e->src->head;
	}
      return next_insn;
    }
  else
    return NULL_RTX;
}

/* USE flows into the end of the insns preceding INSN.  Determine
   their effects (in live_out()) and possibly loop over the preceding INSN,
   or call itself recursively on a basic block border.  When a topleve
   call of this function returns the USE is completely analyzed.  I.e.
   its def-use chain (at least) is built, possibly connected with other
   def-use chains, and all defs during that chain are noted.  */

static void
live_in (df, use, insn)
     struct df *df;
     struct curr_use *use;
     rtx insn;
{
  unsigned int loc_vpass = visited_pass;

  /* Note, that, even _if_ we are called with use->wp a root-part, this might
     become non-root in the for() loop below (due to live_out() unioning
     it).  So beware, not to change use->wp in a way, for which only root-webs
     are allowed.  */
  while (1)
    {
      int uid = INSN_UID (insn);
      basic_block bb = BLOCK_FOR_INSN (insn);
      number_seen[uid]++;

      /* We want to be as fast as possible, so explicitely write
	 this loop.  */
      for (insn = PREV_INSN (insn); insn && !INSN_P (insn);
	   insn = PREV_INSN (insn))
	;
      if (!insn)
	return;
      if (bb != BLOCK_FOR_INSN (insn))
	{
	  edge e;
	  unsigned HOST_WIDE_INT undef = use->undefined;
	  struct ra_bb_info *info = (struct ra_bb_info *) bb->aux;
	  if ((e = bb->pred) == NULL)
	    return;
	  /* We now check, if we already traversed the predecessors of this
	     block for the current pass and the current set of undefined
	     bits.  If yes, we don't need to check the predecessors again.
	     So, conceptually this information is tagged to the first
	     insn of a basic block.  */
	  if (info->pass == loc_vpass && (undef & ~info->undefined) == 0)
	    return;
	  info->pass = loc_vpass;
	  info->undefined = undef;
	  /* All but the last predecessor are handled recursively.  */
	  for (; e->pred_next; e = e->pred_next)
	    {
	      insn = live_in_edge (df, use, e);
	      if (insn)
		live_in (df, use, insn);
	      use->undefined = undef;
	    }
	  insn = live_in_edge (df, use, e);
	  if (!insn)
	    return;
	}
      else if (!live_out (df, use, insn))
	return;
    }
}

/* Determine all regnos which are mentioned in a basic block, in an
   interesting way.  Interesting here means either in a def, or as the
   source of a move insn.  We only look at insns added since the last
   pass.  */

static void
update_regnos_mentioned ()
{
  int last_uid = last_max_uid;
  rtx insn;
  basic_block bb;
  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
    if (INSN_P (insn))
      {
	/* Don't look at old insns.  */
	if (INSN_UID (insn) < last_uid)
	  {
	    /* XXX We should also remember moves over iterations (we already
	       save the cache, but not the movelist).  */
	    if (copy_insn_p (insn, NULL, NULL))
	      remember_move (insn);
	  }
	else if ((bb = BLOCK_FOR_INSN (insn)) != NULL)
	  {
	    rtx source;
	    struct ra_bb_info *info = (struct ra_bb_info *) bb->aux;
	    bitmap mentioned = info->regnos_mentioned;
	    struct df_link *link;
	    if (copy_insn_p (insn, &source, NULL))
	      {
		remember_move (insn);
		bitmap_set_bit (mentioned,
				REGNO (GET_CODE (source) == SUBREG
				       ? SUBREG_REG (source) : source));
	      }
	    for (link = DF_INSN_DEFS (df, insn); link; link = link->next)
	      if (link->ref)
		bitmap_set_bit (mentioned, DF_REF_REGNO (link->ref));
	  }
      }
}

/* Handle the uses which reach a block end, but were defered due
   to it's regno not being mentioned in that block.  This adds the
   remaining conflicts and updates also the crosses_call and
   spanned_deaths members.  */

static void
livethrough_conflicts_bb (bb)
     basic_block bb;
{
  struct ra_bb_info *info = (struct ra_bb_info *) bb->aux;
  rtx insn;
  bitmap all_defs;
  int first, use_id;
  unsigned int deaths = 0;
  unsigned int contains_call = 0;

  /* If there are no defered uses, just return.  */
  if ((first = bitmap_first_set_bit (info->live_throughout)) < 0)
    return;

  /* First collect the IDs of all defs, count the number of death
     containing insns, and if there's some call_insn here.  */
  all_defs = BITMAP_XMALLOC ();
  for (insn = bb->head; insn; insn = NEXT_INSN (insn))
    {
      if (INSN_P (insn))
	{
	  unsigned int n;
	  struct ra_insn_info info;

	  info = insn_df[INSN_UID (insn)];
	  for (n = 0; n < info.num_defs; n++)
	    bitmap_set_bit (all_defs, DF_REF_ID (info.defs[n]));
	  if (TEST_BIT (insns_with_deaths, INSN_UID (insn)))
	    deaths++;
	  if (GET_CODE (insn) == CALL_INSN)
	    contains_call = 1;
	}
      if (insn == bb->end)
	break;
    }

  /* And now, if we have found anything, make all live_through
     uses conflict with all defs, and update their other members.  */
  if (deaths > 0 || bitmap_first_set_bit (all_defs) >= 0)
    EXECUTE_IF_SET_IN_BITMAP (info->live_throughout, first, use_id,
      {
        struct web_part *wp = &web_parts[df->def_id + use_id];
        unsigned int bl = rtx_to_bits (DF_REF_REG (wp->ref));
        bitmap conflicts;
        wp = find_web_part (wp);
        wp->spanned_deaths += deaths;
	wp->crosses_call |= contains_call;
        conflicts = get_sub_conflicts (wp, bl);
        bitmap_operation (conflicts, conflicts, all_defs, BITMAP_IOR);
      });

  BITMAP_XFREE (all_defs);
}

/* Allocate the per basic block info for traversing the insn stream for
   building live ranges.  */

static void
init_bb_info ()
{
  basic_block bb;
  FOR_ALL_BB (bb)
    {
      struct ra_bb_info *info =
	(struct ra_bb_info *) xcalloc (1, sizeof *info);
      info->regnos_mentioned = BITMAP_XMALLOC ();
      info->live_throughout = BITMAP_XMALLOC ();
      info->old_aux = bb->aux;
      bb->aux = (void *) info;
    }
}

/* Free that per basic block info.  */

static void
free_bb_info ()
{
  basic_block bb;
  FOR_ALL_BB (bb)
    {
      struct ra_bb_info *info = (struct ra_bb_info *) bb->aux;
      BITMAP_XFREE (info->regnos_mentioned);
      BITMAP_XFREE (info->live_throughout);
      bb->aux = info->old_aux;
      free (info);
    }
}

/* Toplevel function for the first part of this file.
   Connect web parts, thereby implicitely building webs, and remember
   their conflicts.  */

static void
build_web_parts_and_conflicts (df)
     struct df *df;
{
  struct df_link *link;
  struct curr_use use;
  basic_block bb;

  number_seen = (int *) xcalloc (get_max_uid (), sizeof (int));
  visit_trace = (struct visit_trace *) xcalloc (get_max_uid (),
						sizeof (visit_trace[0]));
  update_regnos_mentioned ();

  /* Here's the main loop.
     It goes through all insn's, connects web parts along the way, notes
     conflicts between webparts, and remembers move instructions.  */
  visited_pass = 0;
  for (use.regno = 0; use.regno < (unsigned int)max_regno; use.regno++)
    if (use.regno >= FIRST_PSEUDO_REGISTER || !fixed_regs[use.regno])
      for (link = df->regs[use.regno].uses; link; link = link->next)
        if (link->ref)
	  {
	    struct ref *ref = link->ref;
	    rtx insn = DF_REF_INSN (ref);
	    /* Only recheck marked or new uses, or uses from hardregs.  */
	    if (use.regno >= FIRST_PSEUDO_REGISTER
		&& DF_REF_ID (ref) < last_use_id
		&& !TEST_BIT (last_check_uses, DF_REF_ID (ref)))
	      continue;
	    use.wp = &web_parts[df->def_id + DF_REF_ID (ref)];
	    use.x = DF_REF_REG (ref);
	    use.live_over_abnormal = 0;
	    use.undefined = rtx_to_undefined (use.x);
	    visited_pass++;
	    live_in (df, &use, insn);
	    if (use.live_over_abnormal)
	      SET_BIT (live_over_abnormal, DF_REF_ID (ref));
	  }

  dump_number_seen ();
  FOR_ALL_BB (bb)
    {
      struct ra_bb_info *info = (struct ra_bb_info *) bb->aux;
      livethrough_conflicts_bb (bb);
      bitmap_zero (info->live_throughout);
      info->pass = 0;
    }
  free (visit_trace);
  free (number_seen);
}

/* Here we look per insn, for DF references being in uses _and_ defs.
   This means, in the RTL a (REG xx) expression was seen as a
   read/modify/write, as happens for (set (subreg:SI (reg:DI xx)) (...))
   e.g.  Our code has created two webs for this, as it should.  Unfortunately,
   as the REG reference is only one time in the RTL we can't color
   both webs different (arguably this also would be wrong for a real
   read-mod-write instruction), so we must reconnect such webs.  */

static void
connect_rmw_web_parts (df)
     struct df *df;
{
  unsigned int i;

  for (i = 0; i < df->use_id; i++)
    {
      struct web_part *wp1 = &web_parts[df->def_id + i];
      rtx reg;
      struct df_link *link;
      if (!wp1->ref)
	continue;
      /* If it's an uninitialized web, we don't want to connect it to others,
	 as the read cycle in read-mod-write had probably no effect.  */
      if (find_web_part (wp1) >= &web_parts[df->def_id])
	continue;
      reg = DF_REF_REAL_REG (wp1->ref);
      link = DF_INSN_DEFS (df, DF_REF_INSN (wp1->ref));
      for (; link; link = link->next)
        if (reg == DF_REF_REAL_REG (link->ref))
	  {
	    struct web_part *wp2 = &web_parts[DF_REF_ID (link->ref)];
	    union_web_parts (wp1, wp2);
	  }
    }
}

/* Deletes all hardregs from *S which are not allowed for MODE.  */

static void
prune_hardregs_for_mode (s, mode)
     HARD_REG_SET *s;
     enum machine_mode mode;
{
  AND_HARD_REG_SET (*s, hardregs_for_mode[(int) mode]);
}

/* Initialize the members of a web, which are deducible from REG.  */

static void
init_one_web_common (web, reg)
     struct web *web;
     rtx reg;
{
  if (GET_CODE (reg) != REG)
    abort ();
  /* web->id isn't initialized here.  */
  web->regno = REGNO (reg);
  web->orig_x = reg;
  if (!web->dlink)
    {
      web->dlink = (struct dlist *) ra_calloc (sizeof (struct dlist));
      DLIST_WEB (web->dlink) = web;
    }
  /* XXX
     the former (superunion) doesn't constrain the graph enough. E.g.
     on x86 QImode _requires_ QI_REGS, but as alternate class usually
     GENERAL_REGS is given.  So the graph is not constrained enough,
     thinking it has more freedom then it really has, which leads
     to repeated spill tryings.  OTOH the latter (only using preferred
     class) is too constrained, as normally (e.g. with all SImode
     pseudos), they can be allocated also in the alternate class.
     What we really want, are the _exact_ hard regs allowed, not
     just a class.  Later.  */
  /*web->regclass = reg_class_superunion
		    [reg_preferred_class (web->regno)]
		    [reg_alternate_class (web->regno)];*/
  /*web->regclass = reg_preferred_class (web->regno);*/
  web->regclass = reg_class_subunion
    [reg_preferred_class (web->regno)] [reg_alternate_class (web->regno)];
  web->regclass = reg_preferred_class (web->regno);
  if (web->regno < FIRST_PSEUDO_REGISTER)
    {
      web->color = web->regno;
      put_web (web, PRECOLORED);
      web->num_conflicts = UINT_MAX;
      web->add_hardregs = 0;
      CLEAR_HARD_REG_SET (web->usable_regs);
      SET_HARD_REG_BIT (web->usable_regs, web->regno);
      web->num_freedom = 1;
    }
  else
    {
      HARD_REG_SET alternate;
      web->color = -1;
      put_web (web, INITIAL);
      /* add_hardregs is wrong in multi-length classes, e.g.
	 using a DFmode pseudo on x86 can result in class FLOAT_INT_REGS,
	 where, if it finally is allocated to GENERAL_REGS it needs two,
	 if allocated to FLOAT_REGS only one hardreg.  XXX */
      web->add_hardregs =
	CLASS_MAX_NREGS (web->regclass, PSEUDO_REGNO_MODE (web->regno)) - 1;
      web->num_conflicts = 0 * web->add_hardregs;
      COPY_HARD_REG_SET (web->usable_regs,
			reg_class_contents[reg_preferred_class (web->regno)]);
      COPY_HARD_REG_SET (alternate,
			reg_class_contents[reg_alternate_class (web->regno)]);
      IOR_HARD_REG_SET (web->usable_regs, alternate);
      /*IOR_HARD_REG_SET (web->usable_regs,
			reg_class_contents[reg_alternate_class
			(web->regno)]);*/
      AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors);
      prune_hardregs_for_mode (&web->usable_regs,
			       PSEUDO_REGNO_MODE (web->regno));
#ifdef CLASS_CANNOT_CHANGE_MODE
      if (web->mode_changed)
        AND_COMPL_HARD_REG_SET (web->usable_regs, reg_class_contents[
			          (int) CLASS_CANNOT_CHANGE_MODE]);
#endif
      web->num_freedom = hard_regs_count (web->usable_regs);
      web->num_freedom -= web->add_hardregs;
      if (!web->num_freedom)
	abort();
    }
  COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs);
}

/* Initializes WEBs members from REG or zero them.  */

static void
init_one_web (web, reg)
     struct web *web;
     rtx reg;
{
  memset (web, 0, sizeof (struct web));
  init_one_web_common (web, reg);
  web->useless_conflicts = BITMAP_XMALLOC ();
}

/* WEB is an old web, meaning it came from the last pass, and got a
   color.  We want to remember some of it's info, so zero only some
   members.  */

static void
reinit_one_web (web, reg)
     struct web *web;
     rtx reg;
{
  web->old_color = web->color + 1;
  init_one_web_common (web, reg);
  web->span_deaths = 0;
  web->spill_temp = 0;
  web->orig_spill_temp = 0;
  web->use_my_regs = 0;
  web->spill_cost = 0;
  web->was_spilled = 0;
  web->is_coalesced = 0;
  web->artificial = 0;
  web->live_over_abnormal = 0;
  web->mode_changed = 0;
  web->move_related = 0;
  web->in_load = 0;
  web->target_of_spilled_move = 0;
  web->num_aliased = 0;
  if (web->type == PRECOLORED)
    {
      web->num_defs = 0;
      web->num_uses = 0;
      web->orig_spill_cost = 0;
    }
  CLEAR_HARD_REG_SET (web->bias_colors);
  CLEAR_HARD_REG_SET (web->prefer_colors);
  web->reg_rtx = NULL;
  web->stack_slot = NULL;
  web->pattern = NULL;
  web->alias = NULL;
  if (web->moves)
    abort ();
  if (!web->useless_conflicts)
    abort ();
}

/* Insert and returns a subweb corresponding to REG into WEB (which
   becomes its super web).  It must not exist already.  */

static struct web *
add_subweb (web, reg)
     struct web *web;
     rtx reg;
{
  struct web *w;
  if (GET_CODE (reg) != SUBREG)
    abort ();
  w = (struct web *) xmalloc (sizeof (struct web));
  /* Copy most content from parent-web.  */
  *w = *web;
  /* And initialize the private stuff.  */
  w->orig_x = reg;
  w->add_hardregs = CLASS_MAX_NREGS (web->regclass, GET_MODE (reg)) - 1;
  w->num_conflicts = 0 * w->add_hardregs;
  w->num_defs = 0;
  w->num_uses = 0;
  w->dlink = NULL;
  w->parent_web = web;
  w->subreg_next = web->subreg_next;
  web->subreg_next = w;
  return w;
}

/* Similar to add_subweb(), but instead of relying on a given SUBREG,
   we have just a size and an offset of the subpart of the REG rtx.
   In difference to add_subweb() this marks the new subweb as artificial.  */

static struct web *
add_subweb_2 (web, size_word)
     struct web *web;
     unsigned int size_word;
{
  /* To get a correct mode for the to be produced subreg, we don't want to
     simply do a mode_for_size() for the mode_class of the whole web.
     Suppose we deal with a CDImode web, but search for a 8 byte part.
     Now mode_for_size() would only search in the class MODE_COMPLEX_INT
     and would find CSImode which probably is not what we want.  Instead
     we want DImode, which is in a completely other class.  For this to work
     we instead first search the already existing subwebs, and take
     _their_ modeclasses as base for a search for ourself.  */
  rtx ref_rtx = (web->subreg_next ? web->subreg_next : web)->orig_x;
  unsigned int size = BYTE_LENGTH (size_word) * BITS_PER_UNIT;
  enum machine_mode mode;
  mode = mode_for_size (size, GET_MODE_CLASS (GET_MODE (ref_rtx)), 0);
  if (mode == BLKmode)
    mode = mode_for_size (size, MODE_INT, 0);
  if (mode == BLKmode)
    abort ();
  web = add_subweb (web, gen_rtx_SUBREG (mode, web->orig_x,
					 BYTE_BEGIN (size_word)));
  web->artificial = 1;
  return web;
}

/* Initialize all the web parts we are going to need.  */

static void
init_web_parts (df)
     struct df *df;
{
  int regno;
  unsigned int no;
  num_webs = 0;
  for (no = 0; no < df->def_id; no++)
    {
      if (df->defs[no])
	{
	  if (no < last_def_id && web_parts[no].ref != df->defs[no])
	    abort ();
	  web_parts[no].ref = df->defs[no];
	  /* Uplink might be set from the last iteration.  */
	  if (!web_parts[no].uplink)
	    num_webs++;
	}
      else
	/* The last iteration might have left .ref set, while df_analyse()
	   removed that ref (due to a removed copy insn) from the df->defs[]
	   array.  As we don't check for that in realloc_web_parts()
	   we do that here.  */
	web_parts[no].ref = NULL;
    }
  for (no = 0; no < df->use_id; no++)
    {
      if (df->uses[no])
	{
	  if (no < last_use_id
	      && web_parts[no + df->def_id].ref != df->uses[no])
	    abort ();
	  web_parts[no + df->def_id].ref = df->uses[no];
	  if (!web_parts[no + df->def_id].uplink)
	    num_webs++;
	}
      else
	web_parts[no + df->def_id].ref = NULL;
    }

  /* We want to have only one web for each precolored register.  */
  for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
    {
      struct web_part *r1 = NULL;
      struct df_link *link;
      /* Here once was a test, if there is any DEF at all, and only then to
	 merge all the parts.  This was incorrect, we really also want to have
	 only one web-part for hardregs, even if there is no explicit DEF.  */
      /* Link together all defs...  */
      for (link = df->regs[regno].defs; link; link = link->next)
        if (link->ref)
	  {
	    struct web_part *r2 = &web_parts[DF_REF_ID (link->ref)];
	    if (!r1)
	      r1 = r2;
	    else
	      r1 = union_web_parts (r1, r2);
	  }
      /* ... and all uses.  */
      for (link = df->regs[regno].uses; link; link = link->next)
	if (link->ref)
	  {
	    struct web_part *r2 = &web_parts[df->def_id
		                             + DF_REF_ID (link->ref)];
	    if (!r1)
	      r1 = r2;
	    else
	      r1 = union_web_parts (r1, r2);
	  }
    }
}

/* In case we want to remember the conflict list of a WEB, before adding
   new conflicts, we copy it here to orig_conflict_list.  */

static void
copy_conflict_list (web)
     struct web *web;
{
  struct conflict_link *cl;
  if (web->orig_conflict_list || web->have_orig_conflicts)
    abort ();
  web->have_orig_conflicts = 1;
  for (cl = web->conflict_list; cl; cl = cl->next)
    {
      struct conflict_link *ncl;
      ncl = (struct conflict_link *) ra_alloc (sizeof *ncl);
      ncl->t = cl->t;
      ncl->sub = NULL;
      ncl->next = web->orig_conflict_list;
      web->orig_conflict_list = ncl;
      if (cl->sub)
	{
	  struct sub_conflict *sl, *nsl;
	  for (sl = cl->sub; sl; sl = sl->next)
	    {
	      nsl = (struct sub_conflict *) ra_alloc (sizeof *nsl);
	      nsl->s = sl->s;
	      nsl->t = sl->t;
	      nsl->next = ncl->sub;
	      ncl->sub = nsl;
	    }
	}
    }
}

/* Possibly add an edge from web FROM to TO marking a conflict between
   those two.  This is one half of marking a complete conflict, which notes
   in FROM, that TO is a conflict.  Adding TO to FROM's conflicts might
   make other conflicts superflous, because the current TO overlaps some web
   already being in conflict with FROM.  In this case the smaller webs are
   deleted from the conflict list.  Likewise if TO is overlapped by a web
   already in the list, it isn't added at all.  Note, that this can only
   happen, if SUBREG webs are involved.  */

static void
add_conflict_edge (from, to)
     struct web *from, *to;
{
  if (from->type != PRECOLORED)
    {
      struct web *pfrom = find_web_for_subweb (from);
      struct web *pto = find_web_for_subweb (to);
      struct sub_conflict *sl;
      struct conflict_link *cl = pfrom->conflict_list;
      int may_delete = 1;

      /* This can happen when subwebs of one web conflict with each
	 other.  In live_out_1() we created such conflicts between yet
	 undefined webparts and defs of parts which didn't overlap with the
	 undefined bits.  Then later they nevertheless could have merged into
	 one web, and then we land here.  */
      if (pfrom == pto)
	return;
      if (remember_conflicts && !pfrom->have_orig_conflicts)
	copy_conflict_list (pfrom);
      if (!TEST_BIT (sup_igraph, (pfrom->id * num_webs + pto->id)))
	{
	  cl = (struct conflict_link *) ra_alloc (sizeof (*cl));
	  cl->t = pto;
	  cl->sub = NULL;
	  cl->next = pfrom->conflict_list;
	  pfrom->conflict_list = cl;
	  if (pto->type != SELECT && pto->type != COALESCED)
	    pfrom->num_conflicts += 1 + pto->add_hardregs;
          SET_BIT (sup_igraph, (pfrom->id * num_webs + pto->id));
	  may_delete = 0;
	}
      else
        /* We don't need to test for cl==NULL, because at this point
	   a cl with cl->t==pto is guaranteed to exist.  */
        while (cl->t != pto)
	  cl = cl->next;
      if (pfrom != from || pto != to)
	{
	  /* This is a subconflict which should be added.
	     If we inserted cl in this invocation, we really need to add this
	     subconflict.  If we did _not_ add it here, we only add the
	     subconflict, if cl already had subconflicts, because otherwise
	     this indicated, that the whole webs already conflict, which
	     means we are not interested in this subconflict.  */
	  if (!may_delete || cl->sub != NULL)
	    {
	      sl = (struct sub_conflict *) ra_alloc (sizeof (*sl));
	      sl->s = from;
	      sl->t = to;
	      sl->next = cl->sub;
	      cl->sub = sl;
	    }
	}
      else
	/* pfrom == from && pto == to means, that we are not interested
	   anymore in the subconflict list for this pair, because anyway
	   the whole webs conflict.  */
	cl->sub = NULL;
    }
}

/* Record a conflict between two webs, if we haven't recorded it
   already.  */

void
record_conflict (web1, web2)
     struct web *web1, *web2;
{
  unsigned int id1 = web1->id, id2 = web2->id;
  unsigned int index = igraph_index (id1, id2);
  /* Trivial non-conflict or already recorded conflict.  */
  if (web1 == web2 || TEST_BIT (igraph, index))
    return;
  if (id1 == id2)
    abort ();
  /* As fixed_regs are no targets for allocation, conflicts with them
     are pointless.  */
  if ((web1->regno < FIRST_PSEUDO_REGISTER && fixed_regs[web1->regno])
      || (web2->regno < FIRST_PSEUDO_REGISTER && fixed_regs[web2->regno]))
    return;
  /* Conflicts with hardregs, which are not even a candidate
     for this pseudo are also pointless.  */
  if ((web1->type == PRECOLORED
       && ! TEST_HARD_REG_BIT (web2->usable_regs, web1->regno))
      || (web2->type == PRECOLORED
	  && ! TEST_HARD_REG_BIT (web1->usable_regs, web2->regno)))
    return;
  /* Similar if the set of possible hardregs don't intersect.  This iteration
     those conflicts are useless (and would make num_conflicts wrong, because
     num_freedom is calculated from the set of possible hardregs).
     But in presence of spilling and incremental building of the graph we
     need to note all uses of webs conflicting with the spilled ones.
     Because the set of possible hardregs can change in the next round for
     spilled webs, we possibly have then conflicts with webs which would
     be excluded now (because then hardregs intersect).  But we actually
     need to check those uses, and to get hold of them, we need to remember
     also webs conflicting with this one, although not conflicting in this
     round because of non-intersecting hardregs.  */
  if (web1->type != PRECOLORED && web2->type != PRECOLORED
      && ! hard_regs_intersect_p (&web1->usable_regs, &web2->usable_regs))
    {
      struct web *p1 = find_web_for_subweb (web1);
      struct web *p2 = find_web_for_subweb (web2);
      /* We expect these to be rare enough to justify bitmaps.  And because
         we have only a special use for it, we note only the superwebs.  */
      bitmap_set_bit (p1->useless_conflicts, p2->id);
      bitmap_set_bit (p2->useless_conflicts, p1->id);
      return;
    }
  SET_BIT (igraph, index);
  add_conflict_edge (web1, web2);
  add_conflict_edge (web2, web1);
}

/* For each web W this produces the missing subwebs Wx, such that it's
   possible to exactly specify (W-Wy) for all already existing subwebs Wy.  */

static void
build_inverse_webs (web)
     struct web *web;
{
  struct web *sweb = web->subreg_next;
  unsigned HOST_WIDE_INT undef;

  undef = rtx_to_undefined (web->orig_x);
  for (; sweb; sweb = sweb->subreg_next)
    /* Only create inverses of non-artificial webs.  */
    if (!sweb->artificial)
      {
	unsigned HOST_WIDE_INT bits;
	bits = undef & ~ rtx_to_undefined (sweb->orig_x);
	while (bits)
	  {
	    unsigned int size_word = undef_to_size_word (web->orig_x, &bits);
	    if (!find_subweb_2 (web, size_word))
	      add_subweb_2 (web, size_word);
	  }
      }
}

/* Copies the content of WEB to a new one, and link it into WL.
   Used for consistency checking.  */

static void
copy_web (web, wl)
     struct web *web;
     struct web_link **wl;
{
  struct web *cweb = (struct web *) xmalloc (sizeof *cweb);
  struct web_link *link = (struct web_link *) ra_alloc (sizeof *link);
  link->next = *wl;
  *wl = link;
  link->web = cweb;
  *cweb = *web;
}

/* Given a list of webs LINK, compare the content of the webs therein
   with the global webs of the same ID.  For consistency checking.  */

static void
compare_and_free_webs (link)
     struct web_link **link;
{
  struct web_link *wl;
  for (wl = *link; wl; wl = wl->next)
    {
      struct web *web1 = wl->web;
      struct web *web2 = ID2WEB (web1->id);
      if (web1->regno != web2->regno
	  || web1->crosses_call != web2->crosses_call
	  || web1->live_over_abnormal != web2->live_over_abnormal
	  || web1->mode_changed != web2->mode_changed
	  || !rtx_equal_p (web1->orig_x, web2->orig_x)
	  || web1->type != web2->type
	  /* Only compare num_defs/num_uses with non-hardreg webs.
	     E.g. the number of uses of the framepointer changes due to
	     inserting spill code.  */
	  || (web1->type != PRECOLORED &&
	      (web1->num_uses != web2->num_uses
	       || web1->num_defs != web2->num_defs)))
	abort ();
      if (web1->type != PRECOLORED)
	{
	  unsigned int i;
	  for (i = 0; i < web1->num_defs; i++)
	    if (web1->defs[i] != web2->defs[i])
	      abort ();
	  for (i = 0; i < web1->num_uses; i++)
	    if (web1->uses[i] != web2->uses[i])
	      abort ();
	}
      if (web1->type == PRECOLORED)
	{
	  if (web1->defs)
	    free (web1->defs);
	  if (web1->uses)
	    free (web1->uses);
	}
      free (web1);
    }
  *link = NULL;
}

/* Setup and fill uses[] and defs[] arrays of the webs.  */

static void
init_webs_defs_uses ()
{
  struct dlist *d;
  for (d = WEBS(INITIAL); d; d = d->next)
    {
      struct web *web = DLIST_WEB (d);
      unsigned int def_i, use_i;
      struct df_link *link;
      if (web->old_web)
	continue;
      if (web->type == PRECOLORED)
	{
	  web->num_defs = web->num_uses = 0;
	  continue;
	}
      if (web->num_defs)
        web->defs = (struct ref **) xmalloc (web->num_defs *
					     sizeof (web->defs[0]));
      if (web->num_uses)
        web->uses = (struct ref **) xmalloc (web->num_uses *
					     sizeof (web->uses[0]));
      def_i = use_i = 0;
      for (link = web->temp_refs; link; link = link->next)
	{
	  if (DF_REF_REG_DEF_P (link->ref))
	    web->defs[def_i++] = link->ref;
	  else
	    web->uses[use_i++] = link->ref;
	}
      web->temp_refs = NULL;
      if (def_i != web->num_defs || use_i != web->num_uses)
	abort ();
    }
}

/* Called by parts_to_webs().  This creates (or recreates) the webs (and
   subwebs) from web parts, gives them IDs (only to super webs), and sets
   up use2web and def2web arrays.  */

static unsigned int
parts_to_webs_1 (df, copy_webs, all_refs)
     struct df *df;
     struct web_link **copy_webs;
     struct df_link *all_refs;
{
  unsigned int i;
  unsigned int webnum;
  unsigned int def_id = df->def_id;
  unsigned int use_id = df->use_id;
  struct web_part *wp_first_use = &web_parts[def_id];

  /* For each root web part: create and initialize a new web,
     setup def2web[] and use2web[] for all defs and uses, and
     id2web for all new webs.  */

  webnum = 0;
  for (i = 0; i < def_id + use_id; i++)
    {
      struct web *subweb, *web = 0; /* Initialize web to silence warnings.  */
      struct web_part *wp = &web_parts[i];
      struct ref *ref = wp->ref;
      unsigned int ref_id;
      rtx reg;
      if (!ref)
	continue;
      ref_id = i;
      if (i >= def_id)
	ref_id -= def_id;
      all_refs[i].ref = ref;
      reg = DF_REF_REG (ref);
      if (! wp->uplink)
	{
	  /* If we have a web part root, create a new web.  */
	  unsigned int newid = ~(unsigned)0;
	  unsigned int old_web = 0;

	  /* In the first pass, there are no old webs, so unconditionally
	     allocate a new one.  */
	  if (ra_pass == 1)
	    {
	      web = (struct web *) xmalloc (sizeof (struct web));
	      newid = last_num_webs++;
	      init_one_web (web, GET_CODE (reg) == SUBREG
			         ? SUBREG_REG (reg) : reg);
	    }
	  /* Otherwise, we look for an old web.  */
	  else
	    {
	      /* Remember, that use2web == def2web + def_id.
		 Ergo is def2web[i] == use2web[i - def_id] for i >= def_id.
		 So we only need to look into def2web[] array.
		 Try to look at the web, which formerly belonged to this
		 def (or use).  */
	      web = def2web[i];
	      /* Or which belonged to this hardreg.  */
	      if (!web && DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER)
		web = hardreg2web[DF_REF_REGNO (ref)];
	      if (web)
		{
		  /* If we found one, reuse it.  */
		  web = find_web_for_subweb (web);
		  remove_list (web->dlink, &WEBS(INITIAL));
		  old_web = 1;
		  copy_web (web, copy_webs);
		}
	      else
		{
		  /* Otherwise use a new one.  First from the free list.  */
		  if (WEBS(FREE))
		    web = DLIST_WEB (pop_list (&WEBS(FREE)));
		  else
		    {
		      /* Else allocate a new one.  */
		      web = (struct web *) xmalloc (sizeof (struct web));
		      newid = last_num_webs++;
		    }
		}
	      /* The id is zeroed in init_one_web().  */
	      if (newid == ~(unsigned)0)
		newid = web->id;
	      if (old_web)
		reinit_one_web (web, GET_CODE (reg) == SUBREG
				     ? SUBREG_REG (reg) : reg);
	      else
		init_one_web (web, GET_CODE (reg) == SUBREG
				   ? SUBREG_REG (reg) : reg);
	      web->old_web = (old_web && web->type != PRECOLORED) ? 1 : 0;
	    }
	  web->span_deaths = wp->spanned_deaths;
	  web->crosses_call = wp->crosses_call;
	  web->id = newid;
	  web->temp_refs = NULL;
	  webnum++;
	  if (web->regno < FIRST_PSEUDO_REGISTER && !hardreg2web[web->regno])
	    hardreg2web[web->regno] = web;
	  else if (web->regno < FIRST_PSEUDO_REGISTER
		   && hardreg2web[web->regno] != web)
	    abort ();
	}

      /* If this reference already had a web assigned, we are done.
         This test better is equivalent to the web being an old web.
         Otherwise something is screwed.  (This is tested)  */
      if (def2web[i] != NULL)
	{
	  web = def2web[i];
	  web = find_web_for_subweb (web);
	  /* But if this ref includes a mode change, or was a use live
	     over an abnormal call, set appropriate flags in the web.  */
	  if ((DF_REF_FLAGS (ref) & DF_REF_MODE_CHANGE) != 0
	      && web->regno >= FIRST_PSEUDO_REGISTER)
	    web->mode_changed = 1;
	  if (i >= def_id
	      && TEST_BIT (live_over_abnormal, ref_id))
	    web->live_over_abnormal = 1;
	  /* And check, that it's not a newly allocated web.  This would be
	     an inconsistency.  */
	  if (!web->old_web || web->type == PRECOLORED)
	    abort ();
	  continue;
	}
      /* In case this was no web part root, we need to initialize WEB
	 from the ref2web array belonging to the root.  */
      if (wp->uplink)
	{
	  struct web_part *rwp = find_web_part (wp);
	  unsigned int j = DF_REF_ID (rwp->ref);
	  if (rwp < wp_first_use)
	    web = def2web[j];
	  else
	    web = use2web[j];
	  web = find_web_for_subweb (web);
	}

      /* Remember all references for a web in a single linked list.  */
      all_refs[i].next = web->temp_refs;
      web->temp_refs = &all_refs[i];

      /* And the test, that if def2web[i] was NULL above, that we are _not_
	 an old web.  */
      if (web->old_web && web->type != PRECOLORED)
	abort ();

      /* Possible create a subweb, if this ref was a subreg.  */
      if (GET_CODE (reg) == SUBREG)
	{
	  subweb = find_subweb (web, reg);
	  if (!subweb)
	    {
	      subweb = add_subweb (web, reg);
	      if (web->old_web)
		abort ();
	    }
	}
      else
	subweb = web;

      /* And look, if the ref involves an invalid mode change.  */
      if ((DF_REF_FLAGS (ref) & DF_REF_MODE_CHANGE) != 0
	  && web->regno >= FIRST_PSEUDO_REGISTER)
	web->mode_changed = 1;

      /* Setup def2web, or use2web, and increment num_defs or num_uses.  */
      if (i < def_id)
	{
	  /* Some sanity checks.  */
	  if (ra_pass > 1)
	    {
	      struct web *compare = def2web[i];
	      if (i < last_def_id)
		{
		  if (web->old_web && compare != subweb)
		    abort ();
		}
	      if (!web->old_web && compare)
		abort ();
	      if (compare && compare != subweb)
		abort ();
	    }
	  def2web[i] = subweb;
	  web->num_defs++;
	}
      else
	{
	  if (ra_pass > 1)
	    {
	      struct web *compare = use2web[ref_id];
	      if (ref_id < last_use_id)
		{
		  if (web->old_web && compare != subweb)
		    abort ();
		}
	      if (!web->old_web && compare)
		abort ();
	      if (compare && compare != subweb)
		abort ();
	    }
	  use2web[ref_id] = subweb;
	  web->num_uses++;
	  if (TEST_BIT (live_over_abnormal, ref_id))
	    web->live_over_abnormal = 1;
	}
    }

  /* We better now have exactly as many webs as we had web part roots.  */
  if (webnum != num_webs)
    abort ();

  return webnum;
}

/* This builds full webs out of web parts, without relating them to each
   other (i.e. without creating the conflict edges).  */

static void
parts_to_webs (df)
     struct df *df;
{
  unsigned int i;
  unsigned int webnum;
  struct web_link *copy_webs = NULL;
  struct dlist *d;
  struct df_link *all_refs;
  num_subwebs = 0;

  /* First build webs and ordinary subwebs.  */
  all_refs = (struct df_link *) xcalloc (df->def_id + df->use_id,
					 sizeof (all_refs[0]));
  webnum = parts_to_webs_1 (df, &copy_webs, all_refs);

  /* Setup the webs for hardregs which are still missing (weren't
     mentioned in the code).  */
  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
    if (!hardreg2web[i])
      {
	struct web *web = (struct web *) xmalloc (sizeof (struct web));
	init_one_web (web, gen_rtx_REG (reg_raw_mode[i], i));
	web->id = last_num_webs++;
	hardreg2web[web->regno] = web;
      }
  num_webs = last_num_webs;

  /* Now create all artificial subwebs, i.e. those, which do
     not correspond to a real subreg in the current function's RTL, but
     which nevertheless is a target of a conflict.
     XXX we need to merge this loop with the one above, which means, we need
     a way to later override the artificiality.  Beware: currently
     add_subweb_2() relies on the existence of normal subwebs for deducing
     a sane mode to use for the artificial subwebs.  */
  for (i = 0; i < df->def_id + df->use_id; i++)
    {
      struct web_part *wp = &web_parts[i];
      struct tagged_conflict *cl;
      struct web *web;
      if (wp->uplink || !wp->ref)
	{
	  if (wp->sub_conflicts)
	    abort ();
	  continue;
	}
      web = def2web[i];
      web = find_web_for_subweb (web);
      for (cl = wp->sub_conflicts; cl; cl = cl->next)
        if (!find_subweb_2 (web, cl->size_word))
	  add_subweb_2 (web, cl->size_word);
    }

  /* And now create artificial subwebs needed for representing the inverse
     of some subwebs.  This also gives IDs to all subwebs.  */
  webnum = last_num_webs;
  for (d = WEBS(INITIAL); d; d = d->next)
    {
      struct web *web = DLIST_WEB (d);
      if (web->subreg_next)
	{
	  struct web *sweb;
          build_inverse_webs (web);
	  for (sweb = web->subreg_next; sweb; sweb = sweb->subreg_next)
	    sweb->id = webnum++;
	}
    }

  /* Now that everyone has an ID, we can setup the id2web array.  */
  id2web = (struct web **) xcalloc (webnum, sizeof (id2web[0]));
  for (d = WEBS(INITIAL); d; d = d->next)
    {
      struct web *web = DLIST_WEB (d);
      ID2WEB (web->id) = web;
      for (web = web->subreg_next; web; web = web->subreg_next)
        ID2WEB (web->id) = web;
    }
  num_subwebs = webnum - last_num_webs;
  num_allwebs = num_webs + num_subwebs;
  num_webs += num_subwebs;

  /* Allocate and clear the conflict graph bitmaps.  */
  igraph = sbitmap_alloc (num_webs * num_webs / 2);
  sup_igraph = sbitmap_alloc (num_webs * num_webs);
  sbitmap_zero (igraph);
  sbitmap_zero (sup_igraph);

  /* Distibute the references to their webs.  */
  init_webs_defs_uses ();
  /* And do some sanity checks if old webs, and those recreated from the
     really are the same.  */
  compare_and_free_webs (&copy_webs);
  free (all_refs);
}

/* This deletes all conflicts to and from webs which need to be renewed
   in this pass of the allocator, i.e. those which were spilled in the
   last pass.  Furthermore it also rebuilds the bitmaps for the remaining
   conflicts.  */

static void
reset_conflicts ()
{
  unsigned int i;
  bitmap newwebs = BITMAP_XMALLOC ();
  for (i = 0; i < num_webs - num_subwebs; i++)
    {
      struct web *web = ID2WEB (i);
      /* Hardreg webs and non-old webs are new webs (which
	 need rebuilding).  */
      if (web->type == PRECOLORED || !web->old_web)
	bitmap_set_bit (newwebs, web->id);
    }

  for (i = 0; i < num_webs - num_subwebs; i++)
    {
      struct web *web = ID2WEB (i);
      struct conflict_link *cl;
      struct conflict_link **pcl;
      pcl = &(web->conflict_list);

      /* First restore the conflict list to be like it was before
	 coalescing.  */
      if (web->have_orig_conflicts)
	{
	  web->conflict_list = web->orig_conflict_list;
	  web->orig_conflict_list = NULL;
	}
      if (web->orig_conflict_list)
	abort ();

      /* New non-precolored webs, have no conflict list.  */
      if (web->type != PRECOLORED && !web->old_web)
	{
	  *pcl = NULL;
	  /* Useless conflicts will be rebuilt completely.  But check
	     for cleanlyness, as the web might have come from the
	     free list.  */
	  if (bitmap_first_set_bit (web->useless_conflicts) >= 0)
	    abort ();
	}
      else
	{
	  /* Useless conflicts with new webs will be rebuilt if they
	     are still there.  */
	  bitmap_operation (web->useless_conflicts, web->useless_conflicts,
			    newwebs, BITMAP_AND_COMPL);
	  /* Go through all conflicts, and retain those to old webs.  */
	  for (cl = web->conflict_list; cl; cl = cl->next)
	    {
	      if (cl->t->old_web || cl->t->type == PRECOLORED)
		{
		  *pcl = cl;
		  pcl = &(cl->next);

		  /* Also restore the entries in the igraph bitmaps.  */
		  web->num_conflicts += 1 + cl->t->add_hardregs;
		  SET_BIT (sup_igraph, (web->id * num_webs + cl->t->id));
		  /* No subconflicts mean full webs conflict.  */
		  if (!cl->sub)
		    SET_BIT (igraph, igraph_index (web->id, cl->t->id));
		  else
		    /* Else only the parts in cl->sub must be in the
		       bitmap.  */
		    {
		      struct sub_conflict *sl;
		      for (sl = cl->sub; sl; sl = sl->next)
			SET_BIT (igraph, igraph_index (sl->s->id, sl->t->id));
		    }
		}
	    }
	  *pcl = NULL;
	}
      web->have_orig_conflicts = 0;
    }
  BITMAP_XFREE (newwebs);
}

/* For each web check it's num_conflicts member against that
   number, as calculated from scratch from all neighbors.  */

#if 0
static void
check_conflict_numbers ()
{
  unsigned int i;
  for (i = 0; i < num_webs; i++)
    {
      struct web *web = ID2WEB (i);
      int new_conf = 0 * web->add_hardregs;
      struct conflict_link *cl;
      for (cl = web->conflict_list; cl; cl = cl->next)
	if (cl->t->type != SELECT && cl->t->type != COALESCED)
	  new_conf += 1 + cl->t->add_hardregs;
      if (web->type != PRECOLORED && new_conf != web->num_conflicts)
	abort ();
    }
}
#endif

/* Convert the conflicts between web parts to conflicts between full webs.

   This can't be done in parts_to_webs(), because for recording conflicts
   between webs we need to know their final usable_regs set, which is used
   to discard non-conflicts (between webs having no hard reg in common).
   But this is set for spill temporaries only after the webs itself are
   built.  Until then the usable_regs set is based on the pseudo regno used
   in this web, which may contain far less registers than later determined.
   This would result in us loosing conflicts (due to record_conflict()
   thinking that a web can only be allocated to the current usable_regs,
   whereas later this is extended) leading to colorings, where some regs which
   in reality conflict get the same color.  */

static void
conflicts_between_webs (df)
     struct df *df;
{
  unsigned int i;
#ifdef STACK_REGS
  struct dlist *d;
#endif
  bitmap ignore_defs = BITMAP_XMALLOC ();
  unsigned int have_ignored;
  unsigned int *pass_cache = (unsigned int *) xcalloc (num_webs, sizeof (int));
  unsigned int pass = 0;

  if (ra_pass > 1)
    reset_conflicts ();

  /* It is possible, that in the conflict bitmaps still some defs I are noted,
     which have web_parts[I].ref being NULL.  This can happen, when from the
     last iteration the conflict bitmap for this part wasn't deleted, but a
     conflicting move insn was removed.  It's DEF is still in the conflict
     bitmap, but it doesn't exist anymore in df->defs.  To not have to check
     it in the tight loop below, we instead remember the ID's of them in a
     bitmap, and loop only over IDs which are not in it.  */
  for (i = 0; i < df->def_id; i++)
    if (web_parts[i].ref == NULL)
      bitmap_set_bit (ignore_defs, i);
  have_ignored = (bitmap_first_set_bit (ignore_defs) >= 0);

  /* Now record all conflicts between webs.  Note that we only check
     the conflict bitmaps of all defs.  Conflict bitmaps are only in
     webpart roots.  If they are in uses, those uses are roots, which
     means, that this is an uninitialized web, whose conflicts
     don't matter.  Nevertheless for hardregs we also need to check uses.
     E.g. hardregs used for argument passing have no DEF in the RTL,
     but if they have uses, they indeed conflict with all DEFs they
     overlap.  */
  for (i = 0; i < df->def_id + df->use_id; i++)
    {
      struct tagged_conflict *cl = web_parts[i].sub_conflicts;
      struct web *supweb1;
      if (!cl
	  || (i >= df->def_id
	      && DF_REF_REGNO (web_parts[i].ref) >= FIRST_PSEUDO_REGISTER))
	continue;
      supweb1 = def2web[i];
      supweb1 = find_web_for_subweb (supweb1);
      for (; cl; cl = cl->next)
        if (cl->conflicts)
	  {
	    int j;
	    struct web *web1 = find_subweb_2 (supweb1, cl->size_word);
	    if (have_ignored)
	      bitmap_operation (cl->conflicts, cl->conflicts, ignore_defs,
			        BITMAP_AND_COMPL);
	    /* We reduce the number of calls to record_conflict() with this
	       pass thing.  record_conflict() itself also has some early-out
	       optimizations, but here we can use the special properties of
	       the loop (constant web1) to reduce that even more.
	       We once used an sbitmap of already handled web indices,
	       but sbitmaps are slow to clear and bitmaps are slow to
	       set/test.  The current approach needs more memory, but
	       locality is large.  */
	    pass++;

	    /* Note, that there are only defs in the conflicts bitset.  */
	    EXECUTE_IF_SET_IN_BITMAP (
	      cl->conflicts, 0, j,
	      {
		struct web *web2 = def2web[j];
		unsigned int id2 = web2->id;
		if (pass_cache[id2] != pass)
		  {
		    pass_cache[id2] = pass;
		    record_conflict (web1, web2);
		  }
	      });
	  }
    }

  free (pass_cache);
  BITMAP_XFREE (ignore_defs);

#ifdef STACK_REGS
  /* Pseudos can't go in stack regs if they are live at the beginning of
     a block that is reached by an abnormal edge.  */
  for (d = WEBS(INITIAL); d; d = d->next)
    {
      struct web *web = DLIST_WEB (d);
      int j;
      if (web->live_over_abnormal)
	for (j = FIRST_STACK_REG; j <= LAST_STACK_REG; j++)
	  record_conflict (web, hardreg2web[j]);
    }
#endif
}

/* Remember that a web was spilled, and change some characteristics
   accordingly.  */

static void
remember_web_was_spilled (web)
     struct web *web;
{
  int i;
  unsigned int found_size = 0;
  int adjust;
  web->spill_temp = 1;

  /* From now on don't use reg_pref/alt_class (regno) anymore for
     this web, but instead  usable_regs.  We can't use spill_temp for
     this, as it might get reset later, when we are coalesced to a
     non-spill-temp.  In that case we still want to use usable_regs.  */
  web->use_my_regs = 1;

  /* We don't constrain spill temporaries in any way for now.
     It's wrong sometimes to have the same constraints or
     preferences as the original pseudo, esp. if they were very narrow.
     (E.g. there once was a reg wanting class AREG (only one register)
     without alternative class.  As long, as also the spill-temps for
     this pseudo had the same constraints it was spilled over and over.
     Ideally we want some constraints also on spill-temps: Because they are
     not only loaded/stored, but also worked with, any constraints from insn
     alternatives needs applying.  Currently this is dealt with by reload, as
     many other things, but at some time we want to integrate that
     functionality into the allocator.  */
  if (web->regno >= max_normal_pseudo)
    {
      COPY_HARD_REG_SET (web->usable_regs,
			reg_class_contents[reg_preferred_class (web->regno)]);
      IOR_HARD_REG_SET (web->usable_regs,
			reg_class_contents[reg_alternate_class (web->regno)]);
    }
  else
    COPY_HARD_REG_SET (web->usable_regs,
		       reg_class_contents[(int) GENERAL_REGS]);
  AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors);
  prune_hardregs_for_mode (&web->usable_regs, PSEUDO_REGNO_MODE (web->regno));
#ifdef CLASS_CANNOT_CHANGE_MODE
  if (web->mode_changed)
    AND_COMPL_HARD_REG_SET (web->usable_regs, reg_class_contents[
			      (int) CLASS_CANNOT_CHANGE_MODE]);
#endif
  web->num_freedom = hard_regs_count (web->usable_regs);
  if (!web->num_freedom)
    abort();
  COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs);
  /* Now look for a class, which is subset of our constraints, to
     setup add_hardregs, and regclass for debug output.  */
  web->regclass = NO_REGS;
  for (i = (int) ALL_REGS - 1; i > 0; i--)
    {
      unsigned int size;
      HARD_REG_SET test;
      COPY_HARD_REG_SET (test, reg_class_contents[i]);
      AND_COMPL_HARD_REG_SET (test, never_use_colors);
      GO_IF_HARD_REG_SUBSET (test, web->usable_regs, found);
      continue;
    found:
      /* Measure the actual number of bits which really are overlapping
	 the target regset, not just the reg_class_size.  */
      size = hard_regs_count (test);
      if (found_size < size)
	{
          web->regclass = (enum reg_class) i;
	  found_size = size;
	}
    }

  adjust = 0 * web->add_hardregs;
  web->add_hardregs =
    CLASS_MAX_NREGS (web->regclass, PSEUDO_REGNO_MODE (web->regno)) - 1;
  web->num_freedom -= web->add_hardregs;
  if (!web->num_freedom)
    abort();
  adjust -= 0 * web->add_hardregs;
  web->num_conflicts -= adjust;
}

/* Look at each web, if it is used as spill web.  Or better said,
   if it will be spillable in this pass.  */

static void
detect_spill_temps ()
{
  struct dlist *d;
  bitmap already = BITMAP_XMALLOC ();

  /* Detect webs used for spill temporaries.  */
  for (d = WEBS(INITIAL); d; d = d->next)
    {
      struct web *web = DLIST_WEB (d);

      /* Below only the detection of spill temporaries.  We never spill
         precolored webs, so those can't be spill temporaries.  The code above
         (remember_web_was_spilled) can't currently cope with hardregs
         anyway.  */
      if (web->regno < FIRST_PSEUDO_REGISTER)
	continue;
      /* Uninitialized webs can't be spill-temporaries.  */
      if (web->num_defs == 0)
	continue;

      /* A web with only defs and no uses can't be spilled.  Nevertheless
	 it must get a color, as it takes away an register from all webs
	 live at these defs.  So we make it a short web.  */
      if (web->num_uses == 0)
	web->spill_temp = 3;
      /* A web which was spilled last time, but for which no insns were
         emitted (can happen with IR spilling ignoring sometimes
	 all deaths).  */
      else if (web->changed)
	web->spill_temp = 1;
      /* A spill temporary has one def, one or more uses, all uses
	 are in one insn, and either the def or use insn was inserted
	 by the allocator.  */
      /* XXX not correct currently.  There might also be spill temps
	 involving more than one def.  Usually that's an additional
	 clobber in the using instruction.  We might also constrain
	 ourself to that, instead of like currently marking all
	 webs involving any spill insns at all.  */
      else
	{
	  unsigned int i;
	  int spill_involved = 0;
	  for (i = 0; i < web->num_uses && !spill_involved; i++)
	    if (DF_REF_INSN_UID (web->uses[i]) >= orig_max_uid)
	      spill_involved = 1;
	  for (i = 0; i < web->num_defs && !spill_involved; i++)
	    if (DF_REF_INSN_UID (web->defs[i]) >= orig_max_uid)
	      spill_involved = 1;

	  if (spill_involved/* && ra_pass > 2*/)
	    {
	      int num_deaths = web->span_deaths;
	      /* Mark webs involving at least one spill insn as
		 spill temps.  */
	      remember_web_was_spilled (web);
	      /* Search for insns which define and use the web in question
		 at the same time, i.e. look for rmw insns.  If these insns
		 are also deaths of other webs they might have been counted
		 as such into web->span_deaths.  But because of the rmw nature
		 of this insn it is no point where a load/reload could be
		 placed successfully (it would still conflict with the
		 dead web), so reduce the number of spanned deaths by those
		 insns.  Note that sometimes such deaths are _not_ counted,
	         so negative values can result.  */
	      bitmap_zero (already);
	      for (i = 0; i < web->num_defs; i++)
		{
		  rtx insn = web->defs[i]->insn;
		  if (TEST_BIT (insns_with_deaths, INSN_UID (insn))
		      && !bitmap_bit_p (already, INSN_UID (insn)))
		    {
		      unsigned int j;
		      bitmap_set_bit (already, INSN_UID (insn));
		      /* Only decrement it once for each insn.  */
		      for (j = 0; j < web->num_uses; j++)
			if (web->uses[j]->insn == insn)
			  {
			    num_deaths--;
			    break;
			  }
		    }
		}
	      /* But mark them specially if they could possibly be spilled,
		 either because they cross some deaths (without the above
		 mentioned ones) or calls.  */
	      if (web->crosses_call || num_deaths > 0)
		web->spill_temp = 1 * 2;
	    }
	  /* A web spanning no deaths can't be spilled either.  No loads
	     would be created for it, ergo no defs.  So the insns wouldn't
	     change making the graph not easier to color.  Make this also
	     a short web.  Don't do this if it crosses calls, as these are
	     also points of reloads.  */
	  else if (web->span_deaths == 0 && !web->crosses_call)
	    web->spill_temp = 3;
	}
      web->orig_spill_temp = web->spill_temp;
    }
  BITMAP_XFREE (already);
}

/* Returns nonzero if the rtx MEM refers somehow to a stack location.  */

int
memref_is_stack_slot (mem)
     rtx mem;
{
  rtx ad = XEXP (mem, 0);
  rtx x;
  if (GET_CODE (ad) != PLUS || GET_CODE (XEXP (ad, 1)) != CONST_INT)
    return 0;
  x = XEXP (ad, 0);
  if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
      || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
      || x == stack_pointer_rtx)
    return 1;
  return 0;
}

/* Returns nonzero, if rtx X somewhere contains any pseudo register.  */

static int
contains_pseudo (x)
     rtx x;
{
  const char *fmt;
  int i;
  if (GET_CODE (x) == SUBREG)
    x = SUBREG_REG (x);
  if (GET_CODE (x) == REG)
    {
      if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
        return 1;
      else
	return 0;
    }

  fmt = GET_RTX_FORMAT (GET_CODE (x));
  for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
    if (fmt[i] == 'e')
      {
	if (contains_pseudo (XEXP (x, i)))
	  return 1;
      }
    else if (fmt[i] == 'E')
      {
	int j;
	for (j = 0; j < XVECLEN (x, i); j++)
	  if (contains_pseudo (XVECEXP (x, i, j)))
	    return 1;
      }
  return 0;
}

/* Returns nonzero, if we are able to rematerialize something with
   value X.  If it's not a general operand, we test if we can produce
   a valid insn which set a pseudo to that value, and that insn doesn't
   clobber anything.  */

static GTY(()) rtx remat_test_insn;
static int
want_to_remat (x)
     rtx x;
{
  int num_clobbers = 0;
  int icode;

  /* If this is a valid operand, we are OK.  If it's VOIDmode, we aren't.  */
  if (general_operand (x, GET_MODE (x)))
    return 1;

  /* Otherwise, check if we can make a valid insn from it.  First initialize
     our test insn if we haven't already.  */
  if (remat_test_insn == 0)
    {
      remat_test_insn
	= make_insn_raw (gen_rtx_SET (VOIDmode,
				      gen_rtx_REG (word_mode,
						   FIRST_PSEUDO_REGISTER * 2),
				      const0_rtx));
      NEXT_INSN (remat_test_insn) = PREV_INSN (remat_test_insn) = 0;
    }

  /* Now make an insn like the one we would make when rematerializing
     the value X and see if valid.  */
  PUT_MODE (SET_DEST (PATTERN (remat_test_insn)), GET_MODE (x));
  SET_SRC (PATTERN (remat_test_insn)) = x;
  /* XXX For now we don't allow any clobbers to be added, not just no
     hardreg clobbers.  */
  return ((icode = recog (PATTERN (remat_test_insn), remat_test_insn,
			  &num_clobbers)) >= 0
	  && (num_clobbers == 0
	      /*|| ! added_clobbers_hard_reg_p (icode)*/));
}

/* Look at all webs, if they perhaps are rematerializable.
   They are, if all their defs are simple sets to the same value,
   and that value is simple enough, and want_to_remat() holds for it.  */

static void
detect_remat_webs ()
{
  struct dlist *d;
  for (d = WEBS(INITIAL); d; d = d->next)
    {
      struct web *web = DLIST_WEB (d);
      unsigned int i;
      rtx pat = NULL_RTX;
      /* Hardregs and useless webs aren't spilled -> no remat necessary.
	 Defless webs obviously also can't be rematerialized.  */
      if (web->regno < FIRST_PSEUDO_REGISTER || !web->num_defs
	  || !web->num_uses)
	continue;
      for (i = 0; i < web->num_defs; i++)
	{
	  rtx insn;
	  rtx set = single_set (insn = DF_REF_INSN (web->defs[i]));
	  rtx src;
	  if (!set)
	    break;
	  src = SET_SRC (set);
	  /* When only subregs of the web are set it isn't easily
	     rematerializable.  */
	  if (!rtx_equal_p (SET_DEST (set), web->orig_x))
	    break;
	  /* If we already have a pattern it must be equal to the current.  */
	  if (pat && !rtx_equal_p (pat, src))
	    break;
	  /* Don't do the expensive checks multiple times.  */
	  if (pat)
	    continue;
	  /* For now we allow only constant sources.  */
	  if ((CONSTANT_P (src)
	       /* If the whole thing is stable already, it is a source for
		  remat, no matter how complicated (probably all needed
		  resources for it are live everywhere, and don't take
		  additional register resources).  */
	       /* XXX Currently we can't use patterns which contain
		  pseudos, _even_ if they are stable.  The code simply isn't
		  prepared for that.  All those operands can't be spilled (or
		  the dependent remat webs are not remat anymore), so they
		  would be oldwebs in the next iteration.  But currently
		  oldwebs can't have their references changed.  The
		  incremental machinery barfs on that.  */
	       || (!rtx_unstable_p (src) && !contains_pseudo (src))
	       /* Additionally also memrefs to stack-slots are usefull, when
		  we created them ourself.  They might not have set their
		  unchanging flag set, but nevertheless they are stable across
		  the livetime in question.  */
	       || (GET_CODE (src) == MEM
		   && INSN_UID (insn) >= orig_max_uid
		   && memref_is_stack_slot (src)))
	      /* And we must be able to construct an insn without
		 side-effects to actually load that value into a reg.  */
	      && want_to_remat (src))
	    pat = src;
	  else
	    break;
	}
      if (pat && i == web->num_defs)
	web->pattern = pat;
    }
}

/* Determine the spill costs of all webs.  */

static void
determine_web_costs ()
{
  struct dlist *d;
  for (d = WEBS(INITIAL); d; d = d->next)
    {
      unsigned int i, num_loads;
      int load_cost, store_cost;
      unsigned HOST_WIDE_INT w;
      struct web *web = DLIST_WEB (d);
      if (web->type == PRECOLORED)
	continue;
      /* Get costs for one load/store.  Note that we offset them by 1,
	 because some patterns have a zero rtx_cost(), but we of course
	 still need the actual load/store insns.  With zero all those
	 webs would be the same, no matter how often and where
	 they are used.  */
      if (web->pattern)
	{
	  /* This web is rematerializable.  Beware, we set store_cost to
	     zero optimistically assuming, that we indeed don't emit any
	     stores in the spill-code addition.  This might be wrong if
	     at the point of the load not all needed resources are
	     available, in which case we emit a stack-based load, for
	     which we in turn need the according stores.  */
	  load_cost = 1 + rtx_cost (web->pattern, 0);
	  store_cost = 0;
	}
      else
	{
	  load_cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x),
					    web->regclass, 1);
	  store_cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x),
					     web->regclass, 0);
	}
      /* We create only loads at deaths, whose number is in span_deaths.  */
      num_loads = MIN (web->span_deaths, web->num_uses);
      for (w = 0, i = 0; i < web->num_uses; i++)
	w += DF_REF_BB (web->uses[i])->frequency + 1;
      if (num_loads < web->num_uses)
	w = (w * num_loads + web->num_uses - 1) / web->num_uses;
      web->spill_cost = w * load_cost;
      if (store_cost)
	{
	  for (w = 0, i = 0; i < web->num_defs; i++)
	    w += DF_REF_BB (web->defs[i])->frequency + 1;
	  web->spill_cost += w * store_cost;
	}
      web->orig_spill_cost = web->spill_cost;
    }
}

/* Detect webs which are set in a conditional jump insn (possibly a
   decrement-and-branch type of insn), and mark them not to be
   spillable.  The stores for them would need to be placed on edges,
   which destroys the CFG.  (Somewhen we want to deal with that XXX)  */

static void
detect_webs_set_in_cond_jump ()
{
  basic_block bb;
  FOR_EACH_BB (bb)
    if (GET_CODE (bb->end) == JUMP_INSN)
      {
	struct df_link *link;
	for (link = DF_INSN_DEFS (df, bb->end); link; link = link->next)
	  if (link->ref && DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER)
	    {
	      struct web *web = def2web[DF_REF_ID (link->ref)];
	      web->orig_spill_temp = web->spill_temp = 3;
	    }
      }
}

/* Second top-level function of this file.
   Converts the connected web parts to full webs.  This means, it allocates
   all webs, and initializes all fields, including detecting spill
   temporaries.  It does not distribute moves to their corresponding webs,
   though.  */

static void
make_webs (df)
     struct df *df;
{
  /* First build all the webs itself.  They are not related with
     others yet.  */
  parts_to_webs (df);
  /* Now detect spill temporaries to initialize their usable_regs set.  */
  detect_spill_temps ();
  detect_webs_set_in_cond_jump ();
  /* And finally relate them to each other, meaning to record all possible
     conflicts between webs (see the comment there).  */
  conflicts_between_webs (df);
  detect_remat_webs ();
  determine_web_costs ();
}

/* Distribute moves to the corresponding webs.  */

static void
moves_to_webs (df)
     struct df *df;
{
  struct df_link *link;
  struct move_list *ml;

  /* Distribute all moves to their corresponding webs, making sure,
     each move is in a web maximally one time (happens on some strange
     insns).  */
  for (ml = wl_moves; ml; ml = ml->next)
    {
      struct move *m = ml->move;
      struct web *web;
      struct move_list *newml;
      if (!m)
	continue;
      m->type = WORKLIST;
      m->dlink = NULL;
      /* Multiple defs/uses can happen in moves involving hard-regs in
	 a wider mode.  For those df.* creates use/def references for each
	 real hard-reg involved.  For coalescing we are interested in
	 the smallest numbered hard-reg.  */
      for (link = DF_INSN_DEFS (df, m->insn); link; link = link->next)
        if (link->ref)
	  {
	    web = def2web[DF_REF_ID (link->ref)];
	    web = find_web_for_subweb (web);
	    if (!m->target_web || web->regno < m->target_web->regno)
	      m->target_web = web;
	  }
      for (link = DF_INSN_USES (df, m->insn); link; link = link->next)
        if (link->ref)
	  {
	    web = use2web[DF_REF_ID (link->ref)];
	    web = find_web_for_subweb (web);
	    if (!m->source_web || web->regno < m->source_web->regno)
	      m->source_web = web;
	  }
      if (m->source_web && m->target_web
	  /* If the usable_regs don't intersect we can't coalesce the two
	     webs anyway, as this is no simple copy insn (it might even
	     need an intermediate stack temp to execute this "copy" insn).  */
	  && hard_regs_intersect_p (&m->source_web->usable_regs,
				    &m->target_web->usable_regs))
	{
	  if (!flag_ra_optimistic_coalescing)
	    {
	      struct move_list *test = m->source_web->moves;
	      for (; test && test->move != m; test = test->next);
	      if (! test)
		{
		  newml = (struct move_list*)
		    ra_alloc (sizeof (struct move_list));
		  newml->move = m;
		  newml->next = m->source_web->moves;
		  m->source_web->moves = newml;
		}
	      test = m->target_web->moves;
	      for (; test && test->move != m; test = test->next);
	      if (! test)
		{
		  newml = (struct move_list*)
		    ra_alloc (sizeof (struct move_list));
		  newml->move = m;
		  newml->next = m->target_web->moves;
		  m->target_web->moves = newml;
		}
	    }
	}
      else
	/* Delete this move.  */
	ml->move = NULL;
    }
}

/* Handle tricky asm insns.
   Supposed to create conflicts to hardregs which aren't allowed in
   the constraints.  Doesn't actually do that, as it might confuse
   and constrain the allocator too much.  */

static void
handle_asm_insn (df, insn)
     struct df *df;
     rtx insn;
{
  const char *constraints[MAX_RECOG_OPERANDS];
  enum machine_mode operand_mode[MAX_RECOG_OPERANDS];
  int i, noperands, in_output;
  HARD_REG_SET clobbered, allowed, conflict;
  rtx pat;
  if (! INSN_P (insn)
      || (noperands = asm_noperands (PATTERN (insn))) < 0)
    return;
  pat = PATTERN (insn);
  CLEAR_HARD_REG_SET (clobbered);

  if (GET_CODE (pat) == PARALLEL)
    for (i = 0; i < XVECLEN (pat, 0); i++)
      {
	rtx t = XVECEXP (pat, 0, i);
	if (GET_CODE (t) == CLOBBER && GET_CODE (XEXP (t, 0)) == REG
	    && REGNO (XEXP (t, 0)) < FIRST_PSEUDO_REGISTER)
	  SET_HARD_REG_BIT (clobbered, REGNO (XEXP (t, 0)));
      }

  decode_asm_operands (pat, recog_data.operand, recog_data.operand_loc,
		       constraints, operand_mode);
  in_output = 1;
  for (i = 0; i < noperands; i++)
    {
      const char *p = constraints[i];
      int cls = (int) NO_REGS;
      struct df_link *link;
      rtx reg;
      struct web *web;
      int nothing_allowed = 1;
      reg = recog_data.operand[i];

      /* Look, if the constraints apply to a pseudo reg, and not to
	 e.g. a mem.  */
      while (GET_CODE (reg) == SUBREG
	     || GET_CODE (reg) == ZERO_EXTRACT
	     || GET_CODE (reg) == SIGN_EXTRACT
	     || GET_CODE (reg) == STRICT_LOW_PART)
	reg = XEXP (reg, 0);
      if (GET_CODE (reg) != REG || REGNO (reg) < FIRST_PSEUDO_REGISTER)
	continue;

      /* Search the web corresponding to this operand.  We depend on
	 that decode_asm_operands() places the output operands
	 before the input operands.  */
      while (1)
	{
	  if (in_output)
	    link = df->insns[INSN_UID (insn)].defs;
	  else
	    link = df->insns[INSN_UID (insn)].uses;
	  while (link && link->ref && DF_REF_REAL_REG (link->ref) != reg)
	    link = link->next;
	  if (!link || !link->ref)
	    {
	      if (in_output)
	        in_output = 0;
	      else
	        abort ();
	    }
	  else
	    break;
	}
      if (in_output)
	web = def2web[DF_REF_ID (link->ref)];
      else
	web = use2web[DF_REF_ID (link->ref)];
      reg = DF_REF_REG (link->ref);

      /* Find the constraints, noting the allowed hardregs in allowed.  */
      CLEAR_HARD_REG_SET (allowed);
      while (1)
	{
	  char c = *p++;

	  if (c == '\0' || c == ',' || c == '#')
	    {
	      /* End of one alternative - mark the regs in the current
	       class, and reset the class.
	       */
	      IOR_HARD_REG_SET (allowed, reg_class_contents[cls]);
	      if (cls != NO_REGS)
		nothing_allowed = 0;
	      cls = NO_REGS;
	      if (c == '#')
		do {
		    c = *p++;
		} while (c != '\0' && c != ',');
	      if (c == '\0')
	        break;
	      continue;
	    }

	  switch (c)
	    {
	      case '=': case '+': case '*': case '%': case '?': case '!':
	      case '0': case '1': case '2': case '3': case '4': case 'm':
	      case '<': case '>': case 'V': case 'o': case '&': case 'E':
	      case 'F': case 's': case 'i': case 'n': case 'X': case 'I':
	      case 'J': case 'K': case 'L': case 'M': case 'N': case 'O':
	      case 'P':
		break;

	      case 'p':
		cls = (int) reg_class_subunion[cls][(int) BASE_REG_CLASS];
		nothing_allowed = 0;
	        break;

	      case 'g':
	      case 'r':
		cls = (int) reg_class_subunion[cls][(int) GENERAL_REGS];
		nothing_allowed = 0;
		break;

	      default:
		cls =
		  (int) reg_class_subunion[cls][(int)
						REG_CLASS_FROM_LETTER (c)];
	    }
	}

      /* Now make conflicts between this web, and all hardregs, which
	 are not allowed by the constraints.  */
      if (nothing_allowed)
	{
	  /* If we had no real constraints nothing was explicitely
	     allowed, so we allow the whole class (i.e. we make no
	     additional conflicts).  */
	  CLEAR_HARD_REG_SET (conflict);
	}
      else
	{
	  COPY_HARD_REG_SET (conflict, usable_regs
			     [reg_preferred_class (web->regno)]);
	  IOR_HARD_REG_SET (conflict, usable_regs
			    [reg_alternate_class (web->regno)]);
	  AND_COMPL_HARD_REG_SET (conflict, allowed);
	  /* We can't yet establish these conflicts.  Reload must go first
	     (or better said, we must implement some functionality of reload).
	     E.g. if some operands must match, and they need the same color
	     we don't see yet, that they do not conflict (because they match).
	     For us it looks like two normal references with different DEFs,
	     so they conflict, and as they both need the same color, the
	     graph becomes uncolorable.  */
#if 0
	  for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
	    if (TEST_HARD_REG_BIT (conflict, c))
	      record_conflict (web, hardreg2web[c]);
#endif
	}
      if (rtl_dump_file)
	{
	  int c;
	  ra_debug_msg (DUMP_ASM, " ASM constrain Web %d conflicts with:", web->id);
	  for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
	    if (TEST_HARD_REG_BIT (conflict, c))
	      ra_debug_msg (DUMP_ASM, " %d", c);
	  ra_debug_msg (DUMP_ASM, "\n");
	}
    }
}

/* The real toplevel function in this file.
   Build (or rebuilds) the complete interference graph with webs
   and conflicts.  */

void
build_i_graph (df)
     struct df *df;
{
  rtx insn;

  init_web_parts (df);

  sbitmap_zero (move_handled);
  wl_moves = NULL;

  build_web_parts_and_conflicts (df);

  /* For read-modify-write instructions we may have created two webs.
     Reconnect them here.  (s.a.)  */
  connect_rmw_web_parts (df);

  /* The webs are conceptually complete now, but still scattered around as
     connected web parts.  Collect all information and build the webs
     including all conflicts between webs (instead web parts).  */
  make_webs (df);
  moves_to_webs (df);

  /* Look for additional constraints given by asms.  */
  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
    handle_asm_insn (df, insn);
}

/* Allocates or reallocates most memory for the interference graph and
   assiciated structures.  If it reallocates memory (meaning, this is not
   the first pass), this also changes some structures to reflect the
   additional entries in various array, and the higher number of
   defs and uses.  */

void
ra_build_realloc (df)
     struct df *df;
{
  struct web_part *last_web_parts = web_parts;
  struct web **last_def2web = def2web;
  struct web **last_use2web = use2web;
  sbitmap last_live_over_abnormal = live_over_abnormal;
  unsigned int i;
  struct dlist *d;
  move_handled = sbitmap_alloc (get_max_uid () );
  web_parts = (struct web_part *) xcalloc (df->def_id + df->use_id,
					   sizeof web_parts[0]);
  def2web = (struct web **) xcalloc (df->def_id + df->use_id,
				     sizeof def2web[0]);
  use2web = &def2web[df->def_id];
  live_over_abnormal = sbitmap_alloc (df->use_id);
  sbitmap_zero (live_over_abnormal);

  /* First go through all old defs and uses.  */
  for (i = 0; i < last_def_id + last_use_id; i++)
    {
      /* And relocate them to the new array.  This is made ugly by the
         fact, that defs and uses are placed consecutive into one array.  */
      struct web_part *dest = &web_parts[i < last_def_id
					 ? i : (df->def_id + i - last_def_id)];
      struct web_part *up;
      *dest = last_web_parts[i];
      up = dest->uplink;
      dest->uplink = NULL;

      /* Also relocate the uplink to point into the new array.  */
      if (up && up->ref)
	{
	  unsigned int id = DF_REF_ID (up->ref);
	  if (up < &last_web_parts[last_def_id])
	    {
	      if (df->defs[id])
	        dest->uplink = &web_parts[DF_REF_ID (up->ref)];
	    }
	  else if (df->uses[id])
	    dest->uplink = &web_parts[df->def_id + DF_REF_ID (up->ref)];
	}
    }

  /* Also set up the def2web and use2web arrays, from the last pass.i
     Remember also the state of live_over_abnormal.  */
  for (i = 0; i < last_def_id; i++)
    {
      struct web *web = last_def2web[i];
      if (web)
	{
	  web = find_web_for_subweb (web);
	  if (web->type != FREE && web->type != PRECOLORED)
	    def2web[i] = last_def2web[i];
	}
    }
  for (i = 0; i < last_use_id; i++)
    {
      struct web *web = last_use2web[i];
      if (web)
	{
	  web = find_web_for_subweb (web);
	  if (web->type != FREE && web->type != PRECOLORED)
	    use2web[i] = last_use2web[i];
	}
      if (TEST_BIT (last_live_over_abnormal, i))
	SET_BIT (live_over_abnormal, i);
    }

  /* We don't have any subwebs for now.  Somewhen we might want to
     remember them too, instead of recreating all of them every time.
     The problem is, that which subwebs we need, depends also on what
     other webs and subwebs exist, and which conflicts are there.
     OTOH it should be no problem, if we had some more subwebs than strictly
     needed.  Later.  */
  for (d = WEBS(FREE); d; d = d->next)
    {
      struct web *web = DLIST_WEB (d);
      struct web *wnext;
      for (web = web->subreg_next; web; web = wnext)
	{
	  wnext = web->subreg_next;
	  free (web);
	}
      DLIST_WEB (d)->subreg_next = NULL;
    }

  /* The uses we anyway are going to check, are not yet live over an abnormal
     edge.  In fact, they might actually not anymore, due to added
     loads.  */
  if (last_check_uses)
    sbitmap_difference (live_over_abnormal, live_over_abnormal,
		        last_check_uses);

  if (last_def_id || last_use_id)
    {
      sbitmap_free (last_live_over_abnormal);
      free (last_web_parts);
      free (last_def2web);
    }
  if (!last_max_uid)
    {
      /* Setup copy cache, for copy_insn_p ().  */
      copy_cache = (struct copy_p_cache *)
	xcalloc (get_max_uid (), sizeof (copy_cache[0]));
      init_bb_info ();
    }
  else
    {
      copy_cache = (struct copy_p_cache *)
	xrealloc (copy_cache, get_max_uid () * sizeof (copy_cache[0]));
      memset (&copy_cache[last_max_uid], 0,
	      (get_max_uid () - last_max_uid) * sizeof (copy_cache[0]));
    }
}

/* Free up/clear some memory, only needed for one pass.  */

void
ra_build_free ()
{
  struct dlist *d;
  unsigned int i;

  /* Clear the moves associated with a web (we also need to look into
     subwebs here).  */
  for (i = 0; i < num_webs; i++)
    {
      struct web *web = ID2WEB (i);
      if (!web)
	abort ();
      if (i >= num_webs - num_subwebs
	  && (web->conflict_list || web->orig_conflict_list))
	abort ();
      web->moves = NULL;
    }
  /* All webs in the free list have no defs or uses anymore.  */
  for (d = WEBS(FREE); d; d = d->next)
    {
      struct web *web = DLIST_WEB (d);
      if (web->defs)
	free (web->defs);
      web->defs = NULL;
      if (web->uses)
	free (web->uses);
      web->uses = NULL;
      /* We can't free the subwebs here, as they are referenced from
	 def2web[], and possibly needed in the next ra_build_realloc().
	 We free them there (or in free_all_mem()).  */
    }

  /* Free all conflict bitmaps from web parts.  Note that we clear
     _all_ these conflicts, and don't rebuild them next time for uses
     which aren't rechecked.  This mean, that those conflict bitmaps
     only contain the incremental information.  The cumulative one
     is still contained in the edges of the I-graph, i.e. in
     conflict_list (or orig_conflict_list) of the webs.  */
  for (i = 0; i < df->def_id + df->use_id; i++)
    {
      struct tagged_conflict *cl;
      for (cl = web_parts[i].sub_conflicts; cl; cl = cl->next)
	{
	  if (cl->conflicts)
	    BITMAP_XFREE (cl->conflicts);
	}
      web_parts[i].sub_conflicts = NULL;
    }

  wl_moves = NULL;

  free (id2web);
  free (move_handled);
  sbitmap_free (sup_igraph);
  sbitmap_free (igraph);
}

/* Free all memory for the interference graph structures.  */

void
ra_build_free_all (df)
     struct df *df;
{
  unsigned int i;

  free_bb_info ();
  free (copy_cache);
  copy_cache = NULL;
  for (i = 0; i < df->def_id + df->use_id; i++)
    {
      struct tagged_conflict *cl;
      for (cl = web_parts[i].sub_conflicts; cl; cl = cl->next)
	{
	  if (cl->conflicts)
	    BITMAP_XFREE (cl->conflicts);
	}
      web_parts[i].sub_conflicts = NULL;
    }
  sbitmap_free (live_over_abnormal);
  free (web_parts);
  web_parts = NULL;
  if (last_check_uses)
    sbitmap_free (last_check_uses);
  last_check_uses = NULL;
  free (def2web);
  use2web = NULL;
  def2web = NULL;
}

#include "gt-ra-build.h"

/*
vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
*/
OpenPOWER on IntegriCloud