summaryrefslogtreecommitdiff
path: root/gcc/bb-reorder.c
blob: 7605e17e7ef3224d57e68c0ca347b4f26597281a (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
/* Basic block reordering routines for the GNU compiler.
   Copyright (C) 2000-2013 Free Software Foundation, Inc.

   This file is part of GCC.

   GCC is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3, or (at your option)
   any later version.

   GCC is distributed in the hope that it will be useful, but WITHOUT
   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
   License for more details.

   You should have received a copy of the GNU General Public License
   along with GCC; see the file COPYING3.  If not see
   <http://www.gnu.org/licenses/>.  */

/* This (greedy) algorithm constructs traces in several rounds.
   The construction starts from "seeds".  The seed for the first round
   is the entry point of the function.  When there are more than one seed,
   the one with the lowest key in the heap is selected first (see bb_to_key).
   Then the algorithm repeatedly adds the most probable successor to the end
   of a trace.  Finally it connects the traces.

   There are two parameters: Branch Threshold and Exec Threshold.
   If the probability of an edge to a successor of the current basic block is
   lower than Branch Threshold or its frequency is lower than Exec Threshold,
   then the successor will be the seed in one of the next rounds.
   Each round has these parameters lower than the previous one.
   The last round has to have these parameters set to zero so that the
   remaining blocks are picked up.

   The algorithm selects the most probable successor from all unvisited
   successors and successors that have been added to this trace.
   The other successors (that has not been "sent" to the next round) will be
   other seeds for this round and the secondary traces will start from them.
   If the successor has not been visited in this trace, it is added to the
   trace (however, there is some heuristic for simple branches).
   If the successor has been visited in this trace, a loop has been found.
   If the loop has many iterations, the loop is rotated so that the source
   block of the most probable edge going out of the loop is the last block
   of the trace.
   If the loop has few iterations and there is no edge from the last block of
   the loop going out of the loop, the loop header is duplicated.

   When connecting traces, the algorithm first checks whether there is an edge
   from the last block of a trace to the first block of another trace.
   When there are still some unconnected traces it checks whether there exists
   a basic block BB such that BB is a successor of the last block of a trace
   and BB is a predecessor of the first block of another trace.  In this case,
   BB is duplicated, added at the end of the first trace and the traces are
   connected through it.
   The rest of traces are simply connected so there will be a jump to the
   beginning of the rest of traces.

   The above description is for the full algorithm, which is used when the
   function is optimized for speed.  When the function is optimized for size,
   in order to reduce long jumps and connect more fallthru edges, the
   algorithm is modified as follows:
   (1) Break long traces to short ones.  A trace is broken at a block that has
   multiple predecessors/ successors during trace discovery.  When connecting
   traces, only connect Trace n with Trace n + 1.  This change reduces most
   long jumps compared with the above algorithm.
   (2) Ignore the edge probability and frequency for fallthru edges.
   (3) Keep the original order of blocks when there is no chance to fall
   through.  We rely on the results of cfg_cleanup.

   To implement the change for code size optimization, block's index is
   selected as the key and all traces are found in one round.

   References:

   "Software Trace Cache"
   A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
   http://citeseer.nj.nec.com/15361.html

*/

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "regs.h"
#include "flags.h"
#include "output.h"
#include "fibheap.h"
#include "target.h"
#include "function.h"
#include "tm_p.h"
#include "obstack.h"
#include "expr.h"
#include "params.h"
#include "diagnostic-core.h"
#include "toplev.h" /* user_defined_section_attribute */
#include "tree-pass.h"
#include "df.h"
#include "bb-reorder.h"
#include "except.h"

/* The number of rounds.  In most cases there will only be 4 rounds, but
   when partitioning hot and cold basic blocks into separate sections of
   the object file there will be an extra round.  */
#define N_ROUNDS 5

/* Stubs in case we don't have a return insn.
   We have to check at run time too, not only compile time.  */

#ifndef HAVE_return
#define HAVE_return 0
#define gen_return() NULL_RTX
#endif


struct target_bb_reorder default_target_bb_reorder;
#if SWITCHABLE_TARGET
struct target_bb_reorder *this_target_bb_reorder = &default_target_bb_reorder;
#endif

#define uncond_jump_length \
  (this_target_bb_reorder->x_uncond_jump_length)

/* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE.  */
static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};

/* Exec thresholds in thousandths (per mille) of the frequency of bb 0.  */
static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};

/* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
   block the edge destination is not duplicated while connecting traces.  */
#define DUPLICATION_THRESHOLD 100

/* Structure to hold needed information for each basic block.  */
typedef struct bbro_basic_block_data_def
{
  /* Which trace is the bb start of (-1 means it is not a start of any).  */
  int start_of_trace;

  /* Which trace is the bb end of (-1 means it is not an end of any).  */
  int end_of_trace;

  /* Which trace is the bb in?  */
  int in_trace;

  /* Which trace was this bb visited in?  */
  int visited;

  /* Which heap is BB in (if any)?  */
  fibheap_t heap;

  /* Which heap node is BB in (if any)?  */
  fibnode_t node;
} bbro_basic_block_data;

/* The current size of the following dynamic array.  */
static int array_size;

/* The array which holds needed information for basic blocks.  */
static bbro_basic_block_data *bbd;

/* To avoid frequent reallocation the size of arrays is greater than needed,
   the number of elements is (not less than) 1.25 * size_wanted.  */
#define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)

/* Free the memory and set the pointer to NULL.  */
#define FREE(P) (gcc_assert (P), free (P), P = 0)

/* Structure for holding information about a trace.  */
struct trace
{
  /* First and last basic block of the trace.  */
  basic_block first, last;

  /* The round of the STC creation which this trace was found in.  */
  int round;

  /* The length (i.e. the number of basic blocks) of the trace.  */
  int length;
};

/* Maximum frequency and count of one of the entry blocks.  */
static int max_entry_frequency;
static gcov_type max_entry_count;

/* Local function prototypes.  */
static void find_traces (int *, struct trace *);
static basic_block rotate_loop (edge, struct trace *, int);
static void mark_bb_visited (basic_block, int);
static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
				 int, fibheap_t *, int);
static basic_block copy_bb (basic_block, edge, basic_block, int);
static fibheapkey_t bb_to_key (basic_block);
static bool better_edge_p (const_basic_block, const_edge, int, int, int, int,
			   const_edge);
static bool connect_better_edge_p (const_edge, bool, int, const_edge,
				   struct trace *);
static void connect_traces (int, struct trace *);
static bool copy_bb_p (const_basic_block, int);
static bool push_to_next_round_p (const_basic_block, int, int, int, gcov_type);

/* Return the trace number in which BB was visited.  */

static int
bb_visited_trace (const_basic_block bb)
{
  gcc_assert (bb->index < array_size);
  return bbd[bb->index].visited;
}

/* This function marks BB that it was visited in trace number TRACE.  */

static void
mark_bb_visited (basic_block bb, int trace)
{
  bbd[bb->index].visited = trace;
  if (bbd[bb->index].heap)
    {
      fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
      bbd[bb->index].heap = NULL;
      bbd[bb->index].node = NULL;
    }
}

/* Check to see if bb should be pushed into the next round of trace
   collections or not.  Reasons for pushing the block forward are 1).
   If the block is cold, we are doing partitioning, and there will be
   another round (cold partition blocks are not supposed to be
   collected into traces until the very last round); or 2). There will
   be another round, and the basic block is not "hot enough" for the
   current round of trace collection.  */

static bool
push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds,
		      int exec_th, gcov_type count_th)
{
  bool there_exists_another_round;
  bool block_not_hot_enough;

  there_exists_another_round = round < number_of_rounds - 1;

  block_not_hot_enough = (bb->frequency < exec_th
			  || bb->count < count_th
			  || probably_never_executed_bb_p (cfun, bb));

  if (there_exists_another_round
      && block_not_hot_enough)
    return true;
  else
    return false;
}

/* Find the traces for Software Trace Cache.  Chain each trace through
   RBI()->next.  Store the number of traces to N_TRACES and description of
   traces to TRACES.  */

static void
find_traces (int *n_traces, struct trace *traces)
{
  int i;
  int number_of_rounds;
  edge e;
  edge_iterator ei;
  fibheap_t heap;

  /* Add one extra round of trace collection when partitioning hot/cold
     basic blocks into separate sections.  The last round is for all the
     cold blocks (and ONLY the cold blocks).  */

  number_of_rounds = N_ROUNDS - 1;

  /* Insert entry points of function into heap.  */
  heap = fibheap_new ();
  max_entry_frequency = 0;
  max_entry_count = 0;
  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
    {
      bbd[e->dest->index].heap = heap;
      bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
						    e->dest);
      if (e->dest->frequency > max_entry_frequency)
	max_entry_frequency = e->dest->frequency;
      if (e->dest->count > max_entry_count)
	max_entry_count = e->dest->count;
    }

  /* Find the traces.  */
  for (i = 0; i < number_of_rounds; i++)
    {
      gcov_type count_threshold;

      if (dump_file)
	fprintf (dump_file, "STC - round %d\n", i + 1);

      if (max_entry_count < INT_MAX / 1000)
	count_threshold = max_entry_count * exec_threshold[i] / 1000;
      else
	count_threshold = max_entry_count / 1000 * exec_threshold[i];

      find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
			   max_entry_frequency * exec_threshold[i] / 1000,
			   count_threshold, traces, n_traces, i, &heap,
			   number_of_rounds);
    }
  fibheap_delete (heap);

  if (dump_file)
    {
      for (i = 0; i < *n_traces; i++)
	{
	  basic_block bb;
	  fprintf (dump_file, "Trace %d (round %d):  ", i + 1,
		   traces[i].round + 1);
	  for (bb = traces[i].first;
	       bb != traces[i].last;
	       bb = (basic_block) bb->aux)
	    fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
	  fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
	}
      fflush (dump_file);
    }
}

/* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
   (with sequential number TRACE_N).  */

static basic_block
rotate_loop (edge back_edge, struct trace *trace, int trace_n)
{
  basic_block bb;

  /* Information about the best end (end after rotation) of the loop.  */
  basic_block best_bb = NULL;
  edge best_edge = NULL;
  int best_freq = -1;
  gcov_type best_count = -1;
  /* The best edge is preferred when its destination is not visited yet
     or is a start block of some trace.  */
  bool is_preferred = false;

  /* Find the most frequent edge that goes out from current trace.  */
  bb = back_edge->dest;
  do
    {
      edge e;
      edge_iterator ei;

      FOR_EACH_EDGE (e, ei, bb->succs)
	if (e->dest != EXIT_BLOCK_PTR
	    && bb_visited_trace (e->dest) != trace_n
	    && (e->flags & EDGE_CAN_FALLTHRU)
	    && !(e->flags & EDGE_COMPLEX))
	{
	  if (is_preferred)
	    {
	      /* The best edge is preferred.  */
	      if (!bb_visited_trace (e->dest)
		  || bbd[e->dest->index].start_of_trace >= 0)
		{
		  /* The current edge E is also preferred.  */
		  int freq = EDGE_FREQUENCY (e);
		  if (freq > best_freq || e->count > best_count)
		    {
		      best_freq = freq;
		      best_count = e->count;
		      best_edge = e;
		      best_bb = bb;
		    }
		}
	    }
	  else
	    {
	      if (!bb_visited_trace (e->dest)
		  || bbd[e->dest->index].start_of_trace >= 0)
		{
		  /* The current edge E is preferred.  */
		  is_preferred = true;
		  best_freq = EDGE_FREQUENCY (e);
		  best_count = e->count;
		  best_edge = e;
		  best_bb = bb;
		}
	      else
		{
		  int freq = EDGE_FREQUENCY (e);
		  if (!best_edge || freq > best_freq || e->count > best_count)
		    {
		      best_freq = freq;
		      best_count = e->count;
		      best_edge = e;
		      best_bb = bb;
		    }
		}
	    }
	}
      bb = (basic_block) bb->aux;
    }
  while (bb != back_edge->dest);

  if (best_bb)
    {
      /* Rotate the loop so that the BEST_EDGE goes out from the last block of
	 the trace.  */
      if (back_edge->dest == trace->first)
	{
	  trace->first = (basic_block) best_bb->aux;
	}
      else
	{
	  basic_block prev_bb;

	  for (prev_bb = trace->first;
	       prev_bb->aux != back_edge->dest;
	       prev_bb = (basic_block) prev_bb->aux)
	    ;
	  prev_bb->aux = best_bb->aux;

	  /* Try to get rid of uncond jump to cond jump.  */
	  if (single_succ_p (prev_bb))
	    {
	      basic_block header = single_succ (prev_bb);

	      /* Duplicate HEADER if it is a small block containing cond jump
		 in the end.  */
	      if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
		  && !find_reg_note (BB_END (header), REG_CROSSING_JUMP,
				     NULL_RTX))
		copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
	    }
	}
    }
  else
    {
      /* We have not found suitable loop tail so do no rotation.  */
      best_bb = back_edge->src;
    }
  best_bb->aux = NULL;
  return best_bb;
}

/* One round of finding traces.  Find traces for BRANCH_TH and EXEC_TH i.e. do
   not include basic blocks whose probability is lower than BRANCH_TH or whose
   frequency is lower than EXEC_TH into traces (or whose count is lower than
   COUNT_TH).  Store the new traces into TRACES and modify the number of
   traces *N_TRACES.  Set the round (which the trace belongs to) to ROUND.
   The function expects starting basic blocks to be in *HEAP and will delete
   *HEAP and store starting points for the next round into new *HEAP.  */

static void
find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
		     struct trace *traces, int *n_traces, int round,
		     fibheap_t *heap, int number_of_rounds)
{
  /* Heap for discarded basic blocks which are possible starting points for
     the next round.  */
  fibheap_t new_heap = fibheap_new ();
  bool for_size = optimize_function_for_size_p (cfun);

  while (!fibheap_empty (*heap))
    {
      basic_block bb;
      struct trace *trace;
      edge best_edge, e;
      fibheapkey_t key;
      edge_iterator ei;

      bb = (basic_block) fibheap_extract_min (*heap);
      bbd[bb->index].heap = NULL;
      bbd[bb->index].node = NULL;

      if (dump_file)
	fprintf (dump_file, "Getting bb %d\n", bb->index);

      /* If the BB's frequency is too low, send BB to the next round.  When
	 partitioning hot/cold blocks into separate sections, make sure all
	 the cold blocks (and ONLY the cold blocks) go into the (extra) final
	 round.  When optimizing for size, do not push to next round.  */

      if (!for_size
	  && push_to_next_round_p (bb, round, number_of_rounds, exec_th,
				   count_th))
	{
	  int key = bb_to_key (bb);
	  bbd[bb->index].heap = new_heap;
	  bbd[bb->index].node = fibheap_insert (new_heap, key, bb);

	  if (dump_file)
	    fprintf (dump_file,
		     "  Possible start point of next round: %d (key: %d)\n",
		     bb->index, key);
	  continue;
	}

      trace = traces + *n_traces;
      trace->first = bb;
      trace->round = round;
      trace->length = 0;
      bbd[bb->index].in_trace = *n_traces;
      (*n_traces)++;

      do
	{
	  int prob, freq;
	  bool ends_in_call;

	  /* The probability and frequency of the best edge.  */
	  int best_prob = INT_MIN / 2;
	  int best_freq = INT_MIN / 2;

	  best_edge = NULL;
	  mark_bb_visited (bb, *n_traces);
	  trace->length++;

	  if (dump_file)
	    fprintf (dump_file, "Basic block %d was visited in trace %d\n",
		     bb->index, *n_traces - 1);

	  ends_in_call = block_ends_with_call_p (bb);

	  /* Select the successor that will be placed after BB.  */
	  FOR_EACH_EDGE (e, ei, bb->succs)
	    {
	      gcc_assert (!(e->flags & EDGE_FAKE));

	      if (e->dest == EXIT_BLOCK_PTR)
		continue;

	      if (bb_visited_trace (e->dest)
		  && bb_visited_trace (e->dest) != *n_traces)
		continue;

	      if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
		continue;

	      prob = e->probability;
	      freq = e->dest->frequency;

	      /* The only sensible preference for a call instruction is the
		 fallthru edge.  Don't bother selecting anything else.  */
	      if (ends_in_call)
		{
		  if (e->flags & EDGE_CAN_FALLTHRU)
		    {
		      best_edge = e;
		      best_prob = prob;
		      best_freq = freq;
		    }
		  continue;
		}

	      /* Edge that cannot be fallthru or improbable or infrequent
		 successor (i.e. it is unsuitable successor).  When optimizing
		 for size, ignore the probability and frequency.  */
	      if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
		  || ((prob < branch_th || EDGE_FREQUENCY (e) < exec_th
		      || e->count < count_th) && (!for_size)))
		continue;

	      /* If partitioning hot/cold basic blocks, don't consider edges
		 that cross section boundaries.  */

	      if (better_edge_p (bb, e, prob, freq, best_prob, best_freq,
				 best_edge))
		{
		  best_edge = e;
		  best_prob = prob;
		  best_freq = freq;
		}
	    }

	  /* If the best destination has multiple predecessors, and can be
	     duplicated cheaper than a jump, don't allow it to be added
	     to a trace.  We'll duplicate it when connecting traces.  */
	  if (best_edge && EDGE_COUNT (best_edge->dest->preds) >= 2
	      && copy_bb_p (best_edge->dest, 0))
	    best_edge = NULL;

	  /* If the best destination has multiple successors or predecessors,
	     don't allow it to be added when optimizing for size.  This makes
	     sure predecessors with smaller index are handled before the best
	     destinarion.  It breaks long trace and reduces long jumps.

	     Take if-then-else as an example.
		A
	       / \
	      B   C
	       \ /
		D
	     If we do not remove the best edge B->D/C->D, the final order might
	     be A B D ... C.  C is at the end of the program.  If D's successors
	     and D are complicated, might need long jumps for A->C and C->D.
	     Similar issue for order: A C D ... B.

	     After removing the best edge, the final result will be ABCD/ ACBD.
	     It does not add jump compared with the previous order.  But it
	     reduces the possiblity of long jumps.  */
	  if (best_edge && for_size
	      && (EDGE_COUNT (best_edge->dest->succs) > 1
		 || EDGE_COUNT (best_edge->dest->preds) > 1))
	    best_edge = NULL;

	  /* Add all non-selected successors to the heaps.  */
	  FOR_EACH_EDGE (e, ei, bb->succs)
	    {
	      if (e == best_edge
		  || e->dest == EXIT_BLOCK_PTR
		  || bb_visited_trace (e->dest))
		continue;

	      key = bb_to_key (e->dest);

	      if (bbd[e->dest->index].heap)
		{
		  /* E->DEST is already in some heap.  */
		  if (key != bbd[e->dest->index].node->key)
		    {
		      if (dump_file)
			{
			  fprintf (dump_file,
				   "Changing key for bb %d from %ld to %ld.\n",
				   e->dest->index,
				   (long) bbd[e->dest->index].node->key,
				   key);
			}
		      fibheap_replace_key (bbd[e->dest->index].heap,
					   bbd[e->dest->index].node, key);
		    }
		}
	      else
		{
		  fibheap_t which_heap = *heap;

		  prob = e->probability;
		  freq = EDGE_FREQUENCY (e);

		  if (!(e->flags & EDGE_CAN_FALLTHRU)
		      || (e->flags & EDGE_COMPLEX)
		      || prob < branch_th || freq < exec_th
		      || e->count < count_th)
		    {
		      /* When partitioning hot/cold basic blocks, make sure
			 the cold blocks (and only the cold blocks) all get
			 pushed to the last round of trace collection.  When
			 optimizing for size, do not push to next round.  */

		      if (!for_size && push_to_next_round_p (e->dest, round,
							     number_of_rounds,
							     exec_th, count_th))
			which_heap = new_heap;
		    }

		  bbd[e->dest->index].heap = which_heap;
		  bbd[e->dest->index].node = fibheap_insert (which_heap,
								key, e->dest);

		  if (dump_file)
		    {
		      fprintf (dump_file,
			       "  Possible start of %s round: %d (key: %ld)\n",
			       (which_heap == new_heap) ? "next" : "this",
			       e->dest->index, (long) key);
		    }

		}
	    }

	  if (best_edge) /* Suitable successor was found.  */
	    {
	      if (bb_visited_trace (best_edge->dest) == *n_traces)
		{
		  /* We do nothing with one basic block loops.  */
		  if (best_edge->dest != bb)
		    {
		      if (EDGE_FREQUENCY (best_edge)
			  > 4 * best_edge->dest->frequency / 5)
			{
			  /* The loop has at least 4 iterations.  If the loop
			     header is not the first block of the function
			     we can rotate the loop.  */

			  if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
			    {
			      if (dump_file)
				{
				  fprintf (dump_file,
					   "Rotating loop %d - %d\n",
					   best_edge->dest->index, bb->index);
				}
			      bb->aux = best_edge->dest;
			      bbd[best_edge->dest->index].in_trace =
							     (*n_traces) - 1;
			      bb = rotate_loop (best_edge, trace, *n_traces);
			    }
			}
		      else
			{
			  /* The loop has less than 4 iterations.  */

			  if (single_succ_p (bb)
			      && copy_bb_p (best_edge->dest,
			      		    optimize_edge_for_speed_p
			      		    (best_edge)))
			    {
			      bb = copy_bb (best_edge->dest, best_edge, bb,
					    *n_traces);
			      trace->length++;
			    }
			}
		    }

		  /* Terminate the trace.  */
		  break;
		}
	      else
		{
		  /* Check for a situation

		    A
		   /|
		  B |
		   \|
		    C

		  where
		  EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
		    >= EDGE_FREQUENCY (AC).
		  (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
		  Best ordering is then A B C.

		  When optimizing for size, A B C is always the best order.

		  This situation is created for example by:

		  if (A) B;
		  C;

		  */

		  FOR_EACH_EDGE (e, ei, bb->succs)
		    if (e != best_edge
			&& (e->flags & EDGE_CAN_FALLTHRU)
			&& !(e->flags & EDGE_COMPLEX)
			&& !bb_visited_trace (e->dest)
			&& single_pred_p (e->dest)
			&& !(e->flags & EDGE_CROSSING)
			&& single_succ_p (e->dest)
			&& (single_succ_edge (e->dest)->flags
			    & EDGE_CAN_FALLTHRU)
			&& !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
			&& single_succ (e->dest) == best_edge->dest
			&& (2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge)
			    || for_size))
		      {
			best_edge = e;
			if (dump_file)
			  fprintf (dump_file, "Selecting BB %d\n",
				   best_edge->dest->index);
			break;
		      }

		  bb->aux = best_edge->dest;
		  bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
		  bb = best_edge->dest;
		}
	    }
	}
      while (best_edge);
      trace->last = bb;
      bbd[trace->first->index].start_of_trace = *n_traces - 1;
      bbd[trace->last->index].end_of_trace = *n_traces - 1;

      /* The trace is terminated so we have to recount the keys in heap
	 (some block can have a lower key because now one of its predecessors
	 is an end of the trace).  */
      FOR_EACH_EDGE (e, ei, bb->succs)
	{
	  if (e->dest == EXIT_BLOCK_PTR
	      || bb_visited_trace (e->dest))
	    continue;

	  if (bbd[e->dest->index].heap)
	    {
	      key = bb_to_key (e->dest);
	      if (key != bbd[e->dest->index].node->key)
		{
		  if (dump_file)
		    {
		      fprintf (dump_file,
			       "Changing key for bb %d from %ld to %ld.\n",
			       e->dest->index,
			       (long) bbd[e->dest->index].node->key, key);
		    }
		  fibheap_replace_key (bbd[e->dest->index].heap,
				       bbd[e->dest->index].node,
				       key);
		}
	    }
	}
    }

  fibheap_delete (*heap);

  /* "Return" the new heap.  */
  *heap = new_heap;
}

/* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
   it to trace after BB, mark OLD_BB visited and update pass' data structures
   (TRACE is a number of trace which OLD_BB is duplicated to).  */

static basic_block
copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
{
  basic_block new_bb;

  new_bb = duplicate_block (old_bb, e, bb);
  BB_COPY_PARTITION (new_bb, old_bb);

  gcc_assert (e->dest == new_bb);

  if (dump_file)
    fprintf (dump_file,
	     "Duplicated bb %d (created bb %d)\n",
	     old_bb->index, new_bb->index);

  if (new_bb->index >= array_size || last_basic_block > array_size)
    {
      int i;
      int new_size;

      new_size = MAX (last_basic_block, new_bb->index + 1);
      new_size = GET_ARRAY_SIZE (new_size);
      bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size);
      for (i = array_size; i < new_size; i++)
	{
	  bbd[i].start_of_trace = -1;
	  bbd[i].end_of_trace = -1;
	  bbd[i].in_trace = -1;
	  bbd[i].visited = 0;
	  bbd[i].heap = NULL;
	  bbd[i].node = NULL;
	}
      array_size = new_size;

      if (dump_file)
	{
	  fprintf (dump_file,
		   "Growing the dynamic array to %d elements.\n",
		   array_size);
	}
    }

  gcc_assert (!bb_visited_trace (e->dest));
  mark_bb_visited (new_bb, trace);
  new_bb->aux = bb->aux;
  bb->aux = new_bb;

  bbd[new_bb->index].in_trace = trace;

  return new_bb;
}

/* Compute and return the key (for the heap) of the basic block BB.  */

static fibheapkey_t
bb_to_key (basic_block bb)
{
  edge e;
  edge_iterator ei;
  int priority = 0;

  /* Use index as key to align with its original order.  */
  if (optimize_function_for_size_p (cfun))
    return bb->index;

  /* Do not start in probably never executed blocks.  */

  if (BB_PARTITION (bb) == BB_COLD_PARTITION
      || probably_never_executed_bb_p (cfun, bb))
    return BB_FREQ_MAX;

  /* Prefer blocks whose predecessor is an end of some trace
     or whose predecessor edge is EDGE_DFS_BACK.  */
  FOR_EACH_EDGE (e, ei, bb->preds)
    {
      if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
	  || (e->flags & EDGE_DFS_BACK))
	{
	  int edge_freq = EDGE_FREQUENCY (e);

	  if (edge_freq > priority)
	    priority = edge_freq;
	}
    }

  if (priority)
    /* The block with priority should have significantly lower key.  */
    return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);

  return -bb->frequency;
}

/* Return true when the edge E from basic block BB is better than the temporary
   best edge (details are in function).  The probability of edge E is PROB. The
   frequency of the successor is FREQ.  The current best probability is
   BEST_PROB, the best frequency is BEST_FREQ.
   The edge is considered to be equivalent when PROB does not differ much from
   BEST_PROB; similarly for frequency.  */

static bool
better_edge_p (const_basic_block bb, const_edge e, int prob, int freq,
	       int best_prob, int best_freq, const_edge cur_best_edge)
{
  bool is_better_edge;

  /* The BEST_* values do not have to be best, but can be a bit smaller than
     maximum values.  */
  int diff_prob = best_prob / 10;
  int diff_freq = best_freq / 10;

  /* The smaller one is better to keep the original order.  */
  if (optimize_function_for_size_p (cfun))
    return !cur_best_edge
	   || cur_best_edge->dest->index > e->dest->index;

  if (prob > best_prob + diff_prob)
    /* The edge has higher probability than the temporary best edge.  */
    is_better_edge = true;
  else if (prob < best_prob - diff_prob)
    /* The edge has lower probability than the temporary best edge.  */
    is_better_edge = false;
  else if (freq < best_freq - diff_freq)
    /* The edge and the temporary best edge  have almost equivalent
       probabilities.  The higher frequency of a successor now means
       that there is another edge going into that successor.
       This successor has lower frequency so it is better.  */
    is_better_edge = true;
  else if (freq > best_freq + diff_freq)
    /* This successor has higher frequency so it is worse.  */
    is_better_edge = false;
  else if (e->dest->prev_bb == bb)
    /* The edges have equivalent probabilities and the successors
       have equivalent frequencies.  Select the previous successor.  */
    is_better_edge = true;
  else
    is_better_edge = false;

  /* If we are doing hot/cold partitioning, make sure that we always favor
     non-crossing edges over crossing edges.  */

  if (!is_better_edge
      && flag_reorder_blocks_and_partition
      && cur_best_edge
      && (cur_best_edge->flags & EDGE_CROSSING)
      && !(e->flags & EDGE_CROSSING))
    is_better_edge = true;

  return is_better_edge;
}

/* Return true when the edge E is better than the temporary best edge
   CUR_BEST_EDGE.  If SRC_INDEX_P is true, the function compares the src bb of
   E and CUR_BEST_EDGE; otherwise it will compare the dest bb.
   BEST_LEN is the trace length of src (or dest) bb in CUR_BEST_EDGE.
   TRACES record the information about traces.
   When optimizing for size, the edge with smaller index is better.
   When optimizing for speed, the edge with bigger probability or longer trace
   is better.  */

static bool
connect_better_edge_p (const_edge e, bool src_index_p, int best_len,
		       const_edge cur_best_edge, struct trace *traces)
{
  int e_index;
  int b_index;
  bool is_better_edge;

  if (!cur_best_edge)
    return true;

  if (optimize_function_for_size_p (cfun))
    {
      e_index = src_index_p ? e->src->index : e->dest->index;
      b_index = src_index_p ? cur_best_edge->src->index
			      : cur_best_edge->dest->index;
      /* The smaller one is better to keep the original order.  */
      return b_index > e_index;
    }

  if (src_index_p)
    {
      e_index = e->src->index;

      if (e->probability > cur_best_edge->probability)
	/* The edge has higher probability than the temporary best edge.  */
	is_better_edge = true;
      else if (e->probability < cur_best_edge->probability)
	/* The edge has lower probability than the temporary best edge.  */
	is_better_edge = false;
      else if (traces[bbd[e_index].end_of_trace].length > best_len)
	/* The edge and the temporary best edge have equivalent probabilities.
	   The edge with longer trace is better.  */
	is_better_edge = true;
      else
	is_better_edge = false;
    }
  else
    {
      e_index = e->dest->index;

      if (e->probability > cur_best_edge->probability)
	/* The edge has higher probability than the temporary best edge.  */
	is_better_edge = true;
      else if (e->probability < cur_best_edge->probability)
	/* The edge has lower probability than the temporary best edge.  */
	is_better_edge = false;
      else if (traces[bbd[e_index].start_of_trace].length > best_len)
	/* The edge and the temporary best edge have equivalent probabilities.
	   The edge with longer trace is better.  */
	is_better_edge = true;
      else
	is_better_edge = false;
    }

  return is_better_edge;
}

/* Connect traces in array TRACES, N_TRACES is the count of traces.  */

static void
connect_traces (int n_traces, struct trace *traces)
{
  int i;
  bool *connected;
  bool two_passes;
  int last_trace;
  int current_pass;
  int current_partition;
  int freq_threshold;
  gcov_type count_threshold;
  bool for_size = optimize_function_for_size_p (cfun);

  freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
  if (max_entry_count < INT_MAX / 1000)
    count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
  else
    count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;

  connected = XCNEWVEC (bool, n_traces);
  last_trace = -1;
  current_pass = 1;
  current_partition = BB_PARTITION (traces[0].first);
  two_passes = false;

  if (flag_reorder_blocks_and_partition)
    for (i = 0; i < n_traces && !two_passes; i++)
      if (BB_PARTITION (traces[0].first)
	  != BB_PARTITION (traces[i].first))
	two_passes = true;

  for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++)
    {
      int t = i;
      int t2;
      edge e, best;
      int best_len;

      if (i >= n_traces)
	{
	  gcc_assert (two_passes && current_pass == 1);
	  i = 0;
	  t = i;
	  current_pass = 2;
	  if (current_partition == BB_HOT_PARTITION)
	    current_partition = BB_COLD_PARTITION;
	  else
	    current_partition = BB_HOT_PARTITION;
	}

      if (connected[t])
	continue;

      if (two_passes
	  && BB_PARTITION (traces[t].first) != current_partition)
	continue;

      connected[t] = true;

      /* Find the predecessor traces.  */
      for (t2 = t; t2 > 0;)
	{
	  edge_iterator ei;
	  best = NULL;
	  best_len = 0;
	  FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
	    {
	      int si = e->src->index;

	      if (e->src != ENTRY_BLOCK_PTR
		  && (e->flags & EDGE_CAN_FALLTHRU)
		  && !(e->flags & EDGE_COMPLEX)
		  && bbd[si].end_of_trace >= 0
		  && !connected[bbd[si].end_of_trace]
		  && (BB_PARTITION (e->src) == current_partition)
		  && connect_better_edge_p (e, true, best_len, best, traces))
		{
		  best = e;
		  best_len = traces[bbd[si].end_of_trace].length;
		}
	    }
	  if (best)
	    {
	      best->src->aux = best->dest;
	      t2 = bbd[best->src->index].end_of_trace;
	      connected[t2] = true;

	      if (dump_file)
		{
		  fprintf (dump_file, "Connection: %d %d\n",
			   best->src->index, best->dest->index);
		}
	    }
	  else
	    break;
	}

      if (last_trace >= 0)
	traces[last_trace].last->aux = traces[t2].first;
      last_trace = t;

      /* Find the successor traces.  */
      while (1)
	{
	  /* Find the continuation of the chain.  */
	  edge_iterator ei;
	  best = NULL;
	  best_len = 0;
	  FOR_EACH_EDGE (e, ei, traces[t].last->succs)
	    {
	      int di = e->dest->index;

	      if (e->dest != EXIT_BLOCK_PTR
		  && (e->flags & EDGE_CAN_FALLTHRU)
		  && !(e->flags & EDGE_COMPLEX)
		  && bbd[di].start_of_trace >= 0
		  && !connected[bbd[di].start_of_trace]
		  && (BB_PARTITION (e->dest) == current_partition)
		  && connect_better_edge_p (e, false, best_len, best, traces))
		{
		  best = e;
		  best_len = traces[bbd[di].start_of_trace].length;
		}
	    }

	  if (for_size)
	    {
	      if (!best)
		/* Stop finding the successor traces.  */
		break;

	      /* It is OK to connect block n with block n + 1 or a block
		 before n.  For others, only connect to the loop header.  */
	      if (best->dest->index > (traces[t].last->index + 1))
		{
		  int count = EDGE_COUNT (best->dest->preds);

		  FOR_EACH_EDGE (e, ei, best->dest->preds)
		    if (e->flags & EDGE_DFS_BACK)
		      count--;

		  /* If dest has multiple predecessors, skip it.  We expect
		     that one predecessor with smaller index connects with it
		     later.  */
		  if (count != 1) 
		    break;
		}

	      /* Only connect Trace n with Trace n + 1.  It is conservative
		 to keep the order as close as possible to the original order.
		 It also helps to reduce long jumps.  */
	      if (last_trace != bbd[best->dest->index].start_of_trace - 1)
		break;

	      if (dump_file)
		fprintf (dump_file, "Connection: %d %d\n",
			 best->src->index, best->dest->index);

	      t = bbd[best->dest->index].start_of_trace;
	      traces[last_trace].last->aux = traces[t].first;
	      connected[t] = true;
	      last_trace = t;
	    }
	  else if (best)
	    {
	      if (dump_file)
		{
		  fprintf (dump_file, "Connection: %d %d\n",
			   best->src->index, best->dest->index);
		}
	      t = bbd[best->dest->index].start_of_trace;
	      traces[last_trace].last->aux = traces[t].first;
	      connected[t] = true;
	      last_trace = t;
	    }
	  else
	    {
	      /* Try to connect the traces by duplication of 1 block.  */
	      edge e2;
	      basic_block next_bb = NULL;
	      bool try_copy = false;

	      FOR_EACH_EDGE (e, ei, traces[t].last->succs)
		if (e->dest != EXIT_BLOCK_PTR
		    && (e->flags & EDGE_CAN_FALLTHRU)
		    && !(e->flags & EDGE_COMPLEX)
		    && (!best || e->probability > best->probability))
		  {
		    edge_iterator ei;
		    edge best2 = NULL;
		    int best2_len = 0;

		    /* If the destination is a start of a trace which is only
		       one block long, then no need to search the successor
		       blocks of the trace.  Accept it.  */
		    if (bbd[e->dest->index].start_of_trace >= 0
			&& traces[bbd[e->dest->index].start_of_trace].length
			   == 1)
		      {
			best = e;
			try_copy = true;
			continue;
		      }

		    FOR_EACH_EDGE (e2, ei, e->dest->succs)
		      {
			int di = e2->dest->index;

			if (e2->dest == EXIT_BLOCK_PTR
			    || ((e2->flags & EDGE_CAN_FALLTHRU)
				&& !(e2->flags & EDGE_COMPLEX)
				&& bbd[di].start_of_trace >= 0
				&& !connected[bbd[di].start_of_trace]
				&& BB_PARTITION (e2->dest) == current_partition
				&& EDGE_FREQUENCY (e2) >= freq_threshold
				&& e2->count >= count_threshold
				&& (!best2
				    || e2->probability > best2->probability
				    || (e2->probability == best2->probability
					&& traces[bbd[di].start_of_trace].length
					   > best2_len))))
			  {
			    best = e;
			    best2 = e2;
			    if (e2->dest != EXIT_BLOCK_PTR)
			      best2_len = traces[bbd[di].start_of_trace].length;
			    else
			      best2_len = INT_MAX;
			    next_bb = e2->dest;
			    try_copy = true;
			  }
		      }
		  }

	      if (flag_reorder_blocks_and_partition)
		try_copy = false;

	      /* Copy tiny blocks always; copy larger blocks only when the
		 edge is traversed frequently enough.  */
	      if (try_copy
		  && copy_bb_p (best->dest,
				optimize_edge_for_speed_p (best)
				&& EDGE_FREQUENCY (best) >= freq_threshold
				&& best->count >= count_threshold))
		{
		  basic_block new_bb;

		  if (dump_file)
		    {
		      fprintf (dump_file, "Connection: %d %d ",
			       traces[t].last->index, best->dest->index);
		      if (!next_bb)
			fputc ('\n', dump_file);
		      else if (next_bb == EXIT_BLOCK_PTR)
			fprintf (dump_file, "exit\n");
		      else
			fprintf (dump_file, "%d\n", next_bb->index);
		    }

		  new_bb = copy_bb (best->dest, best, traces[t].last, t);
		  traces[t].last = new_bb;
		  if (next_bb && next_bb != EXIT_BLOCK_PTR)
		    {
		      t = bbd[next_bb->index].start_of_trace;
		      traces[last_trace].last->aux = traces[t].first;
		      connected[t] = true;
		      last_trace = t;
		    }
		  else
		    break;	/* Stop finding the successor traces.  */
		}
	      else
		break;	/* Stop finding the successor traces.  */
	    }
	}
    }

  if (dump_file)
    {
      basic_block bb;

      fprintf (dump_file, "Final order:\n");
      for (bb = traces[0].first; bb; bb = (basic_block) bb->aux)
	fprintf (dump_file, "%d ", bb->index);
      fprintf (dump_file, "\n");
      fflush (dump_file);
    }

  FREE (connected);
}

/* Return true when BB can and should be copied. CODE_MAY_GROW is true
   when code size is allowed to grow by duplication.  */

static bool
copy_bb_p (const_basic_block bb, int code_may_grow)
{
  int size = 0;
  int max_size = uncond_jump_length;
  rtx insn;

  if (!bb->frequency)
    return false;
  if (EDGE_COUNT (bb->preds) < 2)
    return false;
  if (!can_duplicate_block_p (bb))
    return false;

  /* Avoid duplicating blocks which have many successors (PR/13430).  */
  if (EDGE_COUNT (bb->succs) > 8)
    return false;

  if (code_may_grow && optimize_bb_for_speed_p (bb))
    max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);

  FOR_BB_INSNS (bb, insn)
    {
      if (INSN_P (insn))
	size += get_attr_min_length (insn);
    }

  if (size <= max_size)
    return true;

  if (dump_file)
    {
      fprintf (dump_file,
	       "Block %d can't be copied because its size = %d.\n",
	       bb->index, size);
    }

  return false;
}

/* Return the length of unconditional jump instruction.  */

int
get_uncond_jump_length (void)
{
  rtx label, jump;
  int length;

  label = emit_label_before (gen_label_rtx (), get_insns ());
  jump = emit_jump_insn (gen_jump (label));

  length = get_attr_min_length (jump);

  delete_insn (jump);
  delete_insn (label);
  return length;
}

/* Emit a barrier into the footer of BB.  */

static void
emit_barrier_after_bb (basic_block bb)
{
  rtx barrier = emit_barrier_after (BB_END (bb));
  BB_FOOTER (bb) = unlink_insn_chain (barrier, barrier);
}

/* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
   Duplicate the landing pad and split the edges so that no EH edge
   crosses partitions.  */

static void
fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb)
{
  eh_landing_pad new_lp;
  basic_block new_bb, last_bb, post_bb;
  rtx new_label, jump, post_label;
  unsigned new_partition;
  edge_iterator ei;
  edge e;

  /* Generate the new landing-pad structure.  */
  new_lp = gen_eh_landing_pad (old_lp->region);
  new_lp->post_landing_pad = old_lp->post_landing_pad;
  new_lp->landing_pad = gen_label_rtx ();
  LABEL_PRESERVE_P (new_lp->landing_pad) = 1;

  /* Put appropriate instructions in new bb.  */
  new_label = emit_label (new_lp->landing_pad);

  expand_dw2_landing_pad_for_region (old_lp->region);

  post_bb = BLOCK_FOR_INSN (old_lp->landing_pad);
  post_bb = single_succ (post_bb);
  post_label = block_label (post_bb);
  jump = emit_jump_insn (gen_jump (post_label));
  JUMP_LABEL (jump) = post_label;

  /* Create new basic block to be dest for lp.  */
  last_bb = EXIT_BLOCK_PTR->prev_bb;
  new_bb = create_basic_block (new_label, jump, last_bb);
  new_bb->aux = last_bb->aux;
  last_bb->aux = new_bb;

  emit_barrier_after_bb (new_bb);

  make_edge (new_bb, post_bb, 0);

  /* Make sure new bb is in the other partition.  */
  new_partition = BB_PARTITION (old_bb);
  new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
  BB_SET_PARTITION (new_bb, new_partition);

  /* Fix up the edges.  */
  for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
    if (BB_PARTITION (e->src) == new_partition)
      {
	rtx insn = BB_END (e->src);
	rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);

	gcc_assert (note != NULL);
	gcc_checking_assert (INTVAL (XEXP (note, 0)) == old_lp->index);
	XEXP (note, 0) = GEN_INT (new_lp->index);

	/* Adjust the edge to the new destination.  */
	redirect_edge_succ (e, new_bb);
      }
    else
      ei_next (&ei);
}

/* Find the basic blocks that are rarely executed and need to be moved to
   a separate section of the .o file (to cut down on paging and improve
   cache locality).  Return a vector of all edges that cross.  */

static vec<edge> 
find_rarely_executed_basic_blocks_and_crossing_edges (void)
{
  vec<edge> crossing_edges = vNULL;
  basic_block bb;
  edge e;
  edge_iterator ei;

  /* Mark which partition (hot/cold) each basic block belongs in.  */
  FOR_EACH_BB (bb)
    {
      if (probably_never_executed_bb_p (cfun, bb))
	BB_SET_PARTITION (bb, BB_COLD_PARTITION);
      else
	BB_SET_PARTITION (bb, BB_HOT_PARTITION);
    }

  /* The format of .gcc_except_table does not allow landing pads to
     be in a different partition as the throw.  Fix this by either
     moving or duplicating the landing pads.  */
  if (cfun->eh->lp_array)
    {
      unsigned i;
      eh_landing_pad lp;

      FOR_EACH_VEC_ELT (*cfun->eh->lp_array, i, lp)
	{
	  bool all_same, all_diff;

	  if (lp == NULL
	      || lp->landing_pad == NULL_RTX
	      || !LABEL_P (lp->landing_pad))
	    continue;

	  all_same = all_diff = true;
	  bb = BLOCK_FOR_INSN (lp->landing_pad);
	  FOR_EACH_EDGE (e, ei, bb->preds)
	    {
	      gcc_assert (e->flags & EDGE_EH);
	      if (BB_PARTITION (bb) == BB_PARTITION (e->src))
		all_diff = false;
	      else
		all_same = false;
	    }

	  if (all_same)
	    ;
	  else if (all_diff)
	    {
	      int which = BB_PARTITION (bb);
	      which ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
	      BB_SET_PARTITION (bb, which);
	    }
	  else
	    fix_up_crossing_landing_pad (lp, bb);
	}
    }

  /* Mark every edge that crosses between sections.  */

  FOR_EACH_BB (bb)
    FOR_EACH_EDGE (e, ei, bb->succs)
      {
	unsigned int flags = e->flags;

        /* We should never have EDGE_CROSSING set yet.  */
	gcc_checking_assert ((flags & EDGE_CROSSING) == 0);

	if (e->src != ENTRY_BLOCK_PTR
	    && e->dest != EXIT_BLOCK_PTR
	    && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
	  {
	    crossing_edges.safe_push (e);
	    flags |= EDGE_CROSSING;
	  }

	/* Now that we've split eh edges as appropriate, allow landing pads
	   to be merged with the post-landing pads.  */
	flags &= ~EDGE_PRESERVE;

	e->flags = flags;
      }

  return crossing_edges;
}

/* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru.  */

static void
set_edge_can_fallthru_flag (void)
{
  basic_block bb;

  FOR_EACH_BB (bb)
    {
      edge e;
      edge_iterator ei;

      FOR_EACH_EDGE (e, ei, bb->succs)
	{
	  e->flags &= ~EDGE_CAN_FALLTHRU;

	  /* The FALLTHRU edge is also CAN_FALLTHRU edge.  */
	  if (e->flags & EDGE_FALLTHRU)
	    e->flags |= EDGE_CAN_FALLTHRU;
	}

      /* If the BB ends with an invertible condjump all (2) edges are
	 CAN_FALLTHRU edges.  */
      if (EDGE_COUNT (bb->succs) != 2)
	continue;
      if (!any_condjump_p (BB_END (bb)))
	continue;
      if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
	continue;
      invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0);
      EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
      EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
    }
}

/* If any destination of a crossing edge does not have a label, add label;
   Convert any easy fall-through crossing edges to unconditional jumps.  */

static void
add_labels_and_missing_jumps (vec<edge> crossing_edges)
{
  size_t i;
  edge e;

  FOR_EACH_VEC_ELT (crossing_edges, i, e)
    {
      basic_block src = e->src;
      basic_block dest = e->dest;
      rtx label, new_jump;

      if (dest == EXIT_BLOCK_PTR)
	continue;

      /* Make sure dest has a label.  */
      label = block_label (dest);

      /* Nothing to do for non-fallthru edges.  */
      if (src == ENTRY_BLOCK_PTR)
	continue;
      if ((e->flags & EDGE_FALLTHRU) == 0)
	continue;

      /* If the block does not end with a control flow insn, then we
	 can trivially add a jump to the end to fixup the crossing.
	 Otherwise the jump will have to go in a new bb, which will
	 be handled by fix_up_fall_thru_edges function.  */
      if (control_flow_insn_p (BB_END (src)))
	continue;

      /* Make sure there's only one successor.  */
      gcc_assert (single_succ_p (src));

      new_jump = emit_jump_insn_after (gen_jump (label), BB_END (src));
      BB_END (src) = new_jump;
      JUMP_LABEL (new_jump) = label;
      LABEL_NUSES (label) += 1;

      emit_barrier_after_bb (src);

      /* Mark edge as non-fallthru.  */
      e->flags &= ~EDGE_FALLTHRU;
    }
}

/* Find any bb's where the fall-through edge is a crossing edge (note that
   these bb's must also contain a conditional jump or end with a call
   instruction; we've already dealt with fall-through edges for blocks
   that didn't have a conditional jump or didn't end with call instruction
   in the call to add_labels_and_missing_jumps).  Convert the fall-through
   edge to non-crossing edge by inserting a new bb to fall-through into.
   The new bb will contain an unconditional jump (crossing edge) to the
   original fall through destination.  */

static void
fix_up_fall_thru_edges (void)
{
  basic_block cur_bb;
  basic_block new_bb;
  edge succ1;
  edge succ2;
  edge fall_thru;
  edge cond_jump = NULL;
  edge e;
  bool cond_jump_crosses;
  int invert_worked;
  rtx old_jump;
  rtx fall_thru_label;

  FOR_EACH_BB (cur_bb)
    {
      fall_thru = NULL;
      if (EDGE_COUNT (cur_bb->succs) > 0)
	succ1 = EDGE_SUCC (cur_bb, 0);
      else
	succ1 = NULL;

      if (EDGE_COUNT (cur_bb->succs) > 1)
	succ2 = EDGE_SUCC (cur_bb, 1);
      else
	succ2 = NULL;

      /* Find the fall-through edge.  */

      if (succ1
	  && (succ1->flags & EDGE_FALLTHRU))
	{
	  fall_thru = succ1;
	  cond_jump = succ2;
	}
      else if (succ2
	       && (succ2->flags & EDGE_FALLTHRU))
	{
	  fall_thru = succ2;
	  cond_jump = succ1;
	}
      else if (succ1
	       && (block_ends_with_call_p (cur_bb)
		   || can_throw_internal (BB_END (cur_bb))))
	{
	  edge e;
	  edge_iterator ei;

	  /* Find EDGE_CAN_FALLTHRU edge.  */
	  FOR_EACH_EDGE (e, ei, cur_bb->succs)
	    if (e->flags & EDGE_CAN_FALLTHRU)
	      {
		fall_thru = e;
		break;
	      }
	}

      if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
	{
	  /* Check to see if the fall-thru edge is a crossing edge.  */

	  if (fall_thru->flags & EDGE_CROSSING)
	    {
	      /* The fall_thru edge crosses; now check the cond jump edge, if
		 it exists.  */

	      cond_jump_crosses = true;
	      invert_worked  = 0;
	      old_jump = BB_END (cur_bb);

	      /* Find the jump instruction, if there is one.  */

	      if (cond_jump)
		{
		  if (!(cond_jump->flags & EDGE_CROSSING))
		    cond_jump_crosses = false;

		  /* We know the fall-thru edge crosses; if the cond
		     jump edge does NOT cross, and its destination is the
		     next block in the bb order, invert the jump
		     (i.e. fix it so the fall through does not cross and
		     the cond jump does).  */

		  if (!cond_jump_crosses
		      && cur_bb->aux == cond_jump->dest)
		    {
		      /* Find label in fall_thru block. We've already added
			 any missing labels, so there must be one.  */

		      fall_thru_label = block_label (fall_thru->dest);

		      if (old_jump && JUMP_P (old_jump) && fall_thru_label)
			invert_worked = invert_jump (old_jump,
						     fall_thru_label,0);
		      if (invert_worked)
			{
			  fall_thru->flags &= ~EDGE_FALLTHRU;
			  cond_jump->flags |= EDGE_FALLTHRU;
			  update_br_prob_note (cur_bb);
			  e = fall_thru;
			  fall_thru = cond_jump;
			  cond_jump = e;
			  cond_jump->flags |= EDGE_CROSSING;
			  fall_thru->flags &= ~EDGE_CROSSING;
			}
		    }
		}

	      if (cond_jump_crosses || !invert_worked)
		{
		  /* This is the case where both edges out of the basic
		     block are crossing edges. Here we will fix up the
		     fall through edge. The jump edge will be taken care
		     of later.  The EDGE_CROSSING flag of fall_thru edge
		     is unset before the call to force_nonfallthru
		     function because if a new basic-block is created
		     this edge remains in the current section boundary
		     while the edge between new_bb and the fall_thru->dest
		     becomes EDGE_CROSSING.  */

		  fall_thru->flags &= ~EDGE_CROSSING;
		  new_bb = force_nonfallthru (fall_thru);

		  if (new_bb)
		    {
		      new_bb->aux = cur_bb->aux;
		      cur_bb->aux = new_bb;

		      /* Make sure new fall-through bb is in same
			 partition as bb it's falling through from.  */

		      BB_COPY_PARTITION (new_bb, cur_bb);
		      single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
		    }
		  else
		    {
		      /* If a new basic-block was not created; restore
			 the EDGE_CROSSING flag.  */
		      fall_thru->flags |= EDGE_CROSSING;
		    }

		  /* Add barrier after new jump */
		  emit_barrier_after_bb (new_bb ? new_bb : cur_bb);
		}
	    }
	}
    }
}

/* This function checks the destination block of a "crossing jump" to
   see if it has any crossing predecessors that begin with a code label
   and end with an unconditional jump.  If so, it returns that predecessor
   block.  (This is to avoid creating lots of new basic blocks that all
   contain unconditional jumps to the same destination).  */

static basic_block
find_jump_block (basic_block jump_dest)
{
  basic_block source_bb = NULL;
  edge e;
  rtx insn;
  edge_iterator ei;

  FOR_EACH_EDGE (e, ei, jump_dest->preds)
    if (e->flags & EDGE_CROSSING)
      {
	basic_block src = e->src;

	/* Check each predecessor to see if it has a label, and contains
	   only one executable instruction, which is an unconditional jump.
	   If so, we can use it.  */

	if (LABEL_P (BB_HEAD (src)))
	  for (insn = BB_HEAD (src);
	       !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
	       insn = NEXT_INSN (insn))
	    {
	      if (INSN_P (insn)
		  && insn == BB_END (src)
		  && JUMP_P (insn)
		  && !any_condjump_p (insn))
		{
		  source_bb = src;
		  break;
		}
	    }

	if (source_bb)
	  break;
      }

  return source_bb;
}

/* Find all BB's with conditional jumps that are crossing edges;
   insert a new bb and make the conditional jump branch to the new
   bb instead (make the new bb same color so conditional branch won't
   be a 'crossing' edge).  Insert an unconditional jump from the
   new bb to the original destination of the conditional jump.  */

static void
fix_crossing_conditional_branches (void)
{
  basic_block cur_bb;
  basic_block new_bb;
  basic_block dest;
  edge succ1;
  edge succ2;
  edge crossing_edge;
  edge new_edge;
  rtx old_jump;
  rtx set_src;
  rtx old_label = NULL_RTX;
  rtx new_label;

  FOR_EACH_BB (cur_bb)
    {
      crossing_edge = NULL;
      if (EDGE_COUNT (cur_bb->succs) > 0)
	succ1 = EDGE_SUCC (cur_bb, 0);
      else
	succ1 = NULL;

      if (EDGE_COUNT (cur_bb->succs) > 1)
	succ2 = EDGE_SUCC (cur_bb, 1);
      else
	succ2 = NULL;

      /* We already took care of fall-through edges, so only one successor
	 can be a crossing edge.  */

      if (succ1 && (succ1->flags & EDGE_CROSSING))
	crossing_edge = succ1;
      else if (succ2 && (succ2->flags & EDGE_CROSSING))
	crossing_edge = succ2;

      if (crossing_edge)
	{
	  old_jump = BB_END (cur_bb);

	  /* Check to make sure the jump instruction is a
	     conditional jump.  */

	  set_src = NULL_RTX;

	  if (any_condjump_p (old_jump))
	    {
	      if (GET_CODE (PATTERN (old_jump)) == SET)
		set_src = SET_SRC (PATTERN (old_jump));
	      else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
		{
		  set_src = XVECEXP (PATTERN (old_jump), 0,0);
		  if (GET_CODE (set_src) == SET)
		    set_src = SET_SRC (set_src);
		  else
		    set_src = NULL_RTX;
		}
	    }

	  if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
	    {
	      if (GET_CODE (XEXP (set_src, 1)) == PC)
		old_label = XEXP (set_src, 2);
	      else if (GET_CODE (XEXP (set_src, 2)) == PC)
		old_label = XEXP (set_src, 1);

	      /* Check to see if new bb for jumping to that dest has
		 already been created; if so, use it; if not, create
		 a new one.  */

	      new_bb = find_jump_block (crossing_edge->dest);

	      if (new_bb)
		new_label = block_label (new_bb);
	      else
		{
		  basic_block last_bb;
		  rtx new_jump;

		  /* Create new basic block to be dest for
		     conditional jump.  */

		  /* Put appropriate instructions in new bb.  */

		  new_label = gen_label_rtx ();
		  emit_label (new_label);

		  gcc_assert (GET_CODE (old_label) == LABEL_REF);
		  old_label = JUMP_LABEL (old_jump);
		  new_jump = emit_jump_insn (gen_jump (old_label));
		  JUMP_LABEL (new_jump) = old_label;

		  last_bb = EXIT_BLOCK_PTR->prev_bb;
		  new_bb = create_basic_block (new_label, new_jump, last_bb);
		  new_bb->aux = last_bb->aux;
		  last_bb->aux = new_bb;

		  emit_barrier_after_bb (new_bb);

		  /* Make sure new bb is in same partition as source
		     of conditional branch.  */
		  BB_COPY_PARTITION (new_bb, cur_bb);
		}

	      /* Make old jump branch to new bb.  */

	      redirect_jump (old_jump, new_label, 0);

	      /* Remove crossing_edge as predecessor of 'dest'.  */

	      dest = crossing_edge->dest;

	      redirect_edge_succ (crossing_edge, new_bb);

	      /* Make a new edge from new_bb to old dest; new edge
		 will be a successor for new_bb and a predecessor
		 for 'dest'.  */

	      if (EDGE_COUNT (new_bb->succs) == 0)
		new_edge = make_edge (new_bb, dest, 0);
	      else
		new_edge = EDGE_SUCC (new_bb, 0);

	      crossing_edge->flags &= ~EDGE_CROSSING;
	      new_edge->flags |= EDGE_CROSSING;
	    }
	}
    }
}

/* Find any unconditional branches that cross between hot and cold
   sections.  Convert them into indirect jumps instead.  */

static void
fix_crossing_unconditional_branches (void)
{
  basic_block cur_bb;
  rtx last_insn;
  rtx label;
  rtx label_addr;
  rtx indirect_jump_sequence;
  rtx jump_insn = NULL_RTX;
  rtx new_reg;
  rtx cur_insn;
  edge succ;

  FOR_EACH_BB (cur_bb)
    {
      last_insn = BB_END (cur_bb);

      if (EDGE_COUNT (cur_bb->succs) < 1)
	continue;

      succ = EDGE_SUCC (cur_bb, 0);

      /* Check to see if bb ends in a crossing (unconditional) jump.  At
	 this point, no crossing jumps should be conditional.  */

      if (JUMP_P (last_insn)
	  && (succ->flags & EDGE_CROSSING))
	{
	  gcc_assert (!any_condjump_p (last_insn));

	  /* Make sure the jump is not already an indirect or table jump.  */

	  if (!computed_jump_p (last_insn)
	      && !tablejump_p (last_insn, NULL, NULL))
	    {
	      /* We have found a "crossing" unconditional branch.  Now
		 we must convert it to an indirect jump.  First create
		 reference of label, as target for jump.  */

	      label = JUMP_LABEL (last_insn);
	      label_addr = gen_rtx_LABEL_REF (Pmode, label);
	      LABEL_NUSES (label) += 1;

	      /* Get a register to use for the indirect jump.  */

	      new_reg = gen_reg_rtx (Pmode);

	      /* Generate indirect the jump sequence.  */

	      start_sequence ();
	      emit_move_insn (new_reg, label_addr);
	      emit_indirect_jump (new_reg);
	      indirect_jump_sequence = get_insns ();
	      end_sequence ();

	      /* Make sure every instruction in the new jump sequence has
		 its basic block set to be cur_bb.  */

	      for (cur_insn = indirect_jump_sequence; cur_insn;
		   cur_insn = NEXT_INSN (cur_insn))
		{
		  if (!BARRIER_P (cur_insn))
		    BLOCK_FOR_INSN (cur_insn) = cur_bb;
		  if (JUMP_P (cur_insn))
		    jump_insn = cur_insn;
		}

	      /* Insert the new (indirect) jump sequence immediately before
		 the unconditional jump, then delete the unconditional jump.  */

	      emit_insn_before (indirect_jump_sequence, last_insn);
	      delete_insn (last_insn);

	      /* Make BB_END for cur_bb be the jump instruction (NOT the
		 barrier instruction at the end of the sequence...).  */

	      BB_END (cur_bb) = jump_insn;
	    }
	}
    }
}

/* Add REG_CROSSING_JUMP note to all crossing jump insns.  */

static void
add_reg_crossing_jump_notes (void)
{
  basic_block bb;
  edge e;
  edge_iterator ei;

  FOR_EACH_BB (bb)
    FOR_EACH_EDGE (e, ei, bb->succs)
      if ((e->flags & EDGE_CROSSING)
	  && JUMP_P (BB_END (e->src)))
	add_reg_note (BB_END (e->src), REG_CROSSING_JUMP, NULL_RTX);
}

/* Verify, in the basic block chain, that there is at most one switch
   between hot/cold partitions. This is modelled on
   rtl_verify_flow_info_1, but it cannot go inside that function
   because this condition will not be true until after
   reorder_basic_blocks is called.  */

static void
verify_hot_cold_block_grouping (void)
{
  basic_block bb;
  int err = 0;
  bool switched_sections = false;
  int current_partition = 0;

  FOR_EACH_BB (bb)
    {
      if (!current_partition)
	current_partition = BB_PARTITION (bb);
      if (BB_PARTITION (bb) != current_partition)
	{
	  if (switched_sections)
	    {
	      error ("multiple hot/cold transitions found (bb %i)",
		     bb->index);
	      err = 1;
	    }
	  else
	    {
	      switched_sections = true;
	      current_partition = BB_PARTITION (bb);
	    }
	}
    }

  gcc_assert(!err);
}

/* Reorder basic blocks.  The main entry point to this file.  FLAGS is
   the set of flags to pass to cfg_layout_initialize().  */

static void
reorder_basic_blocks (void)
{
  int n_traces;
  int i;
  struct trace *traces;

  gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);

  if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
    return;

  set_edge_can_fallthru_flag ();
  mark_dfs_back_edges ();

  /* We are estimating the length of uncond jump insn only once since the code
     for getting the insn length always returns the minimal length now.  */
  if (uncond_jump_length == 0)
    uncond_jump_length = get_uncond_jump_length ();

  /* We need to know some information for each basic block.  */
  array_size = GET_ARRAY_SIZE (last_basic_block);
  bbd = XNEWVEC (bbro_basic_block_data, array_size);
  for (i = 0; i < array_size; i++)
    {
      bbd[i].start_of_trace = -1;
      bbd[i].end_of_trace = -1;
      bbd[i].in_trace = -1;
      bbd[i].visited = 0;
      bbd[i].heap = NULL;
      bbd[i].node = NULL;
    }

  traces = XNEWVEC (struct trace, n_basic_blocks);
  n_traces = 0;
  find_traces (&n_traces, traces);
  connect_traces (n_traces, traces);
  FREE (traces);
  FREE (bbd);

  relink_block_chain (/*stay_in_cfglayout_mode=*/true);

  if (dump_file)
    {
      if (dump_flags & TDF_DETAILS)
	dump_reg_info (dump_file);
      dump_flow_info (dump_file, dump_flags);
    }

  if (flag_reorder_blocks_and_partition)
    verify_hot_cold_block_grouping ();
}

/* Determine which partition the first basic block in the function
   belongs to, then find the first basic block in the current function
   that belongs to a different section, and insert a
   NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
   instruction stream.  When writing out the assembly code,
   encountering this note will make the compiler switch between the
   hot and cold text sections.  */

static void
insert_section_boundary_note (void)
{
  basic_block bb;
  rtx new_note;
  int first_partition = 0;

  if (!flag_reorder_blocks_and_partition)
    return;

  FOR_EACH_BB (bb)
    {
      if (!first_partition)
	first_partition = BB_PARTITION (bb);
      if (BB_PARTITION (bb) != first_partition)
	{
	  new_note = emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS,
				       BB_HEAD (bb));
	  /* ??? This kind of note always lives between basic blocks,
	     but add_insn_before will set BLOCK_FOR_INSN anyway.  */
	  BLOCK_FOR_INSN (new_note) = NULL;
	  break;
	}
    }
}

static bool
gate_handle_reorder_blocks (void)
{
  if (targetm.cannot_modify_jumps_p ())
    return false;
  return (optimize > 0
	  && (flag_reorder_blocks || flag_reorder_blocks_and_partition));
}

static unsigned int
rest_of_handle_reorder_blocks (void)
{
  basic_block bb;

  /* Last attempt to optimize CFG, as scheduling, peepholing and insn
     splitting possibly introduced more crossjumping opportunities.  */
  cfg_layout_initialize (CLEANUP_EXPENSIVE);

  reorder_basic_blocks ();
  cleanup_cfg (CLEANUP_EXPENSIVE);

  FOR_EACH_BB (bb)
    if (bb->next_bb != EXIT_BLOCK_PTR)
      bb->aux = bb->next_bb;
  cfg_layout_finalize ();

  /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes.  */
  insert_section_boundary_note ();
  return 0;
}

struct rtl_opt_pass pass_reorder_blocks =
{
 {
  RTL_PASS,
  "bbro",                               /* name */
  OPTGROUP_NONE,                        /* optinfo_flags */
  gate_handle_reorder_blocks,           /* gate */
  rest_of_handle_reorder_blocks,        /* execute */
  NULL,                                 /* sub */
  NULL,                                 /* next */
  0,                                    /* static_pass_number */
  TV_REORDER_BLOCKS,                    /* tv_id */
  0,                                    /* properties_required */
  0,                                    /* properties_provided */
  0,                                    /* properties_destroyed */
  0,                                    /* todo_flags_start */
  TODO_verify_rtl_sharing,              /* todo_flags_finish */
 }
};

/* Duplicate the blocks containing computed gotos.  This basically unfactors
   computed gotos that were factored early on in the compilation process to
   speed up edge based data flow.  We used to not unfactoring them again,
   which can seriously pessimize code with many computed jumps in the source
   code, such as interpreters.  See e.g. PR15242.  */

static bool
gate_duplicate_computed_gotos (void)
{
  if (targetm.cannot_modify_jumps_p ())
    return false;
  return (optimize > 0
	  && flag_expensive_optimizations
	  && ! optimize_function_for_size_p (cfun));
}


static unsigned int
duplicate_computed_gotos (void)
{
  basic_block bb, new_bb;
  bitmap candidates;
  int max_size;

  if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
    return 0;

  clear_bb_flags ();
  cfg_layout_initialize (0);

  /* We are estimating the length of uncond jump insn only once
     since the code for getting the insn length always returns
     the minimal length now.  */
  if (uncond_jump_length == 0)
    uncond_jump_length = get_uncond_jump_length ();

  max_size
    = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
  candidates = BITMAP_ALLOC (NULL);

  /* Look for blocks that end in a computed jump, and see if such blocks
     are suitable for unfactoring.  If a block is a candidate for unfactoring,
     mark it in the candidates.  */
  FOR_EACH_BB (bb)
    {
      rtx insn;
      edge e;
      edge_iterator ei;
      int size, all_flags;

      /* Build the reorder chain for the original order of blocks.  */
      if (bb->next_bb != EXIT_BLOCK_PTR)
	bb->aux = bb->next_bb;

      /* Obviously the block has to end in a computed jump.  */
      if (!computed_jump_p (BB_END (bb)))
	continue;

      /* Only consider blocks that can be duplicated.  */
      if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX)
	  || !can_duplicate_block_p (bb))
	continue;

      /* Make sure that the block is small enough.  */
      size = 0;
      FOR_BB_INSNS (bb, insn)
	if (INSN_P (insn))
	  {
	    size += get_attr_min_length (insn);
	    if (size > max_size)
	       break;
	  }
      if (size > max_size)
	continue;

      /* Final check: there must not be any incoming abnormal edges.  */
      all_flags = 0;
      FOR_EACH_EDGE (e, ei, bb->preds)
	all_flags |= e->flags;
      if (all_flags & EDGE_COMPLEX)
	continue;

      bitmap_set_bit (candidates, bb->index);
    }

  /* Nothing to do if there is no computed jump here.  */
  if (bitmap_empty_p (candidates))
    goto done;

  /* Duplicate computed gotos.  */
  FOR_EACH_BB (bb)
    {
      if (bb->flags & BB_VISITED)
	continue;

      bb->flags |= BB_VISITED;

      /* BB must have one outgoing edge.  That edge must not lead to
	 the exit block or the next block.
	 The destination must have more than one predecessor.  */
      if (!single_succ_p (bb)
	  || single_succ (bb) == EXIT_BLOCK_PTR
	  || single_succ (bb) == bb->next_bb
	  || single_pred_p (single_succ (bb)))
	continue;

      /* The successor block has to be a duplication candidate.  */
      if (!bitmap_bit_p (candidates, single_succ (bb)->index))
	continue;

      new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb);
      new_bb->aux = bb->aux;
      bb->aux = new_bb;
      new_bb->flags |= BB_VISITED;
    }

done:
  cfg_layout_finalize ();

  BITMAP_FREE (candidates);
  return 0;
}

struct rtl_opt_pass pass_duplicate_computed_gotos =
{
 {
  RTL_PASS,
  "compgotos",                          /* name */
  OPTGROUP_NONE,                        /* optinfo_flags */
  gate_duplicate_computed_gotos,        /* gate */
  duplicate_computed_gotos,             /* execute */
  NULL,                                 /* sub */
  NULL,                                 /* next */
  0,                                    /* static_pass_number */
  TV_REORDER_BLOCKS,                    /* tv_id */
  0,                                    /* properties_required */
  0,                                    /* properties_provided */
  0,                                    /* properties_destroyed */
  0,                                    /* todo_flags_start */
  TODO_verify_rtl_sharing,/* todo_flags_finish */
 }
};

static bool
gate_handle_partition_blocks (void)
{
  /* The optimization to partition hot/cold basic blocks into separate
     sections of the .o file does not work well with linkonce or with
     user defined section attributes.  Don't call it if either case
     arises.  */
  return (flag_reorder_blocks_and_partition
          && optimize
	  /* See gate_handle_reorder_blocks.  We should not partition if
	     we are going to omit the reordering.  */
	  && optimize_function_for_speed_p (cfun)
	  && !DECL_ONE_ONLY (current_function_decl)
	  && !user_defined_section_attribute);
}

/* This function is the main 'entrance' for the optimization that
   partitions hot and cold basic blocks into separate sections of the
   .o file (to improve performance and cache locality).  Ideally it
   would be called after all optimizations that rearrange the CFG have
   been called.  However part of this optimization may introduce new
   register usage, so it must be called before register allocation has
   occurred.  This means that this optimization is actually called
   well before the optimization that reorders basic blocks (see
   function above).

   This optimization checks the feedback information to determine
   which basic blocks are hot/cold, updates flags on the basic blocks
   to indicate which section they belong in.  This information is
   later used for writing out sections in the .o file.  Because hot
   and cold sections can be arbitrarily large (within the bounds of
   memory), far beyond the size of a single function, it is necessary
   to fix up all edges that cross section boundaries, to make sure the
   instructions used can actually span the required distance.  The
   fixes are described below.

   Fall-through edges must be changed into jumps; it is not safe or
   legal to fall through across a section boundary.  Whenever a
   fall-through edge crossing a section boundary is encountered, a new
   basic block is inserted (in the same section as the fall-through
   source), and the fall through edge is redirected to the new basic
   block.  The new basic block contains an unconditional jump to the
   original fall-through target.  (If the unconditional jump is
   insufficient to cross section boundaries, that is dealt with a
   little later, see below).

   In order to deal with architectures that have short conditional
   branches (which cannot span all of memory) we take any conditional
   jump that attempts to cross a section boundary and add a level of
   indirection: it becomes a conditional jump to a new basic block, in
   the same section.  The new basic block contains an unconditional
   jump to the original target, in the other section.

   For those architectures whose unconditional branch is also
   incapable of reaching all of memory, those unconditional jumps are
   converted into indirect jumps, through a register.

   IMPORTANT NOTE: This optimization causes some messy interactions
   with the cfg cleanup optimizations; those optimizations want to
   merge blocks wherever possible, and to collapse indirect jump
   sequences (change "A jumps to B jumps to C" directly into "A jumps
   to C").  Those optimizations can undo the jump fixes that
   partitioning is required to make (see above), in order to ensure
   that jumps attempting to cross section boundaries are really able
   to cover whatever distance the jump requires (on many architectures
   conditional or unconditional jumps are not able to reach all of
   memory).  Therefore tests have to be inserted into each such
   optimization to make sure that it does not undo stuff necessary to
   cross partition boundaries.  This would be much less of a problem
   if we could perform this optimization later in the compilation, but
   unfortunately the fact that we may need to create indirect jumps
   (through registers) requires that this optimization be performed
   before register allocation.

   Hot and cold basic blocks are partitioned and put in separate
   sections of the .o file, to reduce paging and improve cache
   performance (hopefully).  This can result in bits of code from the
   same function being widely separated in the .o file.  However this
   is not obvious to the current bb structure.  Therefore we must take
   care to ensure that: 1). There are no fall_thru edges that cross
   between sections; 2). For those architectures which have "short"
   conditional branches, all conditional branches that attempt to
   cross between sections are converted to unconditional branches;
   and, 3). For those architectures which have "short" unconditional
   branches, all unconditional branches that attempt to cross between
   sections are converted to indirect jumps.

   The code for fixing up fall_thru edges that cross between hot and
   cold basic blocks does so by creating new basic blocks containing
   unconditional branches to the appropriate label in the "other"
   section.  The new basic block is then put in the same (hot or cold)
   section as the original conditional branch, and the fall_thru edge
   is modified to fall into the new basic block instead.  By adding
   this level of indirection we end up with only unconditional branches
   crossing between hot and cold sections.

   Conditional branches are dealt with by adding a level of indirection.
   A new basic block is added in the same (hot/cold) section as the
   conditional branch, and the conditional branch is retargeted to the
   new basic block.  The new basic block contains an unconditional branch
   to the original target of the conditional branch (in the other section).

   Unconditional branches are dealt with by converting them into
   indirect jumps.  */

static unsigned
partition_hot_cold_basic_blocks (void)
{
  vec<edge> crossing_edges;

  if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
    return 0;

  df_set_flags (DF_DEFER_INSN_RESCAN);

  crossing_edges = find_rarely_executed_basic_blocks_and_crossing_edges ();
  if (!crossing_edges.exists ())
    return 0;

  /* Make sure the source of any crossing edge ends in a jump and the
     destination of any crossing edge has a label.  */
  add_labels_and_missing_jumps (crossing_edges);

  /* Convert all crossing fall_thru edges to non-crossing fall
     thrus to unconditional jumps (that jump to the original fall
     through dest).  */
  fix_up_fall_thru_edges ();

  /* If the architecture does not have conditional branches that can
     span all of memory, convert crossing conditional branches into
     crossing unconditional branches.  */
  if (!HAS_LONG_COND_BRANCH)
    fix_crossing_conditional_branches ();

  /* If the architecture does not have unconditional branches that
     can span all of memory, convert crossing unconditional branches
     into indirect jumps.  Since adding an indirect jump also adds
     a new register usage, update the register usage information as
     well.  */
  if (!HAS_LONG_UNCOND_BRANCH)
    fix_crossing_unconditional_branches ();

  add_reg_crossing_jump_notes ();

  /* Clear bb->aux fields that the above routines were using.  */
  clear_aux_for_blocks ();

  crossing_edges.release ();

  /* ??? FIXME: DF generates the bb info for a block immediately.
     And by immediately, I mean *during* creation of the block.

	#0  df_bb_refs_collect
	#1  in df_bb_refs_record
	#2  in create_basic_block_structure

     Which means that the bb_has_eh_pred test in df_bb_refs_collect
     will *always* fail, because no edges can have been added to the
     block yet.  Which of course means we don't add the right 
     artificial refs, which means we fail df_verify (much) later.

     Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
     that we also shouldn't grab data from the new blocks those new
     insns are in either.  In this way one can create the block, link
     it up properly, and have everything Just Work later, when deferred
     insns are processed.

     In the meantime, we have no other option but to throw away all
     of the DF data and recompute it all.  */
  if (cfun->eh->lp_array)
    {
      df_finish_pass (true);
      df_scan_alloc (NULL);
      df_scan_blocks ();
      /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
	 data.  We blindly generated all of them when creating the new
	 landing pad.  Delete those assignments we don't use.  */
      df_set_flags (DF_LR_RUN_DCE);
      df_analyze ();
    }

  return TODO_verify_flow | TODO_verify_rtl_sharing;
}

struct rtl_opt_pass pass_partition_blocks =
{
 {
  RTL_PASS,
  "bbpart",                             /* name */
  OPTGROUP_NONE,                        /* optinfo_flags */
  gate_handle_partition_blocks,         /* gate */
  partition_hot_cold_basic_blocks,      /* execute */
  NULL,                                 /* sub */
  NULL,                                 /* next */
  0,                                    /* static_pass_number */
  TV_REORDER_BLOCKS,                    /* tv_id */
  PROP_cfglayout,                       /* properties_required */
  0,                                    /* properties_provided */
  0,                                    /* properties_destroyed */
  0,                                    /* todo_flags_start */
  0					/* todo_flags_finish */
 }
};