llvm.org GIT mirror llvm / e3e43d9 lib / CodeGen / AtomicExpandPass.cpp
e3e43d9

Tree @e3e43d9 (Download .tar.gz)

AtomicExpandPass.cpp @e3e43d9raw · history · blame

   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
//===-- AtomicExpandPass.cpp - Expand atomic instructions -------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains a pass (at IR level) to replace atomic instructions with
// __atomic_* library calls, or target specific instruction which implement the
// same semantics in a way which better fits the target backend.  This can
// include the use of (intrinsic-based) load-linked/store-conditional loops,
// AtomicCmpXchg, or type coercions.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/AtomicExpandUtils.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetSubtargetInfo.h"

using namespace llvm;

#define DEBUG_TYPE "atomic-expand"

namespace {
  class AtomicExpand: public FunctionPass {
    const TargetLowering *TLI;
  public:
    static char ID; // Pass identification, replacement for typeid
    AtomicExpand() : FunctionPass(ID), TLI(nullptr) {
      initializeAtomicExpandPass(*PassRegistry::getPassRegistry());
    }

    bool runOnFunction(Function &F) override;

  private:
    bool bracketInstWithFences(Instruction *I, AtomicOrdering Order);
    IntegerType *getCorrespondingIntegerType(Type *T, const DataLayout &DL);
    LoadInst *convertAtomicLoadToIntegerType(LoadInst *LI);
    bool tryExpandAtomicLoad(LoadInst *LI);
    bool expandAtomicLoadToLL(LoadInst *LI);
    bool expandAtomicLoadToCmpXchg(LoadInst *LI);
    StoreInst *convertAtomicStoreToIntegerType(StoreInst *SI);
    bool expandAtomicStore(StoreInst *SI);
    bool tryExpandAtomicRMW(AtomicRMWInst *AI);
    Value *
    insertRMWLLSCLoop(IRBuilder<> &Builder, Type *ResultTy, Value *Addr,
                      AtomicOrdering MemOpOrder,
                      function_ref<Value *(IRBuilder<> &, Value *)> PerformOp);
    void expandAtomicOpToLLSC(
        Instruction *I, Type *ResultTy, Value *Addr, AtomicOrdering MemOpOrder,
        function_ref<Value *(IRBuilder<> &, Value *)> PerformOp);
    void expandPartwordAtomicRMW(
        AtomicRMWInst *I,
        TargetLoweringBase::AtomicExpansionKind ExpansionKind);
    void expandPartwordCmpXchg(AtomicCmpXchgInst *I);

    AtomicCmpXchgInst *convertCmpXchgToIntegerType(AtomicCmpXchgInst *CI);
    static Value *insertRMWCmpXchgLoop(
        IRBuilder<> &Builder, Type *ResultType, Value *Addr,
        AtomicOrdering MemOpOrder,
        function_ref<Value *(IRBuilder<> &, Value *)> PerformOp,
        CreateCmpXchgInstFun CreateCmpXchg);

    bool expandAtomicCmpXchg(AtomicCmpXchgInst *CI);
    bool isIdempotentRMW(AtomicRMWInst *AI);
    bool simplifyIdempotentRMW(AtomicRMWInst *AI);

    bool expandAtomicOpToLibcall(Instruction *I, unsigned Size, unsigned Align,
                                 Value *PointerOperand, Value *ValueOperand,
                                 Value *CASExpected, AtomicOrdering Ordering,
                                 AtomicOrdering Ordering2,
                                 ArrayRef<RTLIB::Libcall> Libcalls);
    void expandAtomicLoadToLibcall(LoadInst *LI);
    void expandAtomicStoreToLibcall(StoreInst *LI);
    void expandAtomicRMWToLibcall(AtomicRMWInst *I);
    void expandAtomicCASToLibcall(AtomicCmpXchgInst *I);

    friend bool
    llvm::expandAtomicRMWToCmpXchg(AtomicRMWInst *AI,
                                   CreateCmpXchgInstFun CreateCmpXchg);
  };
}

char AtomicExpand::ID = 0;
char &llvm::AtomicExpandID = AtomicExpand::ID;
INITIALIZE_PASS(AtomicExpand, DEBUG_TYPE, "Expand Atomic instructions",
                false, false)

FunctionPass *llvm::createAtomicExpandPass() { return new AtomicExpand(); }

namespace {
// Helper functions to retrieve the size of atomic instructions.
unsigned getAtomicOpSize(LoadInst *LI) {
  const DataLayout &DL = LI->getModule()->getDataLayout();
  return DL.getTypeStoreSize(LI->getType());
}

unsigned getAtomicOpSize(StoreInst *SI) {
  const DataLayout &DL = SI->getModule()->getDataLayout();
  return DL.getTypeStoreSize(SI->getValueOperand()->getType());
}

unsigned getAtomicOpSize(AtomicRMWInst *RMWI) {
  const DataLayout &DL = RMWI->getModule()->getDataLayout();
  return DL.getTypeStoreSize(RMWI->getValOperand()->getType());
}

unsigned getAtomicOpSize(AtomicCmpXchgInst *CASI) {
  const DataLayout &DL = CASI->getModule()->getDataLayout();
  return DL.getTypeStoreSize(CASI->getCompareOperand()->getType());
}

// Helper functions to retrieve the alignment of atomic instructions.
unsigned getAtomicOpAlign(LoadInst *LI) {
  unsigned Align = LI->getAlignment();
  // In the future, if this IR restriction is relaxed, we should
  // return DataLayout::getABITypeAlignment when there's no align
  // value.
  assert(Align != 0 && "An atomic LoadInst always has an explicit alignment");
  return Align;
}

unsigned getAtomicOpAlign(StoreInst *SI) {
  unsigned Align = SI->getAlignment();
  // In the future, if this IR restriction is relaxed, we should
  // return DataLayout::getABITypeAlignment when there's no align
  // value.
  assert(Align != 0 && "An atomic StoreInst always has an explicit alignment");
  return Align;
}

unsigned getAtomicOpAlign(AtomicRMWInst *RMWI) {
  // TODO(PR27168): This instruction has no alignment attribute, but unlike the
  // default alignment for load/store, the default here is to assume
  // it has NATURAL alignment, not DataLayout-specified alignment.
  const DataLayout &DL = RMWI->getModule()->getDataLayout();
  return DL.getTypeStoreSize(RMWI->getValOperand()->getType());
}

unsigned getAtomicOpAlign(AtomicCmpXchgInst *CASI) {
  // TODO(PR27168): same comment as above.
  const DataLayout &DL = CASI->getModule()->getDataLayout();
  return DL.getTypeStoreSize(CASI->getCompareOperand()->getType());
}

// Determine if a particular atomic operation has a supported size,
// and is of appropriate alignment, to be passed through for target
// lowering. (Versus turning into a __atomic libcall)
template <typename Inst>
bool atomicSizeSupported(const TargetLowering *TLI, Inst *I) {
  unsigned Size = getAtomicOpSize(I);
  unsigned Align = getAtomicOpAlign(I);
  return Align >= Size && Size <= TLI->getMaxAtomicSizeInBitsSupported() / 8;
}

} // end anonymous namespace

bool AtomicExpand::runOnFunction(Function &F) {
  auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
  if (!TPC)
    return false;

  auto &TM = TPC->getTM<TargetMachine>();
  if (!TM.getSubtargetImpl(F)->enableAtomicExpand())
    return false;
  TLI = TM.getSubtargetImpl(F)->getTargetLowering();

  SmallVector<Instruction *, 1> AtomicInsts;

  // Changing control-flow while iterating through it is a bad idea, so gather a
  // list of all atomic instructions before we start.
  for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
    Instruction *I = &*II;
    if (I->isAtomic() && !isa<FenceInst>(I))
      AtomicInsts.push_back(I);
  }

  bool MadeChange = false;
  for (auto I : AtomicInsts) {
    auto LI = dyn_cast<LoadInst>(I);
    auto SI = dyn_cast<StoreInst>(I);
    auto RMWI = dyn_cast<AtomicRMWInst>(I);
    auto CASI = dyn_cast<AtomicCmpXchgInst>(I);
    assert((LI || SI || RMWI || CASI) && "Unknown atomic instruction");

    // If the Size/Alignment is not supported, replace with a libcall.
    if (LI) {
      if (!atomicSizeSupported(TLI, LI)) {
        expandAtomicLoadToLibcall(LI);
        MadeChange = true;
        continue;
      }
    } else if (SI) {
      if (!atomicSizeSupported(TLI, SI)) {
        expandAtomicStoreToLibcall(SI);
        MadeChange = true;
        continue;
      }
    } else if (RMWI) {
      if (!atomicSizeSupported(TLI, RMWI)) {
        expandAtomicRMWToLibcall(RMWI);
        MadeChange = true;
        continue;
      }
    } else if (CASI) {
      if (!atomicSizeSupported(TLI, CASI)) {
        expandAtomicCASToLibcall(CASI);
        MadeChange = true;
        continue;
      }
    }

    if (TLI->shouldInsertFencesForAtomic(I)) {
      auto FenceOrdering = AtomicOrdering::Monotonic;
      if (LI && isAcquireOrStronger(LI->getOrdering())) {
        FenceOrdering = LI->getOrdering();
        LI->setOrdering(AtomicOrdering::Monotonic);
      } else if (SI && isReleaseOrStronger(SI->getOrdering())) {
        FenceOrdering = SI->getOrdering();
        SI->setOrdering(AtomicOrdering::Monotonic);
      } else if (RMWI && (isReleaseOrStronger(RMWI->getOrdering()) ||
                          isAcquireOrStronger(RMWI->getOrdering()))) {
        FenceOrdering = RMWI->getOrdering();
        RMWI->setOrdering(AtomicOrdering::Monotonic);
      } else if (CASI && !TLI->shouldExpandAtomicCmpXchgInIR(CASI) &&
                 (isReleaseOrStronger(CASI->getSuccessOrdering()) ||
                  isAcquireOrStronger(CASI->getSuccessOrdering()))) {
        // If a compare and swap is lowered to LL/SC, we can do smarter fence
        // insertion, with a stronger one on the success path than on the
        // failure path. As a result, fence insertion is directly done by
        // expandAtomicCmpXchg in that case.
        FenceOrdering = CASI->getSuccessOrdering();
        CASI->setSuccessOrdering(AtomicOrdering::Monotonic);
        CASI->setFailureOrdering(AtomicOrdering::Monotonic);
      }

      if (FenceOrdering != AtomicOrdering::Monotonic) {
        MadeChange |= bracketInstWithFences(I, FenceOrdering);
      }
    }

    if (LI) {
      if (LI->getType()->isFloatingPointTy()) {
        // TODO: add a TLI hook to control this so that each target can
        // convert to lowering the original type one at a time.
        LI = convertAtomicLoadToIntegerType(LI);
        assert(LI->getType()->isIntegerTy() && "invariant broken");
        MadeChange = true;
      }

      MadeChange |= tryExpandAtomicLoad(LI);
    } else if (SI) {
      if (SI->getValueOperand()->getType()->isFloatingPointTy()) {
        // TODO: add a TLI hook to control this so that each target can
        // convert to lowering the original type one at a time.
        SI = convertAtomicStoreToIntegerType(SI);
        assert(SI->getValueOperand()->getType()->isIntegerTy() &&
               "invariant broken");
        MadeChange = true;
      }

      if (TLI->shouldExpandAtomicStoreInIR(SI))
        MadeChange |= expandAtomicStore(SI);
    } else if (RMWI) {
      // There are two different ways of expanding RMW instructions:
      // - into a load if it is idempotent
      // - into a Cmpxchg/LL-SC loop otherwise
      // we try them in that order.

      if (isIdempotentRMW(RMWI) && simplifyIdempotentRMW(RMWI)) {
        MadeChange = true;
      } else {
        MadeChange |= tryExpandAtomicRMW(RMWI);
      }
    } else if (CASI) {
      // TODO: when we're ready to make the change at the IR level, we can
      // extend convertCmpXchgToInteger for floating point too.
      assert(!CASI->getCompareOperand()->getType()->isFloatingPointTy() &&
             "unimplemented - floating point not legal at IR level");
      if (CASI->getCompareOperand()->getType()->isPointerTy() ) {
        // TODO: add a TLI hook to control this so that each target can
        // convert to lowering the original type one at a time.
        CASI = convertCmpXchgToIntegerType(CASI);
        assert(CASI->getCompareOperand()->getType()->isIntegerTy() &&
               "invariant broken");
        MadeChange = true;
      }

      unsigned MinCASSize = TLI->getMinCmpXchgSizeInBits() / 8;
      unsigned ValueSize = getAtomicOpSize(CASI);
      if (ValueSize < MinCASSize) {
        assert(!TLI->shouldExpandAtomicCmpXchgInIR(CASI) &&
               "MinCmpXchgSizeInBits not yet supported for LL/SC expansions.");
        expandPartwordCmpXchg(CASI);
      } else {
        if (TLI->shouldExpandAtomicCmpXchgInIR(CASI))
          MadeChange |= expandAtomicCmpXchg(CASI);
      }
    }
  }
  return MadeChange;
}

bool AtomicExpand::bracketInstWithFences(Instruction *I, AtomicOrdering Order) {
  IRBuilder<> Builder(I);

  auto LeadingFence = TLI->emitLeadingFence(Builder, I, Order);

  auto TrailingFence = TLI->emitTrailingFence(Builder, I, Order);
  // The trailing fence is emitted before the instruction instead of after
  // because there is no easy way of setting Builder insertion point after
  // an instruction. So we must erase it from the BB, and insert it back
  // in the right place.
  // We have a guard here because not every atomic operation generates a
  // trailing fence.
  if (TrailingFence) {
    TrailingFence->removeFromParent();
    TrailingFence->insertAfter(I);
  }

  return (LeadingFence || TrailingFence);
}

/// Get the iX type with the same bitwidth as T.
IntegerType *AtomicExpand::getCorrespondingIntegerType(Type *T,
                                                       const DataLayout &DL) {
  EVT VT = TLI->getValueType(DL, T);
  unsigned BitWidth = VT.getStoreSizeInBits();
  assert(BitWidth == VT.getSizeInBits() && "must be a power of two");
  return IntegerType::get(T->getContext(), BitWidth);
}

/// Convert an atomic load of a non-integral type to an integer load of the
/// equivalent bitwidth.  See the function comment on
/// convertAtomicStoreToIntegerType for background.  
LoadInst *AtomicExpand::convertAtomicLoadToIntegerType(LoadInst *LI) {
  auto *M = LI->getModule();
  Type *NewTy = getCorrespondingIntegerType(LI->getType(),
                                            M->getDataLayout());

  IRBuilder<> Builder(LI);
  
  Value *Addr = LI->getPointerOperand();
  Type *PT = PointerType::get(NewTy,
                              Addr->getType()->getPointerAddressSpace());
  Value *NewAddr = Builder.CreateBitCast(Addr, PT);
  
  auto *NewLI = Builder.CreateLoad(NewAddr);
  NewLI->setAlignment(LI->getAlignment());
  NewLI->setVolatile(LI->isVolatile());
  NewLI->setAtomic(LI->getOrdering(), LI->getSynchScope());
  DEBUG(dbgs() << "Replaced " << *LI << " with " << *NewLI << "\n");
  
  Value *NewVal = Builder.CreateBitCast(NewLI, LI->getType());
  LI->replaceAllUsesWith(NewVal);
  LI->eraseFromParent();
  return NewLI;
}

bool AtomicExpand::tryExpandAtomicLoad(LoadInst *LI) {
  switch (TLI->shouldExpandAtomicLoadInIR(LI)) {
  case TargetLoweringBase::AtomicExpansionKind::None:
    return false;
  case TargetLoweringBase::AtomicExpansionKind::LLSC:
    expandAtomicOpToLLSC(
        LI, LI->getType(), LI->getPointerOperand(), LI->getOrdering(),
        [](IRBuilder<> &Builder, Value *Loaded) { return Loaded; });
    return true;
  case TargetLoweringBase::AtomicExpansionKind::LLOnly:
    return expandAtomicLoadToLL(LI);
  case TargetLoweringBase::AtomicExpansionKind::CmpXChg:
    return expandAtomicLoadToCmpXchg(LI);
  }
  llvm_unreachable("Unhandled case in tryExpandAtomicLoad");
}

bool AtomicExpand::expandAtomicLoadToLL(LoadInst *LI) {
  IRBuilder<> Builder(LI);

  // On some architectures, load-linked instructions are atomic for larger
  // sizes than normal loads. For example, the only 64-bit load guaranteed
  // to be single-copy atomic by ARM is an ldrexd (A3.5.3).
  Value *Val =
      TLI->emitLoadLinked(Builder, LI->getPointerOperand(), LI->getOrdering());
  TLI->emitAtomicCmpXchgNoStoreLLBalance(Builder);

  LI->replaceAllUsesWith(Val);
  LI->eraseFromParent();

  return true;
}

bool AtomicExpand::expandAtomicLoadToCmpXchg(LoadInst *LI) {
  IRBuilder<> Builder(LI);
  AtomicOrdering Order = LI->getOrdering();
  Value *Addr = LI->getPointerOperand();
  Type *Ty = cast<PointerType>(Addr->getType())->getElementType();
  Constant *DummyVal = Constant::getNullValue(Ty);

  Value *Pair = Builder.CreateAtomicCmpXchg(
      Addr, DummyVal, DummyVal, Order,
      AtomicCmpXchgInst::getStrongestFailureOrdering(Order));
  Value *Loaded = Builder.CreateExtractValue(Pair, 0, "loaded");

  LI->replaceAllUsesWith(Loaded);
  LI->eraseFromParent();

  return true;
}

/// Convert an atomic store of a non-integral type to an integer store of the
/// equivalent bitwidth.  We used to not support floating point or vector
/// atomics in the IR at all.  The backends learned to deal with the bitcast
/// idiom because that was the only way of expressing the notion of a atomic
/// float or vector store.  The long term plan is to teach each backend to
/// instruction select from the original atomic store, but as a migration
/// mechanism, we convert back to the old format which the backends understand.
/// Each backend will need individual work to recognize the new format.
StoreInst *AtomicExpand::convertAtomicStoreToIntegerType(StoreInst *SI) {
  IRBuilder<> Builder(SI);
  auto *M = SI->getModule();
  Type *NewTy = getCorrespondingIntegerType(SI->getValueOperand()->getType(),
                                            M->getDataLayout());
  Value *NewVal = Builder.CreateBitCast(SI->getValueOperand(), NewTy);
  
  Value *Addr = SI->getPointerOperand();
  Type *PT = PointerType::get(NewTy,
                              Addr->getType()->getPointerAddressSpace());
  Value *NewAddr = Builder.CreateBitCast(Addr, PT);

  StoreInst *NewSI = Builder.CreateStore(NewVal, NewAddr);
  NewSI->setAlignment(SI->getAlignment());
  NewSI->setVolatile(SI->isVolatile());
  NewSI->setAtomic(SI->getOrdering(), SI->getSynchScope());
  DEBUG(dbgs() << "Replaced " << *SI << " with " << *NewSI << "\n");
  SI->eraseFromParent();
  return NewSI;
}

bool AtomicExpand::expandAtomicStore(StoreInst *SI) {
  // This function is only called on atomic stores that are too large to be
  // atomic if implemented as a native store. So we replace them by an
  // atomic swap, that can be implemented for example as a ldrex/strex on ARM
  // or lock cmpxchg8/16b on X86, as these are atomic for larger sizes.
  // It is the responsibility of the target to only signal expansion via
  // shouldExpandAtomicRMW in cases where this is required and possible.
  IRBuilder<> Builder(SI);
  AtomicRMWInst *AI =
      Builder.CreateAtomicRMW(AtomicRMWInst::Xchg, SI->getPointerOperand(),
                              SI->getValueOperand(), SI->getOrdering());
  SI->eraseFromParent();

  // Now we have an appropriate swap instruction, lower it as usual.
  return tryExpandAtomicRMW(AI);
}

static void createCmpXchgInstFun(IRBuilder<> &Builder, Value *Addr,
                                 Value *Loaded, Value *NewVal,
                                 AtomicOrdering MemOpOrder,
                                 Value *&Success, Value *&NewLoaded) {
  Value* Pair = Builder.CreateAtomicCmpXchg(
      Addr, Loaded, NewVal, MemOpOrder,
      AtomicCmpXchgInst::getStrongestFailureOrdering(MemOpOrder));
  Success = Builder.CreateExtractValue(Pair, 1, "success");
  NewLoaded = Builder.CreateExtractValue(Pair, 0, "newloaded");
}

/// Emit IR to implement the given atomicrmw operation on values in registers,
/// returning the new value.
static Value *performAtomicOp(AtomicRMWInst::BinOp Op, IRBuilder<> &Builder,
                              Value *Loaded, Value *Inc) {
  Value *NewVal;
  switch (Op) {
  case AtomicRMWInst::Xchg:
    return Inc;
  case AtomicRMWInst::Add:
    return Builder.CreateAdd(Loaded, Inc, "new");
  case AtomicRMWInst::Sub:
    return Builder.CreateSub(Loaded, Inc, "new");
  case AtomicRMWInst::And:
    return Builder.CreateAnd(Loaded, Inc, "new");
  case AtomicRMWInst::Nand:
    return Builder.CreateNot(Builder.CreateAnd(Loaded, Inc), "new");
  case AtomicRMWInst::Or:
    return Builder.CreateOr(Loaded, Inc, "new");
  case AtomicRMWInst::Xor:
    return Builder.CreateXor(Loaded, Inc, "new");
  case AtomicRMWInst::Max:
    NewVal = Builder.CreateICmpSGT(Loaded, Inc);
    return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
  case AtomicRMWInst::Min:
    NewVal = Builder.CreateICmpSLE(Loaded, Inc);
    return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
  case AtomicRMWInst::UMax:
    NewVal = Builder.CreateICmpUGT(Loaded, Inc);
    return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
  case AtomicRMWInst::UMin:
    NewVal = Builder.CreateICmpULE(Loaded, Inc);
    return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
  default:
    llvm_unreachable("Unknown atomic op");
  }
}

bool AtomicExpand::tryExpandAtomicRMW(AtomicRMWInst *AI) {
  switch (TLI->shouldExpandAtomicRMWInIR(AI)) {
  case TargetLoweringBase::AtomicExpansionKind::None:
    return false;
  case TargetLoweringBase::AtomicExpansionKind::LLSC: {
    unsigned MinCASSize = TLI->getMinCmpXchgSizeInBits() / 8;
    unsigned ValueSize = getAtomicOpSize(AI);
    if (ValueSize < MinCASSize) {
      llvm_unreachable(
          "MinCmpXchgSizeInBits not yet supported for LL/SC architectures.");
    } else {
      auto PerformOp = [&](IRBuilder<> &Builder, Value *Loaded) {
        return performAtomicOp(AI->getOperation(), Builder, Loaded,
                               AI->getValOperand());
      };
      expandAtomicOpToLLSC(AI, AI->getType(), AI->getPointerOperand(),
                           AI->getOrdering(), PerformOp);
    }
    return true;
  }
  case TargetLoweringBase::AtomicExpansionKind::CmpXChg: {
    unsigned MinCASSize = TLI->getMinCmpXchgSizeInBits() / 8;
    unsigned ValueSize = getAtomicOpSize(AI);
    if (ValueSize < MinCASSize) {
      expandPartwordAtomicRMW(AI,
                              TargetLoweringBase::AtomicExpansionKind::CmpXChg);
    } else {
      expandAtomicRMWToCmpXchg(AI, createCmpXchgInstFun);
    }
    return true;
  }
  default:
    llvm_unreachable("Unhandled case in tryExpandAtomicRMW");
  }
}

namespace {

/// Result values from createMaskInstrs helper.
struct PartwordMaskValues {
  Type *WordType;
  Type *ValueType;
  Value *AlignedAddr;
  Value *ShiftAmt;
  Value *Mask;
  Value *Inv_Mask;
};
} // end anonymous namespace

/// This is a helper function which builds instructions to provide
/// values necessary for partword atomic operations. It takes an
/// incoming address, Addr, and ValueType, and constructs the address,
/// shift-amounts and masks needed to work with a larger value of size
/// WordSize.
///
/// AlignedAddr: Addr rounded down to a multiple of WordSize
///
/// ShiftAmt: Number of bits to right-shift a WordSize value loaded
///           from AlignAddr for it to have the same value as if
///           ValueType was loaded from Addr.
///
/// Mask: Value to mask with the value loaded from AlignAddr to
///       include only the part that would've been loaded from Addr.
///
/// Inv_Mask: The inverse of Mask.

static PartwordMaskValues createMaskInstrs(IRBuilder<> &Builder, Instruction *I,
                                           Type *ValueType, Value *Addr,
                                           unsigned WordSize) {
  PartwordMaskValues Ret;

  BasicBlock *BB = I->getParent();
  Function *F = BB->getParent();
  Module *M = I->getModule();

  LLVMContext &Ctx = F->getContext();
  const DataLayout &DL = M->getDataLayout();

  unsigned ValueSize = DL.getTypeStoreSize(ValueType);

  assert(ValueSize < WordSize);

  Ret.ValueType = ValueType;
  Ret.WordType = Type::getIntNTy(Ctx, WordSize * 8);

  Type *WordPtrType =
      Ret.WordType->getPointerTo(Addr->getType()->getPointerAddressSpace());

  Value *AddrInt = Builder.CreatePtrToInt(Addr, DL.getIntPtrType(Ctx));
  Ret.AlignedAddr = Builder.CreateIntToPtr(
      Builder.CreateAnd(AddrInt, ~(uint64_t)(WordSize - 1)), WordPtrType,
      "AlignedAddr");

  Value *PtrLSB = Builder.CreateAnd(AddrInt, WordSize - 1, "PtrLSB");
  if (DL.isLittleEndian()) {
    // turn bytes into bits
    Ret.ShiftAmt = Builder.CreateShl(PtrLSB, 3);
  } else {
    // turn bytes into bits, and count from the other side.
    Ret.ShiftAmt =
        Builder.CreateShl(Builder.CreateXor(PtrLSB, WordSize - ValueSize), 3);
  }

  Ret.ShiftAmt = Builder.CreateTrunc(Ret.ShiftAmt, Ret.WordType, "ShiftAmt");
  Ret.Mask = Builder.CreateShl(
      ConstantInt::get(Ret.WordType, (1 << ValueSize * 8) - 1), Ret.ShiftAmt,
      "Mask");
  Ret.Inv_Mask = Builder.CreateNot(Ret.Mask, "Inv_Mask");

  return Ret;
}

/// Emit IR to implement a masked version of a given atomicrmw
/// operation. (That is, only the bits under the Mask should be
/// affected by the operation)
static Value *performMaskedAtomicOp(AtomicRMWInst::BinOp Op,
                                    IRBuilder<> &Builder, Value *Loaded,
                                    Value *Shifted_Inc, Value *Inc,
                                    const PartwordMaskValues &PMV) {
  switch (Op) {
  case AtomicRMWInst::Xchg: {
    Value *Loaded_MaskOut = Builder.CreateAnd(Loaded, PMV.Inv_Mask);
    Value *FinalVal = Builder.CreateOr(Loaded_MaskOut, Shifted_Inc);
    return FinalVal;
  }
  case AtomicRMWInst::Or:
  case AtomicRMWInst::Xor:
    // Or/Xor won't affect any other bits, so can just be done
    // directly.
    return performAtomicOp(Op, Builder, Loaded, Shifted_Inc);
  case AtomicRMWInst::Add:
  case AtomicRMWInst::Sub:
  case AtomicRMWInst::And:
  case AtomicRMWInst::Nand: {
    // The other arithmetic ops need to be masked into place.
    Value *NewVal = performAtomicOp(Op, Builder, Loaded, Shifted_Inc);
    Value *NewVal_Masked = Builder.CreateAnd(NewVal, PMV.Mask);
    Value *Loaded_MaskOut = Builder.CreateAnd(Loaded, PMV.Inv_Mask);
    Value *FinalVal = Builder.CreateOr(Loaded_MaskOut, NewVal_Masked);
    return FinalVal;
  }
  case AtomicRMWInst::Max:
  case AtomicRMWInst::Min:
  case AtomicRMWInst::UMax:
  case AtomicRMWInst::UMin: {
    // Finally, comparison ops will operate on the full value, so
    // truncate down to the original size, and expand out again after
    // doing the operation.
    Value *Loaded_Shiftdown = Builder.CreateTrunc(
        Builder.CreateLShr(Loaded, PMV.ShiftAmt), PMV.ValueType);
    Value *NewVal = performAtomicOp(Op, Builder, Loaded_Shiftdown, Inc);
    Value *NewVal_Shiftup = Builder.CreateShl(
        Builder.CreateZExt(NewVal, PMV.WordType), PMV.ShiftAmt);
    Value *Loaded_MaskOut = Builder.CreateAnd(Loaded, PMV.Inv_Mask);
    Value *FinalVal = Builder.CreateOr(Loaded_MaskOut, NewVal_Shiftup);
    return FinalVal;
  }
  default:
    llvm_unreachable("Unknown atomic op");
  }
}

/// Expand a sub-word atomicrmw operation into an appropriate
/// word-sized operation.
///
/// It will create an LL/SC or cmpxchg loop, as appropriate, the same
/// way as a typical atomicrmw expansion. The only difference here is
/// that the operation inside of the loop must operate only upon a
/// part of the value.
void AtomicExpand::expandPartwordAtomicRMW(
    AtomicRMWInst *AI, TargetLoweringBase::AtomicExpansionKind ExpansionKind) {

  assert(ExpansionKind == TargetLoweringBase::AtomicExpansionKind::CmpXChg);

  AtomicOrdering MemOpOrder = AI->getOrdering();

  IRBuilder<> Builder(AI);

  PartwordMaskValues PMV =
      createMaskInstrs(Builder, AI, AI->getType(), AI->getPointerOperand(),
                       TLI->getMinCmpXchgSizeInBits() / 8);

  Value *ValOperand_Shifted =
      Builder.CreateShl(Builder.CreateZExt(AI->getValOperand(), PMV.WordType),
                        PMV.ShiftAmt, "ValOperand_Shifted");

  auto PerformPartwordOp = [&](IRBuilder<> &Builder, Value *Loaded) {
    return performMaskedAtomicOp(AI->getOperation(), Builder, Loaded,
                                 ValOperand_Shifted, AI->getValOperand(), PMV);
  };

  // TODO: When we're ready to support LLSC conversions too, use
  // insertRMWLLSCLoop here for ExpansionKind==LLSC.
  Value *OldResult =
      insertRMWCmpXchgLoop(Builder, PMV.WordType, PMV.AlignedAddr, MemOpOrder,
                           PerformPartwordOp, createCmpXchgInstFun);
  Value *FinalOldResult = Builder.CreateTrunc(
      Builder.CreateLShr(OldResult, PMV.ShiftAmt), PMV.ValueType);
  AI->replaceAllUsesWith(FinalOldResult);
  AI->eraseFromParent();
}

void AtomicExpand::expandPartwordCmpXchg(AtomicCmpXchgInst *CI) {
  // The basic idea here is that we're expanding a cmpxchg of a
  // smaller memory size up to a word-sized cmpxchg. To do this, we
  // need to add a retry-loop for strong cmpxchg, so that
  // modifications to other parts of the word don't cause a spurious
  // failure.

  // This generates code like the following:
  //     [[Setup mask values PMV.*]]
  //     %NewVal_Shifted = shl i32 %NewVal, %PMV.ShiftAmt
  //     %Cmp_Shifted = shl i32 %Cmp, %PMV.ShiftAmt
  //     %InitLoaded = load i32* %addr
  //     %InitLoaded_MaskOut = and i32 %InitLoaded, %PMV.Inv_Mask
  //     br partword.cmpxchg.loop
  // partword.cmpxchg.loop:
  //     %Loaded_MaskOut = phi i32 [ %InitLoaded_MaskOut, %entry ],
  //        [ %OldVal_MaskOut, %partword.cmpxchg.failure ]
  //     %FullWord_NewVal = or i32 %Loaded_MaskOut, %NewVal_Shifted
  //     %FullWord_Cmp = or i32 %Loaded_MaskOut, %Cmp_Shifted
  //     %NewCI = cmpxchg i32* %PMV.AlignedAddr, i32 %FullWord_Cmp,
  //        i32 %FullWord_NewVal success_ordering failure_ordering
  //     %OldVal = extractvalue { i32, i1 } %NewCI, 0
  //     %Success = extractvalue { i32, i1 } %NewCI, 1
  //     br i1 %Success, label %partword.cmpxchg.end,
  //        label %partword.cmpxchg.failure
  // partword.cmpxchg.failure:
  //     %OldVal_MaskOut = and i32 %OldVal, %PMV.Inv_Mask
  //     %ShouldContinue = icmp ne i32 %Loaded_MaskOut, %OldVal_MaskOut
  //     br i1 %ShouldContinue, label %partword.cmpxchg.loop,
  //         label %partword.cmpxchg.end
  // partword.cmpxchg.end:
  //    %tmp1 = lshr i32 %OldVal, %PMV.ShiftAmt
  //    %FinalOldVal = trunc i32 %tmp1 to i8
  //    %tmp2 = insertvalue { i8, i1 } undef, i8 %FinalOldVal, 0
  //    %Res = insertvalue { i8, i1 } %25, i1 %Success, 1

  Value *Addr = CI->getPointerOperand();
  Value *Cmp = CI->getCompareOperand();
  Value *NewVal = CI->getNewValOperand();

  BasicBlock *BB = CI->getParent();
  Function *F = BB->getParent();
  IRBuilder<> Builder(CI);
  LLVMContext &Ctx = Builder.getContext();

  const int WordSize = TLI->getMinCmpXchgSizeInBits() / 8;

  BasicBlock *EndBB =
      BB->splitBasicBlock(CI->getIterator(), "partword.cmpxchg.end");
  auto FailureBB =
      BasicBlock::Create(Ctx, "partword.cmpxchg.failure", F, EndBB);
  auto LoopBB = BasicBlock::Create(Ctx, "partword.cmpxchg.loop", F, FailureBB);

  // The split call above "helpfully" added a branch at the end of BB
  // (to the wrong place).
  std::prev(BB->end())->eraseFromParent();
  Builder.SetInsertPoint(BB);

  PartwordMaskValues PMV = createMaskInstrs(
      Builder, CI, CI->getCompareOperand()->getType(), Addr, WordSize);

  // Shift the incoming values over, into the right location in the word.
  Value *NewVal_Shifted =
      Builder.CreateShl(Builder.CreateZExt(NewVal, PMV.WordType), PMV.ShiftAmt);
  Value *Cmp_Shifted =
      Builder.CreateShl(Builder.CreateZExt(Cmp, PMV.WordType), PMV.ShiftAmt);

  // Load the entire current word, and mask into place the expected and new
  // values
  LoadInst *InitLoaded = Builder.CreateLoad(PMV.WordType, PMV.AlignedAddr);
  InitLoaded->setVolatile(CI->isVolatile());
  Value *InitLoaded_MaskOut = Builder.CreateAnd(InitLoaded, PMV.Inv_Mask);
  Builder.CreateBr(LoopBB);

  // partword.cmpxchg.loop:
  Builder.SetInsertPoint(LoopBB);
  PHINode *Loaded_MaskOut = Builder.CreatePHI(PMV.WordType, 2);
  Loaded_MaskOut->addIncoming(InitLoaded_MaskOut, BB);

  // Mask/Or the expected and new values into place in the loaded word.
  Value *FullWord_NewVal = Builder.CreateOr(Loaded_MaskOut, NewVal_Shifted);
  Value *FullWord_Cmp = Builder.CreateOr(Loaded_MaskOut, Cmp_Shifted);
  AtomicCmpXchgInst *NewCI = Builder.CreateAtomicCmpXchg(
      PMV.AlignedAddr, FullWord_Cmp, FullWord_NewVal, CI->getSuccessOrdering(),
      CI->getFailureOrdering(), CI->getSynchScope());
  NewCI->setVolatile(CI->isVolatile());
  // When we're building a strong cmpxchg, we need a loop, so you
  // might think we could use a weak cmpxchg inside. But, using strong
  // allows the below comparison for ShouldContinue, and we're
  // expecting the underlying cmpxchg to be a machine instruction,
  // which is strong anyways.
  NewCI->setWeak(CI->isWeak());

  Value *OldVal = Builder.CreateExtractValue(NewCI, 0);
  Value *Success = Builder.CreateExtractValue(NewCI, 1);

  if (CI->isWeak())
    Builder.CreateBr(EndBB);
  else
    Builder.CreateCondBr(Success, EndBB, FailureBB);

  // partword.cmpxchg.failure:
  Builder.SetInsertPoint(FailureBB);
  // Upon failure, verify that the masked-out part of the loaded value
  // has been modified.  If it didn't, abort the cmpxchg, since the
  // masked-in part must've.
  Value *OldVal_MaskOut = Builder.CreateAnd(OldVal, PMV.Inv_Mask);
  Value *ShouldContinue = Builder.CreateICmpNE(Loaded_MaskOut, OldVal_MaskOut);
  Builder.CreateCondBr(ShouldContinue, LoopBB, EndBB);

  // Add the second value to the phi from above
  Loaded_MaskOut->addIncoming(OldVal_MaskOut, FailureBB);

  // partword.cmpxchg.end:
  Builder.SetInsertPoint(CI);

  Value *FinalOldVal = Builder.CreateTrunc(
      Builder.CreateLShr(OldVal, PMV.ShiftAmt), PMV.ValueType);
  Value *Res = UndefValue::get(CI->getType());
  Res = Builder.CreateInsertValue(Res, FinalOldVal, 0);
  Res = Builder.CreateInsertValue(Res, Success, 1);

  CI->replaceAllUsesWith(Res);
  CI->eraseFromParent();
}

void AtomicExpand::expandAtomicOpToLLSC(
    Instruction *I, Type *ResultType, Value *Addr, AtomicOrdering MemOpOrder,
    function_ref<Value *(IRBuilder<> &, Value *)> PerformOp) {
  IRBuilder<> Builder(I);
  Value *Loaded =
      insertRMWLLSCLoop(Builder, ResultType, Addr, MemOpOrder, PerformOp);

  I->replaceAllUsesWith(Loaded);
  I->eraseFromParent();
}

Value *AtomicExpand::insertRMWLLSCLoop(
    IRBuilder<> &Builder, Type *ResultTy, Value *Addr,
    AtomicOrdering MemOpOrder,
    function_ref<Value *(IRBuilder<> &, Value *)> PerformOp) {
  LLVMContext &Ctx = Builder.getContext();
  BasicBlock *BB = Builder.GetInsertBlock();
  Function *F = BB->getParent();

  // Given: atomicrmw some_op iN* %addr, iN %incr ordering
  //
  // The standard expansion we produce is:
  //     [...]
  // atomicrmw.start:
  //     %loaded = @load.linked(%addr)
  //     %new = some_op iN %loaded, %incr
  //     %stored = @store_conditional(%new, %addr)
  //     %try_again = icmp i32 ne %stored, 0
  //     br i1 %try_again, label %loop, label %atomicrmw.end
  // atomicrmw.end:
  //     [...]
  BasicBlock *ExitBB =
      BB->splitBasicBlock(Builder.GetInsertPoint(), "atomicrmw.end");
  BasicBlock *LoopBB =  BasicBlock::Create(Ctx, "atomicrmw.start", F, ExitBB);

  // The split call above "helpfully" added a branch at the end of BB (to the
  // wrong place).
  std::prev(BB->end())->eraseFromParent();
  Builder.SetInsertPoint(BB);
  Builder.CreateBr(LoopBB);

  // Start the main loop block now that we've taken care of the preliminaries.
  Builder.SetInsertPoint(LoopBB);
  Value *Loaded = TLI->emitLoadLinked(Builder, Addr, MemOpOrder);

  Value *NewVal = PerformOp(Builder, Loaded);

  Value *StoreSuccess =
      TLI->emitStoreConditional(Builder, NewVal, Addr, MemOpOrder);
  Value *TryAgain = Builder.CreateICmpNE(
      StoreSuccess, ConstantInt::get(IntegerType::get(Ctx, 32), 0), "tryagain");
  Builder.CreateCondBr(TryAgain, LoopBB, ExitBB);

  Builder.SetInsertPoint(ExitBB, ExitBB->begin());
  return Loaded;
}

/// Convert an atomic cmpxchg of a non-integral type to an integer cmpxchg of
/// the equivalent bitwidth.  We used to not support pointer cmpxchg in the
/// IR.  As a migration step, we convert back to what use to be the standard
/// way to represent a pointer cmpxchg so that we can update backends one by
/// one. 
AtomicCmpXchgInst *AtomicExpand::convertCmpXchgToIntegerType(AtomicCmpXchgInst *CI) {
  auto *M = CI->getModule();
  Type *NewTy = getCorrespondingIntegerType(CI->getCompareOperand()->getType(),
                                            M->getDataLayout());

  IRBuilder<> Builder(CI);
  
  Value *Addr = CI->getPointerOperand();
  Type *PT = PointerType::get(NewTy,
                              Addr->getType()->getPointerAddressSpace());
  Value *NewAddr = Builder.CreateBitCast(Addr, PT);

  Value *NewCmp = Builder.CreatePtrToInt(CI->getCompareOperand(), NewTy);
  Value *NewNewVal = Builder.CreatePtrToInt(CI->getNewValOperand(), NewTy);
  
  
  auto *NewCI = Builder.CreateAtomicCmpXchg(NewAddr, NewCmp, NewNewVal,
                                            CI->getSuccessOrdering(),
                                            CI->getFailureOrdering(),
                                            CI->getSynchScope());
  NewCI->setVolatile(CI->isVolatile());
  NewCI->setWeak(CI->isWeak());
  DEBUG(dbgs() << "Replaced " << *CI << " with " << *NewCI << "\n");

  Value *OldVal = Builder.CreateExtractValue(NewCI, 0);
  Value *Succ = Builder.CreateExtractValue(NewCI, 1);

  OldVal = Builder.CreateIntToPtr(OldVal, CI->getCompareOperand()->getType());

  Value *Res = UndefValue::get(CI->getType());
  Res = Builder.CreateInsertValue(Res, OldVal, 0);
  Res = Builder.CreateInsertValue(Res, Succ, 1);

  CI->replaceAllUsesWith(Res);
  CI->eraseFromParent();
  return NewCI;
}


bool AtomicExpand::expandAtomicCmpXchg(AtomicCmpXchgInst *CI) {
  AtomicOrdering SuccessOrder = CI->getSuccessOrdering();
  AtomicOrdering FailureOrder = CI->getFailureOrdering();
  Value *Addr = CI->getPointerOperand();
  BasicBlock *BB = CI->getParent();
  Function *F = BB->getParent();
  LLVMContext &Ctx = F->getContext();
  // If shouldInsertFencesForAtomic() returns true, then the target does not
  // want to deal with memory orders, and emitLeading/TrailingFence should take
  // care of everything. Otherwise, emitLeading/TrailingFence are no-op and we
  // should preserve the ordering.
  bool ShouldInsertFencesForAtomic = TLI->shouldInsertFencesForAtomic(CI);
  AtomicOrdering MemOpOrder =
      ShouldInsertFencesForAtomic ? AtomicOrdering::Monotonic : SuccessOrder;

  // In implementations which use a barrier to achieve release semantics, we can
  // delay emitting this barrier until we know a store is actually going to be
  // attempted. The cost of this delay is that we need 2 copies of the block
  // emitting the load-linked, affecting code size.
  //
  // Ideally, this logic would be unconditional except for the minsize check
  // since in other cases the extra blocks naturally collapse down to the
  // minimal loop. Unfortunately, this puts too much stress on later
  // optimisations so we avoid emitting the extra logic in those cases too.
  bool HasReleasedLoadBB = !CI->isWeak() && ShouldInsertFencesForAtomic &&
                           SuccessOrder != AtomicOrdering::Monotonic &&
                           SuccessOrder != AtomicOrdering::Acquire &&
                           !F->optForMinSize();

  // There's no overhead for sinking the release barrier in a weak cmpxchg, so
  // do it even on minsize.
  bool UseUnconditionalReleaseBarrier = F->optForMinSize() && !CI->isWeak();

  // Given: cmpxchg some_op iN* %addr, iN %desired, iN %new success_ord fail_ord
  //
  // The full expansion we produce is:
  //     [...]
  // cmpxchg.start:
  //     %unreleasedload = @load.linked(%addr)
  //     %should_store = icmp eq %unreleasedload, %desired
  //     br i1 %should_store, label %cmpxchg.fencedstore,
  //                          label %cmpxchg.nostore
  // cmpxchg.releasingstore:
  //     fence?
  //     br label cmpxchg.trystore
  // cmpxchg.trystore:
  //     %loaded.trystore = phi [%unreleasedload, %releasingstore],
  //                            [%releasedload, %cmpxchg.releasedload]
  //     %stored = @store_conditional(%new, %addr)
  //     %success = icmp eq i32 %stored, 0
  //     br i1 %success, label %cmpxchg.success,
  //                     label %cmpxchg.releasedload/%cmpxchg.failure
  // cmpxchg.releasedload:
  //     %releasedload = @load.linked(%addr)
  //     %should_store = icmp eq %releasedload, %desired
  //     br i1 %should_store, label %cmpxchg.trystore,
  //                          label %cmpxchg.failure
  // cmpxchg.success:
  //     fence?
  //     br label %cmpxchg.end
  // cmpxchg.nostore:
  //     %loaded.nostore = phi [%unreleasedload, %cmpxchg.start],
  //                           [%releasedload,
  //                               %cmpxchg.releasedload/%cmpxchg.trystore]
  //     @load_linked_fail_balance()?
  //     br label %cmpxchg.failure
  // cmpxchg.failure:
  //     fence?
  //     br label %cmpxchg.end
  // cmpxchg.end:
  //     %loaded = phi [%loaded.nostore, %cmpxchg.failure],
  //                   [%loaded.trystore, %cmpxchg.trystore]
  //     %success = phi i1 [true, %cmpxchg.success], [false, %cmpxchg.failure]
  //     %restmp = insertvalue { iN, i1 } undef, iN %loaded, 0
  //     %res = insertvalue { iN, i1 } %restmp, i1 %success, 1
  //     [...]
  BasicBlock *ExitBB = BB->splitBasicBlock(CI->getIterator(), "cmpxchg.end");
  auto FailureBB = BasicBlock::Create(Ctx, "cmpxchg.failure", F, ExitBB);
  auto NoStoreBB = BasicBlock::Create(Ctx, "cmpxchg.nostore", F, FailureBB);
  auto SuccessBB = BasicBlock::Create(Ctx, "cmpxchg.success", F, NoStoreBB);
  auto ReleasedLoadBB =
      BasicBlock::Create(Ctx, "cmpxchg.releasedload", F, SuccessBB);
  auto TryStoreBB =
      BasicBlock::Create(Ctx, "cmpxchg.trystore", F, ReleasedLoadBB);
  auto ReleasingStoreBB =
      BasicBlock::Create(Ctx, "cmpxchg.fencedstore", F, TryStoreBB);
  auto StartBB = BasicBlock::Create(Ctx, "cmpxchg.start", F, ReleasingStoreBB);

  // This grabs the DebugLoc from CI
  IRBuilder<> Builder(CI);

  // The split call above "helpfully" added a branch at the end of BB (to the
  // wrong place), but we might want a fence too. It's easiest to just remove
  // the branch entirely.
  std::prev(BB->end())->eraseFromParent();
  Builder.SetInsertPoint(BB);
  if (ShouldInsertFencesForAtomic && UseUnconditionalReleaseBarrier)
    TLI->emitLeadingFence(Builder, CI, SuccessOrder);
  Builder.CreateBr(StartBB);

  // Start the main loop block now that we've taken care of the preliminaries.
  Builder.SetInsertPoint(StartBB);
  Value *UnreleasedLoad = TLI->emitLoadLinked(Builder, Addr, MemOpOrder);
  Value *ShouldStore = Builder.CreateICmpEQ(
      UnreleasedLoad, CI->getCompareOperand(), "should_store");

  // If the cmpxchg doesn't actually need any ordering when it fails, we can
  // jump straight past that fence instruction (if it exists).
  Builder.CreateCondBr(ShouldStore, ReleasingStoreBB, NoStoreBB);

  Builder.SetInsertPoint(ReleasingStoreBB);
  if (ShouldInsertFencesForAtomic && !UseUnconditionalReleaseBarrier)
    TLI->emitLeadingFence(Builder, CI, SuccessOrder);
  Builder.CreateBr(TryStoreBB);

  Builder.SetInsertPoint(TryStoreBB);
  Value *StoreSuccess = TLI->emitStoreConditional(
      Builder, CI->getNewValOperand(), Addr, MemOpOrder);
  StoreSuccess = Builder.CreateICmpEQ(
      StoreSuccess, ConstantInt::get(Type::getInt32Ty(Ctx), 0), "success");
  BasicBlock *RetryBB = HasReleasedLoadBB ? ReleasedLoadBB : StartBB;
  Builder.CreateCondBr(StoreSuccess, SuccessBB,
                       CI->isWeak() ? FailureBB : RetryBB);

  Builder.SetInsertPoint(ReleasedLoadBB);
  Value *SecondLoad;
  if (HasReleasedLoadBB) {
    SecondLoad = TLI->emitLoadLinked(Builder, Addr, MemOpOrder);
    ShouldStore = Builder.CreateICmpEQ(SecondLoad, CI->getCompareOperand(),
                                       "should_store");

    // If the cmpxchg doesn't actually need any ordering when it fails, we can
    // jump straight past that fence instruction (if it exists).
    Builder.CreateCondBr(ShouldStore, TryStoreBB, NoStoreBB);
  } else
    Builder.CreateUnreachable();

  // Make sure later instructions don't get reordered with a fence if
  // necessary.
  Builder.SetInsertPoint(SuccessBB);
  if (ShouldInsertFencesForAtomic)
    TLI->emitTrailingFence(Builder, CI, SuccessOrder);
  Builder.CreateBr(ExitBB);

  Builder.SetInsertPoint(NoStoreBB);
  // In the failing case, where we don't execute the store-conditional, the
  // target might want to balance out the load-linked with a dedicated
  // instruction (e.g., on ARM, clearing the exclusive monitor).
  TLI->emitAtomicCmpXchgNoStoreLLBalance(Builder);
  Builder.CreateBr(FailureBB);

  Builder.SetInsertPoint(FailureBB);
  if (ShouldInsertFencesForAtomic)
    TLI->emitTrailingFence(Builder, CI, FailureOrder);
  Builder.CreateBr(ExitBB);

  // Finally, we have control-flow based knowledge of whether the cmpxchg
  // succeeded or not. We expose this to later passes by converting any
  // subsequent "icmp eq/ne %loaded, %oldval" into a use of an appropriate
  // PHI.
  Builder.SetInsertPoint(ExitBB, ExitBB->begin());
  PHINode *Success = Builder.CreatePHI(Type::getInt1Ty(Ctx), 2);
  Success->addIncoming(ConstantInt::getTrue(Ctx), SuccessBB);
  Success->addIncoming(ConstantInt::getFalse(Ctx), FailureBB);

  // Setup the builder so we can create any PHIs we need.
  Value *Loaded;
  if (!HasReleasedLoadBB)
    Loaded = UnreleasedLoad;
  else {
    Builder.SetInsertPoint(TryStoreBB, TryStoreBB->begin());
    PHINode *TryStoreLoaded = Builder.CreatePHI(UnreleasedLoad->getType(), 2);
    TryStoreLoaded->addIncoming(UnreleasedLoad, ReleasingStoreBB);
    TryStoreLoaded->addIncoming(SecondLoad, ReleasedLoadBB);

    Builder.SetInsertPoint(NoStoreBB, NoStoreBB->begin());
    PHINode *NoStoreLoaded = Builder.CreatePHI(UnreleasedLoad->getType(), 2);
    NoStoreLoaded->addIncoming(UnreleasedLoad, StartBB);
    NoStoreLoaded->addIncoming(SecondLoad, ReleasedLoadBB);

    Builder.SetInsertPoint(ExitBB, ++ExitBB->begin());
    PHINode *ExitLoaded = Builder.CreatePHI(UnreleasedLoad->getType(), 2);
    ExitLoaded->addIncoming(TryStoreLoaded, SuccessBB);
    ExitLoaded->addIncoming(NoStoreLoaded, FailureBB);

    Loaded = ExitLoaded;
  }

  // Look for any users of the cmpxchg that are just comparing the loaded value
  // against the desired one, and replace them with the CFG-derived version.
  SmallVector<ExtractValueInst *, 2> PrunedInsts;
  for (auto User : CI->users()) {
    ExtractValueInst *EV = dyn_cast<ExtractValueInst>(User);
    if (!EV)
      continue;

    assert(EV->getNumIndices() == 1 && EV->getIndices()[0] <= 1 &&
           "weird extraction from { iN, i1 }");

    if (EV->getIndices()[0] == 0)
      EV->replaceAllUsesWith(Loaded);
    else
      EV->replaceAllUsesWith(Success);

    PrunedInsts.push_back(EV);
  }

  // We can remove the instructions now we're no longer iterating through them.
  for (auto EV : PrunedInsts)
    EV->eraseFromParent();

  if (!CI->use_empty()) {
    // Some use of the full struct return that we don't understand has happened,
    // so we've got to reconstruct it properly.
    Value *Res;
    Res = Builder.CreateInsertValue(UndefValue::get(CI->getType()), Loaded, 0);
    Res = Builder.CreateInsertValue(Res, Success, 1);

    CI->replaceAllUsesWith(Res);
  }

  CI->eraseFromParent();
  return true;
}

bool AtomicExpand::isIdempotentRMW(AtomicRMWInst* RMWI) {
  auto C = dyn_cast<ConstantInt>(RMWI->getValOperand());
  if(!C)
    return false;

  AtomicRMWInst::BinOp Op = RMWI->getOperation();
  switch(Op) {
    case AtomicRMWInst::Add:
    case AtomicRMWInst::Sub:
    case AtomicRMWInst::Or:
    case AtomicRMWInst::Xor:
      return C->isZero();
    case AtomicRMWInst::And:
      return C->isMinusOne();
    // FIXME: we could also treat Min/Max/UMin/UMax by the INT_MIN/INT_MAX/...
    default:
      return false;
  }
}

bool AtomicExpand::simplifyIdempotentRMW(AtomicRMWInst* RMWI) {
  if (auto ResultingLoad = TLI->lowerIdempotentRMWIntoFencedLoad(RMWI)) {
    tryExpandAtomicLoad(ResultingLoad);
    return true;
  }
  return false;
}

Value *AtomicExpand::insertRMWCmpXchgLoop(
    IRBuilder<> &Builder, Type *ResultTy, Value *Addr,
    AtomicOrdering MemOpOrder,
    function_ref<Value *(IRBuilder<> &, Value *)> PerformOp,
    CreateCmpXchgInstFun CreateCmpXchg) {
  LLVMContext &Ctx = Builder.getContext();
  BasicBlock *BB = Builder.GetInsertBlock();
  Function *F = BB->getParent();

  // Given: atomicrmw some_op iN* %addr, iN %incr ordering
  //
  // The standard expansion we produce is:
  //     [...]
  //     %init_loaded = load atomic iN* %addr
  //     br label %loop
  // loop:
  //     %loaded = phi iN [ %init_loaded, %entry ], [ %new_loaded, %loop ]
  //     %new = some_op iN %loaded, %incr
  //     %pair = cmpxchg iN* %addr, iN %loaded, iN %new
  //     %new_loaded = extractvalue { iN, i1 } %pair, 0
  //     %success = extractvalue { iN, i1 } %pair, 1
  //     br i1 %success, label %atomicrmw.end, label %loop
  // atomicrmw.end:
  //     [...]
  BasicBlock *ExitBB =
      BB->splitBasicBlock(Builder.GetInsertPoint(), "atomicrmw.end");
  BasicBlock *LoopBB = BasicBlock::Create(Ctx, "atomicrmw.start", F, ExitBB);

  // The split call above "helpfully" added a branch at the end of BB (to the
  // wrong place), but we want a load. It's easiest to just remove
  // the branch entirely.
  std::prev(BB->end())->eraseFromParent();
  Builder.SetInsertPoint(BB);
  LoadInst *InitLoaded = Builder.CreateLoad(ResultTy, Addr);
  // Atomics require at least natural alignment.
  InitLoaded->setAlignment(ResultTy->getPrimitiveSizeInBits() / 8);
  Builder.CreateBr(LoopBB);

  // Start the main loop block now that we've taken care of the preliminaries.
  Builder.SetInsertPoint(LoopBB);
  PHINode *Loaded = Builder.CreatePHI(ResultTy, 2, "loaded");
  Loaded->addIncoming(InitLoaded, BB);

  Value *NewVal = PerformOp(Builder, Loaded);

  Value *NewLoaded = nullptr;
  Value *Success = nullptr;

  CreateCmpXchg(Builder, Addr, Loaded, NewVal,
                MemOpOrder == AtomicOrdering::Unordered
                    ? AtomicOrdering::Monotonic
                    : MemOpOrder,
                Success, NewLoaded);
  assert(Success && NewLoaded);

  Loaded->addIncoming(NewLoaded, LoopBB);

  Builder.CreateCondBr(Success, ExitBB, LoopBB);

  Builder.SetInsertPoint(ExitBB, ExitBB->begin());
  return NewLoaded;
}

// Note: This function is exposed externally by AtomicExpandUtils.h
bool llvm::expandAtomicRMWToCmpXchg(AtomicRMWInst *AI,
                                    CreateCmpXchgInstFun CreateCmpXchg) {
  IRBuilder<> Builder(AI);
  Value *Loaded = AtomicExpand::insertRMWCmpXchgLoop(
      Builder, AI->getType(), AI->getPointerOperand(), AI->getOrdering(),
      [&](IRBuilder<> &Builder, Value *Loaded) {
        return performAtomicOp(AI->getOperation(), Builder, Loaded,
                               AI->getValOperand());
      },
      CreateCmpXchg);

  AI->replaceAllUsesWith(Loaded);
  AI->eraseFromParent();
  return true;
}

// In order to use one of the sized library calls such as
// __atomic_fetch_add_4, the alignment must be sufficient, the size
// must be one of the potentially-specialized sizes, and the value
// type must actually exist in C on the target (otherwise, the
// function wouldn't actually be defined.)
static bool canUseSizedAtomicCall(unsigned Size, unsigned Align,
                                  const DataLayout &DL) {
  // TODO: "LargestSize" is an approximation for "largest type that
  // you can express in C". It seems to be the case that int128 is
  // supported on all 64-bit platforms, otherwise only up to 64-bit
  // integers are supported. If we get this wrong, then we'll try to
  // call a sized libcall that doesn't actually exist. There should
  // really be some more reliable way in LLVM of determining integer
  // sizes which are valid in the target's C ABI...
  unsigned LargestSize = DL.getLargestLegalIntTypeSizeInBits() >= 64 ? 16 : 8;
  return Align >= Size &&
         (Size == 1 || Size == 2 || Size == 4 || Size == 8 || Size == 16) &&
         Size <= LargestSize;
}

void AtomicExpand::expandAtomicLoadToLibcall(LoadInst *I) {
  static const RTLIB::Libcall Libcalls[6] = {
      RTLIB::ATOMIC_LOAD,   RTLIB::ATOMIC_LOAD_1, RTLIB::ATOMIC_LOAD_2,
      RTLIB::ATOMIC_LOAD_4, RTLIB::ATOMIC_LOAD_8, RTLIB::ATOMIC_LOAD_16};
  unsigned Size = getAtomicOpSize(I);
  unsigned Align = getAtomicOpAlign(I);

  bool expanded = expandAtomicOpToLibcall(
      I, Size, Align, I->getPointerOperand(), nullptr, nullptr,
      I->getOrdering(), AtomicOrdering::NotAtomic, Libcalls);
  (void)expanded;
  assert(expanded && "expandAtomicOpToLibcall shouldn't fail tor Load");
}

void AtomicExpand::expandAtomicStoreToLibcall(StoreInst *I) {
  static const RTLIB::Libcall Libcalls[6] = {
      RTLIB::ATOMIC_STORE,   RTLIB::ATOMIC_STORE_1, RTLIB::ATOMIC_STORE_2,
      RTLIB::ATOMIC_STORE_4, RTLIB::ATOMIC_STORE_8, RTLIB::ATOMIC_STORE_16};
  unsigned Size = getAtomicOpSize(I);
  unsigned Align = getAtomicOpAlign(I);

  bool expanded = expandAtomicOpToLibcall(
      I, Size, Align, I->getPointerOperand(), I->getValueOperand(), nullptr,
      I->getOrdering(), AtomicOrdering::NotAtomic, Libcalls);
  (void)expanded;
  assert(expanded && "expandAtomicOpToLibcall shouldn't fail tor Store");
}

void AtomicExpand::expandAtomicCASToLibcall(AtomicCmpXchgInst *I) {
  static const RTLIB::Libcall Libcalls[6] = {
      RTLIB::ATOMIC_COMPARE_EXCHANGE,   RTLIB::ATOMIC_COMPARE_EXCHANGE_1,
      RTLIB::ATOMIC_COMPARE_EXCHANGE_2, RTLIB::ATOMIC_COMPARE_EXCHANGE_4,
      RTLIB::ATOMIC_COMPARE_EXCHANGE_8, RTLIB::ATOMIC_COMPARE_EXCHANGE_16};
  unsigned Size = getAtomicOpSize(I);
  unsigned Align = getAtomicOpAlign(I);

  bool expanded = expandAtomicOpToLibcall(
      I, Size, Align, I->getPointerOperand(), I->getNewValOperand(),
      I->getCompareOperand(), I->getSuccessOrdering(), I->getFailureOrdering(),
      Libcalls);
  (void)expanded;
  assert(expanded && "expandAtomicOpToLibcall shouldn't fail tor CAS");
}

static ArrayRef<RTLIB::Libcall> GetRMWLibcall(AtomicRMWInst::BinOp Op) {
  static const RTLIB::Libcall LibcallsXchg[6] = {
      RTLIB::ATOMIC_EXCHANGE,   RTLIB::ATOMIC_EXCHANGE_1,
      RTLIB::ATOMIC_EXCHANGE_2, RTLIB::ATOMIC_EXCHANGE_4,
      RTLIB::ATOMIC_EXCHANGE_8, RTLIB::ATOMIC_EXCHANGE_16};
  static const RTLIB::Libcall LibcallsAdd[6] = {
      RTLIB::UNKNOWN_LIBCALL,    RTLIB::ATOMIC_FETCH_ADD_1,
      RTLIB::ATOMIC_FETCH_ADD_2, RTLIB::ATOMIC_FETCH_ADD_4,
      RTLIB::ATOMIC_FETCH_ADD_8, RTLIB::ATOMIC_FETCH_ADD_16};
  static const RTLIB::Libcall LibcallsSub[6] = {
      RTLIB::UNKNOWN_LIBCALL,    RTLIB::ATOMIC_FETCH_SUB_1,
      RTLIB::ATOMIC_FETCH_SUB_2, RTLIB::ATOMIC_FETCH_SUB_4,
      RTLIB::ATOMIC_FETCH_SUB_8, RTLIB::ATOMIC_FETCH_SUB_16};
  static const RTLIB::Libcall LibcallsAnd[6] = {
      RTLIB::UNKNOWN_LIBCALL,    RTLIB::ATOMIC_FETCH_AND_1,
      RTLIB::ATOMIC_FETCH_AND_2, RTLIB::ATOMIC_FETCH_AND_4,
      RTLIB::ATOMIC_FETCH_AND_8, RTLIB::ATOMIC_FETCH_AND_16};
  static const RTLIB::Libcall LibcallsOr[6] = {
      RTLIB::UNKNOWN_LIBCALL,   RTLIB::ATOMIC_FETCH_OR_1,
      RTLIB::ATOMIC_FETCH_OR_2, RTLIB::ATOMIC_FETCH_OR_4,
      RTLIB::ATOMIC_FETCH_OR_8, RTLIB::ATOMIC_FETCH_OR_16};
  static const RTLIB::Libcall LibcallsXor[6] = {
      RTLIB::UNKNOWN_LIBCALL,    RTLIB::ATOMIC_FETCH_XOR_1,
      RTLIB::ATOMIC_FETCH_XOR_2, RTLIB::ATOMIC_FETCH_XOR_4,
      RTLIB::ATOMIC_FETCH_XOR_8, RTLIB::ATOMIC_FETCH_XOR_16};
  static const RTLIB::Libcall LibcallsNand[6] = {
      RTLIB::UNKNOWN_LIBCALL,     RTLIB::ATOMIC_FETCH_NAND_1,
      RTLIB::ATOMIC_FETCH_NAND_2, RTLIB::ATOMIC_FETCH_NAND_4,
      RTLIB::ATOMIC_FETCH_NAND_8, RTLIB::ATOMIC_FETCH_NAND_16};

  switch (Op) {
  case AtomicRMWInst::BAD_BINOP:
    llvm_unreachable("Should not have BAD_BINOP.");
  case AtomicRMWInst::Xchg:
    return makeArrayRef(LibcallsXchg);
  case AtomicRMWInst::Add:
    return makeArrayRef(LibcallsAdd);
  case AtomicRMWInst::Sub:
    return makeArrayRef(LibcallsSub);
  case AtomicRMWInst::And:
    return makeArrayRef(LibcallsAnd);
  case AtomicRMWInst::Or:
    return makeArrayRef(LibcallsOr);
  case AtomicRMWInst::Xor:
    return makeArrayRef(LibcallsXor);
  case AtomicRMWInst::Nand:
    return makeArrayRef(LibcallsNand);
  case AtomicRMWInst::Max:
  case AtomicRMWInst::Min:
  case AtomicRMWInst::UMax:
  case AtomicRMWInst::UMin:
    // No atomic libcalls are available for max/min/umax/umin.
    return {};
  }
  llvm_unreachable("Unexpected AtomicRMW operation.");
}

void AtomicExpand::expandAtomicRMWToLibcall(AtomicRMWInst *I) {
  ArrayRef<RTLIB::Libcall> Libcalls = GetRMWLibcall(I->getOperation());

  unsigned Size = getAtomicOpSize(I);
  unsigned Align = getAtomicOpAlign(I);

  bool Success = false;
  if (!Libcalls.empty())
    Success = expandAtomicOpToLibcall(
        I, Size, Align, I->getPointerOperand(), I->getValOperand(), nullptr,
        I->getOrdering(), AtomicOrdering::NotAtomic, Libcalls);

  // The expansion failed: either there were no libcalls at all for
  // the operation (min/max), or there were only size-specialized
  // libcalls (add/sub/etc) and we needed a generic. So, expand to a
  // CAS libcall, via a CAS loop, instead.
  if (!Success) {
    expandAtomicRMWToCmpXchg(I, [this](IRBuilder<> &Builder, Value *Addr,
                                       Value *Loaded, Value *NewVal,
                                       AtomicOrdering MemOpOrder,
                                       Value *&Success, Value *&NewLoaded) {
      // Create the CAS instruction normally...
      AtomicCmpXchgInst *Pair = Builder.CreateAtomicCmpXchg(
          Addr, Loaded, NewVal, MemOpOrder,
          AtomicCmpXchgInst::getStrongestFailureOrdering(MemOpOrder));
      Success = Builder.CreateExtractValue(Pair, 1, "success");
      NewLoaded = Builder.CreateExtractValue(Pair, 0, "newloaded");

      // ...and then expand the CAS into a libcall.
      expandAtomicCASToLibcall(Pair);
    });
  }
}

// A helper routine for the above expandAtomic*ToLibcall functions.
//
// 'Libcalls' contains an array of enum values for the particular
// ATOMIC libcalls to be emitted. All of the other arguments besides
// 'I' are extracted from the Instruction subclass by the
// caller. Depending on the particular call, some will be null.
bool AtomicExpand::expandAtomicOpToLibcall(
    Instruction *I, unsigned Size, unsigned Align, Value *PointerOperand,
    Value *ValueOperand, Value *CASExpected, AtomicOrdering Ordering,
    AtomicOrdering Ordering2, ArrayRef<RTLIB::Libcall> Libcalls) {
  assert(Libcalls.size() == 6);

  LLVMContext &Ctx = I->getContext();
  Module *M = I->getModule();
  const DataLayout &DL = M->getDataLayout();
  IRBuilder<> Builder(I);
  IRBuilder<> AllocaBuilder(&I->getFunction()->getEntryBlock().front());

  bool UseSizedLibcall = canUseSizedAtomicCall(Size, Align, DL);
  Type *SizedIntTy = Type::getIntNTy(Ctx, Size * 8);

  unsigned AllocaAlignment = DL.getPrefTypeAlignment(SizedIntTy);

  // TODO: the "order" argument type is "int", not int32. So
  // getInt32Ty may be wrong if the arch uses e.g. 16-bit ints.
  ConstantInt *SizeVal64 = ConstantInt::get(Type::getInt64Ty(Ctx), Size);
  assert(Ordering != AtomicOrdering::NotAtomic && "expect atomic MO");
  Constant *OrderingVal =
      ConstantInt::get(Type::getInt32Ty(Ctx), (int)toCABI(Ordering));
  Constant *Ordering2Val = nullptr;
  if (CASExpected) {
    assert(Ordering2 != AtomicOrdering::NotAtomic && "expect atomic MO");
    Ordering2Val =
        ConstantInt::get(Type::getInt32Ty(Ctx), (int)toCABI(Ordering2));
  }
  bool HasResult = I->getType() != Type::getVoidTy(Ctx);

  RTLIB::Libcall RTLibType;
  if (UseSizedLibcall) {
    switch (Size) {
    case 1: RTLibType = Libcalls[1]; break;
    case 2: RTLibType = Libcalls[2]; break;
    case 4: RTLibType = Libcalls[3]; break;
    case 8: RTLibType = Libcalls[4]; break;
    case 16: RTLibType = Libcalls[5]; break;
    }
  } else if (Libcalls[0] != RTLIB::UNKNOWN_LIBCALL) {
    RTLibType = Libcalls[0];
  } else {
    // Can't use sized function, and there's no generic for this
    // operation, so give up.
    return false;
  }

  // Build up the function call. There's two kinds. First, the sized
  // variants.  These calls are going to be one of the following (with
  // N=1,2,4,8,16):
  //  iN    __atomic_load_N(iN *ptr, int ordering)
  //  void  __atomic_store_N(iN *ptr, iN val, int ordering)
  //  iN    __atomic_{exchange|fetch_*}_N(iN *ptr, iN val, int ordering)
  //  bool  __atomic_compare_exchange_N(iN *ptr, iN *expected, iN desired,
  //                                    int success_order, int failure_order)
  //
  // Note that these functions can be used for non-integer atomic
  // operations, the values just need to be bitcast to integers on the
  // way in and out.
  //
  // And, then, the generic variants. They look like the following:
  //  void  __atomic_load(size_t size, void *ptr, void *ret, int ordering)
  //  void  __atomic_store(size_t size, void *ptr, void *val, int ordering)
  //  void  __atomic_exchange(size_t size, void *ptr, void *val, void *ret,
  //                          int ordering)
  //  bool  __atomic_compare_exchange(size_t size, void *ptr, void *expected,
  //                                  void *desired, int success_order,
  //                                  int failure_order)
  //
  // The different signatures are built up depending on the
  // 'UseSizedLibcall', 'CASExpected', 'ValueOperand', and 'HasResult'
  // variables.

  AllocaInst *AllocaCASExpected = nullptr;
  Value *AllocaCASExpected_i8 = nullptr;
  AllocaInst *AllocaValue = nullptr;
  Value *AllocaValue_i8 = nullptr;
  AllocaInst *AllocaResult = nullptr;
  Value *AllocaResult_i8 = nullptr;

  Type *ResultTy;
  SmallVector<Value *, 6> Args;
  AttributeList Attr;

  // 'size' argument.
  if (!UseSizedLibcall) {
    // Note, getIntPtrType is assumed equivalent to size_t.
    Args.push_back(ConstantInt::get(DL.getIntPtrType(Ctx), Size));
  }

  // 'ptr' argument.
  Value *PtrVal =
      Builder.CreateBitCast(PointerOperand, Type::getInt8PtrTy(Ctx));
  Args.push_back(PtrVal);

  // 'expected' argument, if present.
  if (CASExpected) {
    AllocaCASExpected = AllocaBuilder.CreateAlloca(CASExpected->getType());
    AllocaCASExpected->setAlignment(AllocaAlignment);
    AllocaCASExpected_i8 =
        Builder.CreateBitCast(AllocaCASExpected, Type::getInt8PtrTy(Ctx));
    Builder.CreateLifetimeStart(AllocaCASExpected_i8, SizeVal64);
    Builder.CreateAlignedStore(CASExpected, AllocaCASExpected, AllocaAlignment);
    Args.push_back(AllocaCASExpected_i8);
  }

  // 'val' argument ('desired' for cas), if present.
  if (ValueOperand) {
    if (UseSizedLibcall) {
      Value *IntValue =
          Builder.CreateBitOrPointerCast(ValueOperand, SizedIntTy);
      Args.push_back(IntValue);
    } else {
      AllocaValue = AllocaBuilder.CreateAlloca(ValueOperand->getType());
      AllocaValue->setAlignment(AllocaAlignment);
      AllocaValue_i8 =
          Builder.CreateBitCast(AllocaValue, Type::getInt8PtrTy(Ctx));
      Builder.CreateLifetimeStart(AllocaValue_i8, SizeVal64);
      Builder.CreateAlignedStore(ValueOperand, AllocaValue, AllocaAlignment);
      Args.push_back(AllocaValue_i8);
    }
  }

  // 'ret' argument.
  if (!CASExpected && HasResult && !UseSizedLibcall) {
    AllocaResult = AllocaBuilder.CreateAlloca(I->getType());
    AllocaResult->setAlignment(AllocaAlignment);
    AllocaResult_i8 =
        Builder.CreateBitCast(AllocaResult, Type::getInt8PtrTy(Ctx));
    Builder.CreateLifetimeStart(AllocaResult_i8, SizeVal64);
    Args.push_back(AllocaResult_i8);
  }

  // 'ordering' ('success_order' for cas) argument.
  Args.push_back(OrderingVal);

  // 'failure_order' argument, if present.
  if (Ordering2Val)
    Args.push_back(Ordering2Val);

  // Now, the return type.
  if (CASExpected) {
    ResultTy = Type::getInt1Ty(Ctx);
    Attr = Attr.addAttribute(Ctx, AttributeList::ReturnIndex, Attribute::ZExt);
  } else if (HasResult && UseSizedLibcall)
    ResultTy = SizedIntTy;
  else
    ResultTy = Type::getVoidTy(Ctx);

  // Done with setting up arguments and return types, create the call:
  SmallVector<Type *, 6> ArgTys;
  for (Value *Arg : Args)
    ArgTys.push_back(Arg->getType());
  FunctionType *FnType = FunctionType::get(ResultTy, ArgTys, false);
  Constant *LibcallFn =
      M->getOrInsertFunction(TLI->getLibcallName(RTLibType), FnType, Attr);
  CallInst *Call = Builder.CreateCall(LibcallFn, Args);
  Call->setAttributes(Attr);
  Value *Result = Call;

  // And then, extract the results...
  if (ValueOperand && !UseSizedLibcall)
    Builder.CreateLifetimeEnd(AllocaValue_i8, SizeVal64);

  if (CASExpected) {
    // The final result from the CAS is {load of 'expected' alloca, bool result
    // from call}
    Type *FinalResultTy = I->getType();
    Value *V = UndefValue::get(FinalResultTy);
    Value *ExpectedOut =
        Builder.CreateAlignedLoad(AllocaCASExpected, AllocaAlignment);
    Builder.CreateLifetimeEnd(AllocaCASExpected_i8, SizeVal64);
    V = Builder.CreateInsertValue(V, ExpectedOut, 0);
    V = Builder.CreateInsertValue(V, Result, 1);
    I->replaceAllUsesWith(V);
  } else if (HasResult) {
    Value *V;
    if (UseSizedLibcall)
      V = Builder.CreateBitOrPointerCast(Result, I->getType());
    else {
      V = Builder.CreateAlignedLoad(AllocaResult, AllocaAlignment);
      Builder.CreateLifetimeEnd(AllocaResult_i8, SizeVal64);
    }
    I->replaceAllUsesWith(V);
  }
  I->eraseFromParent();
  return true;
}