aboutsummaryrefslogtreecommitdiff
path: root/gcc/ssa.c
blob: dd4b4736164d3467b806bbcb6360a9d20eb968d6 (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
/* Static Single Assignment conversion routines for the GNU compiler.
   Copyright (C) 2000 Free Software Foundation, Inc.

This file is part of GNU CC.

GNU CC 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.

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

/* References:

   Building an Optimizing Compiler
   Robert Morgan
   Butterworth-Heinemann, 1998

   Static Single Assignment Construction
   Preston Briggs, Tim Harvey, Taylor Simpson
   Technical Report, Rice University, 1995
   ftp://ftp.cs.rice.edu/public/preston/optimizer/SSA.ps.gz
*/

#include "config.h"
#include "system.h"

#include "rtl.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
#include "function.h"
#include "real.h"
#include "insn-config.h"
#include "recog.h"
#include "basic-block.h"
#include "output.h"
#include "partition.h"


/* TODO: 

   Handle subregs better, maybe.  For now, if a reg that's set in a
   subreg expression is duplicated going into SSA form, an extra copy
   is inserted first that copies the entire reg into the duplicate, so
   that the other bits are preserved.  This isn't strictly SSA, since
   at least part of the reg is assigned in more than one place (though
   they are adjacent).

   ??? What to do about strict_low_part.  Probably I'll have to split
   them out of their current instructions first thing.

   Actually the best solution may be to have a kind of "mid-level rtl"
   in which the RTL encodes exactly what we want, without exposing a
   lot of niggling processor details.  At some later point we lower
   the representation, calling back into optabs to finish any necessary
   expansion.  */


/* If conservative_reg_partition is non-zero, use a conservative
   register partitioning algorithm (which leaves more regs after
   emerging from SSA) instead of the coalescing one.  This is being
   left in for a limited time only, as a debugging tool until the
   coalescing algorithm is validated.  */
static int conservative_reg_partition;

/* This flag is set when the CFG is in SSA form.  */
int in_ssa_form = 0;

/* Element I is the single instruction that sets register I+PSEUDO.  */
varray_type ssa_definition;

/* Element I is an INSN_LIST of instructions that use register I+PSEUDO.  */
varray_type ssa_uses;

/* Element I-PSEUDO is the normal register that originated the ssa
   register in question.  */
varray_type ssa_rename_from;

/* The running target ssa register for a given normal register.  */
static rtx *ssa_rename_to;

/* The number of registers that were live on entry to the SSA routines.  */
static unsigned int ssa_max_reg_num;

/* Local function prototypes.  */

static inline rtx * phi_alternative
  PARAMS ((rtx, int));

static int remove_phi_alternative
  PARAMS ((rtx, int));
static void simplify_to_immediate_dominators 
  PARAMS ((int *idom, sbitmap *dominators));
static void compute_dominance_frontiers_1
  PARAMS ((sbitmap *frontiers, int *idom, int bb, sbitmap done));
static void compute_dominance_frontiers
  PARAMS ((sbitmap *frontiers, int *idom));
static void find_evaluations_1
  PARAMS ((rtx dest, rtx set, void *data));
static void find_evaluations
  PARAMS ((sbitmap *evals, int nregs));
static void compute_iterated_dominance_frontiers
  PARAMS ((sbitmap *idfs, sbitmap *frontiers, sbitmap *evals, int nregs));
static void insert_phi_node
  PARAMS ((int regno, int b));
static void insert_phi_nodes
  PARAMS ((sbitmap *idfs, sbitmap *evals, int nregs));
static int rename_insn_1 
  PARAMS ((rtx *ptr, void *data));
static void rename_block 
  PARAMS ((int b, int *idom));
static void rename_registers 
  PARAMS ((int nregs, int *idom));

static inline int ephi_add_node
  PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
static int * ephi_forward
  PARAMS ((int t, sbitmap visited, sbitmap *succ, int *tstack));
static void ephi_backward
  PARAMS ((int t, sbitmap visited, sbitmap *pred, rtx *nodes));
static void ephi_create
  PARAMS ((int t, sbitmap visited, sbitmap *pred, sbitmap *succ, rtx *nodes));
static void eliminate_phi
  PARAMS ((edge e, partition reg_partition));
static int make_regs_equivalent_over_bad_edges 
  PARAMS ((int bb, partition reg_partition));

/* These are used only in the conservative register partitioning
   algorithms.  */
static int make_equivalent_phi_alternatives_equivalent 
  PARAMS ((int bb, partition reg_partition));
static partition compute_conservative_reg_partition 
  PARAMS ((void));
static int rename_equivalent_regs_in_insn 
  PARAMS ((rtx *ptr, void *data));

/* These are used in the register coalescing algorithm.  */
static int coalesce_if_unconflicting
  PARAMS ((partition p, conflict_graph conflicts, int reg1, int reg2));
static int coalesce_regs_in_copies
  PARAMS ((basic_block bb, partition p, conflict_graph conflicts));
static int coalesce_reg_in_phi
  PARAMS ((rtx, int dest_regno, int src_regno, void *data));
static int coalesce_regs_in_successor_phi_nodes
  PARAMS ((basic_block bb, partition p, conflict_graph conflicts));
static partition compute_coalesced_reg_partition
  PARAMS ((void));
static int mark_reg_in_phi 
  PARAMS ((rtx *ptr, void *data));
static void mark_phi_and_copy_regs
  PARAMS ((regset phi_set));

static int rename_equivalent_regs_in_insn 
  PARAMS ((rtx *ptr, void *data));
static void rename_equivalent_regs 
  PARAMS ((partition reg_partition));


/* Given the SET of a PHI node, return the address of the alternative
   for predecessor block C.  */

static inline rtx *
phi_alternative (set, c)
     rtx set;
     int c;
{
  rtvec phi_vec = XVEC (SET_SRC (set), 0);
  int v;

  for (v = GET_NUM_ELEM (phi_vec) - 2; v >= 0; v -= 2)
    if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
      return &RTVEC_ELT (phi_vec, v);

  return NULL;
}

/* Given the SET of a phi node, remove the alternative for predecessor
   block C.  Return non-zero on success, or zero if no alternative is
   found for C.  */

static int
remove_phi_alternative (set, c)
     rtx set;
     int c;
{
  rtvec phi_vec = XVEC (SET_SRC (set), 0);
  int num_elem = GET_NUM_ELEM (phi_vec);
  int v;

  for (v = num_elem - 2; v >= 0; v -= 2)
    if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
      {
	if (v < num_elem - 2)
	  {
	    RTVEC_ELT (phi_vec, v) = RTVEC_ELT (phi_vec, num_elem - 2);
	    RTVEC_ELT (phi_vec, v + 1) = RTVEC_ELT (phi_vec, num_elem - 1);
	  }
	PUT_NUM_ELEM (phi_vec, num_elem - 2);
	return 1;
      }

  return 0;
}

/* Computing the Immediate Dominators:

   Throughout, we don't actually want the full dominators set as
   calculated by flow, but rather the immediate dominators.
*/

static void
simplify_to_immediate_dominators (idom, dominators)
     int *idom;
     sbitmap *dominators;
{
  sbitmap *tmp;
  int b;

  tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);

  /* Begin with tmp(n) = dom(n) - { n }.  */
  for (b = n_basic_blocks; --b >= 0; )
    {
      sbitmap_copy (tmp[b], dominators[b]);
      RESET_BIT (tmp[b], b);
    }

  /* Subtract out all of our dominator's dominators.  */
  for (b = n_basic_blocks; --b >= 0; )
    {
      sbitmap tmp_b = tmp[b];
      int s;

      for (s = n_basic_blocks; --s >= 0; )
	if (TEST_BIT (tmp_b, s))
	  sbitmap_difference (tmp_b, tmp_b, tmp[s]);
    }

  /* Find the one bit set in the bitmap and put it in the output array.  */
  for (b = n_basic_blocks; --b >= 0; )
    {
      int t;
      EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
    }

  sbitmap_vector_free (tmp);
}


/* For all registers, find all blocks in which they are set.

   This is the transform of what would be local kill information that
   we ought to be getting from flow.  */

static sbitmap *fe_evals;
static int fe_current_bb;

static void
find_evaluations_1 (dest, set, data)
     rtx dest;
     rtx set ATTRIBUTE_UNUSED;
     void *data ATTRIBUTE_UNUSED;
{
  if (GET_CODE (dest) == REG
      && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
    SET_BIT (fe_evals[REGNO (dest) - FIRST_PSEUDO_REGISTER], fe_current_bb);
}

static void
find_evaluations (evals, nregs)
     sbitmap *evals;
     int nregs;
{
  int bb;

  sbitmap_vector_zero (evals, nregs);
  fe_evals = evals;

  for (bb = n_basic_blocks; --bb >= 0; )
    {
      rtx p, last;

      fe_current_bb = bb;
      p = BLOCK_HEAD (bb);
      last = BLOCK_END (bb);
      while (1)
	{
	  if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
	    note_stores (PATTERN (p), find_evaluations_1, NULL);

	  if (p == last)
	    break;
	  p = NEXT_INSN (p);
	}
    }
}


/* Computing the Dominance Frontier:
  
   As decribed in Morgan, section 3.5, this may be done simply by 
   walking the dominator tree bottom-up, computing the frontier for
   the children before the parent.  When considering a block B,
   there are two cases:

   (1) A flow graph edge leaving B that does not lead to a child
   of B in the dominator tree must be a block that is either equal
   to B or not dominated by B.  Such blocks belong in the frontier
   of B.

   (2) Consider a block X in the frontier of one of the children C
   of B.  If X is not equal to B and is not dominated by B, it
   is in the frontier of B.
*/

static void
compute_dominance_frontiers_1 (frontiers, idom, bb, done)
     sbitmap *frontiers;
     int *idom;
     int bb;
     sbitmap done;
{
  basic_block b = BASIC_BLOCK (bb);
  edge e;
  int c;

  SET_BIT (done, bb);
  sbitmap_zero (frontiers[bb]);

  /* Do the frontier of the children first.  Not all children in the
     dominator tree (blocks dominated by this one) are children in the
     CFG, so check all blocks.  */
  for (c = 0; c < n_basic_blocks; ++c)
    if (idom[c] == bb && ! TEST_BIT (done, c))
      compute_dominance_frontiers_1 (frontiers, idom, c, done);

  /* Find blocks conforming to rule (1) above.  */
  for (e = b->succ; e; e = e->succ_next)
    {
      if (e->dest == EXIT_BLOCK_PTR)
	continue;
      if (idom[e->dest->index] != bb)
	SET_BIT (frontiers[bb], e->dest->index);
    }

  /* Find blocks conforming to rule (2).  */
  for (c = 0; c < n_basic_blocks; ++c)
    if (idom[c] == bb)
      {
	int x;
	EXECUTE_IF_SET_IN_SBITMAP (frontiers[c], 0, x,
	  {
	    if (idom[x] != bb)
	      SET_BIT (frontiers[bb], x);
	  });
      }
}

static void
compute_dominance_frontiers (frontiers, idom)
     sbitmap *frontiers;
     int *idom;
{
  sbitmap done = sbitmap_alloc (n_basic_blocks);
  sbitmap_zero (done);

  compute_dominance_frontiers_1 (frontiers, idom, 0, done);

  sbitmap_free (done);
}


/* Computing the Iterated Dominance Frontier:

   This is the set of merge points for a given register.

   This is not particularly intuitive.  See section 7.1 of Morgan, in
   particular figures 7.3 and 7.4 and the immediately surrounding text.
*/

static void
compute_iterated_dominance_frontiers (idfs, frontiers, evals, nregs)
     sbitmap *idfs;
     sbitmap *frontiers;
     sbitmap *evals;
     int nregs;
{
  sbitmap worklist;
  int reg, passes = 0;

  worklist = sbitmap_alloc (n_basic_blocks);

  for (reg = 0; reg < nregs; ++reg)
    {
      sbitmap idf = idfs[reg];
      int b, changed;

      /* Start the iterative process by considering those blocks that
	 evaluate REG.  We'll add their dominance frontiers to the
	 IDF, and then consider the blocks we just added.  */
      sbitmap_copy (worklist, evals[reg]);

      /* Morgan's algorithm is incorrect here.  Blocks that evaluate
	 REG aren't necessarily in REG's IDF.  Start with an empty IDF.  */
      sbitmap_zero (idf);

      /* Iterate until the worklist is empty.  */
      do
	{
	  changed = 0;
	  passes++;
	  EXECUTE_IF_SET_IN_SBITMAP (worklist, 0, b,
	    {
	      RESET_BIT (worklist, b);
	      /* For each block on the worklist, add to the IDF all
		 blocks on its dominance frontier that aren't already
		 on the IDF.  Every block that's added is also added
		 to the worklist.  */
	      sbitmap_union_of_diff (worklist, worklist, frontiers[b], idf);
	      sbitmap_a_or_b (idf, idf, frontiers[b]);
	      changed = 1;
	    });
	}
      while (changed);
    }

  sbitmap_free (worklist);

  if (rtl_dump_file)
    {
      fprintf(rtl_dump_file,
	      "Iterated dominance frontier: %d passes on %d regs.\n",
	      passes, nregs);
    }
}


/* Insert the phi nodes.  */

static void
insert_phi_node (regno, bb)
     int regno, bb;
{
  basic_block b = BASIC_BLOCK (bb);
  edge e;
  int npred, i;
  rtvec vec;
  rtx phi, reg;

  /* Find out how many predecessors there are.  */
  for (e = b->pred, npred = 0; e; e = e->pred_next)
    if (e->src != ENTRY_BLOCK_PTR)
      npred++;

  /* If this block has no "interesting" preds, then there is nothing to
     do.  Consider a block that only has the entry block as a pred.  */
  if (npred == 0)
    return;

  /* This is the register to which the phi function will be assinged.  */
  reg = regno_reg_rtx[regno + FIRST_PSEUDO_REGISTER];

  /* Construct the arguments to the PHI node.  The use of pc_rtx is just
     a placeholder; we'll insert the proper value in rename_registers.  */
  vec = rtvec_alloc (npred * 2);
  for (e = b->pred, i = 0; e ; e = e->pred_next, i += 2)
    if (e->src != ENTRY_BLOCK_PTR)
      {
	RTVEC_ELT (vec, i + 0) = pc_rtx;
	RTVEC_ELT (vec, i + 1) = GEN_INT (e->src->index);
      }

  phi = gen_rtx_PHI (VOIDmode, vec);
  phi = gen_rtx_SET (VOIDmode, reg, phi);

  if (GET_CODE (b->head) == CODE_LABEL)
    emit_insn_after (phi, b->head);
  else
    b->head = emit_insn_before (phi, b->head);
}


static void
insert_phi_nodes (idfs, evals, nregs)
     sbitmap *idfs;
     sbitmap *evals ATTRIBUTE_UNUSED;
     int nregs;
{
  int reg;

  for (reg = 0; reg < nregs; ++reg)
    {
      int b;
      EXECUTE_IF_SET_IN_SBITMAP (idfs[reg], 0, b,
	{
	  if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, 
			       reg + FIRST_PSEUDO_REGISTER))
	    insert_phi_node (reg, b);
	});
    }
}

/* Rename the registers to conform to SSA. 

   This is essentially the algorithm presented in Figure 7.8 of Morgan,
   with a few changes to reduce pattern search time in favour of a bit
   more memory usage.  */


/* One of these is created for each set.  It will live in a list local
   to its basic block for the duration of that block's processing.  */
struct rename_set_data
{
  struct rename_set_data *next;
  rtx *reg_loc;
  rtx set_dest;
  rtx new_reg;
  rtx prev_reg;
  rtx set_insn;
};

/* This struct is used to pass information to callback functions while
   renaming registers.  */
struct rename_context
{
  struct rename_set_data *set_data;
  rtx current_insn;
};

static void new_registers_for_updates 
  PARAMS ((struct rename_set_data *set_data,
	   struct rename_set_data *old_set_data, rtx insn));

/* This is part of a rather ugly hack to allow the pre-ssa regno to be
   reused.  If, during processing, a register has not yet been touched,
   ssa_rename_to[regno] will be NULL.  Now, in the course of pushing
   and popping values from ssa_rename_to, when we would ordinarily 
   pop NULL back in, we pop RENAME_NO_RTX.  We treat this exactly the
   same as NULL, except that it signals that the original regno has
   already been reused.  */
#define RENAME_NO_RTX  pc_rtx

/* Part one of the first step of rename_block, called through for_each_rtx. 
   Mark pseudos that are set for later update.  Transform uses of pseudos.  */

static int
rename_insn_1 (ptr, data)
     rtx *ptr;
     void *data;
{
  rtx x = *ptr;
  struct rename_context *context = data;
  struct rename_set_data **set_datap = &(context->set_data);

  if (x == NULL_RTX)
    return 0;

  switch (GET_CODE (x))
    {
    case SET:
      {
	rtx *destp = &SET_DEST (x);
	rtx dest = SET_DEST (x);

	/* Subregs at word 0 are interesting.  Subregs at word != 0 are
	   presumed to be part of a contiguous multi-word set sequence.  */
	while (GET_CODE (dest) == SUBREG
	       && SUBREG_WORD (dest) == 0)
	  {
	    destp = &SUBREG_REG (dest);
	    dest = SUBREG_REG (dest);
	  }

	if (GET_CODE (dest) == REG
	    && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
	  {
	    /* We found a genuine set of an interesting register.  Tag
	       it so that we can create a new name for it after we finish
	       processing this insn.  */

	    struct rename_set_data *r;
	    r = (struct rename_set_data *) xmalloc (sizeof(*r));

	    r->reg_loc = destp;
	    r->set_dest = SET_DEST (x);
	    r->set_insn = context->current_insn;
	    r->next = *set_datap;
	    *set_datap = r;

	    /* Since we do not wish to (directly) traverse the
	       SET_DEST, recurse through for_each_rtx for the SET_SRC
	       and return.  */
	    for_each_rtx (&SET_SRC (x), rename_insn_1, data);
	    return -1;
	  }

	/* Otherwise, this was not an interesting destination.  Continue
	   on, marking uses as normal.  */
	return 0;
      }

    case REG:
      if (REGNO (x) >= FIRST_PSEUDO_REGISTER
	  && REGNO (x) < ssa_max_reg_num)
	{
	  rtx new_reg = ssa_rename_to[REGNO(x) - FIRST_PSEUDO_REGISTER];

	  if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX)
	    {
	      if (GET_MODE (x) != GET_MODE (new_reg))
		abort ();
	      *ptr = new_reg;
	    }
	  /* Else this is a use before a set.  Warn?  */
	}
      return -1;

    case PHI:
      /* Never muck with the phi.  We do that elsewhere, special-like.  */
      return -1;

    default:
      /* Anything else, continue traversing.  */
      return 0;
    }
}

/* Second part of the first step of rename_block.  The portion of the list
   beginning at SET_DATA through OLD_SET_DATA contain the sets present in
   INSN.  Update data structures accordingly.  */

static void
new_registers_for_updates (set_data, old_set_data, insn)
     struct rename_set_data *set_data, *old_set_data;
     rtx insn;
{
  while (set_data != old_set_data)
    {
      int regno, new_regno;
      rtx old_reg, new_reg, prev_reg;

      old_reg = *set_data->reg_loc;
      regno = REGNO (*set_data->reg_loc);

      /* For the first set we come across, reuse the original regno.  */
      if (ssa_rename_to[regno - FIRST_PSEUDO_REGISTER] == NULL_RTX)
	{
	  new_reg = old_reg;
	  prev_reg = RENAME_NO_RTX;
	}
      else
	{
	  prev_reg = ssa_rename_to[regno - FIRST_PSEUDO_REGISTER];
	  new_reg = gen_reg_rtx (GET_MODE (old_reg));
	}

      set_data->new_reg = new_reg;
      set_data->prev_reg = prev_reg;
      new_regno = REGNO (new_reg);
      ssa_rename_to[regno - FIRST_PSEUDO_REGISTER] = new_reg;

      if (new_regno >= (int) ssa_definition->num_elements)
	{
	  int new_limit = new_regno * 5 / 4;
	  ssa_definition = VARRAY_GROW (ssa_definition, new_limit);
	  ssa_uses = VARRAY_GROW (ssa_uses, new_limit);
	  ssa_rename_from = VARRAY_GROW (ssa_rename_from, new_limit);
	}

      VARRAY_RTX (ssa_definition, new_regno) = insn;
      VARRAY_RTX (ssa_rename_from, new_regno) = old_reg;

      set_data = set_data->next;
    }
}

static void
rename_block (bb, idom)
     int bb;
     int *idom;
{
  basic_block b = BASIC_BLOCK (bb);
  edge e;
  rtx insn, next, last;
  struct rename_set_data *set_data = NULL;
  int c;

  /* Step One: Walk the basic block, adding new names for sets and
     replacing uses.  */
     
  next = b->head;
  last = b->end;
  do
    {
      insn = next;
      if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
	{
	  struct rename_context context;
	  context.set_data = set_data;
	  context.current_insn = insn;

	  for_each_rtx (&PATTERN (insn), rename_insn_1, &context);
	  for_each_rtx (&REG_NOTES (insn), rename_insn_1, &context);
	  
	  new_registers_for_updates (context.set_data, set_data, insn);
	  set_data = context.set_data;
	}

      next = NEXT_INSN (insn);
    }
  while (insn != last);

  /* Step Two: Update the phi nodes of this block's successors.  */

  for (e = b->succ; e; e = e->succ_next)
    {
      if (e->dest == EXIT_BLOCK_PTR)
	continue;

      insn = e->dest->head;
      if (GET_CODE (insn) == CODE_LABEL)
	insn = NEXT_INSN (insn);

      while (PHI_NODE_P (insn))
	{
	  rtx phi = PATTERN (insn);
	  unsigned int regno;
	  rtx reg;

	  /* Find out which of our outgoing registers this node is
	     indended to replace.  Note that if this not the first PHI
	     node to have been created for this register, we have to
	     jump through rename links to figure out which register
	     we're talking about.  This can easily be recognized by
	     noting that the regno is new to this pass.  */
	  regno = REGNO (SET_DEST (phi));
	  if (regno >= ssa_max_reg_num)
	    regno = REGNO (VARRAY_RTX (ssa_rename_from, regno));
	  reg = ssa_rename_to[regno - FIRST_PSEUDO_REGISTER];

	  /* It is possible for the variable to be uninitialized on
	     edges in.  Reduce the arity of the PHI so that we don't
	     consider those edges.  */
	  if (reg == NULL || reg == RENAME_NO_RTX)
	    {
	      if (! remove_phi_alternative (phi, bb))
		abort ();
	    }
	  else
	    {
	      /* When we created the PHI nodes, we did not know what mode
	     the register should be.  Now that we've found an original,
	     we can fill that in.  */
	      if (GET_MODE (SET_DEST (phi)) == VOIDmode)
		PUT_MODE (SET_DEST (phi), GET_MODE (reg));
	      else if (GET_MODE (SET_DEST (phi)) != GET_MODE (reg))
		abort();

	      *phi_alternative (phi, bb) = reg;
	      /* ??? Mark for a new ssa_uses entry.  */
	    }

	  insn = NEXT_INSN (insn);
	}
    }

  /* Step Three: Do the same to the children of this block in
     dominator order.  */

  for (c = 0; c < n_basic_blocks; ++c)
    if (idom[c] == bb)
      rename_block (c, idom);

  /* Step Four: Update the sets to refer to their new register.  */

  while (set_data)
    {
      struct rename_set_data *next;
      rtx old_reg = *set_data->reg_loc;

      /* If the set is of a subreg only, copy the entire reg first so
	 that unmodified bits are preserved.  Of course, we don't
	 strictly have SSA any more, but that's the best we can do
	 without a lot of hard work.  */

      if (GET_CODE (set_data->set_dest) == SUBREG) 
	{
	  if (old_reg != set_data->new_reg)
	    {
	      rtx copy = gen_rtx_SET (GET_MODE (old_reg), 
				      set_data->new_reg, old_reg);
	      emit_insn_before (copy, set_data->set_insn);
	    }
	}

      *set_data->reg_loc = set_data->new_reg;
      ssa_rename_to[REGNO (old_reg)-FIRST_PSEUDO_REGISTER]
	= set_data->prev_reg;

      next = set_data->next;
      free (set_data);
      set_data = next;
    }      
}

static void
rename_registers (nregs, idom)
     int nregs;
     int *idom;
{
  VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
  VARRAY_RTX_INIT (ssa_uses, nregs * 3, "ssa_uses");
  VARRAY_RTX_INIT (ssa_rename_from, nregs * 3, "ssa_rename_from");

  ssa_rename_to = (rtx *) alloca (nregs * sizeof(rtx));
  bzero ((char *) ssa_rename_to, nregs * sizeof(rtx));

  rename_block (0, idom);

  /* ??? Update basic_block_live_at_start, and other flow info 
     as needed.  */

  ssa_rename_to = NULL;
}


/* The main entry point for moving to SSA.  */

void
convert_to_ssa()
{
  /* Element I is the set of blocks that set register I.  */
  sbitmap *evals;

  /* Dominator bitmaps.  */
  sbitmap *dominators;
  sbitmap *dfs;
  sbitmap *idfs;

  /* Element I is the immediate dominator of block I.  */
  int *idom;

  int nregs;

  /* Don't do it twice.  */
  if (in_ssa_form)
    abort ();

  /* Need global_live_at_{start,end} up to date.  */
  life_analysis (get_insns (), NULL, PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE);

  /* Compute dominators.  */
  dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
  compute_flow_dominators (dominators, NULL);

  idom = (int *) alloca (n_basic_blocks * sizeof (int));
  memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int));
  simplify_to_immediate_dominators (idom, dominators);

  sbitmap_vector_free (dominators);

  if (rtl_dump_file)
    {
      int i;
      fputs (";; Immediate Dominators:\n", rtl_dump_file);
      for (i = 0; i < n_basic_blocks; ++i)
	fprintf (rtl_dump_file, ";\t%3d = %3d\n", i, idom[i]);
      fflush (rtl_dump_file);
    }

  /* Compute dominance frontiers.  */

  dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
  compute_dominance_frontiers (dfs, idom);

  if (rtl_dump_file)
    {
      dump_sbitmap_vector (rtl_dump_file, ";; Dominance Frontiers:",
			   "; Basic Block", dfs, n_basic_blocks);
      fflush (rtl_dump_file);
    }

  /* Compute register evaluations.  */

  ssa_max_reg_num = max_reg_num();
  nregs = ssa_max_reg_num - FIRST_PSEUDO_REGISTER;
  evals = sbitmap_vector_alloc (nregs, n_basic_blocks);
  find_evaluations (evals, nregs);

  /* Compute the iterated dominance frontier for each register.  */

  idfs = sbitmap_vector_alloc (nregs, n_basic_blocks);
  compute_iterated_dominance_frontiers (idfs, dfs, evals, nregs);

  if (rtl_dump_file)
    {
      dump_sbitmap_vector (rtl_dump_file, ";; Iterated Dominance Frontiers:",
			   "; Register-FIRST_PSEUDO_REGISTER", idfs, nregs);
      fflush (rtl_dump_file);
    }

  /* Insert the phi nodes.  */

  insert_phi_nodes (idfs, evals, nregs);

  /* Rename the registers to satisfy SSA.  */

  rename_registers (nregs, idom);

  /* All done!  Clean up and go home.  */

  sbitmap_vector_free (dfs);
  sbitmap_vector_free (evals);
  sbitmap_vector_free (idfs);
  in_ssa_form = 1;

  reg_scan (get_insns (), max_reg_num (), 1);
}


/* REG is the representative temporary of its partition.  Add it to the
   set of nodes to be processed, if it hasn't been already.  Return the
   index of this register in the node set.  */

static inline int
ephi_add_node (reg, nodes, n_nodes)
     rtx reg, *nodes;
     int *n_nodes;
{
  int i;
  for (i = *n_nodes - 1; i >= 0; --i)
    if (REGNO (reg) == REGNO (nodes[i]))
      return i;

  nodes[i = (*n_nodes)++] = reg;
  return i;
}

/* Part one of the topological sort.  This is a forward (downward) search
   through the graph collecting a stack of nodes to process.  Assuming no
   cycles, the nodes at top of the stack when we are finished will have
   no other dependancies.  */

static int *
ephi_forward (t, visited, succ, tstack)
     int t;
     sbitmap visited;
     sbitmap *succ;
     int *tstack;
{
  int s;

  SET_BIT (visited, t);

  EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
    {
      if (! TEST_BIT (visited, s))
        tstack = ephi_forward (s, visited, succ, tstack);
    });

  *tstack++ = t;
  return tstack;
}

/* Part two of the topological sort.  The is a backward search through
   a cycle in the graph, copying the data forward as we go.  */

static void
ephi_backward (t, visited, pred, nodes)
     int t;
     sbitmap visited, *pred;
     rtx *nodes;
{
  int p;

  SET_BIT (visited, t);

  EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
    {
      if (! TEST_BIT (visited, p))
	{
	  ephi_backward (p, visited, pred, nodes);
	  emit_move_insn (nodes[p], nodes[t]);
	}
    });
}

/* Part two of the topological sort.  Create the copy for a register
   and any cycle of which it is a member.  */

static void
ephi_create (t, visited, pred, succ, nodes)
     int t;
     sbitmap visited, *pred, *succ;
     rtx *nodes;
{
  rtx reg_u = NULL_RTX;
  int unvisited_predecessors = 0;
  int p;

  /* Iterate through the predecessor list looking for unvisited nodes.
     If there are any, we have a cycle, and must deal with that.  At 
     the same time, look for a visited predecessor.  If there is one,
     we won't need to create a temporary.  */

  EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
    {
      if (! TEST_BIT (visited, p))
	unvisited_predecessors = 1;
      else if (!reg_u)
	reg_u = nodes[p];
    });

  if (unvisited_predecessors)
    {
      /* We found a cycle.  Copy out one element of the ring (if necessary),
	 then traverse the ring copying as we go.  */

      if (!reg_u)
	{
	  reg_u = gen_reg_rtx (GET_MODE (nodes[t]));
	  emit_move_insn (reg_u, nodes[t]);
	}

      EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
	{
	  if (! TEST_BIT (visited, p))
	    {
	      ephi_backward (p, visited, pred, nodes);
	      emit_move_insn (nodes[p], reg_u);
	    }
	});
    }  
  else 
    {
      /* No cycle.  Just copy the value from a successor.  */

      int s;
      EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
	{
	  SET_BIT (visited, t);
	  emit_move_insn (nodes[t], nodes[s]);
	  return;
	});
    }
}

/* Convert the edge to normal form.  */

static void
eliminate_phi (e, reg_partition)
     edge e;
     partition reg_partition;
{
  int n_nodes;
  sbitmap *pred, *succ;
  sbitmap visited;
  rtx *nodes;
  int *stack, *tstack;
  rtx insn;
  int i;

  /* Collect an upper bound on the number of registers needing processing.  */

  insn = e->dest->head;
  if (GET_CODE (insn) == CODE_LABEL)
    insn = next_nonnote_insn (insn);

  n_nodes = 0;
  while (PHI_NODE_P (insn))
    {
      insn = next_nonnote_insn (insn);
      n_nodes += 2;
    }

  if (n_nodes == 0)
    return;

  /* Build the auxilliary graph R(B). 

     The nodes of the graph are the members of the register partition
     present in Phi(B).  There is an edge from FIND(T0)->FIND(T1) for
     each T0 = PHI(...,T1,...), where T1 is for the edge from block C.  */

  nodes = (rtx *) alloca (n_nodes * sizeof(rtx));
  pred = sbitmap_vector_alloc (n_nodes, n_nodes);
  succ = sbitmap_vector_alloc (n_nodes, n_nodes);
  sbitmap_vector_zero (pred, n_nodes);
  sbitmap_vector_zero (succ, n_nodes);

  insn = e->dest->head;
  if (GET_CODE (insn) == CODE_LABEL)
    insn = next_nonnote_insn (insn);

  n_nodes = 0;
  for (; PHI_NODE_P (insn); insn = next_nonnote_insn (insn))
    {
      rtx* preg = phi_alternative (PATTERN (insn), e->src->index);
      rtx tgt = SET_DEST (PATTERN (insn));
      rtx reg;

      /* There may be no phi alternative corresponding to this edge.
	 This indicates that the phi variable is undefined along this
	 edge.  */
      if (preg == NULL)
	continue;
      reg = *preg;

      if (GET_CODE (reg) != REG || GET_CODE (tgt) != REG)
	abort();

      reg = regno_reg_rtx[partition_find (reg_partition, REGNO (reg))];
      tgt = regno_reg_rtx[partition_find (reg_partition, REGNO (tgt))];
      /* If the two registers are already in the same partition, 
	 nothing will need to be done.  */
      if (reg != tgt)
	{
	  int ireg, itgt;

	  ireg = ephi_add_node (reg, nodes, &n_nodes);
	  itgt = ephi_add_node (tgt, nodes, &n_nodes);

	  SET_BIT (pred[ireg], itgt);
	  SET_BIT (succ[itgt], ireg);
	}
    }

  if (n_nodes == 0)
    goto out;

  /* Begin a topological sort of the graph.  */

  visited = sbitmap_alloc (n_nodes);
  sbitmap_zero (visited);

  tstack = stack = (int *) alloca (n_nodes * sizeof (int));

  for (i = 0; i < n_nodes; ++i)
    if (! TEST_BIT (visited, i))
      tstack = ephi_forward (i, visited, succ, tstack);

  sbitmap_zero (visited);

  /* As we find a solution to the tsort, collect the implementation 
     insns in a sequence.  */
  start_sequence ();
  
  while (tstack != stack)
    {
      i = *--tstack;
      if (! TEST_BIT (visited, i))
	ephi_create (i, visited, pred, succ, nodes);
    }

  insn = gen_sequence ();
  end_sequence ();
  insert_insn_on_edge (insn, e);
  if (rtl_dump_file)
    fprintf (rtl_dump_file, "Emitting copy on edge (%d,%d)\n",
	     e->src->index, e->dest->index);

  sbitmap_free (visited);
out:
  sbitmap_vector_free (pred);
  sbitmap_vector_free (succ);
}


/* For basic block B, consider all phi insns which provide an
   alternative corresponding to an incoming abnormal critical edge.
   Place the phi alternative corresponding to that abnormal critical
   edge in the same register class as the destination of the set.  

   From Morgan, p. 178:

     For each abnormal critical edge (C, B), 
     if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B, 
     and C is the ith predecessor of B, 
     then T0 and Ti must be equivalent. 

   Return non-zero iff any such cases were found for which the two
   regs were not already in the same class.  */

static int
make_regs_equivalent_over_bad_edges (bb, reg_partition)
     int bb;
     partition reg_partition;
{
  int changed = 0;
  basic_block b = BASIC_BLOCK (bb);
  rtx phi = b->head;

  /* Advance to the first phi node.  */
  if (GET_CODE (phi) == CODE_LABEL)
    phi = next_nonnote_insn (phi);

  /* Scan all the phi nodes.  */
  for (; 
       PHI_NODE_P (phi);
       phi = next_nonnote_insn (phi))
    {
      edge e;
      int tgt_regno;
      rtx set = PATTERN (phi);
      rtx tgt = SET_DEST (set);

      /* The set target is expected to be a pseudo.  */
      if (GET_CODE (tgt) != REG 
	  || REGNO (tgt) < FIRST_PSEUDO_REGISTER)
	abort ();
      tgt_regno = REGNO (tgt);

      /* Scan incoming abnormal critical edges.  */
      for (e = b->pred; e; e = e->pred_next)
	if ((e->flags & (EDGE_ABNORMAL | EDGE_CRITICAL)) 
		== (EDGE_ABNORMAL | EDGE_CRITICAL))
	  {
	    rtx *alt = phi_alternative (set, e->src->index);
	    int alt_regno;

	    /* If there is no alternative corresponding to this edge,
	       the value is undefined along the edge, so just go on.  */
	    if (alt == 0)
	      continue;

	    /* The phi alternative is expected to be a pseudo.  */
	    if (GET_CODE (*alt) != REG 
		|| REGNO (*alt) < FIRST_PSEUDO_REGISTER)
	      abort ();
	    alt_regno = REGNO (*alt);

	    /* If the set destination and the phi alternative aren't
	       already in the same class...  */
	    if (partition_find (reg_partition, tgt_regno) 
		!= partition_find (reg_partition, alt_regno))
	      {
		/* ... make them such.  */
		partition_union (reg_partition, 
				 tgt_regno, alt_regno);
		++changed;
	      }
	  }
    }

  return changed;
}


/* Consider phi insns in basic block BB pairwise.  If the set target
   of both isns are equivalent pseudos, make the corresponding phi
   alternatives in each phi corresponding equivalent.

   Return nonzero if any new register classes were unioned.  */

static int
make_equivalent_phi_alternatives_equivalent (bb, reg_partition)
     int bb;
     partition reg_partition;
{
  int changed = 0;
  rtx phi = BLOCK_HEAD (bb);
  basic_block b = BASIC_BLOCK (bb);

  /* Advance to the first phi node.  */
  if (GET_CODE (phi) == CODE_LABEL)
    phi = next_nonnote_insn (phi);

  /* Scan all the phi nodes.  */
  for (; 
       PHI_NODE_P (phi);
       phi = next_nonnote_insn (phi))
    {
      rtx set = PATTERN (phi);
      /* The regno of the destination of the set.  */
      int tgt_regno = REGNO (SET_DEST (PATTERN (phi)));

      rtx phi2 = next_nonnote_insn (phi);

      /* Scan all phi nodes following this one.  */
      for (;
	   PHI_NODE_P (phi2);
	   phi2 = next_nonnote_insn (phi2))
	{
	  rtx set2 = PATTERN (phi2);
	  /* The regno of the destination of the set.  */
	  int tgt2_regno = REGNO (SET_DEST (set2));
		  
	  /* Are the set destinations equivalent regs?  */
	  if (partition_find (reg_partition, tgt_regno) ==
	      partition_find (reg_partition, tgt2_regno))
	    {
	      edge e;
	      /* Scan over edges.  */
	      for (e = b->pred; e; e = e->pred_next)
		{
		  int pred_block = e->src->index;
		  /* Identify the phi altnernatives from both phi
		     nodes corresponding to this edge.  */
		  rtx *alt = phi_alternative (set, pred_block);
		  rtx *alt2 = phi_alternative (set2, pred_block);

		  /* If one of the phi nodes doesn't have a
		     corresponding alternative, just skip it.  */
		  if (alt == 0 || alt2 == 0)
		    continue;

		  /* Both alternatives should be pseudos.  */
		  if (GET_CODE (*alt) != REG
		      || REGNO (*alt) < FIRST_PSEUDO_REGISTER)
		    abort ();
		  if (GET_CODE (*alt2) != REG
		      || REGNO (*alt2) < FIRST_PSEUDO_REGISTER)
		    abort ();

		  /* If the altneratives aren't already in the same
		     class ... */
		  if (partition_find (reg_partition, REGNO (*alt)) 
		      != partition_find (reg_partition, REGNO (*alt2)))
		    {
		      /* ... make them so.  */
		      partition_union (reg_partition, 
				       REGNO (*alt), REGNO (*alt2));
		      ++changed;
		    }
		}
	    }
	}
    }

  return changed;
}

/* Compute a conservative partition of outstanding pseudo registers.
   See Morgan 7.3.1.  */

static partition
compute_conservative_reg_partition ()
{
  int bb;
  int changed = 0;

  /* We don't actually work with hard registers, but it's easier to
     carry them around anyway rather than constantly doing register
     number arithmetic.  */
  partition p = 
    partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER);

  /* The first priority is to make sure registers that might have to
     be copied on abnormal critical edges are placed in the same
     partition.  This saves us from having to split abnormal critical
     edges.  */
  for (bb = n_basic_blocks; --bb >= 0; )
    changed += make_regs_equivalent_over_bad_edges (bb, p);
  
  /* Now we have to insure that corresponding arguments of phi nodes
     assigning to corresponding regs are equivalent.  Iterate until
     nothing changes.  */
  while (changed > 0)
    {
      changed = 0;
      for (bb = n_basic_blocks; --bb >= 0; )
	changed += make_equivalent_phi_alternatives_equivalent (bb, p);
    }

  return p;
}

/* The following functions compute a register partition that attempts
   to eliminate as many reg copies and phi node copies as possible by
   coalescing registers.   This is the strategy:

    1. As in the conservative case, the top priority is to coalesce
       registers that otherwise would cause copies to be placed on
       abnormal critical edges (which isn't possible).

    2. Figure out which regs are involved (in the LHS or RHS) of
       copies and phi nodes.  Compute conflicts among these regs.  

    3. Walk around the instruction stream, placing two regs in the
       same class of the partition if one appears on the LHS and the
       other on the RHS of a copy or phi node and the two regs don't
       conflict.  The conflict information of course needs to be
       updated.  

    4. If anything has changed, there may be new opportunities to
       coalesce regs, so go back to 2.
*/

/* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
   same class of partition P, if they aren't already.  Update
   CONFLICTS appropriately.  

   Returns one if REG1 and REG2 were placed in the same class but were
   not previously; zero otherwise.  

   See Morgan figure 11.15.  */

static int 
coalesce_if_unconflicting (p, conflicts, reg1, reg2)
     partition p;
     conflict_graph conflicts;
     int reg1;
     int reg2;
{
  int reg;

  /* Don't mess with hard regs.  */
  if (reg1 < FIRST_PSEUDO_REGISTER || reg2 < FIRST_PSEUDO_REGISTER)
    return 0;

  /* Find the canonical regs for the classes containing REG1 and
     REG2.  */
  reg1 = partition_find (p, reg1);
  reg2 = partition_find (p, reg2);
  
  /* If they're already in the same class, there's nothing to do.  */
  if (reg1 == reg2)
    return 0;

  /* If the regs conflict, our hands are tied.  */
  if (conflict_graph_conflict_p (conflicts, reg1, reg2))
    return 0;

  /* We're good to go.  Put the regs in the same partition.  */
  partition_union (p, reg1, reg2);

  /* Find the new canonical reg for the merged class.  */
  reg = partition_find (p, reg1);
  
  /* Merge conflicts from the two previous classes.  */
  conflict_graph_merge_regs (conflicts, reg, reg1);
  conflict_graph_merge_regs (conflicts, reg, reg2);

  return 1;
}

/* For each register copy insn in basic block BB, place the LHS and
   RHS regs in the same class in partition P if they do not conflict
   according to CONFLICTS.

   Returns the number of changes that were made to P.

   See Morgan figure 11.14.  */

static int
coalesce_regs_in_copies (bb, p, conflicts)
     basic_block bb;
     partition p;
     conflict_graph conflicts;
{
  int changed = 0;
  rtx insn;
  rtx end = bb->end;

  /* Scan the instruction stream of the block.  */
  for (insn = bb->head; insn != end; insn = NEXT_INSN (insn))
    {
      rtx pattern;
      rtx src;
      rtx dest;

      /* If this isn't a set insn, go to the next insn.  */
      if (GET_CODE (insn) != INSN)
	continue;
      pattern = PATTERN (insn);
      if (GET_CODE (pattern) != SET)
	continue;

      src = SET_SRC (pattern);
      dest = SET_DEST (pattern);

      /* If src or dest are subregs, find the underlying reg.  */
      while (GET_CODE (src) == SUBREG
	     && SUBREG_WORD (src) != 0)
	src = SUBREG_REG (src);
      while (GET_CODE (dest) == SUBREG
	     && SUBREG_WORD (dest) != 0)
	dest = SUBREG_REG (dest);

      /* We're only looking for copies.  */
      if (GET_CODE (src) != REG || GET_CODE (dest) != REG)
	continue;

      /* Coalesce only if the reg modes are the same.  As long as
	 each reg's rtx is unique, it can have only one mode, so two
	 pseudos of different modes can't be coalesced into one.  

         FIXME: We can probably get around this by inserting SUBREGs
         where appropriate, but for now we don't bother.  */
      if (GET_MODE (src) != GET_MODE (dest))
	continue;

      /* Found a copy; see if we can use the same reg for both the
	 source and destination (and thus eliminate the copy,
	 ultimately).  */
      changed += coalesce_if_unconflicting (p, conflicts, 
					    REGNO (src), REGNO (dest));
    }

  return changed;
}


struct phi_coalesce_context
{
  partition p;
  conflict_graph conflicts;
  int changed;
};

/* Callback function for for_each_successor_phi.  If the set
   destination and the phi alternative regs do not conflict, place
   them in the same paritition class.  DATA is a pointer to a
   phi_coalesce_context struct.  */

static int
coalesce_reg_in_phi (insn, dest_regno, src_regno, data)
     rtx insn ATTRIBUTE_UNUSED;
     int dest_regno;
     int src_regno;
     void *data;
{
  struct phi_coalesce_context *context = 
    (struct phi_coalesce_context *) data;
  
  /* Attempt to use the same reg, if they don't conflict.  */
  context->changed 
    += coalesce_if_unconflicting (context->p, context->conflicts, 
				  dest_regno, src_regno);
  return 0;
}

/* For each alternative in a phi function corresponding to basic block
   BB (in phi nodes in successor block to BB), place the reg in the
   phi alternative and the reg to which the phi value is set into the
   same class in partition P, if allowed by CONFLICTS.  

   Return the number of changes that were made to P.
   
   See Morgan figure 11.14.  */

static int
coalesce_regs_in_successor_phi_nodes (bb, p, conflicts)
     basic_block bb;
     partition p;
     conflict_graph conflicts;
{
  struct phi_coalesce_context context;
  context.p = p;
  context.conflicts = conflicts;
  context.changed = 0;

  for_each_successor_phi (bb, &coalesce_reg_in_phi, &context);

  return context.changed;
}

/* Compute and return a partition of pseudos.  Where possible,
   non-conflicting pseudos are placed in the same class.  

   The caller is responsible for deallocating the returned partition.  */

static partition
compute_coalesced_reg_partition ()
{
  int bb;
  int changed = 0;

  /* We don't actually work with hard registers, but it's easier to
     carry them around anyway rather than constantly doing register
     number arithmetic.  */
  partition p = 
    partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER);

  /* The first priority is to make sure registers that might have to
     be copied on abnormal critical edges are placed in the same
     partition.  This saves us from having to split abnormal critical
     edges (which can't be done).  */
  for (bb = n_basic_blocks; --bb >= 0; )
    make_regs_equivalent_over_bad_edges (bb, p);

  do
    {
      regset_head phi_set;
      conflict_graph conflicts;

      changed = 0;

      /* Build the set of registers involved in phi nodes, either as
	 arguments to the phi function or as the target of a set.  */
      INITIALIZE_REG_SET (phi_set);
      mark_phi_and_copy_regs (&phi_set);

      /* Compute conflicts.  */
      conflicts = conflict_graph_compute (&phi_set, p);

      /* FIXME: Better would be to process most frequently executed
	 blocks first, so that most frequently executed copies would
	 be more likely to be removed by register coalescing.  But any
	 order will generate correct, if non-optimal, results.  */
      for (bb = n_basic_blocks; --bb >= 0; )
	{
	  basic_block block = BASIC_BLOCK (bb);
	  changed += coalesce_regs_in_copies (block, p, conflicts);
	  changed += 
	    coalesce_regs_in_successor_phi_nodes (block, p, conflicts);
	}

      conflict_graph_delete (conflicts);
    }
  while (changed > 0);

  return p;
}

/* Mark the regs in a phi node.  PTR is a phi expression or one of its
   components (a REG or a CONST_INT).  DATA is a reg set in which to
   set all regs.  Called from for_each_rtx.  */

static int
mark_reg_in_phi (ptr, data)
     rtx *ptr;
     void *data;
{
  rtx expr = *ptr;
  regset set = (regset) data;

  switch (GET_CODE (expr))
    {
    case REG:
      SET_REGNO_REG_SET (set, REGNO (expr));
      /* Fall through.  */
    case CONST_INT:
    case PHI:
      return 0;
    default:
      abort ();
    }
}

/* Mark in PHI_SET all pseudos that are used in a phi node -- either
   set from a phi expression, or used as an argument in one.  Also
   mark regs that are the source or target of a reg copy.  Uses
   ssa_definition.  */

static void
mark_phi_and_copy_regs (phi_set)
     regset phi_set;
{
  int reg;

  /* Scan the definitions of all regs.  */
  for (reg = VARRAY_SIZE (ssa_definition); 
       --reg >= FIRST_PSEUDO_REGISTER; 
       ) 
    {
      rtx insn = VARRAY_RTX (ssa_definition, reg);
      rtx pattern;
      rtx src;

      if (insn == NULL)
	continue;
      pattern = PATTERN (insn);
      /* Sometimes we get PARALLEL insns.  These aren't phi nodes or
	 copies.  */
      if (GET_CODE (pattern) != SET)
	continue;
      src = SET_SRC (pattern);

      if (GET_CODE (src) == REG)
	{
	  /* It's a reg copy.  */
	  SET_REGNO_REG_SET (phi_set, reg);
	  SET_REGNO_REG_SET (phi_set, REGNO (src));
	}
      else if (GET_CODE (src) == PHI)
	{
	  /* It's a phi node.  Mark the reg being set.  */
	  SET_REGNO_REG_SET (phi_set, reg);
	  /* Mark the regs used in the phi function.  */
	  for_each_rtx (&src, mark_reg_in_phi, phi_set);
	}
      /* ... else nothing to do.  */
    }
}

/* Rename regs in insn PTR that are equivalent.  DATA is the register
   partition which specifies equivalences.  */

static int
rename_equivalent_regs_in_insn (ptr, data)
     rtx *ptr;
     void* data;
{
  rtx x = *ptr;
  partition reg_partition = (partition) data;

  if (x == NULL_RTX)
    return 0;

  switch (GET_CODE (x))
    {
    case SET:
      {
	rtx *destp = &SET_DEST (x);
	rtx dest = SET_DEST (x);

	/* Subregs at word 0 are interesting.  Subregs at word != 0 are
	   presumed to be part of a contiguous multi-word set sequence.  */
	while (GET_CODE (dest) == SUBREG
	       && SUBREG_WORD (dest) == 0)
	  {
	    destp = &SUBREG_REG (dest);
	    dest = SUBREG_REG (dest);
	  }

	if (GET_CODE (dest) == REG
	    && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
	  {
	    /* Got a pseudo; replace it.  */
	    int regno = REGNO (dest);
	    int new_regno = partition_find (reg_partition, regno);
	    if (regno != new_regno)
	      *destp = regno_reg_rtx[new_regno];

	    for_each_rtx (&SET_SRC (x), 
			  rename_equivalent_regs_in_insn, 
			  data);
	    return -1;
	  }

	/* Otherwise, this was not an interesting destination.  Continue
	   on, marking uses as normal.  */
	return 0;
      }

    case REG:
      if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
	{
	  int regno = REGNO (x);
	  int new_regno = partition_find (reg_partition, regno);
	  if (regno != new_regno)
	    {
	      rtx new_reg = regno_reg_rtx[new_regno];
	      if (GET_MODE (x) != GET_MODE (new_reg))
		abort ();
	      *ptr = new_reg;
	    }
	}
      return -1;

    case PHI:
      /* No need to rename the phi nodes.  We'll check equivalence
	 when inserting copies.  */
      return -1;

    default:
      /* Anything else, continue traversing.  */
      return 0;
    }
}

/* Rename regs that are equivalent in REG_PARTITION.  */

static void
rename_equivalent_regs (reg_partition)
     partition reg_partition;
{
  int bb;

  for (bb = n_basic_blocks; --bb >= 0; )
    {
      basic_block b = BASIC_BLOCK (bb);
      rtx next = b->head;
      rtx last = b->end;
      rtx insn;

      do
	{
	  insn = next;
	  if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
	    {
	      for_each_rtx (&PATTERN (insn), 
			    rename_equivalent_regs_in_insn, 
			    reg_partition);
	      for_each_rtx (&REG_NOTES (insn), 
			    rename_equivalent_regs_in_insn, 
			    reg_partition);
	    }

	  next = NEXT_INSN (insn);
	}
      while (insn != last);
    }
}

/* The main entry point for moving from SSA.  */

void
convert_from_ssa()
{
  int bb;
  partition reg_partition;
  rtx insns = get_insns ();
    
  /* Need global_live_at_{start,end} up to date.  */
  life_analysis (insns, NULL, 
	  PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE | PROP_DEATH_NOTES);

  /* Figure out which regs in copies and phi nodes don't conflict and
     therefore can be coalesced.  */
  if (conservative_reg_partition)
    reg_partition = compute_conservative_reg_partition ();
  else
    reg_partition = compute_coalesced_reg_partition ();

  rename_equivalent_regs (reg_partition);

  /* Eliminate the PHI nodes.  */
  for (bb = n_basic_blocks; --bb >= 0; )
    {
      basic_block b = BASIC_BLOCK (bb);
      edge e;

      for (e = b->pred; e; e = e->pred_next)
	if (e->src != ENTRY_BLOCK_PTR)
	  eliminate_phi (e, reg_partition);
    }

  partition_delete (reg_partition);

  /* Actually delete the PHI nodes.  */
  for (bb = n_basic_blocks; --bb >= 0; )
    {
      rtx insn = BLOCK_HEAD (bb);
      int start = (GET_CODE (insn) != CODE_LABEL);

      if (! start)
	insn = next_nonnote_insn (insn);
      while (PHI_NODE_P (insn))
	{
	  /* If a phi node is the last insn in the block, there must
	     have been nothing else.  Set the block end to the block
	     head.  */
	  if (insn == BLOCK_END (bb))
	    BLOCK_END (bb) = BLOCK_HEAD (bb);
	  insn = delete_insn (insn);
	  if (GET_CODE (insn) == NOTE)
	    insn = next_nonnote_insn (insn);
	}
      if (start)
	BLOCK_HEAD (bb) = insn;
    }

  /* Commit all the copy nodes needed to convert out of SSA form.  */
  commit_edge_insertions ();

  in_ssa_form = 0;

  count_or_remove_death_notes (NULL, 1);
}

/* Scan phi nodes in successors to BB.  For each such phi node that
   has a phi alternative value corresponding to BB, invoke FN.  FN
   is passed the entire phi node insn, the regno of the set
   destination, the regno of the phi argument corresponding to BB,
   and DATA.

   If FN ever returns non-zero, stops immediately and returns this
   value.  Otherwise, returns zero.  */

int
for_each_successor_phi (bb, fn, data)
     basic_block bb;
     successor_phi_fn fn;
     void *data;
{
  edge e;
  
  if (bb == EXIT_BLOCK_PTR)
    return 0;

  /* Scan outgoing edges.  */
  for (e = bb->succ; e != NULL; e = e->succ_next)
    {
      rtx insn;

      basic_block successor = e->dest;
      if (successor == ENTRY_BLOCK_PTR 
	  || successor == EXIT_BLOCK_PTR)
	continue;

      /* Advance to the first non-label insn of the successor block.  */
      insn = successor->head;
      while (insn != NULL 
	     && (GET_CODE (insn) == CODE_LABEL
		 || GET_CODE (insn) == NOTE))
	insn = NEXT_INSN (insn);

      if (insn == NULL)
	continue;

      /* Scan phi nodes in the successor.  */
      for ( ; PHI_NODE_P (insn); insn = NEXT_INSN (insn))
	{
	  int result;
	  rtx phi_set = PATTERN (insn);
	  rtx *alternative = phi_alternative (phi_set, bb->index);
	  rtx phi_src;
	  
	  /* This phi function may not have an alternative
	     corresponding to the incoming edge, indicating the
	     assigned variable is not defined along the edge.  */
	  if (alternative == NULL)
	    continue;
	  phi_src = *alternative;

	  /* Invoke the callback.  */
	  result = (*fn) (insn, REGNO (SET_DEST (phi_set)), 
			  REGNO (phi_src), data);

	  /* Terminate if requested.  */
	  if (result != 0)
	    return result;
	}
    }

  return 0;
}