llvm.org GIT mirror llvm / release_80 docs / Coroutines.rst
release_80

Tree @release_80 (Download .tar.gz)

Coroutines.rst @release_80

e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
315f732
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
f202abf
e48bbc4
 
 
bce16c6
e48bbc4
 
b6ae34d
e48bbc4
 
 
 
 
 
 
 
 
bce16c6
e48bbc4
 
 
2d33745
e48bbc4
 
 
 
 
b6ae34d
 
 
 
 
 
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
f202abf
e48bbc4
 
 
 
 
 
 
f202abf
e48bbc4
 
 
bce16c6
e48bbc4
b6ae34d
c53e16c
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
b6ae34d
 
 
e48bbc4
f202abf
e48bbc4
 
bce16c6
b6ae34d
 
e48bbc4
 
 
 
 
b6ae34d
 
e48bbc4
 
 
 
 
f202abf
e48bbc4
 
bce16c6
e48bbc4
 
 
 
 
 
 
 
 
af5d051
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
315f732
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
f202abf
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5b9e6bf
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
f202abf
e48bbc4
 
 
f202abf
e48bbc4
 
 
 
 
f202abf
e48bbc4
 
 
 
 
 
 
 
 
 
 
b6ae34d
 
e48bbc4
 
 
 
f202abf
e48bbc4
 
 
 
 
bce16c6
b6ae34d
 
af5d051
e48bbc4
 
af5d051
 
b6ae34d
 
e48bbc4
 
af5d051
e48bbc4
 
 
 
 
 
bce16c6
e48bbc4
 
 
2d33745
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
af5d051
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
315f732
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
315f732
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
f202abf
e48bbc4
 
 
 
 
b6ae34d
bce16c6
e48bbc4
b6ae34d
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
b6ae34d
e48bbc4
 
 
 
b6ae34d
e48bbc4
 
 
 
b6ae34d
 
e48bbc4
b6ae34d
 
e48bbc4
 
 
 
 
b6ae34d
 
 
 
e48bbc4
af5d051
e48bbc4
 
 
 
 
 
 
bce16c6
e48bbc4
 
 
 
 
 
 
 
 
 
 
bce16c6
 
 
 
 
e48bbc4
 
 
 
f202abf
e48bbc4
 
bce16c6
e48bbc4
 
 
 
 
 
 
 
 
 
 
f202abf
e48bbc4
 
bce16c6
e48bbc4
 
 
 
 
 
 
 
 
b6ae34d
e48bbc4
 
 
 
b6ae34d
bc6790d
e48bbc4
 
 
 
b6ae34d
 
e48bbc4
 
 
 
af5d051
b6ae34d
 
bd0032e
e48bbc4
 
 
f202abf
e48bbc4
 
bce16c6
b6ae34d
 
e48bbc4
 
 
 
 
 
 
b6ae34d
 
e48bbc4
78cbb42
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
b6ae34d
 
 
 
 
 
 
 
 
 
 
 
 
 
 
bce16c6
 
b6ae34d
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
bce16c6
 
 
 
b6ae34d
 
 
e48bbc4
 
 
 
b6ae34d
 
 
 
 
 
e48bbc4
 
 
 
 
 
 
2d33745
e48bbc4
 
 
 
 
2d33745
e48bbc4
 
 
 
 
2d33745
 
 
 
e48bbc4
 
2d33745
 
e48bbc4
 
 
2d33745
 
 
e48bbc4
2d33745
 
 
e48bbc4
 
2d33745
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
f202abf
e48bbc4
2d33745
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
f202abf
e48bbc4
 
 
 
 
 
 
 
f202abf
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
f202abf
e48bbc4
 
f202abf
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
af5d051
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
315f732
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5b9e6bf
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
b6ae34d
 
 
 
e48bbc4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
   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
=====================================
Coroutines in LLVM
=====================================

.. contents::
   :local:
   :depth: 3

.. warning::
  This is a work in progress. Compatibility across LLVM releases is not 
  guaranteed.

Introduction
============

.. _coroutine handle:

LLVM coroutines are functions that have one or more `suspend points`_. 
When a suspend point is reached, the execution of a coroutine is suspended and
control is returned back to its caller. A suspended coroutine can be resumed 
to continue execution from the last suspend point or it can be destroyed. 

In the following example, we call function `f` (which may or may not be a 
coroutine itself) that returns a handle to a suspended coroutine 
(**coroutine handle**) that is used by `main` to resume the coroutine twice and
then destroy it:

.. code-block:: llvm

  define i32 @main() {
  entry:
    %hdl = call i8* @f(i32 4)
    call void @llvm.coro.resume(i8* %hdl)
    call void @llvm.coro.resume(i8* %hdl)
    call void @llvm.coro.destroy(i8* %hdl)
    ret i32 0
  }

.. _coroutine frame:

In addition to the function stack frame which exists when a coroutine is 
executing, there is an additional region of storage that contains objects that 
keep the coroutine state when a coroutine is suspended. This region of storage
is called **coroutine frame**. It is created when a coroutine is called and 
destroyed when a coroutine runs to completion or destroyed by a call to 
the `coro.destroy`_ intrinsic. 

An LLVM coroutine is represented as an LLVM function that has calls to
`coroutine intrinsics`_ defining the structure of the coroutine.
After lowering, a coroutine is split into several
functions that represent three different ways of how control can enter the 
coroutine: 

1. a ramp function, which represents an initial invocation of the coroutine that
   creates the coroutine frame and executes the coroutine code until it 
   encounters a suspend point or reaches the end of the function;

2. a coroutine resume function that is invoked when the coroutine is resumed;

3. a coroutine destroy function that is invoked when the coroutine is destroyed.

.. note:: Splitting out resume and destroy functions are just one of the 
   possible ways of lowering the coroutine. We chose it for initial 
   implementation as it matches closely the mental model and results in 
   reasonably nice code.

Coroutines by Example
=====================

Coroutine Representation
------------------------

Let's look at an example of an LLVM coroutine with the behavior sketched
by the following pseudo-code.

.. code-block:: c++

  void *f(int n) {
     for(;;) {
       print(n++);
       <suspend> // returns a coroutine handle on first suspend
     }     
  } 

This coroutine calls some function `print` with value `n` as an argument and
suspends execution. Every time this coroutine resumes, it calls `print` again with an argument one bigger than the last time. This coroutine never completes by itself and must be destroyed explicitly. If we use this coroutine with 
a `main` shown in the previous section. It will call `print` with values 4, 5 
and 6 after which the coroutine will be destroyed.

The LLVM IR for this coroutine looks like this:

.. code-block:: llvm

  define i8* @f(i32 %n) {
  entry:
    %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
    %size = call i32 @llvm.coro.size.i32()
    %alloc = call i8* @malloc(i32 %size)
    %hdl = call noalias i8* @llvm.coro.begin(token %id, i8* %alloc)
    br label %loop
  loop:
    %n.val = phi i32 [ %n, %entry ], [ %inc, %loop ]
    %inc = add nsw i32 %n.val, 1
    call void @print(i32 %n.val)
    %0 = call i8 @llvm.coro.suspend(token none, i1 false)
    switch i8 %0, label %suspend [i8 0, label %loop
                                  i8 1, label %cleanup]
  cleanup:
    %mem = call i8* @llvm.coro.free(token %id, i8* %hdl)
    call void @free(i8* %mem)
    br label %suspend
  suspend:
    %unused = call i1 @llvm.coro.end(i8* %hdl, i1 false)
    ret i8* %hdl
  }

The `entry` block establishes the coroutine frame. The `coro.size`_ intrinsic is
lowered to a constant representing the size required for the coroutine frame. 
The `coro.begin`_ intrinsic initializes the coroutine frame and returns the 
coroutine handle. The second parameter of `coro.begin` is given a block of memory 
to be used if the coroutine frame needs to be allocated dynamically.
The `coro.id`_ intrinsic serves as coroutine identity useful in cases when the
`coro.begin`_ intrinsic get duplicated by optimization passes such as 
jump-threading.

The `cleanup` block destroys the coroutine frame. The `coro.free`_ intrinsic, 
given the coroutine handle, returns a pointer of the memory block to be freed or
`null` if the coroutine frame was not allocated dynamically. The `cleanup` 
block is entered when coroutine runs to completion by itself or destroyed via
call to the `coro.destroy`_ intrinsic.

The `suspend` block contains code to be executed when coroutine runs to 
completion or suspended. The `coro.end`_ intrinsic marks the point where 
a coroutine needs to return control back to the caller if it is not an initial 
invocation of the coroutine. 

The `loop` blocks represents the body of the coroutine. The `coro.suspend`_ 
intrinsic in combination with the following switch indicates what happens to 
control flow when a coroutine is suspended (default case), resumed (case 0) or 
destroyed (case 1).

Coroutine Transformation
------------------------

One of the steps of coroutine lowering is building the coroutine frame. The
def-use chains are analyzed to determine which objects need be kept alive across
suspend points. In the coroutine shown in the previous section, use of virtual register 
`%n.val` is separated from the definition by a suspend point, therefore, it 
cannot reside on the stack frame since the latter goes away once the coroutine 
is suspended and control is returned back to the caller. An i32 slot is 
allocated in the coroutine frame and `%n.val` is spilled and reloaded from that
slot as needed.

We also store addresses of the resume and destroy functions so that the 
`coro.resume` and `coro.destroy` intrinsics can resume and destroy the coroutine
when its identity cannot be determined statically at compile time. For our 
example, the coroutine frame will be:

.. code-block:: llvm

  %f.frame = type { void (%f.frame*)*, void (%f.frame*)*, i32 }

After resume and destroy parts are outlined, function `f` will contain only the 
code responsible for creation and initialization of the coroutine frame and 
execution of the coroutine until a suspend point is reached:

.. code-block:: llvm

  define i8* @f(i32 %n) {
  entry:
    %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
    %alloc = call noalias i8* @malloc(i32 24)
    %0 = call noalias i8* @llvm.coro.begin(token %id, i8* %alloc)
    %frame = bitcast i8* %0 to %f.frame*
    %1 = getelementptr %f.frame, %f.frame* %frame, i32 0, i32 0
    store void (%f.frame*)* @f.resume, void (%f.frame*)** %1
    %2 = getelementptr %f.frame, %f.frame* %frame, i32 0, i32 1
    store void (%f.frame*)* @f.destroy, void (%f.frame*)** %2
   
    %inc = add nsw i32 %n, 1
    %inc.spill.addr = getelementptr inbounds %f.Frame, %f.Frame* %FramePtr, i32 0, i32 2
    store i32 %inc, i32* %inc.spill.addr
    call void @print(i32 %n)
   
    ret i8* %frame
  }

Outlined resume part of the coroutine will reside in function `f.resume`:

.. code-block:: llvm

  define internal fastcc void @f.resume(%f.frame* %frame.ptr.resume) {
  entry:
    %inc.spill.addr = getelementptr %f.frame, %f.frame* %frame.ptr.resume, i64 0, i32 2
    %inc.spill = load i32, i32* %inc.spill.addr, align 4
    %inc = add i32 %n.val, 1
    store i32 %inc, i32* %inc.spill.addr, align 4
    tail call void @print(i32 %inc)
    ret void
  }

Whereas function `f.destroy` will contain the cleanup code for the coroutine:

.. code-block:: llvm

  define internal fastcc void @f.destroy(%f.frame* %frame.ptr.destroy) {
  entry:
    %0 = bitcast %f.frame* %frame.ptr.destroy to i8*
    tail call void @free(i8* %0)
    ret void
  }

Avoiding Heap Allocations
-------------------------
 
A particular coroutine usage pattern, which is illustrated by the `main` 
function in the overview section, where a coroutine is created, manipulated and 
destroyed by the same calling function, is common for coroutines implementing
RAII idiom and is suitable for allocation elision optimization which avoid 
dynamic allocation by storing the coroutine frame as a static `alloca` in its 
caller.

In the entry block, we will call `coro.alloc`_ intrinsic that will return `true`
when dynamic allocation is required, and `false` if dynamic allocation is 
elided.

.. code-block:: llvm

  entry:
    %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
    %need.dyn.alloc = call i1 @llvm.coro.alloc(token %id)
    br i1 %need.dyn.alloc, label %dyn.alloc, label %coro.begin
  dyn.alloc:
    %size = call i32 @llvm.coro.size.i32()
    %alloc = call i8* @CustomAlloc(i32 %size)
    br label %coro.begin
  coro.begin:
    %phi = phi i8* [ null, %entry ], [ %alloc, %dyn.alloc ]
    %hdl = call noalias i8* @llvm.coro.begin(token %id, i8* %phi)

In the cleanup block, we will make freeing the coroutine frame conditional on
`coro.free`_ intrinsic. If allocation is elided, `coro.free`_ returns `null`
thus skipping the deallocation code:

.. code-block:: llvm

  cleanup:
    %mem = call i8* @llvm.coro.free(token %id, i8* %hdl)
    %need.dyn.free = icmp ne i8* %mem, null
    br i1 %need.dyn.free, label %dyn.free, label %if.end
  dyn.free:
    call void @CustomFree(i8* %mem)
    br label %if.end
  if.end:
    ...

With allocations and deallocations represented as described as above, after
coroutine heap allocation elision optimization, the resulting main will be:

.. code-block:: llvm

  define i32 @main() {
  entry:
    call void @print(i32 4)
    call void @print(i32 5)
    call void @print(i32 6)
    ret i32 0
  }

Multiple Suspend Points
-----------------------

Let's consider the coroutine that has more than one suspend point:

.. code-block:: c++

  void *f(int n) {
     for(;;) {
       print(n++);
       <suspend>
       print(-n);
       <suspend>
     }
  }

Matching LLVM code would look like (with the rest of the code remaining the same
as the code in the previous section):

.. code-block:: llvm

  loop:
    %n.addr = phi i32 [ %n, %entry ], [ %inc, %loop.resume ]
    call void @print(i32 %n.addr) #4
    %2 = call i8 @llvm.coro.suspend(token none, i1 false)
    switch i8 %2, label %suspend [i8 0, label %loop.resume
                                  i8 1, label %cleanup]
  loop.resume:
    %inc = add nsw i32 %n.addr, 1
    %sub = xor i32 %n.addr, -1
    call void @print(i32 %sub)
    %3 = call i8 @llvm.coro.suspend(token none, i1 false)
    switch i8 %3, label %suspend [i8 0, label %loop
                                  i8 1, label %cleanup]

In this case, the coroutine frame would include a suspend index that will 
indicate at which suspend point the coroutine needs to resume. The resume 
function will use an index to jump to an appropriate basic block and will look 
as follows:

.. code-block:: llvm

  define internal fastcc void @f.Resume(%f.Frame* %FramePtr) {
  entry.Resume:
    %index.addr = getelementptr inbounds %f.Frame, %f.Frame* %FramePtr, i64 0, i32 2
    %index = load i8, i8* %index.addr, align 1
    %switch = icmp eq i8 %index, 0
    %n.addr = getelementptr inbounds %f.Frame, %f.Frame* %FramePtr, i64 0, i32 3
    %n = load i32, i32* %n.addr, align 4
    br i1 %switch, label %loop.resume, label %loop

  loop.resume:
    %sub = xor i32 %n, -1
    call void @print(i32 %sub)
    br label %suspend
  loop:
    %inc = add nsw i32 %n, 1
    store i32 %inc, i32* %n.addr, align 4
    tail call void @print(i32 %inc)
    br label %suspend

  suspend:
    %storemerge = phi i8 [ 0, %loop ], [ 1, %loop.resume ]
    store i8 %storemerge, i8* %index.addr, align 1
    ret void
  }

If different cleanup code needs to get executed for different suspend points, 
a similar switch will be in the `f.destroy` function.

.. note ::

  Using suspend index in a coroutine state and having a switch in `f.resume` and
  `f.destroy` is one of the possible implementation strategies. We explored 
  another option where a distinct `f.resume1`, `f.resume2`, etc. are created for
  every suspend point, and instead of storing an index, the resume and destroy 
  function pointers are updated at every suspend. Early testing showed that the
  current approach is easier on the optimizer than the latter so it is a 
  lowering strategy implemented at the moment.

Distinct Save and Suspend
-------------------------

In the previous example, setting a resume index (or some other state change that 
needs to happen to prepare a coroutine for resumption) happens at the same time as
a suspension of a coroutine. However, in certain cases, it is necessary to control 
when coroutine is prepared for resumption and when it is suspended.

In the following example, a coroutine represents some activity that is driven
by completions of asynchronous operations `async_op1` and `async_op2` which get
a coroutine handle as a parameter and resume the coroutine once async
operation is finished.

.. code-block:: text

  void g() {
     for (;;)
       if (cond()) {
          async_op1(<coroutine-handle>); // will resume once async_op1 completes
          <suspend>
          do_one();
       }
       else {
          async_op2(<coroutine-handle>); // will resume once async_op2 completes
          <suspend>
          do_two();
       }
     }
  }

In this case, coroutine should be ready for resumption prior to a call to 
`async_op1` and `async_op2`. The `coro.save`_ intrinsic is used to indicate a
point when coroutine should be ready for resumption (namely, when a resume index
should be stored in the coroutine frame, so that it can be resumed at the 
correct resume point):

.. code-block:: llvm

  if.true:
    %save1 = call token @llvm.coro.save(i8* %hdl)
    call void @async_op1(i8* %hdl)
    %suspend1 = call i1 @llvm.coro.suspend(token %save1, i1 false)
    switch i8 %suspend1, label %suspend [i8 0, label %resume1
                                         i8 1, label %cleanup]
  if.false:
    %save2 = call token @llvm.coro.save(i8* %hdl)
    call void @async_op2(i8* %hdl)
    %suspend2 = call i1 @llvm.coro.suspend(token %save2, i1 false)
    switch i8 %suspend1, label %suspend [i8 0, label %resume2
                                         i8 1, label %cleanup]

.. _coroutine promise:

Coroutine Promise
-----------------

A coroutine author or a frontend may designate a distinguished `alloca` that can
be used to communicate with the coroutine. This distinguished alloca is called
**coroutine promise** and is provided as the second parameter to the 
`coro.id`_ intrinsic.

The following coroutine designates a 32 bit integer `promise` and uses it to
store the current value produced by a coroutine.

.. code-block:: llvm

  define i8* @f(i32 %n) {
  entry:
    %promise = alloca i32
    %pv = bitcast i32* %promise to i8*
    %id = call token @llvm.coro.id(i32 0, i8* %pv, i8* null, i8* null)
    %need.dyn.alloc = call i1 @llvm.coro.alloc(token %id)
    br i1 %need.dyn.alloc, label %dyn.alloc, label %coro.begin
  dyn.alloc:
    %size = call i32 @llvm.coro.size.i32()
    %alloc = call i8* @malloc(i32 %size)
    br label %coro.begin
  coro.begin:
    %phi = phi i8* [ null, %entry ], [ %alloc, %dyn.alloc ]
    %hdl = call noalias i8* @llvm.coro.begin(token %id, i8* %phi)
    br label %loop
  loop:
    %n.val = phi i32 [ %n, %coro.begin ], [ %inc, %loop ]
    %inc = add nsw i32 %n.val, 1
    store i32 %n.val, i32* %promise
    %0 = call i8 @llvm.coro.suspend(token none, i1 false)
    switch i8 %0, label %suspend [i8 0, label %loop
                                  i8 1, label %cleanup]
  cleanup:
    %mem = call i8* @llvm.coro.free(token %id, i8* %hdl)
    call void @free(i8* %mem)
    br label %suspend
  suspend:
    %unused = call i1 @llvm.coro.end(i8* %hdl, i1 false)
    ret i8* %hdl
  }

A coroutine consumer can rely on the `coro.promise`_ intrinsic to access the
coroutine promise.

.. code-block:: llvm

  define i32 @main() {
  entry:
    %hdl = call i8* @f(i32 4)
    %promise.addr.raw = call i8* @llvm.coro.promise(i8* %hdl, i32 4, i1 false)
    %promise.addr = bitcast i8* %promise.addr.raw to i32*
    %val0 = load i32, i32* %promise.addr
    call void @print(i32 %val0)
    call void @llvm.coro.resume(i8* %hdl)
    %val1 = load i32, i32* %promise.addr
    call void @print(i32 %val1)
    call void @llvm.coro.resume(i8* %hdl)
    %val2 = load i32, i32* %promise.addr
    call void @print(i32 %val2)
    call void @llvm.coro.destroy(i8* %hdl)
    ret i32 0
  }

After example in this section is compiled, result of the compilation will be:

.. code-block:: llvm

  define i32 @main() {
  entry:
    tail call void @print(i32 4)
    tail call void @print(i32 5)
    tail call void @print(i32 6)
    ret i32 0
  }

.. _final:
.. _final suspend:

Final Suspend
-------------

A coroutine author or a frontend may designate a particular suspend to be final,
by setting the second argument of the `coro.suspend`_ intrinsic to `true`.
Such a suspend point has two properties:

* it is possible to check whether a suspended coroutine is at the final suspend
  point via `coro.done`_ intrinsic;

* a resumption of a coroutine stopped at the final suspend point leads to 
  undefined behavior. The only possible action for a coroutine at a final
  suspend point is destroying it via `coro.destroy`_ intrinsic.

From the user perspective, the final suspend point represents an idea of a 
coroutine reaching the end. From the compiler perspective, it is an optimization
opportunity for reducing number of resume points (and therefore switch cases) in
the resume function.

The following is an example of a function that keeps resuming the coroutine
until the final suspend point is reached after which point the coroutine is 
destroyed:

.. code-block:: llvm

  define i32 @main() {
  entry:
    %hdl = call i8* @f(i32 4)
    br label %while
  while:
    call void @llvm.coro.resume(i8* %hdl)
    %done = call i1 @llvm.coro.done(i8* %hdl)
    br i1 %done, label %end, label %while
  end:
    call void @llvm.coro.destroy(i8* %hdl)
    ret i32 0
  }

Usually, final suspend point is a frontend injected suspend point that does not
correspond to any explicitly authored suspend point of the high level language.
For example, for a Python generator that has only one suspend point:

.. code-block:: python

  def coroutine(n):
    for i in range(n):
      yield i

Python frontend would inject two more suspend points, so that the actual code
looks like this:

.. code-block:: c

  void* coroutine(int n) {
    int current_value; 
    <designate current_value to be coroutine promise>
    <SUSPEND> // injected suspend point, so that the coroutine starts suspended
    for (int i = 0; i < n; ++i) {
      current_value = i; <SUSPEND>; // corresponds to "yield i"
    }
    <SUSPEND final=true> // injected final suspend point
  }

and python iterator `__next__` would look like:

.. code-block:: c++

  int __next__(void* hdl) {
    coro.resume(hdl);
    if (coro.done(hdl)) throw StopIteration();
    return *(int*)coro.promise(hdl, 4, false);
  }

Intrinsics
==========

Coroutine Manipulation Intrinsics
---------------------------------

Intrinsics described in this section are used to manipulate an existing
coroutine. They can be used in any function which happen to have a pointer
to a `coroutine frame`_ or a pointer to a `coroutine promise`_.

.. _coro.destroy:

'llvm.coro.destroy' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Syntax:
"""""""

::

      declare void @llvm.coro.destroy(i8* <handle>)

Overview:
"""""""""

The '``llvm.coro.destroy``' intrinsic destroys a suspended
coroutine.

Arguments:
""""""""""

The argument is a coroutine handle to a suspended coroutine.

Semantics:
""""""""""

When possible, the `coro.destroy` intrinsic is replaced with a direct call to 
the coroutine destroy function. Otherwise it is replaced with an indirect call 
based on the function pointer for the destroy function stored in the coroutine
frame. Destroying a coroutine that is not suspended leads to undefined behavior.

.. _coro.resume:

'llvm.coro.resume' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

::

      declare void @llvm.coro.resume(i8* <handle>)

Overview:
"""""""""

The '``llvm.coro.resume``' intrinsic resumes a suspended coroutine.

Arguments:
""""""""""

The argument is a handle to a suspended coroutine.

Semantics:
""""""""""

When possible, the `coro.resume` intrinsic is replaced with a direct call to the
coroutine resume function. Otherwise it is replaced with an indirect call based 
on the function pointer for the resume function stored in the coroutine frame. 
Resuming a coroutine that is not suspended leads to undefined behavior.

.. _coro.done:

'llvm.coro.done' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

::

      declare i1 @llvm.coro.done(i8* <handle>)

Overview:
"""""""""

The '``llvm.coro.done``' intrinsic checks whether a suspended coroutine is at 
the final suspend point or not.

Arguments:
""""""""""

The argument is a handle to a suspended coroutine.

Semantics:
""""""""""

Using this intrinsic on a coroutine that does not have a `final suspend`_ point 
or on a coroutine that is not suspended leads to undefined behavior.

.. _coro.promise:

'llvm.coro.promise' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

::

      declare i8* @llvm.coro.promise(i8* <ptr>, i32 <alignment>, i1 <from>)

Overview:
"""""""""

The '``llvm.coro.promise``' intrinsic obtains a pointer to a 
`coroutine promise`_ given a coroutine handle and vice versa.

Arguments:
""""""""""

The first argument is a handle to a coroutine if `from` is false. Otherwise, 
it is a pointer to a coroutine promise.

The second argument is an alignment requirements of the promise. 
If a frontend designated `%promise = alloca i32` as a promise, the alignment 
argument to `coro.promise` should be the alignment of `i32` on the target 
platform. If a frontend designated `%promise = alloca i32, align 16` as a 
promise, the alignment argument should be 16.
This argument only accepts constants.

The third argument is a boolean indicating a direction of the transformation.
If `from` is true, the intrinsic returns a coroutine handle given a pointer 
to a promise. If `from` is false, the intrinsics return a pointer to a promise 
from a coroutine handle. This argument only accepts constants.

Semantics:
""""""""""

Using this intrinsic on a coroutine that does not have a coroutine promise
leads to undefined behavior. It is possible to read and modify coroutine
promise of the coroutine which is currently executing. The coroutine author and
a coroutine user are responsible to makes sure there is no data races.

Example:
""""""""

.. code-block:: llvm

  define i8* @f(i32 %n) {
  entry:
    %promise = alloca i32
    %pv = bitcast i32* %promise to i8*
    ; the second argument to coro.id points to the coroutine promise.
    %id = call token @llvm.coro.id(i32 0, i8* %pv, i8* null, i8* null)
    ...
    %hdl = call noalias i8* @llvm.coro.begin(token %id, i8* %alloc)
    ...
    store i32 42, i32* %promise ; store something into the promise
    ...
    ret i8* %hdl
  }

  define i32 @main() {
  entry:
    %hdl = call i8* @f(i32 4) ; starts the coroutine and returns its handle
    %promise.addr.raw = call i8* @llvm.coro.promise(i8* %hdl, i32 4, i1 false)
    %promise.addr = bitcast i8* %promise.addr.raw to i32*    
    %val = load i32, i32* %promise.addr ; load a value from the promise
    call void @print(i32 %val)
    call void @llvm.coro.destroy(i8* %hdl)
    ret i32 0
  }

.. _coroutine intrinsics:

Coroutine Structure Intrinsics
------------------------------
Intrinsics described in this section are used within a coroutine to describe
the coroutine structure. They should not be used outside of a coroutine.

.. _coro.size:

'llvm.coro.size' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
::

    declare i32 @llvm.coro.size.i32()
    declare i64 @llvm.coro.size.i64()

Overview:
"""""""""

The '``llvm.coro.size``' intrinsic returns the number of bytes
required to store a `coroutine frame`_.

Arguments:
""""""""""

None

Semantics:
""""""""""

The `coro.size` intrinsic is lowered to a constant representing the size of
the coroutine frame. 

.. _coro.begin:

'llvm.coro.begin' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
::

  declare i8* @llvm.coro.begin(token <id>, i8* <mem>)

Overview:
"""""""""

The '``llvm.coro.begin``' intrinsic returns an address of the coroutine frame.

Arguments:
""""""""""

The first argument is a token returned by a call to '``llvm.coro.id``' 
identifying the coroutine.

The second argument is a pointer to a block of memory where coroutine frame
will be stored if it is allocated dynamically.

Semantics:
""""""""""

Depending on the alignment requirements of the objects in the coroutine frame
and/or on the codegen compactness reasons the pointer returned from `coro.begin` 
may be at offset to the `%mem` argument. (This could be beneficial if 
instructions that express relative access to data can be more compactly encoded 
with small positive and negative offsets).

A frontend should emit exactly one `coro.begin` intrinsic per coroutine.

.. _coro.free:

'llvm.coro.free' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
::

  declare i8* @llvm.coro.free(token %id, i8* <frame>)

Overview:
"""""""""

The '``llvm.coro.free``' intrinsic returns a pointer to a block of memory where 
coroutine frame is stored or `null` if this instance of a coroutine did not use
dynamically allocated memory for its coroutine frame.

Arguments:
""""""""""

The first argument is a token returned by a call to '``llvm.coro.id``' 
identifying the coroutine.

The second argument is a pointer to the coroutine frame. This should be the same
pointer that was returned by prior `coro.begin` call.

Example (custom deallocation function):
"""""""""""""""""""""""""""""""""""""""

.. code-block:: llvm

  cleanup:
    %mem = call i8* @llvm.coro.free(token %id, i8* %frame)
    %mem_not_null = icmp ne i8* %mem, null
    br i1 %mem_not_null, label %if.then, label %if.end
  if.then:
    call void @CustomFree(i8* %mem)
    br label %if.end
  if.end:
    ret void

Example (standard deallocation functions):
""""""""""""""""""""""""""""""""""""""""""

.. code-block:: llvm

  cleanup:
    %mem = call i8* @llvm.coro.free(token %id, i8* %frame)
    call void @free(i8* %mem)
    ret void

.. _coro.alloc:

'llvm.coro.alloc' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
::

  declare i1 @llvm.coro.alloc(token <id>)

Overview:
"""""""""

The '``llvm.coro.alloc``' intrinsic returns `true` if dynamic allocation is
required to obtain a memory for the coroutine frame and `false` otherwise.

Arguments:
""""""""""

The first argument is a token returned by a call to '``llvm.coro.id``' 
identifying the coroutine.

Semantics:
""""""""""

A frontend should emit at most one `coro.alloc` intrinsic per coroutine.
The intrinsic is used to suppress dynamic allocation of the coroutine frame
when possible.

Example:
""""""""

.. code-block:: llvm

  entry:
    %id = call token @llvm.coro.id(i32 0, i8* null, i8* null, i8* null)
    %dyn.alloc.required = call i1 @llvm.coro.alloc(token %id)
    br i1 %dyn.alloc.required, label %coro.alloc, label %coro.begin

  coro.alloc:
    %frame.size = call i32 @llvm.coro.size()
    %alloc = call i8* @MyAlloc(i32 %frame.size)
    br label %coro.begin

  coro.begin:
    %phi = phi i8* [ null, %entry ], [ %alloc, %coro.alloc ]
    %frame = call i8* @llvm.coro.begin(token %id, i8* %phi)

.. _coro.noop:

'llvm.coro.noop' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
::

  declare i8* @llvm.coro.noop()

Overview:
"""""""""

The '``llvm.coro.noop``' intrinsic returns an address of the coroutine frame of
a coroutine that does nothing when resumed or destroyed.

Arguments:
""""""""""

None

Semantics:
""""""""""

This intrinsic is lowered to refer to a private constant coroutine frame. The
resume and destroy handlers for this frame are empty functions that do nothing.
Note that in different translation units llvm.coro.noop may return different pointers.

.. _coro.frame:

'llvm.coro.frame' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
::

  declare i8* @llvm.coro.frame()

Overview:
"""""""""

The '``llvm.coro.frame``' intrinsic returns an address of the coroutine frame of
the enclosing coroutine.

Arguments:
""""""""""

None

Semantics:
""""""""""

This intrinsic is lowered to refer to the `coro.begin`_ instruction. This is
a frontend convenience intrinsic that makes it easier to refer to the
coroutine frame.

.. _coro.id:

'llvm.coro.id' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
::

  declare token @llvm.coro.id(i32 <align>, i8* <promise>, i8* <coroaddr>, 
                                                          i8* <fnaddrs>)

Overview:
"""""""""

The '``llvm.coro.id``' intrinsic returns a token identifying a coroutine.

Arguments:
""""""""""

The first argument provides information on the alignment of the memory returned 
by the allocation function and given to `coro.begin` by the first argument. If 
this argument is 0, the memory is assumed to be aligned to 2 * sizeof(i8*).
This argument only accepts constants.

The second argument, if not `null`, designates a particular alloca instruction
to be a `coroutine promise`_.

The third argument is `null` coming out of the frontend. The CoroEarly pass sets
this argument to point to the function this coro.id belongs to. 

The fourth argument is `null` before coroutine is split, and later is replaced 
to point to a private global constant array containing function pointers to 
outlined resume and destroy parts of the coroutine.


Semantics:
""""""""""

The purpose of this intrinsic is to tie together `coro.id`, `coro.alloc` and
`coro.begin` belonging to the same coroutine to prevent optimization passes from
duplicating any of these instructions unless entire body of the coroutine is
duplicated.

A frontend should emit exactly one `coro.id` intrinsic per coroutine.

.. _coro.end:

'llvm.coro.end' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
::

  declare i1 @llvm.coro.end(i8* <handle>, i1 <unwind>)

Overview:
"""""""""

The '``llvm.coro.end``' marks the point where execution of the resume part of 
the coroutine should end and control should return to the caller.


Arguments:
""""""""""

The first argument should refer to the coroutine handle of the enclosing
coroutine. A frontend is allowed to supply null as the first parameter, in this
case `coro-early` pass will replace the null with an appropriate coroutine 
handle value.

The second argument should be `true` if this coro.end is in the block that is 
part of the unwind sequence leaving the coroutine body due to an exception and 
`false` otherwise.

Semantics:
""""""""""
The purpose of this intrinsic is to allow frontends to mark the cleanup and
other code that is only relevant during the initial invocation of the coroutine
and should not be present in resume and destroy parts. 

This intrinsic is lowered when a coroutine is split into
the start, resume and destroy parts. In the start part, it is a no-op,
in resume and destroy parts, it is replaced with `ret void` instruction and
the rest of the block containing `coro.end` instruction is discarded.
In landing pads it is replaced with an appropriate instruction to unwind to 
caller. The handling of coro.end differs depending on whether the target is 
using landingpad or WinEH exception model.

For landingpad based exception model, it is expected that frontend uses the 
`coro.end`_ intrinsic as follows:

.. code-block:: llvm

    ehcleanup:
      %InResumePart = call i1 @llvm.coro.end(i8* null, i1 true)
      br i1 %InResumePart, label %eh.resume, label %cleanup.cont

    cleanup.cont:
      ; rest of the cleanup

    eh.resume:
      %exn = load i8*, i8** %exn.slot, align 8
      %sel = load i32, i32* %ehselector.slot, align 4
      %lpad.val = insertvalue { i8*, i32 } undef, i8* %exn, 0
      %lpad.val29 = insertvalue { i8*, i32 } %lpad.val, i32 %sel, 1
      resume { i8*, i32 } %lpad.val29

The `CoroSpit` pass replaces `coro.end` with ``True`` in the resume functions,
thus leading to immediate unwind to the caller, whereas in start function it
is replaced with ``False``, thus allowing to proceed to the rest of the cleanup
code that is only needed during initial invocation of the coroutine.

For Windows Exception handling model, a frontend should attach a funclet bundle
referring to an enclosing cleanuppad as follows:

.. code-block:: llvm

    ehcleanup: 
      %tok = cleanuppad within none []
      %unused = call i1 @llvm.coro.end(i8* null, i1 true) [ "funclet"(token %tok) ]
      cleanupret from %tok unwind label %RestOfTheCleanup

The `CoroSplit` pass, if the funclet bundle is present, will insert 
``cleanupret from %tok unwind to caller`` before
the `coro.end`_ intrinsic and will remove the rest of the block.

The following table summarizes the handling of `coro.end`_ intrinsic.

+--------------------------+-------------------+-------------------------------+
|                          | In Start Function | In Resume/Destroy Functions   |
+--------------------------+-------------------+-------------------------------+
|unwind=false              | nothing           |``ret void``                   |
+------------+-------------+-------------------+-------------------------------+
|            | WinEH       | nothing           |``cleanupret unwind to caller``|
|unwind=true +-------------+-------------------+-------------------------------+
|            | Landingpad  | nothing           | nothing                       |
+------------+-------------+-------------------+-------------------------------+

.. _coro.suspend:
.. _suspend points:

'llvm.coro.suspend' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
::

  declare i8 @llvm.coro.suspend(token <save>, i1 <final>)

Overview:
"""""""""

The '``llvm.coro.suspend``' marks the point where execution of the coroutine 
need to get suspended and control returned back to the caller.
Conditional branches consuming the result of this intrinsic lead to basic blocks
where coroutine should proceed when suspended (-1), resumed (0) or destroyed 
(1).

Arguments:
""""""""""

The first argument refers to a token of `coro.save` intrinsic that marks the 
point when coroutine state is prepared for suspension. If `none` token is passed,
the intrinsic behaves as if there were a `coro.save` immediately preceding
the `coro.suspend` intrinsic.

The second argument indicates whether this suspension point is `final`_.
The second argument only accepts constants. If more than one suspend point is
designated as final, the resume and destroy branches should lead to the same
basic blocks.

Example (normal suspend point):
"""""""""""""""""""""""""""""""

.. code-block:: llvm

    %0 = call i8 @llvm.coro.suspend(token none, i1 false)
    switch i8 %0, label %suspend [i8 0, label %resume
                                  i8 1, label %cleanup]

Example (final suspend point):
""""""""""""""""""""""""""""""

.. code-block:: llvm

  while.end:
    %s.final = call i8 @llvm.coro.suspend(token none, i1 true)
    switch i8 %s.final, label %suspend [i8 0, label %trap
                                        i8 1, label %cleanup]
  trap: 
    call void @llvm.trap()
    unreachable

Semantics:
""""""""""

If a coroutine that was suspended at the suspend point marked by this intrinsic
is resumed via `coro.resume`_ the control will transfer to the basic block
of the 0-case. If it is resumed via `coro.destroy`_, it will proceed to the
basic block indicated by the 1-case. To suspend, coroutine proceed to the 
default label.

If suspend intrinsic is marked as final, it can consider the `true` branch
unreachable and can perform optimizations that can take advantage of that fact.

.. _coro.save:

'llvm.coro.save' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
::

  declare token @llvm.coro.save(i8* <handle>)

Overview:
"""""""""

The '``llvm.coro.save``' marks the point where a coroutine need to update its 
state to prepare for resumption to be considered suspended (and thus eligible 
for resumption). 

Arguments:
""""""""""

The first argument points to a coroutine handle of the enclosing coroutine.

Semantics:
""""""""""

Whatever coroutine state changes are required to enable resumption of
the coroutine from the corresponding suspend point should be done at the point 
of `coro.save` intrinsic.

Example:
""""""""

Separate save and suspend points are necessary when a coroutine is used to 
represent an asynchronous control flow driven by callbacks representing
completions of asynchronous operations.

In such a case, a coroutine should be ready for resumption prior to a call to 
`async_op` function that may trigger resumption of a coroutine from the same or
a different thread possibly prior to `async_op` call returning control back
to the coroutine:

.. code-block:: llvm

    %save1 = call token @llvm.coro.save(i8* %hdl)
    call void @async_op1(i8* %hdl)
    %suspend1 = call i1 @llvm.coro.suspend(token %save1, i1 false)
    switch i8 %suspend1, label %suspend [i8 0, label %resume1
                                         i8 1, label %cleanup]

.. _coro.param:

'llvm.coro.param' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
::

  declare i1 @llvm.coro.param(i8* <original>, i8* <copy>)

Overview:
"""""""""

The '``llvm.coro.param``' is used by a frontend to mark up the code used to
construct and destruct copies of the parameters. If the optimizer discovers that
a particular parameter copy is not used after any suspends, it can remove the
construction and destruction of the copy by replacing corresponding coro.param
with `i1 false` and replacing any use of the `copy` with the `original`.

Arguments:
""""""""""

The first argument points to an `alloca` storing the value of a parameter to a 
coroutine. 

The second argument points to an `alloca` storing the value of the copy of that
parameter.

Semantics:
""""""""""

The optimizer is free to always replace this intrinsic with `i1 true`.

The optimizer is also allowed to replace it with `i1 false` provided that the 
parameter copy is only used prior to control flow reaching any of the suspend
points. The code that would be DCE'd if the `coro.param` is replaced with 
`i1 false` is not considered to be a use of the parameter copy.

The frontend can emit this intrinsic if its language rules allow for this 
optimization.

Example:
""""""""
Consider the following example. A coroutine takes two parameters `a` and `b`
that has a destructor and a move constructor.

.. code-block:: c++

  struct A { ~A(); A(A&&); bool foo(); void bar(); };

  task<int> f(A a, A b) {
    if (a.foo())
      return 42;

    a.bar();
    co_await read_async(); // introduces suspend point
    b.bar();
  }

Note that, uses of `b` is used after a suspend point and thus must be copied
into a coroutine frame, whereas `a` does not have to, since it never used 
after suspend.

A frontend can create parameter copies for `a` and `b` as follows:

.. code-block:: text

  task<int> f(A a', A b') {
    a = alloca A;
    b = alloca A;
    // move parameters to its copies
    if (coro.param(a', a)) A::A(a, A&& a');
    if (coro.param(b', b)) A::A(b, A&& b');
    ...
    // destroy parameters copies
    if (coro.param(a', a)) A::~A(a);
    if (coro.param(b', b)) A::~A(b);
  }

The optimizer can replace coro.param(a',a) with `i1 false` and replace all uses
of `a` with `a'`, since it is not used after suspend.

The optimizer must replace coro.param(b', b) with `i1 true`, since `b` is used
after suspend and therefore, it has to reside in the coroutine frame.

Coroutine Transformation Passes
===============================
CoroEarly
---------
The pass CoroEarly lowers coroutine intrinsics that hide the details of the
structure of the coroutine frame, but, otherwise not needed to be preserved to
help later coroutine passes. This pass lowers `coro.frame`_, `coro.done`_, 
and `coro.promise`_ intrinsics.

.. _CoroSplit:

CoroSplit
---------
The pass CoroSplit buides coroutine frame and outlines resume and destroy parts 
into separate functions.

CoroElide
---------
The pass CoroElide examines if the inlined coroutine is eligible for heap 
allocation elision optimization. If so, it replaces 
`coro.begin` intrinsic with an address of a coroutine frame placed on its caller
and replaces `coro.alloc` and `coro.free` intrinsics with `false` and `null`
respectively to remove the deallocation code. 
This pass also replaces `coro.resume` and `coro.destroy` intrinsics with direct 
calls to resume and destroy functions for a particular coroutine where possible.

CoroCleanup
-----------
This pass runs late to lower all coroutine related intrinsics not replaced by
earlier passes.

Areas Requiring Attention
=========================
#. A coroutine frame is bigger than it could be. Adding stack packing and stack 
   coloring like optimization on the coroutine frame will result in tighter
   coroutine frames.

#. Take advantage of the lifetime intrinsics for the data that goes into the
   coroutine frame. Leave lifetime intrinsics as is for the data that stays in
   allocas.

#. The CoroElide optimization pass relies on coroutine ramp function to be
   inlined. It would be beneficial to split the ramp function further to 
   increase the chance that it will get inlined into its caller.

#. Design a convention that would make it possible to apply coroutine heap
   elision optimization across ABI boundaries.

#. Cannot handle coroutines with `inalloca` parameters (used in x86 on Windows).

#. Alignment is ignored by coro.begin and coro.free intrinsics.

#. Make required changes to make sure that coroutine optimizations work with
   LTO.

#. More tests, more tests, more tests