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
39#include
40#include
41#include
42#include
43#include
44
45namespace llvm {
46
66
68
69
70
71
74
75
76
78
79
81
82protected:
83
85
86
87
89
90public:
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
134
140
142
143
145
146
148
149
151
152
154
155
157
158
160
161
162
163
164
165
166
167
168
169
173
174
175
177
178
180};
181
182
183
186
190 }
191
193 return X.FastID.ComputeHash();
194 }
195};
196
201
202
203
204
205
212
213
214
217
218
219
221
222public:
224
225protected:
230
231public:
233
235
236
237
239
240
241
243
244
246
247
248
250};
251
253 P.print(OS);
254 return OS;
255}
256
257
258
259template <>
264
268 }
269
272 return X.FastID.ComputeHash();
273 }
274};
275
276
277
279
281 const SCEV *LHS;
282 const SCEV *RHS;
283
284public:
287 const SCEV *LHS, const SCEV *RHS);
288
289
293
295
296
298
299
301
302
306};
307
308
309
310
311
312
313
314
315
316
317
319public:
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
349
350
356 "Invalid flags value!");
358 }
359
367
373 "Invalid flags value!");
374
376 }
377
378
379
382
383private:
385 IncrementWrapFlags Flags;
386
387public:
390 IncrementWrapFlags Flags);
391
392
394
395
399 bool isAlwaysTrue() const override;
400
401
403 return P->getKind() == P_Wrap;
404 }
405};
406
407
408
409
410
411
412
414private:
415 using PredicateMap =
417
418
420
421
423
424public:
427
429
430
431
435 Result.add(N, SE);
436 return Result;
437 }
438
439
440 bool isAlwaysTrue() const override;
443
444
445
446 unsigned getComplexity() const override { return Preds.size(); }
447
448
450 return P->getKind() == P_Union;
451 }
452};
453
454
455
456
459
460public:
461
467
468
474
475
476
491 return TestFlags == maskFlags(Flags, TestFlags);
492 };
493
499
501
502
503
504
505
507
508
509
511
512
513
514
516
517
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
535
536
537
539
540
541
542
546
547
548
549
550
551
552 LLVM_ABI std::optionalSCEV::NoWrapFlags
554
555
557
558
560
561
562
564
565
566
568
569
571
576 unsigned Depth = 0);
579 unsigned Depth = 0);
585 unsigned Depth = 0);
587 unsigned Depth = 0);
589 unsigned Depth = 0);
591 unsigned Depth = 0);
596 unsigned Depth = 0);
599 unsigned Depth = 0) {
602 }
605 unsigned Depth = 0) {
608 }
611 unsigned Depth = 0);
614 unsigned Depth = 0) {
617 }
620 unsigned Depth = 0) {
623 }
636
637
638
639
640
642 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
644
645
646
647
648
649
654 Type *SrcElementTy,
669 bool Sequential = false);
671 bool Sequential = false);
674
675
677
678
680
681
686
687
691
692
694
695
697
698
700
701
703 unsigned FieldNo);
704
705
708
709
711
712
713
714
715
716
717
718
721 unsigned Depth = 0);
722
723
724
725
726
727
728
729
730
732
733
734
736 unsigned Depth = 0);
737
738
739
741 unsigned Depth = 0);
742
743
744
745
747
748
749
750
752
753
754
755
757
758
759
761
762
763
766
767
768
771 bool Sequential = false);
772
773
774
777 bool Sequential = false);
778
779
780
781
782
784
785
787
788
789
790
791
792
793
794
795
796
797
799
800
802
803
804
805
808
809
810
815
816
817
820
821
822
824
825
826
827
828
829
830
831
833 Type *EvalTy, const Loop *L);
834
835
836
837
838
840
841
842
843
844
845
846
847
848
849
852
853
854
855
856
858 const Loop *L,
860
861
862
863
864
865
866
868 const SCEV *ExitCount);
869
870
871
872
874
875
876
877
878
879
880
883
884
885
886
896
897
898
899
900
901
902
906
907
908
913
914
915
916
917
918
919
920
921
922
923
926
927
928
929
930
933
934
935
936
937
941
942
943
944
945
948
949
950
951
952
956
957
958
959
960
963
964
965
967
968
969
971
972
973
974
975
976
978
979
980
981
982
984
985
986
987
988
990
991
992
993
995
996
997
999
1000
1001
1002
1003
1004
1006
1007
1008
1009
1010
1011
1013
1014
1015
1016
1017
1018
1021
1022
1023
1026
1027
1029
1030
1031
1033 return getRangeRef(S, HINT_RANGE_UNSIGNED);
1034 }
1035
1036
1038 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
1039 }
1040
1041
1043 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
1044 }
1045
1046
1047
1049 return getRangeRef(S, HINT_RANGE_SIGNED);
1050 }
1051
1052
1054 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
1055 }
1056
1057
1059 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
1060 }
1061
1062
1064
1065
1067
1068
1070
1071
1073
1074
1076
1077
1078
1080 bool OrNegative = false);
1081
1082
1083
1084
1085
1089
1090
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109 LLVM_ABI std::pair<const SCEV *, const SCEV *>
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1132
1133
1134
1137
1138
1139
1140
1141 LLVM_ABI std::optional
1143
1144
1145
1148
1149
1150
1151
1156
1157
1158
1162
1163
1164
1165
1166
1170
1172
1173
1175
1176
1177
1178
1180
1181
1182
1183
1185
1190
1194
1195
1196
1201
1202
1206 };
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1219 bool ExitIfTrue,
1220 bool ControlsOnlyExit,
1221 bool AllowPredicates = false);
1222
1223
1224
1225
1226
1227
1232
1233
1234
1235
1236
1237
1238 LLVM_ABI std::optional
1241
1250
1251
1252
1253 LLVM_ABI std::optional
1256
1257
1258
1259
1260
1261
1262 LLVM_ABI std::optional
1267 const SCEV *MaxIter);
1268
1269 LLVM_ABI std::optional
1273
1274
1275
1276
1277
1280
1281
1282
1284
1285
1286
1288
1289
1290
1291
1293
1294
1295
1296
1297
1299
1300
1301
1304
1305
1306
1308
1309
1310
1312
1313
1315
1316
1318
1322 FunctionAnalysisManager::Invalidator &Inv);
1323
1324
1325
1327
1333
1337
1338
1341
1342
1344 const SCEV *S, const Loop *L,
1346
1347
1348
1349
1350
1351
1352
1353
1356
1357
1358
1359
1361
1362 class LoopGuards {
1365 bool PreserveNUW = false;
1366 bool PreserveNSW = false;
1368
1370
1371
1372
1373
1374 static void
1378 unsigned Depth = 0);
1379
1380
1381
1382
1383
1384 static void collectFromPHI(
1388 unsigned Depth);
1389
1390 public:
1391
1392
1394
1395
1397 };
1398
1399
1403
1404
1405
1406
1407
1409 return getLoopProperties(L).HasNoAbnormalExits;
1410 }
1411
1412
1413
1415
1416
1417
1418
1421 const SCEV *S);
1422
1423
1424
1425
1429
1431 const SCEV *Op = nullptr;
1432 const Type *Ty = nullptr;
1433 unsigned short C;
1434
1435 public:
1440
1442
1446 reinterpret_cast<uintptr_t>(Ty)));
1447 }
1448
1450 return std::tie(Op, Ty, C) == std::tie(RHS.Op, RHS.Ty, RHS.C);
1451 }
1452 };
1453
1454private:
1455
1456
1459
1460 void deleted() override;
1461 void allUsesReplacedWith(Value *New) override;
1462
1463 public:
1465 };
1466
1467 friend class SCEVCallbackVH;
1470
1471
1473
1474
1476
1477
1478
1479
1480 bool HasGuards;
1481
1482
1484
1485
1487
1488
1490
1491
1493
1494
1495 std::unique_ptr CouldNotCompute;
1496
1497
1499
1500
1501 HasRecMapType HasRecMap;
1502
1503
1506
1507
1508
1509 ExprValueMapType ExprValueMap;
1510
1511
1512 using ValueExprMapType =
1514
1515
1516 ValueExprMapType ValueExprMap;
1517
1518
1519
1522
1523
1525
1526
1528
1529
1531
1532
1534
1535
1536
1537 bool WalkingBEDominatingConds = false;
1538
1539
1540
1541 bool ProvingSplitPredicate = false;
1542
1543
1545
1546
1548
1549
1550
1551 APInt getConstantMultipleImpl(const SCEV *S,
1553
1554
1555
1556 struct ExitNotTakenInfo {
1558 const SCEV *ExactNotTaken;
1559 const SCEV *ConstantMaxNotTaken;
1560 const SCEV *SymbolicMaxNotTaken;
1562
1564 const SCEV *ExactNotTaken,
1565 const SCEV *ConstantMaxNotTaken,
1566 const SCEV *SymbolicMaxNotTaken,
1568 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1569 ConstantMaxNotTaken(ConstantMaxNotTaken),
1570 SymbolicMaxNotTaken(SymbolicMaxNotTaken), Predicates(Predicates) {}
1571
1572 bool hasAlwaysTruePredicate() const {
1573 return Predicates.empty();
1574 }
1575 };
1576
1577
1578
1579
1580 class BackedgeTakenInfo {
1581 friend class ScalarEvolution;
1582
1583
1584
1585 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1586
1587
1588
1589
1590 const SCEV *ConstantMax = nullptr;
1591
1592
1593
1594 bool IsComplete = false;
1595
1596
1597
1598 const SCEV *SymbolicMax = nullptr;
1599
1600
1601 bool MaxOrZero = false;
1602
1603 bool isComplete() const { return IsComplete; }
1604 const SCEV *getConstantMax() const { return ConstantMax; }
1605
1606 LLVM_ABI const ExitNotTakenInfo *getExitNotTaken(
1607 const BasicBlock *ExitingBlock,
1608 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const;
1609
1610 public:
1611 BackedgeTakenInfo() = default;
1612 BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
1613 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
1614
1615 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1616
1617
1619 bool IsComplete, const SCEV *ConstantMax,
1620 bool MaxOrZero);
1621
1622
1623
1624 bool hasAnyInfo() const {
1625 return !ExitNotTaken.empty() ||
1627 }
1628
1629
1630 bool hasFullInfo() const { return isComplete(); }
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650 LLVM_ABI const SCEV *getExact(
1651 const Loop *L, ScalarEvolution *SE,
1652 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const;
1653
1654
1655
1656
1657
1658
1659 const SCEV *getExact(
1660 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1661 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const {
1662 if (auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1663 return ENT->ExactNotTaken;
1664 else
1665 return SE->getCouldNotCompute();
1666 }
1667
1668
1669 LLVM_ABI const SCEV *getConstantMax(
1670 ScalarEvolution *SE,
1671 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const;
1672
1673
1674 const SCEV *getConstantMax(
1675 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1676 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const {
1677 if (auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1678 return ENT->ConstantMaxNotTaken;
1679 else
1680 return SE->getCouldNotCompute();
1681 }
1682
1683
1684 LLVM_ABI const SCEV *getSymbolicMax(
1685 const Loop *L, ScalarEvolution *SE,
1686 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr);
1687
1688
1689 const SCEV *getSymbolicMax(
1690 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1691 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const {
1692 if (auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1693 return ENT->SymbolicMaxNotTaken;
1694 else
1695 return SE->getCouldNotCompute();
1696 }
1697
1698
1699
1700 LLVM_ABI bool isConstantMaxOrZero(ScalarEvolution *SE) const;
1701 };
1702
1703
1704
1705 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1706
1707
1708
1709 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1710
1711
1712 DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1713 BECountUsers;
1714
1715
1716
1717
1718
1719 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1720
1721
1722
1723
1724 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1725 ValuesAtScopes;
1726
1727
1728
1729 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1730 ValuesAtScopesUsers;
1731
1732
1733 DenseMap<const SCEV *,
1735 LoopDispositions;
1736
1737 struct LoopProperties {
1738
1739
1740
1741
1742
1743 bool HasNoAbnormalExits;
1744
1745
1746
1747 bool HasNoSideEffects;
1748 };
1749
1750
1751 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1752
1753
1754 LLVM_ABI LoopProperties getLoopProperties(const Loop *L);
1755
1756 bool loopHasNoSideEffects(const Loop *L) {
1757 return getLoopProperties(L).HasNoSideEffects;
1758 }
1759
1760
1761 LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
1762
1763
1764 DenseMap<
1765 const SCEV *,
1767 BlockDispositions;
1768
1769
1770 BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
1771
1772
1773 DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1774
1775
1776 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1777
1778
1779 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1780
1781
1782 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1783
1784
1785 const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
1786 ConstantRange CR) {
1787 DenseMap<const SCEV *, ConstantRange> &Cache =
1788 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1789
1790 auto Pair = Cache.insert_or_assign(S, std::move(CR));
1791 return Pair.first->second;
1792 }
1793
1794
1795
1796
1797 LLVM_ABI const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint,
1798 unsigned Depth = 0);
1799
1800
1801
1802 const ConstantRange &getRangeRefIter(const SCEV *S, RangeSignHint Hint);
1803
1804
1805
1806 ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Step,
1807 const APInt &MaxBECount);
1808
1809
1810
1811 ConstantRange getRangeForAffineNoSelfWrappingAR(const SCEVAddRecExpr *AddRec,
1812 const SCEV *MaxBECount,
1814 RangeSignHint SignHint);
1815
1816
1817
1818
1819 ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Step,
1820 const APInt &MaxBECount);
1821
1822
1823
1824
1825
1826 ConstantRange getRangeForUnknownRecurrence(const SCEVUnknown *U);
1827
1828
1829
1830 const SCEV *createSCEV(Value *V);
1831
1832
1833
1834 const SCEV *createSCEVIter(Value *V);
1835
1836
1837
1838 const SCEV *getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
1839
1840
1841
1842 const SCEV *createNodeForPHIWithIdenticalOperands(PHINode *PN);
1843
1844
1845 const SCEV *createNodeForPHI(PHINode *PN);
1846
1847
1848 const SCEV *createAddRecFromPHI(PHINode *PN);
1849
1850
1851 const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1852 Value *StartValueV);
1853
1854
1855 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1856
1857
1858
1859
1860
1861 std::optional<const SCEV *>
1862 createNodeForSelectOrPHIInstWithICmpInstCond(Type *Ty, ICmpInst *Cond,
1864
1865
1866 const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *I, Value *Cond,
1868 Value *FalseVal);
1869
1870
1871
1872
1873
1874 const SCEV *createNodeForSelectOrPHI(Value *V, Value *Cond, Value *TrueVal,
1875 Value *FalseVal);
1876
1877
1878 const SCEV *createNodeForGEP(GEPOperator *GEP);
1879
1880
1881
1882 const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
1883
1884
1885
1886
1887 BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
1888
1889
1890
1891 BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
1892
1893
1894
1895
1896 BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
1897 bool AllowPredicates = false);
1898
1899
1900
1901
1902
1903 ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
1904 bool IsOnlyExit, bool AllowPredicates = false);
1905
1906
1907
1908
1909 class ExitLimitCache {
1910
1911
1912
1913
1914
1915 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1916
1917 const Loop *L;
1918 bool ExitIfTrue;
1919 bool AllowPredicates;
1920
1921 public:
1922 ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates)
1923 : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1924
1925 LLVM_ABI std::optional find(const Loop *L, Value *ExitCond,
1926 bool ExitIfTrue,
1927 bool ControlsOnlyExit,
1928 bool AllowPredicates);
1929
1930 LLVM_ABI void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1931 bool ControlsOnlyExit, bool AllowPredicates,
1932 const ExitLimit &EL);
1933 };
1934
1935 using ExitLimitCacheTy = ExitLimitCache;
1936
1937 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1938 const Loop *L, Value *ExitCond,
1939 bool ExitIfTrue,
1940 bool ControlsOnlyExit,
1941 bool AllowPredicates);
1942 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
1943 Value *ExitCond, bool ExitIfTrue,
1944 bool ControlsOnlyExit,
1945 bool AllowPredicates);
1946 std::optionalScalarEvolution::ExitLimit computeExitLimitFromCondFromBinOp(
1947 ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue,
1948 bool ControlsOnlyExit, bool AllowPredicates);
1949
1950
1951
1952
1953
1954
1955 ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
1956 bool ExitIfTrue,
1957 bool IsSubExpr,
1958 bool AllowPredicates = false);
1959
1960
1961
1962
1963
1964 ExitLimit computeExitLimitFromICmp(const Loop *L, CmpPredicate Pred,
1965 const SCEV *LHS, const SCEV *RHS,
1966 bool IsSubExpr,
1967 bool AllowPredicates = false);
1968
1969
1970
1971
1972 ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
1973 SwitchInst *Switch,
1974 BasicBlock *ExitingBB,
1975 bool IsSubExpr);
1976
1977
1978
1979
1980
1981
1982
1983
1986
1987
1988
1989
1990
1991
1992 const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
1993 bool ExitWhen);
1994
1995
1996
1997
1998
1999 ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
2000 bool AllowPredicates = false);
2001
2002
2003
2004
2005 ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019 ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
2020 bool isSigned, bool ControlsOnlyExit,
2021 bool AllowPredicates = false);
2022
2023 ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
2024 bool isSigned, bool IsSubExpr,
2025 bool AllowPredicates = false);
2026
2027
2028
2029
2030 std::pair<const BasicBlock *, const BasicBlock *>
2031 getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB) const;
2032
2033
2034
2035
2036
2037 LLVM_ABI bool isImpliedCond(CmpPredicate Pred, const SCEV *LHS,
2038 const SCEV *RHS, const Value *FoundCondValue,
2039 bool Inverse,
2040 const Instruction *Context = nullptr);
2041
2042
2043
2044
2045
2046 LLVM_ABI bool isImpliedCondBalancedTypes(CmpPredicate Pred, const SCEV *LHS,
2047 const SCEV *RHS,
2048 CmpPredicate FoundPred,
2049 const SCEV *FoundLHS,
2050 const SCEV *FoundRHS,
2051 const Instruction *CtxI);
2052
2053
2054
2055
2056
2057 LLVM_ABI bool isImpliedCond(CmpPredicate Pred, const SCEV *LHS,
2058 const SCEV *RHS, CmpPredicate FoundPred,
2059 const SCEV *FoundLHS, const SCEV *FoundRHS,
2060 const Instruction *Context = nullptr);
2061
2062
2063
2064
2065
2066 bool isImpliedCondOperands(CmpPredicate Pred, const SCEV *LHS,
2067 const SCEV *RHS, const SCEV *FoundLHS,
2068 const SCEV *FoundRHS,
2069 const Instruction *Context = nullptr);
2070
2071
2072
2073
2074
2075 bool isImpliedViaOperations(CmpPredicate Pred, const SCEV *LHS,
2076 const SCEV *RHS, const SCEV *FoundLHS,
2077 const SCEV *FoundRHS, unsigned Depth = 0);
2078
2079
2080
2081 bool isKnownViaNonRecursiveReasoning(CmpPredicate Pred, const SCEV *LHS,
2082 const SCEV *RHS);
2083
2084
2085
2086
2087 bool isImpliedCondOperandsHelper(CmpPredicate Pred, const SCEV *LHS,
2088 const SCEV *RHS, const SCEV *FoundLHS,
2089 const SCEV *FoundRHS);
2090
2091
2092
2093
2094
2095 bool isImpliedCondOperandsViaRanges(CmpPredicate Pred, const SCEV *LHS,
2096 const SCEV *RHS, CmpPredicate FoundPred,
2097 const SCEV *FoundLHS,
2098 const SCEV *FoundRHS);
2099
2100
2101
2102 bool isImpliedViaGuard(const BasicBlock *BB, CmpPredicate Pred,
2103 const SCEV *LHS, const SCEV *RHS);
2104
2105
2106
2107
2108
2109
2110
2111 bool isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred, const SCEV *LHS,
2112 const SCEV *RHS, const SCEV *FoundLHS,
2113 const SCEV *FoundRHS);
2114
2115
2116
2117
2118
2119
2120
2121 bool isImpliedCondOperandsViaAddRecStart(CmpPredicate Pred, const SCEV *LHS,
2122 const SCEV *RHS,
2123 const SCEV *FoundLHS,
2124 const SCEV *FoundRHS,
2125 const Instruction *CtxI);
2126
2127
2128
2129
2130
2131
2132
2133
2134 bool isImpliedViaMerge(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS,
2135 const SCEV *FoundLHS, const SCEV *FoundRHS,
2136 unsigned Depth);
2137
2138
2139
2140
2141
2142
2143 bool isImpliedCondOperandsViaShift(CmpPredicate Pred, const SCEV *LHS,
2144 const SCEV *RHS, const SCEV *FoundLHS,
2145 const SCEV *FoundRHS);
2146
2147
2148
2149
2150 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
2151 const Loop *L);
2152
2153
2154
2155 bool isKnownPredicateViaConstantRanges(CmpPredicate Pred, const SCEV *LHS,
2156 const SCEV *RHS);
2157
2158
2159
2160
2161
2162
2163 bool isKnownPredicateViaNoOverflow(CmpPredicate Pred, const SCEV *LHS,
2164 const SCEV *RHS);
2165
2166
2167
2168 bool isKnownPredicateViaSplitting(CmpPredicate Pred, const SCEV *LHS,
2169 const SCEV *RHS);
2170
2171
2172 bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
2174
2175
2176 void forgetBackedgeTakenCounts(const Loop *L, bool Predicated);
2177
2178
2180
2181
2182 void forgetMemoizedResultsImpl(const SCEV *S);
2183
2184
2185
2186 void visitAndClearUsers(SmallVectorImpl<Instruction *> &Worklist,
2187 SmallPtrSetImpl<Instruction *> &Visited,
2188 SmallVectorImpl<const SCEV *> &ToForget);
2189
2190
2191 void eraseValueFromMap(Value *V);
2192
2193
2194 void insertValueToMap(Value *V, const SCEV *S);
2195
2196
2197
2198 bool checkValidity(const SCEV *S) const;
2199
2200
2201
2202
2203
2204
2205 template
2206 bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
2207 const Loop *L);
2208
2209
2210 SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
2211
2212
2213
2214 SCEV::NoWrapFlags proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR);
2215
2216
2217
2218 SCEV::NoWrapFlags proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR);
2219
2220 std::optional
2221 getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS,
2223
2224
2225
2226
2228
2229
2230
2231
2232
2233 const Instruction *getNonTrivialDefiningScopeBound(const SCEV *S);
2234
2235
2236
2237
2239 bool &Precise);
2240
2241
2242
2244
2245
2246
2247 bool isGuaranteedToTransferExecutionTo(const Instruction *A,
2248 const Instruction *B);
2249
2250
2251 bool isGuaranteedNotToCauseUB(const SCEV *Op);
2252
2253
2254 static bool isGuaranteedNotToBePoison(const SCEV *Op);
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272 bool isSCEVExprNeverPoison(const Instruction *I);
2273
2274
2275
2276
2277
2278 bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2291 createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302 const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
2303 const SCEV *End, unsigned BitWidth,
2304 bool IsSigned);
2305
2306
2307
2308
2309 bool canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2310
2311
2312
2313
2314 bool canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2315
2316
2319
2320
2323
2324
2327
2328
2329 const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
2330
2331
2332
2333
2334 void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2335
2336
2337
2339
2340
2341
2342 void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2343 Function &F);
2344
2345
2346
2347 const SCEV *getWithOperands(const SCEV *S,
2348 SmallVectorImpl<const SCEV *> &NewOps);
2349
2350 FoldingSet UniqueSCEVs;
2351 FoldingSet UniquePreds;
2353
2354
2355 DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2356
2357
2358
2359 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2360 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2361 PredicatedSCEVRewrites;
2362
2363
2364
2365 SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
2366
2367
2368
2369 SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
2370
2371
2372
2373
2375};
2376
2377
2381
2383
2384public:
2386
2388};
2389
2390
2392 : public PassInfoMixin {
2393public:
2396};
2397
2398
2400 : public PassInfoMixin {
2402
2403public:
2405
2407
2409};
2410
2412 std::unique_ptr SE;
2413
2414public:
2416
2418
2421
2423 void releaseMemory() override;
2424 void getAnalysisUsage(AnalysisUsage &AU) const override;
2426 void verifyAnalysis() const override;
2427};
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2443public:
2445
2447
2448
2449
2450
2451
2453
2454
2456
2457
2459
2460
2461
2463
2464
2466
2467
2468
2469
2470
2472
2473
2476
2477
2478
2481
2482
2484
2485
2487
2488
2489
2491
2492
2493
2496
2497private:
2498
2499
2500 void updateGeneration();
2501
2502
2503
2504 using RewriteEntry = std::pair<unsigned, const SCEV *>;
2505
2506
2507
2508
2509
2510
2512
2513
2515
2516
2518
2519
2520 const Loop &L;
2521
2522
2523
2524 std::unique_ptr Preds;
2525
2526
2527
2528
2529
2530 unsigned Generation = 0;
2531
2532
2533 const SCEV *BackedgeCount = nullptr;
2534
2535
2536 const SCEV *SymbolicMaxBackedgeCount = nullptr;
2537
2538
2539 std::optional SmallConstantMaxTripCount;
2540};
2541
2561
2562}
2563
2564#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
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")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
static bool runOnFunction(Function &F, bool PostInlining)
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.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
This file defines the PointerIntPair class.
const SmallVectorImpl< MachineOperand > & Cond
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
Class for arbitrary precision integers.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
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.
This is an important base class in LLVM.
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.
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.
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags none()
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 ...
Definition ScalarEvolution.h:2442
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
Definition ScalarEvolution.h:2483
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
LLVM_ABI void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI 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.
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
const SCEV * getRHS() const
Returns the right hand side of the predicate.
Definition ScalarEvolution.h:300
ICmpInst::Predicate getPredicate() const
Definition ScalarEvolution.h:294
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEV * getLHS() const
Returns the left hand side of the predicate.
Definition ScalarEvolution.h:297
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition ScalarEvolution.h:303
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class represents an assumption made using SCEV expressions which can be checked at run-time.
Definition ScalarEvolution.h:215
SCEVPredicateKind getKind() const
Definition ScalarEvolution.h:234
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
Definition ScalarEvolution.h:238
SCEVPredicate & operator=(const SCEVPredicate &)=default
SCEVPredicate(const SCEVPredicate &)=default
SCEVPredicateKind
Definition ScalarEvolution.h:223
@ P_Compare
Definition ScalarEvolution.h:223
@ P_Union
Definition ScalarEvolution.h:223
@ P_Wrap
Definition ScalarEvolution.h:223
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.
SCEVPredicateKind Kind
Definition ScalarEvolution.h:226
unsigned getComplexity() const override
We estimate the complexity of a union predicate as the size number of predicates in the union.
Definition ScalarEvolution.h:446
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
SCEVUnionPredicate getUnionWith(const SCEVPredicate *N, ScalarEvolution &SE) const
Returns a new SCEVUnionPredicate that is the union of this predicate and the given predicate N.
Definition ScalarEvolution.h:432
ArrayRef< const SCEVPredicate * > getPredicates() const
Definition ScalarEvolution.h:428
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition ScalarEvolution.h:449
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.
Definition ScalarEvolution.h:318
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
Definition ScalarEvolution.h:342
@ IncrementAnyWrap
Definition ScalarEvolution.h:343
@ IncrementNUSW
Definition ScalarEvolution.h:344
@ IncrementNoWrapMask
Definition ScalarEvolution.h:347
@ IncrementNSSW
Definition ScalarEvolution.h:345
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
Definition ScalarEvolution.h:369
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
Definition ScalarEvolution.h:352
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition ScalarEvolution.h:402
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
Definition ScalarEvolution.h:393
static SCEVWrapPredicate::IncrementWrapFlags maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask)
Definition ScalarEvolution.h:361
This class represents an analyzed expression in the program.
Definition ScalarEvolution.h:72
LLVM_ABI ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
unsigned short getExpressionSize() const
Definition ScalarEvolution.h:170
SCEV & operator=(const SCEV &)=delete
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
SCEV(const SCEV &)=delete
LLVM_ABI void dump() const
This method is used for debugging.
LLVM_ABI bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
const unsigned short ExpressionSize
Definition ScalarEvolution.h:84
LLVM_ABI 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)
Definition ScalarEvolution.h:135
SCEVTypes getSCEVType() const
Definition ScalarEvolution.h:141
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information.
Definition ScalarEvolution.h:88
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Definition ScalarEvolution.h:127
@ FlagAnyWrap
Definition ScalarEvolution.h:128
@ FlagNSW
Definition ScalarEvolution.h:131
@ FlagNUW
Definition ScalarEvolution.h:130
@ NoWrapMask
Definition ScalarEvolution.h:132
@ FlagNW
Definition ScalarEvolution.h:129
Analysis pass that exposes the ScalarEvolution for a function.
Definition ScalarEvolution.h:2379
ScalarEvolution Result
Definition ScalarEvolution.h:2385
LLVM_ABI ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
ScalarEvolutionPrinterPass(raw_ostream &OS)
Definition ScalarEvolution.h:2404
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static bool isRequired()
Definition ScalarEvolution.h:2408
Verifier pass for the ScalarEvolutionAnalysis results.
Definition ScalarEvolution.h:2392
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static bool isRequired()
Definition ScalarEvolution.h:2395
ScalarEvolution & getSE()
Definition ScalarEvolution.h:2419
static char ID
Definition ScalarEvolution.h:2415
ScalarEvolutionWrapperPass()
const ScalarEvolution & getSE() const
Definition ScalarEvolution.h:2420
Definition ScalarEvolution.h:1430
FoldID(unsigned short C)
Definition ScalarEvolution.h:1441
bool operator==(const FoldID &RHS) const
Definition ScalarEvolution.h:1449
FoldID(SCEVTypes C, const SCEV *Op, const Type *Ty)
Definition ScalarEvolution.h:1436
unsigned computeHash() const
Definition ScalarEvolution.h:1443
Definition ScalarEvolution.h:1362
static LLVM_ABI 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 ...
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
Definition ScalarEvolution.h:457
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
Definition ScalarEvolution.h:938
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
Definition ScalarEvolution.h:489
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
Definition ScalarEvolution.h:1326
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI 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 ...
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI 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...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI 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.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI 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...
LLVM_ABI const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI 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)
Definition ScalarEvolution.h:597
LLVM_ABI 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.
Definition ScalarEvolution.h:676
LLVM_ABI 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)?
LLVM_ABI 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...
LLVM_ABI const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI 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 ...
LLVM_ABI 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.
Definition ScalarEvolution.h:1048
friend class SCEVExpander
Definition ScalarEvolution.h:1468
LLVM_ABI 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.
Definition ScalarEvolution.h:1408
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
Definition ScalarEvolution.h:679
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
LLVM_ABI const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
LLVM_ABI 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.
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI 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)
Definition ScalarEvolution.h:612
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI 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...
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI 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.
Definition ScalarEvolution.h:1037
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
LLVM_ABI const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LLVM_ABI LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
LLVM_ABI const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI 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)
Definition ScalarEvolution.h:631
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
LLVM_ABI bool haveSameSign(const SCEV *S1, const SCEV *S2)
Return true if we know that S1 and S2 must have the same sign.
LLVM_ABI const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
LLVM_ABI 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.
Definition ScalarEvolution.h:1032
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
LLVM_ABI 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)
Definition ScalarEvolution.h:486
LLVM_ABI void forgetTopmostLoop(const Loop *L)
friend class ScalarEvolutionsTest
Definition ScalarEvolution.h:458
LLVM_ABI 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.
Definition ScalarEvolution.h:1053
const SCEV * getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Definition ScalarEvolution.h:618
LLVM_ABI const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI 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...
Definition ScalarEvolution.h:1228
@ MonotonicallyDecreasing
Definition ScalarEvolution.h:1230
@ MonotonicallyIncreasing
Definition ScalarEvolution.h:1229
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate 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...
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI 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.
LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
Definition ScalarEvolution.h:688
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
Definition ScalarEvolution.h:481
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
friend class SCEVUnknown
Definition ScalarEvolution.h:1469
LLVM_ABI 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...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
Definition ScalarEvolution.h:462
@ LoopComputable
The SCEV varies predictably with the loop.
Definition ScalarEvolution.h:465
@ LoopVariant
The SCEV is loop-variant (unknown).
Definition ScalarEvolution.h:463
@ LoopInvariant
The SCEV is loop-invariant.
Definition ScalarEvolution.h:464
friend class SCEVCallbackVH
Definition ScalarEvolution.h:1467
LLVM_ABI bool isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > &Assumptions)
Check that S is a multiple of M.
LLVM_ABI const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI 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,...
LLVM_ABI 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...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI 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,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
Definition ScalarEvolution.h:469
@ DominatesBlock
The SCEV dominates the block.
Definition ScalarEvolution.h:471
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
Definition ScalarEvolution.h:472
@ DoesNotDominateBlock
The SCEV does not dominate the block.
Definition ScalarEvolution.h:470
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< const SCEV * > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI 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...
LLVM_ABI const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI 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.
LLVM_ABI void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI 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.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI 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.
Definition ScalarEvolution.h:682
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
LLVM_ABI void forgetAllLoops()
LLVM_ABI 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.
Definition ScalarEvolution.h:1042
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
Definition ScalarEvolution.h:887
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
Definition ScalarEvolution.h:894
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
Definition ScalarEvolution.h:892
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
Definition ScalarEvolution.h:890
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI 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.
LLVM_ABI 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...
LLVM_ABI const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI 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.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI 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.
LLVM_ABI 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.
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
Definition ScalarEvolution.h:477
LLVM_ABI 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'...
LLVM_ABI 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)
Definition ScalarEvolution.h:603
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI 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.
LLVM_ABI 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,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI 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,...
LLVM_ABI 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.
Definition ScalarEvolution.h:953
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
Definition ScalarEvolution.h:1058
LLVM_ABI void verify() const
LLVMContext & getContext() const
Definition ScalarEvolution.h:500
Implements a dense probed hash-table based set with some number of buckets stored inline.
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.
unsigned combineHashValue(unsigned a, unsigned b)
Simplistic combination of 32-bit hash values into 32-bit hash values.
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
FunctionAddr VTableAddr Value
FoldingSetBase::Node FoldingSetNode
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa - Return true if the parameter to the template is an instance of one of the template type argu...
DWARFExpression::Operation Op
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
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)
Definition ScalarEvolution.h:2552
static ScalarEvolution::FoldID getTombstoneKey()
Definition ScalarEvolution.h:2547
static ScalarEvolution::FoldID getEmptyKey()
Definition ScalarEvolution.h:2543
static bool isEqual(const ScalarEvolution::FoldID &LHS, const ScalarEvolution::FoldID &RHS)
Definition ScalarEvolution.h:2556
An information struct used to provide DenseMap with the various necessary components for a given valu...
static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID)
Definition ScalarEvolution.h:261
static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
Definition ScalarEvolution.h:265
static unsigned ComputeHash(const SCEVPredicate &X, FoldingSetNodeID &TempID)
Definition ScalarEvolution.h:270
static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
Definition ScalarEvolution.h:187
static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID)
Definition ScalarEvolution.h:192
static void Profile(const SCEV &X, FoldingSetNodeID &ID)
Definition ScalarEvolution.h:185
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.
LLVM_ABI SCEVCouldNotCompute()
static LLVM_ABI 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...
Definition ScalarEvolution.h:1167
bool MaxOrZero
Definition ScalarEvolution.h:1174
LLVM_ABI ExitLimit(const SCEV *E)
Construct either an exact exit limit from a constant, or an unknown one from a SCEVCouldNotCompute.
bool hasAnyInfo() const
Test whether this ExitLimit contains any computed information, or whether it's all SCEVCouldNotComput...
Definition ScalarEvolution.h:1197
const SCEV * ExactNotTaken
Definition ScalarEvolution.h:1168
const SCEV * SymbolicMaxNotTaken
Definition ScalarEvolution.h:1171
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
Definition ScalarEvolution.h:1179
bool hasFullInfo() const
Test whether this ExitLimit contains all information.
Definition ScalarEvolution.h:1203
const SCEV * ConstantMaxNotTaken
Definition ScalarEvolution.h:1169
LoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Definition ScalarEvolution.h:1247
const SCEV * LHS
Definition ScalarEvolution.h:1244
const SCEV * RHS
Definition ScalarEvolution.h:1245
CmpPredicate Pred
Definition ScalarEvolution.h:1243