aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm12/lib/Target/ARM/ARMLowOverheadLoops.cpp
blob: 8dc532058492991c39a9937abef642d1c4cd0c78 (plain) (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
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
//===-- ARMLowOverheadLoops.cpp - CodeGen Low-overhead Loops ---*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
/// \file
/// Finalize v8.1-m low-overhead loops by converting the associated pseudo
/// instructions into machine operations.
/// The expectation is that the loop contains three pseudo instructions:
/// - t2*LoopStart - placed in the preheader or pre-preheader. The do-loop
///   form should be in the preheader, whereas the while form should be in the
///   preheaders only predecessor.
/// - t2LoopDec - placed within in the loop body.
/// - t2LoopEnd - the loop latch terminator.
///
/// In addition to this, we also look for the presence of the VCTP instruction,
/// which determines whether we can generated the tail-predicated low-overhead
/// loop form.
///
/// Assumptions and Dependencies:
/// Low-overhead loops are constructed and executed using a setup instruction:
/// DLS, WLS, DLSTP or WLSTP and an instruction that loops back: LE or LETP.
/// WLS(TP) and LE(TP) are branching instructions with a (large) limited range
/// but fixed polarity: WLS can only branch forwards and LE can only branch
/// backwards. These restrictions mean that this pass is dependent upon block
/// layout and block sizes, which is why it's the last pass to run. The same is
/// true for ConstantIslands, but this pass does not increase the size of the
/// basic blocks, nor does it change the CFG. Instructions are mainly removed
/// during the transform and pseudo instructions are replaced by real ones. In
/// some cases, when we have to revert to a 'normal' loop, we have to introduce
/// multiple instructions for a single pseudo (see RevertWhile and
/// RevertLoopEnd). To handle this situation, t2WhileLoopStart and t2LoopEnd
/// are defined to be as large as this maximum sequence of replacement
/// instructions.
///
/// A note on VPR.P0 (the lane mask):
/// VPT, VCMP, VPNOT and VCTP won't overwrite VPR.P0 when they update it in a
/// "VPT Active" context (which includes low-overhead loops and vpt blocks).
/// They will simply "and" the result of their calculation with the current
/// value of VPR.P0. You can think of it like this:
/// \verbatim
/// if VPT active:    ; Between a DLSTP/LETP, or for predicated instrs
///   VPR.P0 &= Value
/// else
///   VPR.P0 = Value
/// \endverbatim
/// When we're inside the low-overhead loop (between DLSTP and LETP), we always
/// fall in the "VPT active" case, so we can consider that all VPR writes by
/// one of those instruction is actually a "and".
//===----------------------------------------------------------------------===//

#include "ARM.h"
#include "ARMBaseInstrInfo.h"
#include "ARMBaseRegisterInfo.h"
#include "ARMBasicBlockInfo.h"
#include "ARMSubtarget.h"
#include "MVETailPredUtils.h"
#include "Thumb2InstrInfo.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineLoopUtils.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/ReachingDefAnalysis.h"
#include "llvm/MC/MCInstrDesc.h"

using namespace llvm;

#define DEBUG_TYPE "arm-low-overhead-loops"
#define ARM_LOW_OVERHEAD_LOOPS_NAME "ARM Low Overhead Loops pass"

static cl::opt<bool>
DisableTailPredication("arm-loloops-disable-tailpred", cl::Hidden,
    cl::desc("Disable tail-predication in the ARM LowOverheadLoop pass"),
    cl::init(false));

static bool isVectorPredicated(MachineInstr *MI) {
  int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);
  return PIdx != -1 && MI->getOperand(PIdx + 1).getReg() == ARM::VPR;
}

static bool isVectorPredicate(MachineInstr *MI) {
  return MI->findRegisterDefOperandIdx(ARM::VPR) != -1;
}

static bool hasVPRUse(MachineInstr &MI) {
  return MI.findRegisterUseOperandIdx(ARM::VPR) != -1;
}

static bool isDomainMVE(MachineInstr *MI) {
  uint64_t Domain = MI->getDesc().TSFlags & ARMII::DomainMask;
  return Domain == ARMII::DomainMVE;
}

static bool shouldInspect(MachineInstr &MI) {
  return isDomainMVE(&MI) || isVectorPredicate(&MI) || hasVPRUse(MI);
}

static bool isDo(MachineInstr *MI) {
  return MI->getOpcode() != ARM::t2WhileLoopStart;
}

namespace {

  using InstSet = SmallPtrSetImpl<MachineInstr *>;

  class PostOrderLoopTraversal {
    MachineLoop &ML;
    MachineLoopInfo &MLI;
    SmallPtrSet<MachineBasicBlock*, 4> Visited;
    SmallVector<MachineBasicBlock*, 4> Order;

  public:
    PostOrderLoopTraversal(MachineLoop &ML, MachineLoopInfo &MLI)
      : ML(ML), MLI(MLI) { }

    const SmallVectorImpl<MachineBasicBlock*> &getOrder() const {
      return Order;
    }

    // Visit all the blocks within the loop, as well as exit blocks and any
    // blocks properly dominating the header.
    void ProcessLoop() {
      std::function<void(MachineBasicBlock*)> Search = [this, &Search]
        (MachineBasicBlock *MBB) -> void {
        if (Visited.count(MBB))
          return;

        Visited.insert(MBB);
        for (auto *Succ : MBB->successors()) {
          if (!ML.contains(Succ))
            continue;
          Search(Succ);
        }
        Order.push_back(MBB);
      };

      // Insert exit blocks.
      SmallVector<MachineBasicBlock*, 2> ExitBlocks;
      ML.getExitBlocks(ExitBlocks);
      append_range(Order, ExitBlocks);

      // Then add the loop body.
      Search(ML.getHeader());

      // Then try the preheader and its predecessors.
      std::function<void(MachineBasicBlock*)> GetPredecessor =
        [this, &GetPredecessor] (MachineBasicBlock *MBB) -> void {
        Order.push_back(MBB);
        if (MBB->pred_size() == 1)
          GetPredecessor(*MBB->pred_begin());
      };

      if (auto *Preheader = ML.getLoopPreheader())
        GetPredecessor(Preheader);
      else if (auto *Preheader = MLI.findLoopPreheader(&ML, true))
        GetPredecessor(Preheader);
    }
  };

  struct PredicatedMI {
    MachineInstr *MI = nullptr;
    SetVector<MachineInstr*> Predicates;

  public:
    PredicatedMI(MachineInstr *I, SetVector<MachineInstr *> &Preds) : MI(I) {
      assert(I && "Instruction must not be null!");
      Predicates.insert(Preds.begin(), Preds.end());
    }
  };

  // Represent the current state of the VPR and hold all instances which
  // represent a VPT block, which is a list of instructions that begins with a
  // VPT/VPST and has a maximum of four proceeding instructions. All
  // instructions within the block are predicated upon the vpr and we allow
  // instructions to define the vpr within in the block too.
  class VPTState {
    friend struct LowOverheadLoop;

    SmallVector<MachineInstr *, 4> Insts;

    static SmallVector<VPTState, 4> Blocks;
    static SetVector<MachineInstr *> CurrentPredicates;
    static std::map<MachineInstr *,
      std::unique_ptr<PredicatedMI>> PredicatedInsts;

    static void CreateVPTBlock(MachineInstr *MI) {
      assert((CurrentPredicates.size() || MI->getParent()->isLiveIn(ARM::VPR))
             && "Can't begin VPT without predicate");
      Blocks.emplace_back(MI);
      // The execution of MI is predicated upon the current set of instructions
      // that are AND'ed together to form the VPR predicate value. In the case
      // that MI is a VPT, CurrentPredicates will also just be MI.
      PredicatedInsts.emplace(
        MI, std::make_unique<PredicatedMI>(MI, CurrentPredicates));
    }

    static void reset() {
      Blocks.clear();
      PredicatedInsts.clear();
      CurrentPredicates.clear();
    }

    static void addInst(MachineInstr *MI) {
      Blocks.back().insert(MI);
      PredicatedInsts.emplace(
        MI, std::make_unique<PredicatedMI>(MI, CurrentPredicates));
    }

    static void addPredicate(MachineInstr *MI) {
      LLVM_DEBUG(dbgs() << "ARM Loops: Adding VPT Predicate: " << *MI);
      CurrentPredicates.insert(MI);
    }

    static void resetPredicate(MachineInstr *MI) {
      LLVM_DEBUG(dbgs() << "ARM Loops: Resetting VPT Predicate: " << *MI);
      CurrentPredicates.clear();
      CurrentPredicates.insert(MI);
    }

  public:
    // Have we found an instruction within the block which defines the vpr? If
    // so, not all the instructions in the block will have the same predicate.
    static bool hasUniformPredicate(VPTState &Block) {
      return getDivergent(Block) == nullptr;
    }

    // If it exists, return the first internal instruction which modifies the
    // VPR.
    static MachineInstr *getDivergent(VPTState &Block) {
      SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
      for (unsigned i = 1; i < Insts.size(); ++i) {
        MachineInstr *Next = Insts[i];
        if (isVectorPredicate(Next))
          return Next; // Found an instruction altering the vpr.
      }
      return nullptr;
    }

    // Return whether the given instruction is predicated upon a VCTP.
    static bool isPredicatedOnVCTP(MachineInstr *MI, bool Exclusive = false) {
      SetVector<MachineInstr *> &Predicates = PredicatedInsts[MI]->Predicates;
      if (Exclusive && Predicates.size() != 1)
        return false;
      for (auto *PredMI : Predicates)
        if (isVCTP(PredMI))
          return true;
      return false;
    }

    // Is the VPST, controlling the block entry, predicated upon a VCTP.
    static bool isEntryPredicatedOnVCTP(VPTState &Block,
                                        bool Exclusive = false) {
      SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
      return isPredicatedOnVCTP(Insts.front(), Exclusive);
    }

    // If this block begins with a VPT, we can check whether it's using
    // at least one predicated input(s), as well as possible loop invariant
    // which would result in it being implicitly predicated.
    static bool hasImplicitlyValidVPT(VPTState &Block,
                                      ReachingDefAnalysis &RDA) {
      SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
      MachineInstr *VPT = Insts.front();
      assert(isVPTOpcode(VPT->getOpcode()) &&
             "Expected VPT block to begin with VPT/VPST");

      if (VPT->getOpcode() == ARM::MVE_VPST)
        return false;

      auto IsOperandPredicated = [&](MachineInstr *MI, unsigned Idx) {
        MachineInstr *Op = RDA.getMIOperand(MI, MI->getOperand(Idx));
        return Op && PredicatedInsts.count(Op) && isPredicatedOnVCTP(Op);
      };

      auto IsOperandInvariant = [&](MachineInstr *MI, unsigned Idx) {
        MachineOperand &MO = MI->getOperand(Idx);
        if (!MO.isReg() || !MO.getReg())
          return true;

        SmallPtrSet<MachineInstr *, 2> Defs;
        RDA.getGlobalReachingDefs(MI, MO.getReg(), Defs);
        if (Defs.empty())
          return true;

        for (auto *Def : Defs)
          if (Def->getParent() == VPT->getParent())
            return false;
        return true;
      };

      // Check that at least one of the operands is directly predicated on a
      // vctp and allow an invariant value too.
      return (IsOperandPredicated(VPT, 1) || IsOperandPredicated(VPT, 2)) &&
             (IsOperandPredicated(VPT, 1) || IsOperandInvariant(VPT, 1)) &&
             (IsOperandPredicated(VPT, 2) || IsOperandInvariant(VPT, 2));
    }

    static bool isValid(ReachingDefAnalysis &RDA) {
      // All predication within the loop should be based on vctp. If the block
      // isn't predicated on entry, check whether the vctp is within the block
      // and that all other instructions are then predicated on it.
      for (auto &Block : Blocks) {
        if (isEntryPredicatedOnVCTP(Block, false) ||
            hasImplicitlyValidVPT(Block, RDA))
          continue;

        SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
        // We don't know how to convert a block with just a VPT;VCTP into
        // anything valid once we remove the VCTP. For now just bail out.
        assert(isVPTOpcode(Insts.front()->getOpcode()) &&
               "Expected VPT block to start with a VPST or VPT!");
        if (Insts.size() == 2 && Insts.front()->getOpcode() != ARM::MVE_VPST &&
            isVCTP(Insts.back()))
          return false;

        for (auto *MI : Insts) {
          // Check that any internal VCTPs are 'Then' predicated.
          if (isVCTP(MI) && getVPTInstrPredicate(*MI) != ARMVCC::Then)
            return false;
          // Skip other instructions that build up the predicate.
          if (MI->getOpcode() == ARM::MVE_VPST || isVectorPredicate(MI))
            continue;
          // Check that any other instructions are predicated upon a vctp.
          // TODO: We could infer when VPTs are implicitly predicated on the
          // vctp (when the operands are predicated).
          if (!isPredicatedOnVCTP(MI)) {
            LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *MI);
            return false;
          }
        }
      }
      return true;
    }

    VPTState(MachineInstr *MI) { Insts.push_back(MI); }

    void insert(MachineInstr *MI) {
      Insts.push_back(MI);
      // VPT/VPST + 4 predicated instructions.
      assert(Insts.size() <= 5 && "Too many instructions in VPT block!");
    }

    bool containsVCTP() const {
      for (auto *MI : Insts)
        if (isVCTP(MI))
          return true;
      return false;
    }

    unsigned size() const { return Insts.size(); }
    SmallVectorImpl<MachineInstr *> &getInsts() { return Insts; }
  };

  struct LowOverheadLoop {

    MachineLoop &ML;
    MachineBasicBlock *Preheader = nullptr;
    MachineLoopInfo &MLI;
    ReachingDefAnalysis &RDA;
    const TargetRegisterInfo &TRI;
    const ARMBaseInstrInfo &TII;
    MachineFunction *MF = nullptr;
    MachineBasicBlock::iterator StartInsertPt;
    MachineBasicBlock *StartInsertBB = nullptr;
    MachineInstr *Start = nullptr;
    MachineInstr *Dec = nullptr;
    MachineInstr *End = nullptr;
    MachineOperand TPNumElements;
    SmallVector<MachineInstr*, 4> VCTPs;
    SmallPtrSet<MachineInstr*, 4> ToRemove;
    SmallPtrSet<MachineInstr*, 4> BlockMasksToRecompute;
    bool Revert = false;
    bool CannotTailPredicate = false;

    LowOverheadLoop(MachineLoop &ML, MachineLoopInfo &MLI,
                    ReachingDefAnalysis &RDA, const TargetRegisterInfo &TRI,
                    const ARMBaseInstrInfo &TII)
        : ML(ML), MLI(MLI), RDA(RDA), TRI(TRI), TII(TII),
          TPNumElements(MachineOperand::CreateImm(0)) {
      MF = ML.getHeader()->getParent();
      if (auto *MBB = ML.getLoopPreheader())
        Preheader = MBB;
      else if (auto *MBB = MLI.findLoopPreheader(&ML, true))
        Preheader = MBB;
      VPTState::reset();
    }

    // If this is an MVE instruction, check that we know how to use tail
    // predication with it. Record VPT blocks and return whether the
    // instruction is valid for tail predication.
    bool ValidateMVEInst(MachineInstr *MI);

    void AnalyseMVEInst(MachineInstr *MI) {
      CannotTailPredicate = !ValidateMVEInst(MI);
    }

    bool IsTailPredicationLegal() const {
      // For now, let's keep things really simple and only support a single
      // block for tail predication.
      return !Revert && FoundAllComponents() && !VCTPs.empty() &&
             !CannotTailPredicate && ML.getNumBlocks() == 1;
    }

    // Given that MI is a VCTP, check that is equivalent to any other VCTPs
    // found.
    bool AddVCTP(MachineInstr *MI);

    // Check that the predication in the loop will be equivalent once we
    // perform the conversion. Also ensure that we can provide the number
    // of elements to the loop start instruction.
    bool ValidateTailPredicate();

    // Check that any values available outside of the loop will be the same
    // after tail predication conversion.
    bool ValidateLiveOuts();

    // Is it safe to define LR with DLS/WLS?
    // LR can be defined if it is the operand to start, because it's the same
    // value, or if it's going to be equivalent to the operand to Start.
    MachineInstr *isSafeToDefineLR();

    // Check the branch targets are within range and we satisfy our
    // restrictions.
    void Validate(ARMBasicBlockUtils *BBUtils);

    bool FoundAllComponents() const {
      return Start && Dec && End;
    }

    SmallVectorImpl<VPTState> &getVPTBlocks() {
      return VPTState::Blocks;
    }

    // Return the operand for the loop start instruction. This will be the loop
    // iteration count, or the number of elements if we're tail predicating.
    MachineOperand &getLoopStartOperand() {
      if (IsTailPredicationLegal())
        return TPNumElements;
      return isDo(Start) ? Start->getOperand(1) : Start->getOperand(0);
    }

    unsigned getStartOpcode() const {
      bool IsDo = isDo(Start);
      if (!IsTailPredicationLegal())
        return IsDo ? ARM::t2DLS : ARM::t2WLS;

      return VCTPOpcodeToLSTP(VCTPs.back()->getOpcode(), IsDo);
    }

    void dump() const {
      if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;
      if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;
      if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;
      if (!VCTPs.empty()) {
        dbgs() << "ARM Loops: Found VCTP(s):\n";
        for (auto *MI : VCTPs)
          dbgs() << " - " << *MI;
      }
      if (!FoundAllComponents())
        dbgs() << "ARM Loops: Not a low-overhead loop.\n";
      else if (!(Start && Dec && End))
        dbgs() << "ARM Loops: Failed to find all loop components.\n";
    }
  };

  class ARMLowOverheadLoops : public MachineFunctionPass {
    MachineFunction           *MF = nullptr;
    MachineLoopInfo           *MLI = nullptr;
    ReachingDefAnalysis       *RDA = nullptr;
    const ARMBaseInstrInfo    *TII = nullptr;
    MachineRegisterInfo       *MRI = nullptr;
    const TargetRegisterInfo  *TRI = nullptr;
    std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;

  public:
    static char ID;

    ARMLowOverheadLoops() : MachineFunctionPass(ID) { }

    void getAnalysisUsage(AnalysisUsage &AU) const override {
      AU.setPreservesCFG();
      AU.addRequired<MachineLoopInfo>();
      AU.addRequired<ReachingDefAnalysis>();
      MachineFunctionPass::getAnalysisUsage(AU);
    }

    bool runOnMachineFunction(MachineFunction &MF) override;

    MachineFunctionProperties getRequiredProperties() const override {
      return MachineFunctionProperties().set(
          MachineFunctionProperties::Property::NoVRegs).set(
          MachineFunctionProperties::Property::TracksLiveness);
    }

    StringRef getPassName() const override {
      return ARM_LOW_OVERHEAD_LOOPS_NAME;
    }

  private:
    bool ProcessLoop(MachineLoop *ML);

    bool RevertNonLoops();

    void RevertWhile(MachineInstr *MI) const;
    void RevertDo(MachineInstr *MI) const;

    bool RevertLoopDec(MachineInstr *MI) const;

    void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const;

    void RevertLoopEndDec(MachineInstr *MI) const;

    void ConvertVPTBlocks(LowOverheadLoop &LoLoop);

    MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop);

    void Expand(LowOverheadLoop &LoLoop);

    void IterationCountDCE(LowOverheadLoop &LoLoop);
  };
}

char ARMLowOverheadLoops::ID = 0;

SmallVector<VPTState, 4> VPTState::Blocks;
SetVector<MachineInstr *> VPTState::CurrentPredicates;
std::map<MachineInstr *,
         std::unique_ptr<PredicatedMI>> VPTState::PredicatedInsts;

INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,
                false, false)

static bool TryRemove(MachineInstr *MI, ReachingDefAnalysis &RDA,
                      InstSet &ToRemove, InstSet &Ignore) {

  // Check that we can remove all of Killed without having to modify any IT
  // blocks.
  auto WontCorruptITs = [](InstSet &Killed, ReachingDefAnalysis &RDA) {
    // Collect the dead code and the MBBs in which they reside.
    SmallPtrSet<MachineBasicBlock*, 2> BasicBlocks;
    for (auto *Dead : Killed)
      BasicBlocks.insert(Dead->getParent());

    // Collect IT blocks in all affected basic blocks.
    std::map<MachineInstr *, SmallPtrSet<MachineInstr *, 2>> ITBlocks;
    for (auto *MBB : BasicBlocks) {
      for (auto &IT : *MBB) {
        if (IT.getOpcode() != ARM::t2IT)
          continue;
        RDA.getReachingLocalUses(&IT, MCRegister::from(ARM::ITSTATE),
                                 ITBlocks[&IT]);
      }
    }

    // If we're removing all of the instructions within an IT block, then
    // also remove the IT instruction.
    SmallPtrSet<MachineInstr *, 2> ModifiedITs;
    SmallPtrSet<MachineInstr *, 2> RemoveITs;
    for (auto *Dead : Killed) {
      if (MachineOperand *MO = Dead->findRegisterUseOperand(ARM::ITSTATE)) {
        MachineInstr *IT = RDA.getMIOperand(Dead, *MO);
        RemoveITs.insert(IT);
        auto &CurrentBlock = ITBlocks[IT];
        CurrentBlock.erase(Dead);
        if (CurrentBlock.empty())
          ModifiedITs.erase(IT);
        else
          ModifiedITs.insert(IT);
      }
    }
    if (!ModifiedITs.empty())
      return false;
    Killed.insert(RemoveITs.begin(), RemoveITs.end());
    return true;
  };

  SmallPtrSet<MachineInstr *, 2> Uses;
  if (!RDA.isSafeToRemove(MI, Uses, Ignore))
    return false;

  if (WontCorruptITs(Uses, RDA)) {
    ToRemove.insert(Uses.begin(), Uses.end());
    LLVM_DEBUG(dbgs() << "ARM Loops: Able to remove: " << *MI
               << " - can also remove:\n";
               for (auto *Use : Uses)
                 dbgs() << "   - " << *Use);

    SmallPtrSet<MachineInstr*, 4> Killed;
    RDA.collectKilledOperands(MI, Killed);
    if (WontCorruptITs(Killed, RDA)) {
      ToRemove.insert(Killed.begin(), Killed.end());
      LLVM_DEBUG(for (auto *Dead : Killed)
                   dbgs() << "   - " << *Dead);
    }
    return true;
  }
  return false;
}

bool LowOverheadLoop::ValidateTailPredicate() {
  if (!IsTailPredicationLegal()) {
    LLVM_DEBUG(if (VCTPs.empty())
                 dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n";
               dbgs() << "ARM Loops: Tail-predication is not valid.\n");
    return false;
  }

  assert(!VCTPs.empty() && "VCTP instruction expected but is not set");
  assert(ML.getBlocks().size() == 1 &&
         "Shouldn't be processing a loop with more than one block");

  if (DisableTailPredication) {
    LLVM_DEBUG(dbgs() << "ARM Loops: tail-predication is disabled\n");
    return false;
  }

  if (!VPTState::isValid(RDA)) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Invalid VPT state.\n");
    return false;
  }

  if (!ValidateLiveOuts()) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Invalid live outs.\n");
    return false;
  }

  // Check that creating a [W|D]LSTP, which will define LR with an element
  // count instead of iteration count, won't affect any other instructions
  // than the LoopStart and LoopDec.
  // TODO: We should try to insert the [W|D]LSTP after any of the other uses.
  Register StartReg = isDo(Start) ? Start->getOperand(1).getReg()
                                  : Start->getOperand(0).getReg();
  if (StartInsertPt == Start && StartReg == ARM::LR) {
    if (auto *IterCount = RDA.getMIOperand(Start, isDo(Start) ? 1 : 0)) {
      SmallPtrSet<MachineInstr *, 2> Uses;
      RDA.getGlobalUses(IterCount, MCRegister::from(ARM::LR), Uses);
      for (auto *Use : Uses) {
        if (Use != Start && Use != Dec) {
          LLVM_DEBUG(dbgs() << " ARM Loops: Found LR use: " << *Use);
          return false;
        }
      }
    }
  }

  // For tail predication, we need to provide the number of elements, instead
  // of the iteration count, to the loop start instruction. The number of
  // elements is provided to the vctp instruction, so we need to check that
  // we can use this register at InsertPt.
  MachineInstr *VCTP = VCTPs.back();
  if (Start->getOpcode() == ARM::t2DoLoopStartTP) {
    TPNumElements = Start->getOperand(2);
    StartInsertPt = Start;
    StartInsertBB = Start->getParent();
  } else {
    TPNumElements = VCTP->getOperand(1);
    MCRegister NumElements = TPNumElements.getReg().asMCReg();

    // If the register is defined within loop, then we can't perform TP.
    // TODO: Check whether this is just a mov of a register that would be
    // available.
    if (RDA.hasLocalDefBefore(VCTP, NumElements)) {
      LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n");
      return false;
    }

    // The element count register maybe defined after InsertPt, in which case we
    // need to try to move either InsertPt or the def so that the [w|d]lstp can
    // use the value.

    if (StartInsertPt != StartInsertBB->end() &&
        !RDA.isReachingDefLiveOut(&*StartInsertPt, NumElements)) {
      if (auto *ElemDef =
              RDA.getLocalLiveOutMIDef(StartInsertBB, NumElements)) {
        if (RDA.isSafeToMoveForwards(ElemDef, &*StartInsertPt)) {
          ElemDef->removeFromParent();
          StartInsertBB->insert(StartInsertPt, ElemDef);
          LLVM_DEBUG(dbgs()
                     << "ARM Loops: Moved element count def: " << *ElemDef);
        } else if (RDA.isSafeToMoveBackwards(&*StartInsertPt, ElemDef)) {
          StartInsertPt->removeFromParent();
          StartInsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef),
                                     &*StartInsertPt);
          LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef);
        } else {
          // If we fail to move an instruction and the element count is provided
          // by a mov, use the mov operand if it will have the same value at the
          // insertion point
          MachineOperand Operand = ElemDef->getOperand(1);
          if (isMovRegOpcode(ElemDef->getOpcode()) &&
              RDA.getUniqueReachingMIDef(ElemDef, Operand.getReg().asMCReg()) ==
                  RDA.getUniqueReachingMIDef(&*StartInsertPt,
                                             Operand.getReg().asMCReg())) {
            TPNumElements = Operand;
            NumElements = TPNumElements.getReg();
          } else {
            LLVM_DEBUG(dbgs()
                       << "ARM Loops: Unable to move element count to loop "
                       << "start instruction.\n");
            return false;
          }
        }
      }
    }

    // Especially in the case of while loops, InsertBB may not be the
    // preheader, so we need to check that the register isn't redefined
    // before entering the loop.
    auto CannotProvideElements = [this](MachineBasicBlock *MBB,
                                        MCRegister NumElements) {
      if (MBB->empty())
        return false;
      // NumElements is redefined in this block.
      if (RDA.hasLocalDefBefore(&MBB->back(), NumElements))
        return true;

      // Don't continue searching up through multiple predecessors.
      if (MBB->pred_size() > 1)
        return true;

      return false;
    };

    // Search backwards for a def, until we get to InsertBB.
    MachineBasicBlock *MBB = Preheader;
    while (MBB && MBB != StartInsertBB) {
      if (CannotProvideElements(MBB, NumElements)) {
        LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n");
        return false;
      }
      MBB = *MBB->pred_begin();
    }
  }

  // Could inserting the [W|D]LSTP cause some unintended affects? In a perfect
  // world the [w|d]lstp instruction would be last instruction in the preheader
  // and so it would only affect instructions within the loop body. But due to
  // scheduling, and/or the logic in this pass (above), the insertion point can
  // be moved earlier. So if the Loop Start isn't the last instruction in the
  // preheader, and if the initial element count is smaller than the vector
  // width, the Loop Start instruction will immediately generate one or more
  // false lane mask which can, incorrectly, affect the proceeding MVE
  // instructions in the preheader.
  if (std::any_of(StartInsertPt, StartInsertBB->end(), shouldInspect)) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Instruction blocks [W|D]LSTP\n");
    return false;
  }

  // Check that the value change of the element count is what we expect and
  // that the predication will be equivalent. For this we need:
  // NumElements = NumElements - VectorWidth. The sub will be a sub immediate
  // and we can also allow register copies within the chain too.
  auto IsValidSub = [](MachineInstr *MI, int ExpectedVecWidth) {
    return -getAddSubImmediate(*MI) == ExpectedVecWidth;
  };

  MachineBasicBlock *MBB = VCTP->getParent();
  // Remove modifications to the element count since they have no purpose in a
  // tail predicated loop. Explicitly refer to the vctp operand no matter which
  // register NumElements has been assigned to, since that is what the
  // modifications will be using
  if (auto *Def = RDA.getUniqueReachingMIDef(
          &MBB->back(), VCTP->getOperand(1).getReg().asMCReg())) {
    SmallPtrSet<MachineInstr*, 2> ElementChain;
    SmallPtrSet<MachineInstr*, 2> Ignore;
    unsigned ExpectedVectorWidth = getTailPredVectorWidth(VCTP->getOpcode());

    Ignore.insert(VCTPs.begin(), VCTPs.end());

    if (TryRemove(Def, RDA, ElementChain, Ignore)) {
      bool FoundSub = false;

      for (auto *MI : ElementChain) {
        if (isMovRegOpcode(MI->getOpcode()))
          continue;

        if (isSubImmOpcode(MI->getOpcode())) {
          if (FoundSub || !IsValidSub(MI, ExpectedVectorWidth)) {
            LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"
                       " count: " << *MI);
            return false;
          }
          FoundSub = true;
        } else {
          LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"
                     " count: " << *MI);
          return false;
        }
      }
      ToRemove.insert(ElementChain.begin(), ElementChain.end());
    }
  }
  return true;
}

static bool isRegInClass(const MachineOperand &MO,
                         const TargetRegisterClass *Class) {
  return MO.isReg() && MO.getReg() && Class->contains(MO.getReg());
}

// MVE 'narrowing' operate on half a lane, reading from half and writing
// to half, which are referred to has the top and bottom half. The other
// half retains its previous value.
static bool retainsPreviousHalfElement(const MachineInstr &MI) {
  const MCInstrDesc &MCID = MI.getDesc();
  uint64_t Flags = MCID.TSFlags;
  return (Flags & ARMII::RetainsPreviousHalfElement) != 0;
}

// Some MVE instructions read from the top/bottom halves of their operand(s)
// and generate a vector result with result elements that are double the
// width of the input.
static bool producesDoubleWidthResult(const MachineInstr &MI) {
  const MCInstrDesc &MCID = MI.getDesc();
  uint64_t Flags = MCID.TSFlags;
  return (Flags & ARMII::DoubleWidthResult) != 0;
}

static bool isHorizontalReduction(const MachineInstr &MI) {
  const MCInstrDesc &MCID = MI.getDesc();
  uint64_t Flags = MCID.TSFlags;
  return (Flags & ARMII::HorizontalReduction) != 0;
}

// Can this instruction generate a non-zero result when given only zeroed
// operands? This allows us to know that, given operands with false bytes
// zeroed by masked loads, that the result will also contain zeros in those
// bytes.
static bool canGenerateNonZeros(const MachineInstr &MI) {

  // Check for instructions which can write into a larger element size,
  // possibly writing into a previous zero'd lane.
  if (producesDoubleWidthResult(MI))
    return true;

  switch (MI.getOpcode()) {
  default:
    break;
  // FIXME: VNEG FP and -0? I think we'll need to handle this once we allow
  // fp16 -> fp32 vector conversions.
  // Instructions that perform a NOT will generate 1s from 0s.
  case ARM::MVE_VMVN:
  case ARM::MVE_VORN:
  // Count leading zeros will do just that!
  case ARM::MVE_VCLZs8:
  case ARM::MVE_VCLZs16:
  case ARM::MVE_VCLZs32:
    return true;
  }
  return false;
}

// Look at its register uses to see if it only can only receive zeros
// into its false lanes which would then produce zeros. Also check that
// the output register is also defined by an FalseLanesZero instruction
// so that if tail-predication happens, the lanes that aren't updated will
// still be zeros.
static bool producesFalseLanesZero(MachineInstr &MI,
                                   const TargetRegisterClass *QPRs,
                                   const ReachingDefAnalysis &RDA,
                                   InstSet &FalseLanesZero) {
  if (canGenerateNonZeros(MI))
    return false;

  bool isPredicated = isVectorPredicated(&MI);
  // Predicated loads will write zeros to the falsely predicated bytes of the
  // destination register.
  if (MI.mayLoad())
    return isPredicated;

  auto IsZeroInit = [](MachineInstr *Def) {
    return !isVectorPredicated(Def) &&
           Def->getOpcode() == ARM::MVE_VMOVimmi32 &&
           Def->getOperand(1).getImm() == 0;
  };

  bool AllowScalars = isHorizontalReduction(MI);
  for (auto &MO : MI.operands()) {
    if (!MO.isReg() || !MO.getReg())
      continue;
    if (!isRegInClass(MO, QPRs) && AllowScalars)
      continue;

    // Check that this instruction will produce zeros in its false lanes:
    // - If it only consumes false lanes zero or constant 0 (vmov #0)
    // - If it's predicated, it only matters that it's def register already has
    //   false lane zeros, so we can ignore the uses.
    SmallPtrSet<MachineInstr *, 2> Defs;
    RDA.getGlobalReachingDefs(&MI, MO.getReg(), Defs);
    for (auto *Def : Defs) {
      if (Def == &MI || FalseLanesZero.count(Def) || IsZeroInit(Def))
        continue;
      if (MO.isUse() && isPredicated)
        continue;
      return false;
    }
  }
  LLVM_DEBUG(dbgs() << "ARM Loops: Always False Zeros: " << MI);
  return true;
}

bool LowOverheadLoop::ValidateLiveOuts() {
  // We want to find out if the tail-predicated version of this loop will
  // produce the same values as the loop in its original form. For this to
  // be true, the newly inserted implicit predication must not change the
  // the (observable) results.
  // We're doing this because many instructions in the loop will not be
  // predicated and so the conversion from VPT predication to tail-predication
  // can result in different values being produced; due to the tail-predication
  // preventing many instructions from updating their falsely predicated
  // lanes. This analysis assumes that all the instructions perform lane-wise
  // operations and don't perform any exchanges.
  // A masked load, whether through VPT or tail predication, will write zeros
  // to any of the falsely predicated bytes. So, from the loads, we know that
  // the false lanes are zeroed and here we're trying to track that those false
  // lanes remain zero, or where they change, the differences are masked away
  // by their user(s).
  // All MVE stores have to be predicated, so we know that any predicate load
  // operands, or stored results are equivalent already. Other explicitly
  // predicated instructions will perform the same operation in the original
  // loop and the tail-predicated form too. Because of this, we can insert
  // loads, stores and other predicated instructions into our Predicated
  // set and build from there.
  const TargetRegisterClass *QPRs = TRI.getRegClass(ARM::MQPRRegClassID);
  SetVector<MachineInstr *> FalseLanesUnknown;
  SmallPtrSet<MachineInstr *, 4> FalseLanesZero;
  SmallPtrSet<MachineInstr *, 4> Predicated;
  MachineBasicBlock *Header = ML.getHeader();

  for (auto &MI : *Header) {
    if (!shouldInspect(MI))
      continue;

    if (isVCTP(&MI) || isVPTOpcode(MI.getOpcode()))
      continue;

    bool isPredicated = isVectorPredicated(&MI);
    bool retainsOrReduces =
      retainsPreviousHalfElement(MI) || isHorizontalReduction(MI);

    if (isPredicated)
      Predicated.insert(&MI);
    if (producesFalseLanesZero(MI, QPRs, RDA, FalseLanesZero))
      FalseLanesZero.insert(&MI);
    else if (MI.getNumDefs() == 0)
      continue;
    else if (!isPredicated && retainsOrReduces)
      return false;
    else if (!isPredicated)
      FalseLanesUnknown.insert(&MI);
  }

  auto HasPredicatedUsers = [this](MachineInstr *MI, const MachineOperand &MO,
                              SmallPtrSetImpl<MachineInstr *> &Predicated) {
    SmallPtrSet<MachineInstr *, 2> Uses;
    RDA.getGlobalUses(MI, MO.getReg().asMCReg(), Uses);
    for (auto *Use : Uses) {
      if (Use != MI && !Predicated.count(Use))
        return false;
    }
    return true;
  };

  // Visit the unknowns in reverse so that we can start at the values being
  // stored and then we can work towards the leaves, hopefully adding more
  // instructions to Predicated. Successfully terminating the loop means that
  // all the unknown values have to found to be masked by predicated user(s).
  // For any unpredicated values, we store them in NonPredicated so that we
  // can later check whether these form a reduction.
  SmallPtrSet<MachineInstr*, 2> NonPredicated;
  for (auto *MI : reverse(FalseLanesUnknown)) {
    for (auto &MO : MI->operands()) {
      if (!isRegInClass(MO, QPRs) || !MO.isDef())
        continue;
      if (!HasPredicatedUsers(MI, MO, Predicated)) {
        LLVM_DEBUG(dbgs() << "ARM Loops: Found an unknown def of : "
                          << TRI.getRegAsmName(MO.getReg()) << " at " << *MI);
        NonPredicated.insert(MI);
        break;
      }
    }
    // Any unknown false lanes have been masked away by the user(s).
    if (!NonPredicated.contains(MI))
      Predicated.insert(MI);
  }

  SmallPtrSet<MachineInstr *, 2> LiveOutMIs;
  SmallVector<MachineBasicBlock *, 2> ExitBlocks;
  ML.getExitBlocks(ExitBlocks);
  assert(ML.getNumBlocks() == 1 && "Expected single block loop!");
  assert(ExitBlocks.size() == 1 && "Expected a single exit block");
  MachineBasicBlock *ExitBB = ExitBlocks.front();
  for (const MachineBasicBlock::RegisterMaskPair &RegMask : ExitBB->liveins()) {
    // TODO: Instead of blocking predication, we could move the vctp to the exit
    // block and calculate it's operand there in or the preheader.
    if (RegMask.PhysReg == ARM::VPR)
      return false;
    // Check Q-regs that are live in the exit blocks. We don't collect scalars
    // because they won't be affected by lane predication.
    if (QPRs->contains(RegMask.PhysReg))
      if (auto *MI = RDA.getLocalLiveOutMIDef(Header, RegMask.PhysReg))
        LiveOutMIs.insert(MI);
  }

  // We've already validated that any VPT predication within the loop will be
  // equivalent when we perform the predication transformation; so we know that
  // any VPT predicated instruction is predicated upon VCTP. Any live-out
  // instruction needs to be predicated, so check this here. The instructions
  // in NonPredicated have been found to be a reduction that we can ensure its
  // legality.
  for (auto *MI : LiveOutMIs) {
    if (NonPredicated.count(MI) && FalseLanesUnknown.contains(MI)) {
      LLVM_DEBUG(dbgs() << "ARM Loops: Unable to handle live out: " << *MI);
      return false;
    }
  }

  return true;
}

void LowOverheadLoop::Validate(ARMBasicBlockUtils *BBUtils) {
  if (Revert)
    return;

  // Check branch target ranges: WLS[TP] can only branch forwards and LE[TP]
  // can only jump back.
  auto ValidateRanges = [](MachineInstr *Start, MachineInstr *End,
                           ARMBasicBlockUtils *BBUtils, MachineLoop &ML) {
    MachineBasicBlock *TgtBB = End->getOpcode() == ARM::t2LoopEnd
                                   ? End->getOperand(1).getMBB()
                                   : End->getOperand(2).getMBB();
    // TODO Maybe there's cases where the target doesn't have to be the header,
    // but for now be safe and revert.
    if (TgtBB != ML.getHeader()) {
      LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targeting header.\n");
      return false;
    }

    // The WLS and LE instructions have 12-bits for the label offset. WLS
    // requires a positive offset, while LE uses negative.
    if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML.getHeader()) ||
        !BBUtils->isBBInRange(End, ML.getHeader(), 4094)) {
      LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n");
      return false;
    }

    if (Start->getOpcode() == ARM::t2WhileLoopStart &&
        (BBUtils->getOffsetOf(Start) >
         BBUtils->getOffsetOf(Start->getOperand(1).getMBB()) ||
         !BBUtils->isBBInRange(Start, Start->getOperand(1).getMBB(), 4094))) {
      LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
      return false;
    }
    return true;
  };

  // Find a suitable position to insert the loop start instruction. It needs to
  // be able to safely define LR.
  auto FindStartInsertionPoint = [](MachineInstr *Start, MachineInstr *Dec,
                                    MachineBasicBlock::iterator &InsertPt,
                                    MachineBasicBlock *&InsertBB,
                                    ReachingDefAnalysis &RDA,
                                    InstSet &ToRemove) {
    // For a t2DoLoopStart it is always valid to use the start insertion point.
    // For WLS we can define LR if LR already contains the same value.
    if (isDo(Start) || Start->getOperand(0).getReg() == ARM::LR) {
      InsertPt = MachineBasicBlock::iterator(Start);
      InsertBB = Start->getParent();
      return true;
    }

    // We've found no suitable LR def and Start doesn't use LR directly. Can we
    // just define LR anyway?
    if (!RDA.isSafeToDefRegAt(Start, MCRegister::from(ARM::LR)))
      return false;

    InsertPt = MachineBasicBlock::iterator(Start);
    InsertBB = Start->getParent();
    return true;
  };

  if (!FindStartInsertionPoint(Start, Dec, StartInsertPt, StartInsertBB, RDA,
                               ToRemove)) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n");
    Revert = true;
    return;
  }
  LLVM_DEBUG(if (StartInsertPt == StartInsertBB->end())
               dbgs() << "ARM Loops: Will insert LoopStart at end of block\n";
             else
               dbgs() << "ARM Loops: Will insert LoopStart at "
                      << *StartInsertPt
            );

  Revert = !ValidateRanges(Start, End, BBUtils, ML);
  CannotTailPredicate = !ValidateTailPredicate();
}

bool LowOverheadLoop::AddVCTP(MachineInstr *MI) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Adding VCTP: " << *MI);
  if (VCTPs.empty()) {
    VCTPs.push_back(MI);
    return true;
  }

  // If we find another VCTP, check whether it uses the same value as the main VCTP.
  // If it does, store it in the VCTPs set, else refuse it.
  MachineInstr *Prev = VCTPs.back();
  if (!Prev->getOperand(1).isIdenticalTo(MI->getOperand(1)) ||
      !RDA.hasSameReachingDef(Prev, MI, MI->getOperand(1).getReg().asMCReg())) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Found VCTP with a different reaching "
                         "definition from the main VCTP");
    return false;
  }
  VCTPs.push_back(MI);
  return true;
}

bool LowOverheadLoop::ValidateMVEInst(MachineInstr* MI) {
  if (CannotTailPredicate)
    return false;

  if (!shouldInspect(*MI))
    return true;

  if (MI->getOpcode() == ARM::MVE_VPSEL ||
      MI->getOpcode() == ARM::MVE_VPNOT) {
    // TODO: Allow VPSEL and VPNOT, we currently cannot because:
    // 1) It will use the VPR as a predicate operand, but doesn't have to be
    //    instead a VPT block, which means we can assert while building up
    //    the VPT block because we don't find another VPT or VPST to being a new
    //    one.
    // 2) VPSEL still requires a VPR operand even after tail predicating,
    //    which means we can't remove it unless there is another
    //    instruction, such as vcmp, that can provide the VPR def.
    return false;
  }

  // Record all VCTPs and check that they're equivalent to one another.
  if (isVCTP(MI) && !AddVCTP(MI))
    return false;

  // Inspect uses first so that any instructions that alter the VPR don't
  // alter the predicate upon themselves.
  const MCInstrDesc &MCID = MI->getDesc();
  bool IsUse = false;
  unsigned LastOpIdx = MI->getNumOperands() - 1;
  for (auto &Op : enumerate(reverse(MCID.operands()))) {
    const MachineOperand &MO = MI->getOperand(LastOpIdx - Op.index());
    if (!MO.isReg() || !MO.isUse() || MO.getReg() != ARM::VPR)
      continue;

    if (ARM::isVpred(Op.value().OperandType)) {
      VPTState::addInst(MI);
      IsUse = true;
    } else if (MI->getOpcode() != ARM::MVE_VPST) {
      LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI);
      return false;
    }
  }

  // If we find an instruction that has been marked as not valid for tail
  // predication, only allow the instruction if it's contained within a valid
  // VPT block.
  bool RequiresExplicitPredication =
    (MCID.TSFlags & ARMII::ValidForTailPredication) == 0;
  if (isDomainMVE(MI) && RequiresExplicitPredication) {
    LLVM_DEBUG(if (!IsUse)
               dbgs() << "ARM Loops: Can't tail predicate: " << *MI);
    return IsUse;
  }

  // If the instruction is already explicitly predicated, then the conversion
  // will be fine, but ensure that all store operations are predicated.
  if (MI->mayStore())
    return IsUse;

  // If this instruction defines the VPR, update the predicate for the
  // proceeding instructions.
  if (isVectorPredicate(MI)) {
    // Clear the existing predicate when we're not in VPT Active state,
    // otherwise we add to it.
    if (!isVectorPredicated(MI))
      VPTState::resetPredicate(MI);
    else
      VPTState::addPredicate(MI);
  }

  // Finally once the predicate has been modified, we can start a new VPT
  // block if necessary.
  if (isVPTOpcode(MI->getOpcode()))
    VPTState::CreateVPTBlock(MI);

  return true;
}

bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
  const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget());
  if (!ST.hasLOB())
    return false;

  MF = &mf;
  LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n");

  MLI = &getAnalysis<MachineLoopInfo>();
  RDA = &getAnalysis<ReachingDefAnalysis>();
  MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
  MRI = &MF->getRegInfo();
  TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo());
  TRI = ST.getRegisterInfo();
  BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF));
  BBUtils->computeAllBlockSizes();
  BBUtils->adjustBBOffsetsAfter(&MF->front());

  bool Changed = false;
  for (auto ML : *MLI) {
    if (ML->isOutermost())
      Changed |= ProcessLoop(ML);
  }
  Changed |= RevertNonLoops();
  return Changed;
}

bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {

  bool Changed = false;

  // Process inner loops first.
  for (auto I = ML->begin(), E = ML->end(); I != E; ++I)
    Changed |= ProcessLoop(*I);

  LLVM_DEBUG(dbgs() << "ARM Loops: Processing loop containing:\n";
             if (auto *Preheader = ML->getLoopPreheader())
               dbgs() << " - " << Preheader->getName() << "\n";
             else if (auto *Preheader = MLI->findLoopPreheader(ML))
               dbgs() << " - " << Preheader->getName() << "\n";
             else if (auto *Preheader = MLI->findLoopPreheader(ML, true))
               dbgs() << " - " << Preheader->getName() << "\n";
             for (auto *MBB : ML->getBlocks())
               dbgs() << " - " << MBB->getName() << "\n";
            );

  // Search the given block for a loop start instruction. If one isn't found,
  // and there's only one predecessor block, search that one too.
  std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart =
    [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* {
    for (auto &MI : *MBB) {
      if (isLoopStart(MI))
        return &MI;
    }
    if (MBB->pred_size() == 1)
      return SearchForStart(*MBB->pred_begin());
    return nullptr;
  };

  LowOverheadLoop LoLoop(*ML, *MLI, *RDA, *TRI, *TII);
  // Search the preheader for the start intrinsic.
  // FIXME: I don't see why we shouldn't be supporting multiple predecessors
  // with potentially multiple set.loop.iterations, so we need to enable this.
  if (LoLoop.Preheader)
    LoLoop.Start = SearchForStart(LoLoop.Preheader);
  else
    return false;

  // Find the low-overhead loop components and decide whether or not to fall
  // back to a normal loop. Also look for a vctp instructions and decide
  // whether we can convert that predicate using tail predication.
  for (auto *MBB : reverse(ML->getBlocks())) {
    for (auto &MI : *MBB) {
      if (MI.isDebugValue())
        continue;
      else if (MI.getOpcode() == ARM::t2LoopDec)
        LoLoop.Dec = &MI;
      else if (MI.getOpcode() == ARM::t2LoopEnd)
        LoLoop.End = &MI;
      else if (MI.getOpcode() == ARM::t2LoopEndDec)
        LoLoop.End = LoLoop.Dec = &MI;
      else if (isLoopStart(MI))
        LoLoop.Start = &MI;
      else if (MI.getDesc().isCall()) {
        // TODO: Though the call will require LE to execute again, does this
        // mean we should revert? Always executing LE hopefully should be
        // faster than performing a sub,cmp,br or even subs,br.
        LoLoop.Revert = true;
        LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n");
      } else {
        // Record VPR defs and build up their corresponding vpt blocks.
        // Check we know how to tail predicate any mve instructions.
        LoLoop.AnalyseMVEInst(&MI);
      }
    }
  }

  LLVM_DEBUG(LoLoop.dump());
  if (!LoLoop.FoundAllComponents()) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n");
    return false;
  }

  // Check that the only instruction using LoopDec is LoopEnd. This can only
  // happen when the Dec and End are separate, not a single t2LoopEndDec.
  // TODO: Check for copy chains that really have no effect.
  if (LoLoop.Dec != LoLoop.End) {
    SmallPtrSet<MachineInstr *, 2> Uses;
    RDA->getReachingLocalUses(LoLoop.Dec, MCRegister::from(ARM::LR), Uses);
    if (Uses.size() > 1 || !Uses.count(LoLoop.End)) {
      LLVM_DEBUG(dbgs() << "ARM Loops: Unable to remove LoopDec.\n");
      LoLoop.Revert = true;
    }
  }
  LoLoop.Validate(BBUtils.get());
  Expand(LoLoop);
  return true;
}

// WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a
// beq that branches to the exit branch.
// TODO: We could also try to generate a cbz if the value in LR is also in
// another low register.
void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
  LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp: " << *MI);
  MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
  unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
    ARM::tBcc : ARM::t2Bcc;

  RevertWhileLoopStart(MI, TII, BrOpc);
}

void ARMLowOverheadLoops::RevertDo(MachineInstr *MI) const {
  LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to mov: " << *MI);
  RevertDoLoopStart(MI, TII);
}

bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const {
  LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
  MachineBasicBlock *MBB = MI->getParent();
  SmallPtrSet<MachineInstr*, 1> Ignore;
  for (auto I = MachineBasicBlock::iterator(MI), E = MBB->end(); I != E; ++I) {
    if (I->getOpcode() == ARM::t2LoopEnd) {
      Ignore.insert(&*I);
      break;
    }
  }

  // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
  bool SetFlags =
      RDA->isSafeToDefRegAt(MI, MCRegister::from(ARM::CPSR), Ignore);

  llvm::RevertLoopDec(MI, TII, SetFlags);
  return SetFlags;
}

// Generate a subs, or sub and cmp, and a branch instead of an LE.
void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const {
  LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp, br: " << *MI);

  MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
  unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
    ARM::tBcc : ARM::t2Bcc;

  llvm::RevertLoopEnd(MI, TII, BrOpc, SkipCmp);
}

// Generate a subs, or sub and cmp, and a branch instead of an LE.
void ARMLowOverheadLoops::RevertLoopEndDec(MachineInstr *MI) const {
  LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to subs, br: " << *MI);
  assert(MI->getOpcode() == ARM::t2LoopEndDec && "Expected a t2LoopEndDec!");
  MachineBasicBlock *MBB = MI->getParent();

  MachineInstrBuilder MIB =
      BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::t2SUBri));
  MIB.addDef(ARM::LR);
  MIB.add(MI->getOperand(1));
  MIB.addImm(1);
  MIB.addImm(ARMCC::AL);
  MIB.addReg(ARM::NoRegister);
  MIB.addReg(ARM::CPSR);
  MIB->getOperand(5).setIsDef(true);

  MachineBasicBlock *DestBB = MI->getOperand(2).getMBB();
  unsigned BrOpc =
      BBUtils->isBBInRange(MI, DestBB, 254) ? ARM::tBcc : ARM::t2Bcc;

  // Create bne
  MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
  MIB.add(MI->getOperand(2)); // branch target
  MIB.addImm(ARMCC::NE);      // condition code
  MIB.addReg(ARM::CPSR);

  MI->eraseFromParent();
}

// Perform dead code elimation on the loop iteration count setup expression.
// If we are tail-predicating, the number of elements to be processed is the
// operand of the VCTP instruction in the vector body, see getCount(), which is
// register $r3 in this example:
//
//   $lr = big-itercount-expression
//   ..
//   $lr = t2DoLoopStart renamable $lr
//   vector.body:
//     ..
//     $vpr = MVE_VCTP32 renamable $r3
//     renamable $lr = t2LoopDec killed renamable $lr, 1
//     t2LoopEnd renamable $lr, %vector.body
//     tB %end
//
// What we would like achieve here is to replace the do-loop start pseudo
// instruction t2DoLoopStart with:
//
//    $lr = MVE_DLSTP_32 killed renamable $r3
//
// Thus, $r3 which defines the number of elements, is written to $lr,
// and then we want to delete the whole chain that used to define $lr,
// see the comment below how this chain could look like.
//
void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) {
  if (!LoLoop.IsTailPredicationLegal())
    return;

  LLVM_DEBUG(dbgs() << "ARM Loops: Trying DCE on loop iteration count.\n");

  MachineInstr *Def =
      RDA->getMIOperand(LoLoop.Start, isDo(LoLoop.Start) ? 1 : 0);
  if (!Def) {
    LLVM_DEBUG(dbgs() << "ARM Loops: Couldn't find iteration count.\n");
    return;
  }

  // Collect and remove the users of iteration count.
  SmallPtrSet<MachineInstr*, 4> Killed  = { LoLoop.Start, LoLoop.Dec,
                                            LoLoop.End };
  if (!TryRemove(Def, *RDA, LoLoop.ToRemove, Killed))
    LLVM_DEBUG(dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\n");
}

MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
  LLVM_DEBUG(dbgs() << "ARM Loops: Expanding LoopStart.\n");
  // When using tail-predication, try to delete the dead code that was used to
  // calculate the number of loop iterations.
  IterationCountDCE(LoLoop);

  MachineBasicBlock::iterator InsertPt = LoLoop.StartInsertPt;
  MachineInstr *Start = LoLoop.Start;
  MachineBasicBlock *MBB = LoLoop.StartInsertBB;
  unsigned Opc = LoLoop.getStartOpcode();
  MachineOperand &Count = LoLoop.getLoopStartOperand();

  MachineInstrBuilder MIB =
    BuildMI(*MBB, InsertPt, Start->getDebugLoc(), TII->get(Opc));

  MIB.addDef(ARM::LR);
  MIB.add(Count);
  if (!isDo(Start))
    MIB.add(Start->getOperand(1));

  LoLoop.ToRemove.insert(Start);
  LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);
  return &*MIB;
}

void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) {
  auto RemovePredicate = [](MachineInstr *MI) {
    if (MI->isDebugInstr())
      return;
    LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI);
    int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);
    assert(PIdx >= 1 && "Trying to unpredicate a non-predicated instruction");
    assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then &&
           "Expected Then predicate!");
    MI->getOperand(PIdx).setImm(ARMVCC::None);
    MI->getOperand(PIdx + 1).setReg(0);
  };

  for (auto &Block : LoLoop.getVPTBlocks()) {
    SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();

    auto ReplaceVCMPWithVPT = [&](MachineInstr *&TheVCMP, MachineInstr *At) {
      assert(TheVCMP && "Replacing a removed or non-existent VCMP");
      // Replace the VCMP with a VPT
      MachineInstrBuilder MIB =
          BuildMI(*At->getParent(), At, At->getDebugLoc(),
                  TII->get(VCMPOpcodeToVPT(TheVCMP->getOpcode())));
      MIB.addImm(ARMVCC::Then);
      // Register one
      MIB.add(TheVCMP->getOperand(1));
      // Register two
      MIB.add(TheVCMP->getOperand(2));
      // The comparison code, e.g. ge, eq, lt
      MIB.add(TheVCMP->getOperand(3));
      LLVM_DEBUG(dbgs() << "ARM Loops: Combining with VCMP to VPT: " << *MIB);
      LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());
      LoLoop.ToRemove.insert(TheVCMP);
      TheVCMP = nullptr;
    };

    if (VPTState::isEntryPredicatedOnVCTP(Block, /*exclusive*/ true)) {
      MachineInstr *VPST = Insts.front();
      if (VPTState::hasUniformPredicate(Block)) {
        // A vpt block starting with VPST, is only predicated upon vctp and has no
        // internal vpr defs:
        // - Remove vpst.
        // - Unpredicate the remaining instructions.
        LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
        for (unsigned i = 1; i < Insts.size(); ++i)
          RemovePredicate(Insts[i]);
      } else {
        // The VPT block has a non-uniform predicate but it uses a vpst and its
        // entry is guarded only by a vctp, which means we:
        // - Need to remove the original vpst.
        // - Then need to unpredicate any following instructions, until
        //   we come across the divergent vpr def.
        // - Insert a new vpst to predicate the instruction(s) that following
        //   the divergent vpr def.
        MachineInstr *Divergent = VPTState::getDivergent(Block);
        MachineBasicBlock *MBB = Divergent->getParent();
        auto DivergentNext = ++MachineBasicBlock::iterator(Divergent);
        while (DivergentNext != MBB->end() && DivergentNext->isDebugInstr())
          ++DivergentNext;

        bool DivergentNextIsPredicated =
            DivergentNext != MBB->end() &&
            getVPTInstrPredicate(*DivergentNext) != ARMVCC::None;

        for (auto I = ++MachineBasicBlock::iterator(VPST), E = DivergentNext;
             I != E; ++I)
          RemovePredicate(&*I);

        // Check if the instruction defining vpr is a vcmp so it can be combined
        // with the VPST This should be the divergent instruction
        MachineInstr *VCMP =
            VCMPOpcodeToVPT(Divergent->getOpcode()) != 0 ? Divergent : nullptr;

        if (DivergentNextIsPredicated) {
          // Insert a VPST at the divergent only if the next instruction
          // would actually use it. A VCMP following a VPST can be
          // merged into a VPT so do that instead if the VCMP exists.
          if (!VCMP) {
            // Create a VPST (with a null mask for now, we'll recompute it
            // later)
            MachineInstrBuilder MIB =
                BuildMI(*Divergent->getParent(), Divergent,
                        Divergent->getDebugLoc(), TII->get(ARM::MVE_VPST));
            MIB.addImm(0);
            LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB);
            LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());
          } else {
            // No RDA checks are necessary here since the VPST would have been
            // directly after the VCMP
            ReplaceVCMPWithVPT(VCMP, VCMP);
          }
        }
      }
      LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
      LoLoop.ToRemove.insert(VPST);
    } else if (Block.containsVCTP()) {
      // The vctp will be removed, so either the entire block will be dead or
      // the block mask of the vp(s)t will need to be recomputed.
      MachineInstr *VPST = Insts.front();
      if (Block.size() == 2) {
        assert(VPST->getOpcode() == ARM::MVE_VPST &&
               "Found a VPST in an otherwise empty vpt block");
        LoLoop.ToRemove.insert(VPST);
      } else
        LoLoop.BlockMasksToRecompute.insert(VPST);
    } else if (Insts.front()->getOpcode() == ARM::MVE_VPST) {
      // If this block starts with a VPST then attempt to merge it with the
      // preceeding un-merged VCMP into a VPT. This VCMP comes from a VPT
      // block that no longer exists
      MachineInstr *VPST = Insts.front();
      auto Next = ++MachineBasicBlock::iterator(VPST);
      assert(getVPTInstrPredicate(*Next) != ARMVCC::None &&
             "The instruction after a VPST must be predicated");
      (void)Next;
      MachineInstr *VprDef = RDA->getUniqueReachingMIDef(VPST, ARM::VPR);
      if (VprDef && VCMPOpcodeToVPT(VprDef->getOpcode()) &&
          !LoLoop.ToRemove.contains(VprDef)) {
        MachineInstr *VCMP = VprDef;
        // The VCMP and VPST can only be merged if the VCMP's operands will have
        // the same values at the VPST.
        // If any of the instructions between the VCMP and VPST are predicated
        // then a different code path is expected to have merged the VCMP and
        // VPST already.
        if (!std::any_of(++MachineBasicBlock::iterator(VCMP),
                         MachineBasicBlock::iterator(VPST), hasVPRUse) &&
            RDA->hasSameReachingDef(VCMP, VPST, VCMP->getOperand(1).getReg()) &&
            RDA->hasSameReachingDef(VCMP, VPST, VCMP->getOperand(2).getReg())) {
          ReplaceVCMPWithVPT(VCMP, VPST);
          LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
          LoLoop.ToRemove.insert(VPST);
        }
      }
    }
  }

  LoLoop.ToRemove.insert(LoLoop.VCTPs.begin(), LoLoop.VCTPs.end());
}

void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) {

  // Combine the LoopDec and LoopEnd instructions into LE(TP).
  auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) {
    MachineInstr *End = LoLoop.End;
    MachineBasicBlock *MBB = End->getParent();
    unsigned Opc = LoLoop.IsTailPredicationLegal() ?
      ARM::MVE_LETP : ARM::t2LEUpdate;
    MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(),
                                      TII->get(Opc));
    MIB.addDef(ARM::LR);
    unsigned Off = LoLoop.Dec == LoLoop.End ? 1 : 0;
    MIB.add(End->getOperand(Off + 0));
    MIB.add(End->getOperand(Off + 1));
    LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB);
    LoLoop.ToRemove.insert(LoLoop.Dec);
    LoLoop.ToRemove.insert(End);
    return &*MIB;
  };

  // TODO: We should be able to automatically remove these branches before we
  // get here - probably by teaching analyzeBranch about the pseudo
  // instructions.
  // If there is an unconditional branch, after I, that just branches to the
  // next block, remove it.
  auto RemoveDeadBranch = [](MachineInstr *I) {
    MachineBasicBlock *BB = I->getParent();
    MachineInstr *Terminator = &BB->instr_back();
    if (Terminator->isUnconditionalBranch() && I != Terminator) {
      MachineBasicBlock *Succ = Terminator->getOperand(0).getMBB();
      if (BB->isLayoutSuccessor(Succ)) {
        LLVM_DEBUG(dbgs() << "ARM Loops: Removing branch: " << *Terminator);
        Terminator->eraseFromParent();
      }
    }
  };

  if (LoLoop.Revert) {
    if (LoLoop.Start->getOpcode() == ARM::t2WhileLoopStart)
      RevertWhile(LoLoop.Start);
    else
      RevertDo(LoLoop.Start);
    if (LoLoop.Dec == LoLoop.End)
      RevertLoopEndDec(LoLoop.End);
    else
      RevertLoopEnd(LoLoop.End, RevertLoopDec(LoLoop.Dec));
  } else {
    LoLoop.Start = ExpandLoopStart(LoLoop);
    RemoveDeadBranch(LoLoop.Start);
    LoLoop.End = ExpandLoopEnd(LoLoop);
    RemoveDeadBranch(LoLoop.End);
    if (LoLoop.IsTailPredicationLegal())
      ConvertVPTBlocks(LoLoop);
    for (auto *I : LoLoop.ToRemove) {
      LLVM_DEBUG(dbgs() << "ARM Loops: Erasing " << *I);
      I->eraseFromParent();
    }
    for (auto *I : LoLoop.BlockMasksToRecompute) {
      LLVM_DEBUG(dbgs() << "ARM Loops: Recomputing VPT/VPST Block Mask: " << *I);
      recomputeVPTBlockMask(*I);
      LLVM_DEBUG(dbgs() << "           ... done: " << *I);
    }
  }

  PostOrderLoopTraversal DFS(LoLoop.ML, *MLI);
  DFS.ProcessLoop();
  const SmallVectorImpl<MachineBasicBlock*> &PostOrder = DFS.getOrder();
  for (auto *MBB : PostOrder) {
    recomputeLiveIns(*MBB);
    // FIXME: For some reason, the live-in print order is non-deterministic for
    // our tests and I can't out why... So just sort them.
    MBB->sortUniqueLiveIns();
  }

  for (auto *MBB : reverse(PostOrder))
    recomputeLivenessFlags(*MBB);

  // We've moved, removed and inserted new instructions, so update RDA.
  RDA->reset();
}

bool ARMLowOverheadLoops::RevertNonLoops() {
  LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n");
  bool Changed = false;

  for (auto &MBB : *MF) {
    SmallVector<MachineInstr*, 4> Starts;
    SmallVector<MachineInstr*, 4> Decs;
    SmallVector<MachineInstr*, 4> Ends;
    SmallVector<MachineInstr *, 4> EndDecs;

    for (auto &I : MBB) {
      if (isLoopStart(I))
        Starts.push_back(&I);
      else if (I.getOpcode() == ARM::t2LoopDec)
        Decs.push_back(&I);
      else if (I.getOpcode() == ARM::t2LoopEnd)
        Ends.push_back(&I);
      else if (I.getOpcode() == ARM::t2LoopEndDec)
        EndDecs.push_back(&I);
    }

    if (Starts.empty() && Decs.empty() && Ends.empty() && EndDecs.empty())
      continue;

    Changed = true;

    for (auto *Start : Starts) {
      if (Start->getOpcode() == ARM::t2WhileLoopStart)
        RevertWhile(Start);
      else
        RevertDo(Start);
    }
    for (auto *Dec : Decs)
      RevertLoopDec(Dec);

    for (auto *End : Ends)
      RevertLoopEnd(End);
    for (auto *End : EndDecs)
      RevertLoopEndDec(End);
  }
  return Changed;
}

FunctionPass *llvm::createARMLowOverheadLoopsPass() {
  return new ARMLowOverheadLoops();
}