LLVM: include/llvm/Analysis/ScalarEvolution.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
21#define LLVM_ANALYSIS_SCALAREVOLUTION_H
22
38#include
39#include
40#include
41#include
42#include
43
44namespace llvm {
45
46class OverflowingBinaryOperator;
47class AssumptionCache;
50class ConstantInt;
51class DataLayout;
52class DominatorTree;
53class GEPOperator;
54class LLVMContext;
55class Loop;
56class LoopInfo;
57class raw_ostream;
58class ScalarEvolution;
59class SCEVAddRecExpr;
60class SCEVUnknown;
61class StructType;
62class TargetLibraryInfo;
65
67
68
69
70
73
74
75
77
78
80
81protected:
82
84
85
86
88
89public:
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
133
139
141
142
144
145
147
148
150
151
152 bool isOne() const;
153
154
156
157
159
160
161
162
163
164
165
166
167
168
171 }
172
173
174
176
177
178 void dump() const;
179};
180
181
182
185
189 }
190
192 return X.FastID.ComputeHash();
193 }
194};
195
198 return OS;
199}
200
201
202
203
204
207
208
210};
211
212
213
216
217
218
220
221public:
223
224protected:
229
230public:
232
234
235
236
238
239
240
242
243
245
246
247
249};
250
253 return OS;
254}
255
256
257
258template <>
262 }
263
267 }
268
271 return X.FastID.ComputeHash();
272 }
273};
274
275
276
278
280 const SCEV *LHS;
281 const SCEV *RHS;
282
283public:
287
288
292
294
295
297
298
300
301
304 }
305};
306
307
308
309
310
311
312
313
314
315
316
318public:
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
343 IncrementNUSW = (1 << 0),
344 IncrementNSSW = (1 << 1),
345
348
349
355 "Invalid flags value!");
357 }
358
363
365 }
366
372 "Invalid flags value!");
373
375 }
376
377
378
381
382private:
385
386public:
390
391
393
394
399
400
402 return P->getKind() == P_Wrap;
403 }
404};
405
406
407
408
409
410
411
413private:
416
417
419
420
422
423public:
426
428
429
433
434
435
437
438
440 return P->getKind() == P_Union;
441 }
442};
443
444
445
446
449
450public:
451
455 LoopComputable
457
458
464
465
466
468 int Mask) {
470 }
474 }
478 }
481 return TestFlags == maskFlags(Flags, TestFlags);
482 };
483
488
490
491
492
493
494
496
497
498
500
501
502
503
505
506
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
524
525
526
528
529
530
531
535
536
537
538
539
540
541 std::optionalSCEV::NoWrapFlags
543
544
546
547
549
550
551
553
554
555
557
558
560
571 unsigned Depth = 0);
574 unsigned Depth = 0);
579 unsigned Depth = 0);
582 unsigned Depth = 0) {
585 }
588 unsigned Depth = 0) {
591 }
594 unsigned Depth = 0);
597 unsigned Depth = 0) {
600 }
603 unsigned Depth = 0) {
606 }
618 }
619
620
621
622
623
624 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
626
627
628
629
630
631
646 bool Sequential = false);
648 bool Sequential = false);
651
652
654
655
657
658
662 }
663
664
666 return getConstant(Ty, -1, true);
667 }
668
669
671
672
674
675
677
678
680
681
684
685
687
688
689
690
691
692
693
694
697 unsigned Depth = 0);
698
699
700
701
702
703
704
705
706
708
709
710
712 unsigned Depth = 0);
713
714
715
717 unsigned Depth = 0);
718
719
720
721
723
724
725
726
728
729
730
731
733
734
735
737
738
739
741
742
743
745 bool Sequential = false);
746
747
748
750 bool Sequential = false);
751
752
753
754
755
757
758
760
761
762
763
764
765
766
767
768
769
770
772
773
775
776
777
778
781
782
783
786
787
788
791
792
793
795
796
797
798
799
800
801
802
804 const Loop *L);
805
806
807
808
809
811
812
813
814
815
816
817
818
819
820
823
824
825
826
827
829 const Loop *L,
831
832
833
834
835
836
837
839 const SCEV *ExitCount);
840
841
842
843
845
846
847
848
849
850
851
854
855
856
857
859
860
862
864
866 };
867
868
869
870
871
872
873
876
877
878
883
884
885
886
887
888
889
890
891
892
893
895
896
897
898
899
902
903
904
905
906
909 }
910
911
912
913
914
917
918
919
920
921
924 }
925
926
927
928
929
932
933
934
936
937
938
940
941
942
943
944
945
947
948
949
950
951
953
954
955
956
957
959
960
961
962
964
965
966
968
969
970
971
972
973
975
976
977
978
979
980
982
983
984
985
986
988
989
991
992
994
995
996
998 return getRangeRef(S, HINT_RANGE_UNSIGNED);
999 }
1000
1001
1003 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
1004 }
1005
1006
1008 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
1009 }
1010
1011
1012
1014 return getRangeRef(S, HINT_RANGE_SIGNED);
1015 }
1016
1017
1019 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
1020 }
1021
1022
1024 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
1025 }
1026
1027
1029
1030
1032
1033
1035
1036
1038
1039
1041
1042
1043
1045 bool OrNegative = false);
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1064 const SCEV *S);
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1085
1086
1087
1089
1090
1091
1092
1095
1096
1097
1100
1101
1102
1103
1107
1108
1109
1112
1113
1114
1115
1116
1120
1122
1123
1125
1126
1127
1128
1130
1131
1132
1133
1135
1139
1143
1144
1145
1147 return !isa(ExactNotTaken) ||
1149 }
1150
1151
1153 return !isa(ExactNotTaken);
1154 }
1155 };
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1168 bool ExitIfTrue, bool ControlsOnlyExit,
1169 bool AllowPredicates = false);
1170
1171
1172
1173
1174
1175
1180
1181
1182
1183
1184
1185
1186 std::optional
1189
1194
1198 };
1199
1200
1201
1202 std::optional
1206
1207
1208
1209
1210
1211
1212 std::optional
1217 const SCEV *MaxIter);
1218
1219 std::optional
1223
1224
1225
1226
1227
1230
1231
1232
1234
1235
1236
1238
1239
1240
1241
1243
1244
1245
1246
1247
1249
1250
1251
1253
1254
1255
1257
1258
1259
1261
1262
1264
1265
1267
1269 void verify() const;
1272
1273
1274
1276
1280
1284
1285
1288
1289
1291 const SCEV *S, const Loop *L,
1293
1294
1295
1296
1297
1298
1299
1300
1303
1304
1305
1306
1308
1311 bool PreserveNUW = false;
1312 bool PreserveNSW = false;
1314
1316
1317
1318
1319
1320 static void
1324 unsigned Depth = 0);
1325
1326
1327
1328
1329
1330 static void collectFromPHI(
1334 unsigned Depth);
1335
1336 public:
1337
1338
1340
1341
1343 };
1344
1345
1348
1349
1350
1351
1352
1354 return getLoopProperties(L).HasNoAbnormalExits;
1355 }
1356
1357
1358
1360
1361
1362
1363
1365 const SCEV *S);
1366
1367
1368
1369
1373
1375 const SCEV *Op = nullptr;
1376 const Type *Ty = nullptr;
1377 unsigned short C;
1378
1379 public:
1383 }
1384
1386
1390 reinterpret_cast<uintptr_t>(Ty)));
1391 }
1392
1394 return std::tie(Op, Ty, C) == std::tie(RHS.Op, RHS.Ty, RHS.C);
1395 }
1396 };
1397
1398private:
1399
1400
1401 class SCEVCallbackVH final : public CallbackVH {
1403
1404 void deleted() override;
1405 void allUsesReplacedWith(Value *New) override;
1406
1407 public:
1409 };
1410
1414
1415
1417
1418
1420
1421
1422
1423
1424 bool HasGuards;
1425
1426
1428
1429
1431
1432
1434
1435
1437
1438
1439 std::unique_ptr CouldNotCompute;
1440
1441
1443
1444
1446
1447
1450
1451
1452
1454
1455
1458
1459
1461
1462
1463
1466
1467
1469
1470
1472
1473
1475
1476
1478
1479
1480
1481 bool WalkingBEDominatingConds = false;
1482
1483
1484
1485 bool ProvingSplitPredicate = false;
1486
1487
1489
1490
1492
1493
1494 APInt getConstantMultipleImpl(const SCEV *S);
1495
1496
1497
1498 struct ExitNotTakenInfo {
1500 const SCEV *ExactNotTaken;
1501 const SCEV *ConstantMaxNotTaken;
1502 const SCEV *SymbolicMaxNotTaken;
1504
1506 const SCEV *ExactNotTaken,
1507 const SCEV *ConstantMaxNotTaken,
1508 const SCEV *SymbolicMaxNotTaken,
1510 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1511 ConstantMaxNotTaken(ConstantMaxNotTaken),
1512 SymbolicMaxNotTaken(SymbolicMaxNotTaken), Predicates(Predicates) {}
1513
1514 bool hasAlwaysTruePredicate() const {
1515 return Predicates.empty();
1516 }
1517 };
1518
1519
1520
1521
1522 class BackedgeTakenInfo {
1523 friend class ScalarEvolution;
1524
1525
1526
1527 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1528
1529
1530
1531
1532 const SCEV *ConstantMax = nullptr;
1533
1534
1535
1536 bool IsComplete = false;
1537
1538
1539
1540 const SCEV *SymbolicMax = nullptr;
1541
1542
1543 bool MaxOrZero = false;
1544
1545 bool isComplete() const { return IsComplete; }
1546 const SCEV *getConstantMax() const { return ConstantMax; }
1547
1548 const ExitNotTakenInfo *getExitNotTaken(
1549 const BasicBlock *ExitingBlock,
1550 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const;
1551
1552 public:
1553 BackedgeTakenInfo() = default;
1554 BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
1555 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
1556
1557 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1558
1559
1560 BackedgeTakenInfo(ArrayRef ExitCounts, bool IsComplete,
1561 const SCEV *ConstantMax, bool MaxOrZero);
1562
1563
1564
1565 bool hasAnyInfo() const {
1566 return !ExitNotTaken.empty() ||
1567 !isa(getConstantMax());
1568 }
1569
1570
1571 bool hasFullInfo() const { return isComplete(); }
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591 const SCEV *getExact(
1592 const Loop *L, ScalarEvolution *SE,
1593 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const;
1594
1595
1596
1597
1598
1599
1600 const SCEV *getExact(
1601 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1602 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const {
1603 if (auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1604 return ENT->ExactNotTaken;
1605 else
1606 return SE->getCouldNotCompute();
1607 }
1608
1609
1610 const SCEV *getConstantMax(
1611 ScalarEvolution *SE,
1612 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const;
1613
1614
1615 const SCEV *getConstantMax(
1616 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1617 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const {
1618 if (auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1619 return ENT->ConstantMaxNotTaken;
1620 else
1621 return SE->getCouldNotCompute();
1622 }
1623
1624
1625 const SCEV *getSymbolicMax(
1626 const Loop *L, ScalarEvolution *SE,
1627 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr);
1628
1629
1630 const SCEV *getSymbolicMax(
1631 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1632 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const {
1633 if (auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1634 return ENT->SymbolicMaxNotTaken;
1635 else
1636 return SE->getCouldNotCompute();
1637 }
1638
1639
1640
1641 bool isConstantMaxOrZero(ScalarEvolution *SE) const;
1642 };
1643
1644
1645
1646 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1647
1648
1649
1650 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1651
1652
1653 DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1654 BECountUsers;
1655
1656
1657
1658
1659
1660 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1661
1662
1663
1664
1665 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1666 ValuesAtScopes;
1667
1668
1669
1670 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1671 ValuesAtScopesUsers;
1672
1673
1674 DenseMap<const SCEV *,
1675 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1676 LoopDispositions;
1677
1678 struct LoopProperties {
1679
1680
1681
1682
1683
1684 bool HasNoAbnormalExits;
1685
1686
1687
1688 bool HasNoSideEffects;
1689 };
1690
1691
1692 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1693
1694
1695 LoopProperties getLoopProperties(const Loop *L);
1696
1697 bool loopHasNoSideEffects(const Loop *L) {
1698 return getLoopProperties(L).HasNoSideEffects;
1699 }
1700
1701
1702 LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
1703
1704
1705 DenseMap<
1706 const SCEV *,
1707 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1708 BlockDispositions;
1709
1710
1711 BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
1712
1713
1714 DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1715
1716
1717 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1718
1719
1720 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1721
1722
1723 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1724
1725
1726 const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
1727 ConstantRange CR) {
1728 DenseMap<const SCEV *, ConstantRange> &Cache =
1729 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1730
1731 auto Pair = Cache.insert_or_assign(S, std::move(CR));
1732 return Pair.first->second;
1733 }
1734
1735
1736
1737
1738 const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint,
1739 unsigned Depth = 0);
1740
1741
1742
1743 const ConstantRange &getRangeRefIter(const SCEV *S, RangeSignHint Hint);
1744
1745
1746
1747 ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Step,
1748 const APInt &MaxBECount);
1749
1750
1751
1752 ConstantRange getRangeForAffineNoSelfWrappingAR(const SCEVAddRecExpr *AddRec,
1753 const SCEV *MaxBECount,
1755 RangeSignHint SignHint);
1756
1757
1758
1759
1760 ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Step,
1761 const APInt &MaxBECount);
1762
1763
1764
1765
1766
1767 ConstantRange getRangeForUnknownRecurrence(const SCEVUnknown *U);
1768
1769
1770
1771 const SCEV *createSCEV(Value *V);
1772
1773
1774
1775 const SCEV *createSCEVIter(Value *V);
1776
1777
1778
1779 const SCEV *getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
1780
1781
1782
1783 const SCEV *createNodeForPHIWithIdenticalOperands(PHINode *PN);
1784
1785
1786 const SCEV *createNodeForPHI(PHINode *PN);
1787
1788
1789 const SCEV *createAddRecFromPHI(PHINode *PN);
1790
1791
1792 const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1793 Value *StartValueV);
1794
1795
1796 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1797
1798
1799
1800
1801
1802 std::optional<const SCEV *>
1803 createNodeForSelectOrPHIInstWithICmpInstCond(Type *Ty, ICmpInst *Cond,
1804 Value *TrueVal, Value *FalseVal);
1805
1806
1807 const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *I, Value *Cond,
1808 Value *TrueVal,
1809 Value *FalseVal);
1810
1811
1812
1813
1814
1815 const SCEV *createNodeForSelectOrPHI(Value *V, Value *Cond, Value *TrueVal,
1816 Value *FalseVal);
1817
1818
1819 const SCEV *createNodeForGEP(GEPOperator *GEP);
1820
1821
1822
1823 const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
1824
1825
1826
1827
1828 BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
1829
1830
1831
1832 BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
1833
1834
1835
1836
1837 BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
1838 bool AllowPredicates = false);
1839
1840
1841
1842
1843
1844 ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
1845 bool IsOnlyExit, bool AllowPredicates = false);
1846
1847
1848
1849
1850 class ExitLimitCache {
1851
1852
1853
1854
1855
1856 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1857
1858 const Loop *L;
1859 bool ExitIfTrue;
1860 bool AllowPredicates;
1861
1862 public:
1863 ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates)
1864 : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1865
1866 std::optional find(const Loop *L, Value *ExitCond,
1867 bool ExitIfTrue, bool ControlsOnlyExit,
1868 bool AllowPredicates);
1869
1870 void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1871 bool ControlsOnlyExit, bool AllowPredicates,
1872 const ExitLimit &EL);
1873 };
1874
1875 using ExitLimitCacheTy = ExitLimitCache;
1876
1877 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1878 const Loop *L, Value *ExitCond,
1879 bool ExitIfTrue,
1880 bool ControlsOnlyExit,
1881 bool AllowPredicates);
1882 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
1883 Value *ExitCond, bool ExitIfTrue,
1884 bool ControlsOnlyExit,
1885 bool AllowPredicates);
1886 std::optionalScalarEvolution::ExitLimit computeExitLimitFromCondFromBinOp(
1887 ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue,
1888 bool ControlsOnlyExit, bool AllowPredicates);
1889
1890
1891
1892
1893
1894
1895 ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
1896 bool ExitIfTrue,
1897 bool IsSubExpr,
1898 bool AllowPredicates = false);
1899
1900
1901
1902
1903
1904 ExitLimit computeExitLimitFromICmp(const Loop *L, CmpPredicate Pred,
1905 const SCEV *LHS, const SCEV *RHS,
1906 bool IsSubExpr,
1907 bool AllowPredicates = false);
1908
1909
1910
1911
1912 ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
1913 SwitchInst *Switch,
1914 BasicBlock *ExitingBB,
1915 bool IsSubExpr);
1916
1917
1918
1919
1920
1921
1922
1923
1924 ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L,
1926
1927
1928
1929
1930
1931
1932 const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
1933 bool ExitWhen);
1934
1935
1936
1937
1938
1939 ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
1940 bool AllowPredicates = false);
1941
1942
1943
1944
1945 ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959 ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1960 bool isSigned, bool ControlsOnlyExit,
1961 bool AllowPredicates = false);
1962
1963 ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1964 bool isSigned, bool IsSubExpr,
1965 bool AllowPredicates = false);
1966
1967
1968
1969
1970 std::pair<const BasicBlock *, const BasicBlock *>
1971 getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB) const;
1972
1973
1974
1975
1976
1977 bool isImpliedCond(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS,
1978 const Value *FoundCondValue, bool Inverse,
1979 const Instruction *Context = nullptr);
1980
1981
1982
1983
1984
1985 bool isImpliedCondBalancedTypes(CmpPredicate Pred, const SCEV *LHS,
1986 const SCEV *RHS, CmpPredicate FoundPred,
1987 const SCEV *FoundLHS, const SCEV *FoundRHS,
1988 const Instruction *CtxI);
1989
1990
1991
1992
1993
1994 bool isImpliedCond(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS,
1995 CmpPredicate FoundPred, const SCEV *FoundLHS,
1996 const SCEV *FoundRHS,
1997 const Instruction *Context = nullptr);
1998
1999
2000
2001
2002
2003 bool isImpliedCondOperands(CmpPredicate Pred, const SCEV *LHS,
2004 const SCEV *RHS, const SCEV *FoundLHS,
2005 const SCEV *FoundRHS,
2006 const Instruction *Context = nullptr);
2007
2008
2009
2010
2011
2012 bool isImpliedViaOperations(CmpPredicate Pred, const SCEV *LHS,
2013 const SCEV *RHS, const SCEV *FoundLHS,
2014 const SCEV *FoundRHS, unsigned Depth = 0);
2015
2016
2017
2018 bool isKnownViaNonRecursiveReasoning(CmpPredicate Pred, const SCEV *LHS,
2019 const SCEV *RHS);
2020
2021
2022
2023
2024 bool isImpliedCondOperandsHelper(CmpPredicate Pred, const SCEV *LHS,
2025 const SCEV *RHS, const SCEV *FoundLHS,
2026 const SCEV *FoundRHS);
2027
2028
2029
2030
2031
2032 bool isImpliedCondOperandsViaRanges(CmpPredicate Pred, const SCEV *LHS,
2033 const SCEV *RHS, CmpPredicate FoundPred,
2034 const SCEV *FoundLHS,
2035 const SCEV *FoundRHS);
2036
2037
2038
2039 bool isImpliedViaGuard(const BasicBlock *BB, CmpPredicate Pred,
2040 const SCEV *LHS, const SCEV *RHS);
2041
2042
2043
2044
2045
2046
2047
2048 bool isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred, const SCEV *LHS,
2049 const SCEV *RHS, const SCEV *FoundLHS,
2050 const SCEV *FoundRHS);
2051
2052
2053
2054
2055
2056
2057
2058 bool isImpliedCondOperandsViaAddRecStart(CmpPredicate Pred, const SCEV *LHS,
2059 const SCEV *RHS,
2060 const SCEV *FoundLHS,
2061 const SCEV *FoundRHS,
2062 const Instruction *CtxI);
2063
2064
2065
2066
2067
2068
2069
2070
2071 bool isImpliedViaMerge(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS,
2072 const SCEV *FoundLHS, const SCEV *FoundRHS,
2073 unsigned Depth);
2074
2075
2076
2077
2078
2079
2080 bool isImpliedCondOperandsViaShift(CmpPredicate Pred, const SCEV *LHS,
2081 const SCEV *RHS, const SCEV *FoundLHS,
2082 const SCEV *FoundRHS);
2083
2084
2085
2086
2087 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
2088 const Loop *L);
2089
2090
2091
2092 bool isKnownPredicateViaConstantRanges(CmpPredicate Pred, const SCEV *LHS,
2093 const SCEV *RHS);
2094
2095
2096
2097
2098
2099
2100 bool isKnownPredicateViaNoOverflow(CmpPredicate Pred, const SCEV *LHS,
2101 const SCEV *RHS);
2102
2103
2104
2105 bool isKnownPredicateViaSplitting(CmpPredicate Pred, const SCEV *LHS,
2106 const SCEV *RHS);
2107
2108
2109 bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
2111
2112
2113 void forgetBackedgeTakenCounts(const Loop *L, bool Predicated);
2114
2115
2116 void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
2117
2118
2119 void forgetMemoizedResultsImpl(const SCEV *S);
2120
2121
2122
2123 void visitAndClearUsers(SmallVectorImpl<Instruction *> &Worklist,
2124 SmallPtrSetImpl<Instruction *> &Visited,
2125 SmallVectorImpl<const SCEV *> &ToForget);
2126
2127
2128 void eraseValueFromMap(Value *V);
2129
2130
2131 void insertValueToMap(Value *V, const SCEV *S);
2132
2133
2134
2135 bool checkValidity(const SCEV *S) const;
2136
2137
2138
2139
2140
2141
2142 template
2143 bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
2144 const Loop *L);
2145
2146
2147 SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
2148
2149
2150
2151 SCEV::NoWrapFlags proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR);
2152
2153
2154
2155 SCEV::NoWrapFlags proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR);
2156
2157 std::optional
2158 getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS,
2160
2161
2162
2163
2165
2166
2167
2168
2169
2170 const Instruction *getNonTrivialDefiningScopeBound(const SCEV *S);
2171
2172
2173
2174
2175 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
2176 bool &Precise);
2177
2178
2179
2180 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops);
2181
2182
2183
2184 bool isGuaranteedToTransferExecutionTo(const Instruction *A,
2185 const Instruction *B);
2186
2187
2188 bool isGuaranteedNotToCauseUB(const SCEV *Op);
2189
2190
2191 static bool isGuaranteedNotToBePoison(const SCEV *Op);
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209 bool isSCEVExprNeverPoison(const Instruction *I);
2210
2211
2212
2213
2214
2215 bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2228 createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239 const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
2241 bool IsSigned);
2242
2243
2244
2245
2246 bool canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2247
2248
2249
2250
2251 bool canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2252
2253
2254 const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2256
2257
2258 const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
2260
2261
2262 const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
2264
2265
2266 const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
2267
2268
2269
2270
2271 void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2272
2273
2274
2275 bool matchURem(const SCEV *Expr, const SCEV *&LHS, const SCEV *&RHS);
2276
2277
2278
2279 SCEV *findExistingSCEVInCache(SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
2280
2281
2282
2283 void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2284 Function &F);
2285
2286
2287
2288 const SCEV *getWithOperands(const SCEV *S,
2289 SmallVectorImpl<const SCEV *> &NewOps);
2290
2291 FoldingSet UniqueSCEVs;
2292 FoldingSet UniquePreds;
2294
2295
2296 DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2297
2298
2299
2300 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2301 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2302 PredicatedSCEVRewrites;
2303
2304
2305
2306 SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
2307
2308
2309
2310 SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
2311
2312
2313
2314
2316};
2317
2318
2322
2324
2325public:
2327
2329};
2330
2331
2333 : public PassInfoMixin {
2334public:
2337};
2338
2339
2341 : public PassInfoMixin {
2343
2344public:
2346
2348
2350};
2351
2353 std::unique_ptr SE;
2354
2355public:
2357
2359
2362
2368};
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2384public:
2386
2388
2389
2390
2391
2392
2394
2395
2397
2398
2400
2401
2402
2404
2405
2407
2408
2409
2410
2411
2413
2414
2416
2417
2418
2420
2421
2423
2424
2426
2427
2428
2430
2431
2432
2435
2436private:
2437
2438
2439 void updateGeneration();
2440
2441
2442
2443 using RewriteEntry = std::pair<unsigned, const SCEV *>;
2444
2445
2446
2447
2448
2449
2451
2452
2454
2455
2457
2458
2459 const Loop &L;
2460
2461
2462
2463 std::unique_ptr Preds;
2464
2465
2466
2467
2468
2469 unsigned Generation = 0;
2470
2471
2472 const SCEV *BackedgeCount = nullptr;
2473
2474
2475 const SCEV *SymbolicMaxBackedgeCount = nullptr;
2476
2477
2478 std::optional SmallConstantMaxTripCount;
2479};
2480
2484 return ID;
2485 }
2488 return ID;
2489 }
2490
2493 }
2494
2498 }
2499};
2500
2501}
2502
2503#endif
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
This header defines various interfaces for pass management in LLVM.
mir Rename Register Operands
This file defines the PointerIntPair class.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Class for arbitrary precision integers.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Value handle with callbacks on RAUW and destruction.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
This is the shared class of boolean and integer constants.
This class represents a range of values.
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Node - This class is used to maintain the singly linked bucket list in a folding set.
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
FunctionPass class - This class is used to implement most global optimizations.
This is an important class for using LLVM in a threaded context.
Represents a single loop in the control flow graph.
A Module instance is used to store all the information related to an LLVM module.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Value handle that poisons itself if the Value is deleted.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
const SCEVPredicate & getPredicate() const
bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
This node represents a polynomial recurrence on the trip count of the specified loop.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
const SCEV * getRHS() const
Returns the right hand side of the predicate.
ICmpInst::Predicate getPredicate() const
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEV * getLHS() const
Returns the left hand side of the predicate.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class uses information about analyze scalars to rewrite expressions in canonical form.
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicateKind getKind() const
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
SCEVPredicate & operator=(const SCEVPredicate &)=default
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
virtual void print(raw_ostream &OS, unsigned Depth=0) const =0
Prints a textual representation of this predicate with an indentation of Depth.
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
unsigned getComplexity() const override
We estimate the complexity of a union predicate as the size number of predicates in the union.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
ArrayRef< const SCEVPredicate * > getPredicates() const
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
static SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
static SCEVWrapPredicate::IncrementWrapFlags maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask)
This class represents an analyzed expression in the program.
ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
unsigned short getExpressionSize() const
SCEV & operator=(const SCEV &)=delete
bool isOne() const
Return true if the expression is a constant one.
bool isZero() const
Return true if the expression is a constant zero.
SCEV(const SCEV &)=delete
void dump() const
This method is used for debugging.
bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
const unsigned short ExpressionSize
void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize)
SCEVTypes getSCEVType() const
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information.
Type * getType() const
Return the LLVM type of this SCEV expression.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Analysis pass that exposes the ScalarEvolution for a function.
ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
Printer pass for the ScalarEvolutionAnalysis results.
ScalarEvolutionPrinterPass(raw_ostream &OS)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Verifier pass for the ScalarEvolutionAnalysis results.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
ScalarEvolution & getSE()
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
ScalarEvolutionWrapperPass()
const ScalarEvolution & getSE() const
bool operator==(const FoldID &RHS) const
FoldID(SCEVTypes C, const SCEV *Op, const Type *Ty)
unsigned computeHash() const
static LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
const SCEV * getGEPExpr(GEPOperator *GEP, const SmallVectorImpl< const SCEV * > &IndexExprs)
Returns an expression for a GEP.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
Type * getWiderType(Type *Ty1, Type *Ty2) const
const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
APInt getConstantMultiple(const SCEV *S)
Returns the max constant multiple of S.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
const SCEV * getAddExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?...
ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
const SCEV * getMulExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
bool SimplifyICmpOperands(CmpPredicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
const SCEV * getAddRecExpr(const SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
uint32_t getMinTrailingZeros(const SCEV *S)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
void print(raw_ostream &OS) const
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
const SCEV * getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock, SmallVectorImpl< const SCEVPredicate * > *Predicates, ExitCountKind Kind=Exact)
Same as above except this uses the predicated backedge taken info and may require predicates.
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
void forgetTopmostLoop(const Loop *L)
friend class ScalarEvolutionsTest
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
const SCEV * getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
MonotonicPredicateType
A predicate is said to be monotonically increasing if may go from being false to being true as the lo...
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
friend class SCEVCallbackVH
const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
const SCEV * getCouldNotCompute()
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
const SCEV * getVScale(Type *Ty)
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
const SCEV * getPowerOfTwo(Type *Ty, unsigned Power)
Return a SCEV for the constant Power of two.
const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
const SCEV * getUnknown(Value *V)
std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getElementCount(Type *Ty, ElementCount EC)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
const SCEV * getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
bool isKnownViaInduction(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVMContext & getContext() const
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Class to represent struct types.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM Value Representation.
This class implements an extremely fast bulk output stream that can only output to a stream.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ BasicBlock
Various leaf nodes.
unsigned combineHashValue(unsigned a, unsigned b)
Simplistic combination of 32-bit hash values into 32-bit hash values.
This is an optimization pass for GlobalISel generic memory operations.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
DWARFExpression::Operation Op
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
constexpr unsigned BitWidth
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...
static unsigned getHashValue(const ScalarEvolution::FoldID &Val)
static ScalarEvolution::FoldID getTombstoneKey()
static ScalarEvolution::FoldID getEmptyKey()
static bool isEqual(const ScalarEvolution::FoldID &LHS, const ScalarEvolution::FoldID &RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID)
static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
static unsigned ComputeHash(const SCEVPredicate &X, FoldingSetNodeID &TempID)
static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID)
static void Profile(const SCEV &X, FoldingSetNodeID &ID)
FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...
A CRTP mix-in to automatically provide informational APIs needed for passes.
An object of this class is returned by queries that could not be answered.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Information about the number of loop iterations for which a loop exit's branch condition evaluates to...
bool hasAnyInfo() const
Test whether this ExitLimit contains any computed information, or whether it's all SCEVCouldNotComput...
const SCEV * ExactNotTaken
const SCEV * SymbolicMaxNotTaken
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
bool hasFullInfo() const
Test whether this ExitLimit contains all information.
const SCEV * ConstantMaxNotTaken
LoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)