Go to the documentation of this file.
104 #ifndef LLVM_ADT_INTERVALMAP_H
105 #define LLVM_ADT_INTERVALMAP_H
139 template <
typename T>
166 template <
typename T>
191 namespace IntervalMapImpl {
222 template <
typename T1,
typename T2,
unsigned N>
235 template <
unsigned M>
237 unsigned j,
unsigned Count) {
238 assert(
i + Count <=
M &&
"Invalid source range");
239 assert(
j + Count <=
N &&
"Invalid dest range");
240 for (
unsigned e =
i + Count;
i !=
e; ++
i, ++
j) {
251 assert(
j <=
i &&
"Use moveRight shift elements right");
260 assert(
i <=
j &&
"Use moveLeft shift elements left");
261 assert(
j + Count <=
N &&
"Invalid range");
272 void erase(
unsigned i,
unsigned j,
unsigned Size) {
297 Sib.
copy(*
this, 0, SSize, Count);
298 erase(0, Count, Size);
309 Sib.
copy(*
this, Size-Count, 0, Count);
339 template <
typename NodeT>
341 unsigned CurSize[],
const unsigned NewSize[]) {
343 for (
int n = Nodes - 1;
n; --
n) {
344 if (CurSize[
n] == NewSize[
n])
346 for (
int m =
n - 1; m != -1; --m) {
347 int d =
Node[
n]->adjustFromLeftSib(CurSize[
n], *
Node[m], CurSize[m],
348 NewSize[
n] - CurSize[
n]);
352 if (CurSize[
n] >= NewSize[
n])
361 for (
unsigned n = 0;
n != Nodes - 1; ++
n) {
362 if (CurSize[
n] == NewSize[
n])
364 for (
unsigned m =
n + 1; m != Nodes; ++m) {
365 int d =
Node[m]->adjustFromLeftSib(CurSize[m], *
Node[
n], CurSize[
n],
366 CurSize[
n] - NewSize[
n]);
370 if (CurSize[
n] >= NewSize[
n])
376 for (
unsigned n = 0;
n != Nodes;
n++)
377 assert(CurSize[
n] == NewSize[
n] &&
"Insufficient element shuffle");
415 const unsigned *CurSize,
unsigned NewSize[],
416 unsigned Position,
bool Grow);
438 template <
typename KeyT,
typename ValT>
447 static_cast<unsigned>(2*
sizeof(
KeyT)+
sizeof(
ValT)),
461 static_cast<unsigned>(
sizeof(
KeyT) +
sizeof(
void*))
494 struct CacheAlignedPointerTraits {
495 static inline void *getAsVoidPointer(
void *
P) {
return P; }
496 static inline void *getFromVoidPointer(
void *
P) {
return P; }
509 template <
typename NodeT>
511 assert(
n <= NodeT::Capacity &&
"Size too big for node");
528 template <
typename NodeT>
530 return *
reinterpret_cast<NodeT*
>(pip.
getPointer());
565 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
583 assert(
i <= Size && Size <=
N &&
"Bad indices");
585 "Index is past the needed point");
586 while (
i != Size && Traits::stopLess(
stop(
i),
x)) ++
i;
600 "Index is past the needed point");
601 while (Traits::stopLess(
stop(
i),
x)) ++
i;
602 assert(
i <
N &&
"Unsafe intervals");
628 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
632 assert(
i <= Size && Size <=
N &&
"Invalid index");
633 assert(!Traits::stopLess(
b,
a) &&
"Invalid interval");
636 assert((
i == 0 || Traits::stopLess(stop(
i - 1),
a)));
637 assert((
i == Size || !Traits::stopLess(stop(
i),
a)));
638 assert((
i == Size || Traits::stopLess(
b, start(
i))) &&
"Overlapping insert");
641 if (
i && value(
i - 1) ==
y && Traits::adjacent(stop(
i - 1),
a)) {
644 if (
i != Size && value(
i) ==
y && Traits::adjacent(
b, start(
i))) {
645 stop(
i - 1) = stop(
i);
646 this->erase(
i, Size);
666 if (value(
i) ==
y && Traits::adjacent(
b, start(
i))) {
676 this->
shift(i, Size);
702 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
718 assert(
i <= Size && Size <=
N &&
"Bad indices");
720 "Index to findFrom is past the needed point");
721 while (
i != Size && Traits::stopLess(
stop(
i),
x)) ++
i;
734 "Index is past the needed point");
735 while (Traits::stopLess(
stop(
i),
x)) ++
i;
736 assert(
i <
N &&
"Unsafe intervals");
753 assert(Size <
N &&
"branch node overflow");
754 assert(
i <= Size &&
"Bad insert position");
755 this->
shift(i, Size);
781 Entry(
void *
Node,
unsigned Size,
unsigned Offset)
797 template <
typename NodeT> NodeT &
node(
unsigned Level)
const {
798 return *
reinterpret_cast<NodeT*
>(path[
Level].node);
805 template <
typename NodeT> NodeT &
leaf()
const {
806 return *
reinterpret_cast<NodeT*
>(path.back().node);
808 unsigned leafSize()
const {
return path.back().size; }
814 return !path.empty() && path.front().offset < path.front().size;
819 unsigned height()
const {
return path.size() - 1; }
838 path.push_back(Entry(
Node, Offset));
851 path[
Level].size = Size;
862 path.push_back(Entry(
Node, Size, Offset));
901 for (
unsigned i = 0,
e = path.size();
i !=
e; ++
i)
911 return path[
Level].offset == path[
Level].size - 1;
923 ++path[
Level].offset;
933 template <
typename KeyT,
typename ValT,
934 unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
935 typename Traits = IntervalMapInfo<KeyT>>
947 DesiredRootBranchCap = (
sizeof(
RootLeaf) -
sizeof(
KeyT)) /
949 RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
956 struct RootBranchData {
986 const RootLeaf &rootLeaf()
const {
987 assert(!branched() &&
"Cannot acces leaf data in branched root");
990 RootLeaf &rootLeaf() {
991 assert(!branched() &&
"Cannot acces leaf data in branched root");
995 const RootBranchData &rootBranchData()
const {
996 assert(branched() &&
"Cannot access branch data in non-branched root");
999 RootBranchData &rootBranchData() {
1000 assert(branched() &&
"Cannot access branch data in non-branched root");
1004 const RootBranch &rootBranch()
const {
return rootBranchData().node; }
1005 RootBranch &rootBranch() {
return rootBranchData().node; }
1006 KeyT rootBranchStart()
const {
return rootBranchData().start; }
1007 KeyT &rootBranchStart() {
return rootBranchData().start; }
1009 template <
typename NodeT> NodeT *newNode() {
1010 return new(
allocator.template Allocate<NodeT>()) NodeT();
1013 template <
typename NodeT>
void deleteNode(NodeT *
P) {
1018 IdxPair branchRoot(
unsigned Position);
1019 IdxPair splitRoot(
unsigned Position);
1021 void switchRootToBranch() {
1022 rootLeaf().~RootLeaf();
1024 new (&rootBranchData()) RootBranchData();
1027 void switchRootToLeaf() {
1028 rootBranchData().~RootBranchData();
1030 new(&rootLeaf()) RootLeaf();
1033 bool branched()
const {
return height > 0; }
1058 rootLeaf().~RootLeaf();
1063 return rootSize == 0;
1068 assert(!
empty() &&
"Empty IntervalMap has no start");
1069 return !branched() ? rootLeaf().
start(0) : rootBranchStart();
1074 assert(!
empty() &&
"Empty IntervalMap has no stop");
1075 return !branched() ? rootLeaf().
stop(rootSize - 1) :
1076 rootBranch().
stop(rootSize - 1);
1081 if (
empty() || Traits::startLess(
x,
start()) || Traits::stopLess(
stop(),
x))
1083 return branched() ? treeSafeLookup(
x,
NotFound) :
1095 unsigned p = rootLeaf().
findFrom(0, rootSize,
a);
1155 return !Traits::stopLess(
b,
I.start());
1161 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1162 ValT IntervalMap<KeyT, ValT, N, Traits>::
1164 assert(branched() &&
"treeLookup assumes a branched root");
1167 for (
unsigned h = height-1;
h; --
h)
1168 NR = NR.get<
Branch>().safeLookup(
x);
1169 return NR.get<Leaf>().safeLookup(
x,
NotFound);
1174 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1176 branchRoot(
unsigned Position) {
1177 using namespace IntervalMapImpl;
1179 const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
1182 unsigned size[Nodes];
1183 IdxPair NewOffset(0, Position);
1189 NewOffset =
distribute(Nodes, rootSize, Leaf::Capacity,
nullptr,
size,
1195 for (
unsigned n = 0;
n != Nodes; ++
n) {
1196 Leaf *L = newNode<Leaf>();
1197 L->copy(rootLeaf(), pos, 0,
size[
n]);
1203 switchRootToBranch();
1204 for (
unsigned n = 0;
n != Nodes; ++
n) {
1205 rootBranch().stop(
n) =
node[
n].template get<Leaf>().stop(
size[
n]-1);
1206 rootBranch().subtree(
n) =
node[
n];
1208 rootBranchStart() =
node[0].template get<Leaf>().start(0);
1215 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1217 splitRoot(
unsigned Position) {
1218 using namespace IntervalMapImpl;
1220 const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
1223 unsigned Size[Nodes];
1224 IdxPair NewOffset(0, Position);
1230 NewOffset =
distribute(Nodes, rootSize, Leaf::Capacity,
nullptr,
Size,
1236 for (
unsigned n = 0;
n != Nodes; ++
n) {
1237 Branch *
B = newNode<Branch>();
1238 B->copy(rootBranch(), Pos, 0,
Size[
n]);
1243 for (
unsigned n = 0;
n != Nodes; ++
n) {
1244 rootBranch().stop(
n) =
Node[
n].template get<Branch>().stop(
Size[
n]-1);
1245 rootBranch().subtree(
n) =
Node[
n];
1253 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1254 void IntervalMap<KeyT, ValT, N, Traits>::
1258 SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;
1261 for (
unsigned i = 0;
i != rootSize; ++
i)
1262 Refs.push_back(rootBranch().subtree(
i));
1265 for (
unsigned h = height - 1;
h; --
h) {
1266 for (
unsigned i = 0,
e = Refs.size();
i !=
e; ++
i) {
1267 for (
unsigned j = 0,
s = Refs[
i].
size();
j !=
s; ++
j)
1268 NextRefs.push_back(Refs[
i].subtree(
j));
1269 (this->*
f)(Refs[
i],
h);
1272 Refs.swap(NextRefs);
1276 for (
unsigned i = 0,
e = Refs.size();
i !=
e; ++
i)
1277 (this->*f)(Refs[
i], 0);
1280 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1281 void IntervalMap<KeyT, ValT, N, Traits>::
1286 deleteNode(&
Node.get<Leaf>());
1289 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1293 visitNodes(&IntervalMap::deleteNode);
1303 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1326 assert(map &&
"Invalid iterator");
1327 return map->branched();
1337 void pathFillFind(
KeyT x);
1338 void treeFind(
KeyT x);
1339 void treeAdvanceTo(
KeyT x);
1343 assert(valid() &&
"Cannot access invalid iterator");
1350 assert(valid() &&
"Cannot access invalid iterator");
1357 assert(valid() &&
"Cannot access invalid iterator");
1388 assert(map ==
RHS.map &&
"Cannot compare iterators from different maps");
1390 return !
RHS.valid();
1393 return &path.template leaf<Leaf>() == &
RHS.path.template leaf<Leaf>();
1409 setRoot(map->rootSize);
1414 assert(valid() &&
"Cannot increment end()");
1429 if (path.
leafOffset() && (valid() || !branched()))
1449 setRoot(map->rootLeaf().
findFrom(0, map->rootSize,
x));
1468 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1472 for (
unsigned i = map->height - path.height() - 1;
i; --
i) {
1482 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1485 setRoot(map->rootBranch().findFrom(0, map->rootSize,
x));
1492 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1496 if (!Traits::stopLess(path.leaf<
Leaf>().
stop(path.leafSize() - 1),
x)) {
1497 path.leafOffset() = path.leaf<
Leaf>().safeFind(path.leafOffset(),
x);
1505 if (path.height()) {
1506 for (
unsigned l = path.height() - 1;
l; --
l) {
1507 if (!Traits::stopLess(path.node<
Branch>(
l).
stop(path.offset(
l)),
x)) {
1509 path.offset(
l + 1) =
1510 path.node<
Branch>(
l + 1).safeFind(path.offset(
l + 1),
x);
1511 return pathFillFind(
x);
1516 if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)),
x)) {
1517 path.offset(1) = path.node<
Branch>(1).safeFind(path.offset(1),
x);
1518 return pathFillFind(
x);
1523 setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize,
x));
1532 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1540 void setNodeStop(
unsigned Level,
KeyT Stop);
1542 template <
typename NodeT>
bool overflow(
unsigned Level);
1544 void eraseNode(
unsigned Level);
1545 void treeErase(
bool UpdateRoot =
true);
1546 bool canCoalesceLeft(
KeyT Start,
ValT x);
1547 bool canCoalesceRight(
KeyT Stop,
ValT x);
1556 void setStart(
KeyT a);
1561 void setStop(
KeyT b);
1566 void setValue(
ValT x);
1579 this->unsafeStop() =
b;
1581 if (this->path.atLastEntry(
this->path.height()))
1582 setNodeStop(this->path.height(),
b);
1624 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1627 using namespace IntervalMapImpl;
1628 Path &
P = this->path;
1629 if (!this->branched()) {
1630 unsigned i =
P.leafOffset();
1631 RootLeaf &
Node =
P.leaf<RootLeaf>();
1633 Traits::adjacent(
Node.stop(
i-1), Start);
1636 if (
unsigned i =
P.leafOffset()) {
1637 Leaf &
Node =
P.leaf<Leaf>();
1638 return Node.value(
i-1) ==
Value && Traits::adjacent(
Node.stop(
i-1), Start);
1639 }
else if (
NodeRef NR =
P.getLeftSibling(
P.height())) {
1640 unsigned i = NR.size() - 1;
1641 Leaf &
Node = NR.get<Leaf>();
1642 return Node.value(
i) ==
Value && Traits::adjacent(
Node.stop(
i), Start);
1652 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1653 bool IntervalMap<KeyT, ValT, N, Traits>::
1655 using namespace IntervalMapImpl;
1657 unsigned i =
P.leafOffset() + 1;
1659 if (i >=
P.leafSize())
1661 RootLeaf &
Node =
P.leaf<RootLeaf>();
1662 return Node.value(
i) ==
Value && Traits::adjacent(Stop,
Node.start(
i));
1665 if (
i <
P.leafSize()) {
1666 Leaf &
Node =
P.leaf<Leaf>();
1667 return Node.value(
i) ==
Value && Traits::adjacent(Stop,
Node.start(
i));
1668 }
else if (
NodeRef NR =
P.getRightSibling(
P.height())) {
1669 Leaf &
Node = NR.get<Leaf>();
1670 return Node.value(0) ==
Value && Traits::adjacent(Stop,
Node.start(0));
1676 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1677 void IntervalMap<KeyT, ValT, N, Traits>::
1678 iterator::setNodeStop(
unsigned Level,
KeyT Stop) {
1682 IntervalMapImpl::Path &
P = this->
path;
1686 if (!
P.atLastEntry(
Level))
1693 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1696 assert(Traits::nonEmpty(
a, this->
stop()) &&
"Cannot move start beyond stop");
1698 if (!Traits::startLess(
a, CurStart) || !canCoalesceLeft(
a, this->
value())) {
1709 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1712 assert(Traits::nonEmpty(this->
start(), b) &&
"Cannot move stop beyond start");
1713 if (Traits::startLess(
b, this->
stop()) ||
1714 !canCoalesceRight(
b, this->
value())) {
1724 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1728 if (canCoalesceRight(this->
stop(), x)) {
1733 if (canCoalesceLeft(this->
start(), x)) {
1747 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1750 assert(
Level &&
"Cannot insert next to the root");
1751 bool SplitRoot =
false;
1758 IM.rootBranch().
insert(
P.offset(0), IM.rootSize,
Node, Stop);
1759 P.setSize(0, ++IM.rootSize);
1767 P.replaceRoot(&IM.rootBranch(), IM.rootSize,
Offset);
1774 P.legalizeForInsert(--
Level);
1779 assert(!SplitRoot &&
"Cannot overflow after splitting the root");
1780 SplitRoot = overflow<Branch>(
Level);
1785 if (
P.atLastEntry(
Level))
1786 setNodeStop(
Level, Stop);
1792 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1796 return treeInsert(
a,
b,
y);
1801 unsigned Size = IM.rootLeaf().
insertFrom(
P.leafOffset(), IM.rootSize,
a,
b,
y);
1805 P.setSize(0, IM.rootSize =
Size);
1810 IdxPair
Offset = IM.branchRoot(
P.leafOffset());
1811 P.replaceRoot(&IM.rootBranch(), IM.rootSize,
Offset);
1814 treeInsert(
a,
b,
y);
1817 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1820 using namespace IntervalMapImpl;
1821 Path &
P = this->
path;
1824 P.legalizeForInsert(this->
map->height);
1827 if (P.leafOffset() == 0 && Traits::startLess(
a,
P.leaf<
Leaf>().
start(0))) {
1829 if (
NodeRef Sib =
P.getLeftSibling(
P.height())) {
1831 unsigned SibOfs = Sib.size() - 1;
1832 if (SibLeaf.
value(SibOfs) ==
y &&
1833 Traits::adjacent(SibLeaf.
stop(SibOfs),
a)) {
1840 P.moveLeft(
P.height());
1841 if (Traits::stopLess(
b, CurLeaf.
start(0)) &&
1842 (
y != CurLeaf.
value(0) || !Traits::adjacent(
b, CurLeaf.
start(0)))) {
1844 setNodeStop(
P.height(), SibLeaf.
stop(SibOfs) =
b);
1849 a = SibLeaf.
start(SibOfs);
1855 this->
map->rootBranchStart() =
a;
1860 unsigned Size =
P.leafSize();
1861 bool Grow =
P.leafOffset() ==
Size;
1862 Size =
P.leaf<Leaf>().insertFrom(
P.leafOffset(),
Size,
a,
b,
y);
1866 overflow<Leaf>(
P.height());
1867 Grow =
P.leafOffset() ==
P.leafSize();
1868 Size =
P.leaf<Leaf>().insertFrom(
P.leafOffset(),
P.leafSize(),
a,
b,
y);
1873 P.setSize(
P.height(),
Size);
1877 setNodeStop(
P.height(),
b);
1881 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1889 IM.rootLeaf().
erase(
P.leafOffset(), IM.rootSize);
1890 P.setSize(0, --IM.rootSize);
1894 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1902 if (
P.leafSize() == 1) {
1903 IM.deleteNode(&
Node);
1904 eraseNode(IM.height);
1906 if (UpdateRoot && IM.branched() &&
P.valid() &&
P.atBegin())
1907 IM.rootBranchStart() =
P.leaf<
Leaf>().
start(0);
1912 Node.erase(
P.leafOffset(),
P.leafSize());
1913 unsigned NewSize =
P.leafSize() - 1;
1914 P.setSize(IM.height, NewSize);
1916 if (
P.leafOffset() == NewSize) {
1917 setNodeStop(IM.height,
Node.stop(NewSize - 1));
1918 P.moveRight(IM.height);
1919 }
else if (UpdateRoot &&
P.atBegin())
1920 IM.rootBranchStart() =
P.leaf<Leaf>().
start(0);
1927 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1928 void IntervalMap<KeyT, ValT, N, Traits>::
1929 iterator::eraseNode(
unsigned Level) {
1932 IntervalMapImpl::Path &
P = this->
path;
1935 IM.rootBranch().erase(
P.offset(0), IM.rootSize);
1936 P.setSize(0, --IM.rootSize);
1939 IM.switchRootToLeaf();
1946 if (
P.size(
Level) == 1) {
1948 IM.deleteNode(&Parent);
1953 unsigned NewSize =
P.size(
Level) - 1;
1954 P.setSize(
Level, NewSize);
1956 if (
P.offset(
Level) == NewSize) {
1957 setNodeStop(
Level, Parent.stop(NewSize - 1));
1975 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1976 template <
typename NodeT>
1977 bool IntervalMap<KeyT, ValT, N, Traits>::
1978 iterator::overflow(
unsigned Level) {
1979 using namespace IntervalMapImpl;
1981 unsigned CurSize[4];
1984 unsigned Elements = 0;
1990 Offset += Elements = CurSize[Nodes] = LeftSib.size();
1991 Node[Nodes++] = &LeftSib.get<NodeT>();
1995 Elements += CurSize[Nodes] =
P.size(
Level);
2001 Elements += CurSize[Nodes] = RightSib.size();
2002 Node[Nodes++] = &RightSib.get<NodeT>();
2006 unsigned NewNode = 0;
2007 if (Elements + 1 > Nodes * NodeT::Capacity) {
2009 NewNode = Nodes == 1 ? 1 : Nodes - 1;
2010 CurSize[Nodes] = CurSize[NewNode];
2012 CurSize[NewNode] = 0;
2013 Node[NewNode] = this->
map->template newNode<NodeT>();
2018 unsigned NewSize[4];
2020 CurSize, NewSize,
Offset,
true);
2028 bool SplitRoot =
false;
2031 KeyT Stop =
Node[Pos]->stop(NewSize[Pos]-1);
2032 if (NewNode && Pos == NewNode) {
2036 P.setSize(
Level, NewSize[Pos]);
2037 setNodeStop(
Level, Stop);
2039 if (Pos + 1 == Nodes)
2046 while(Pos != NewOffset.first) {
2050 P.offset(
Level) = NewOffset.second;
2070 template <
typename MapA,
typename MapB>
2072 using KeyType =
typename MapA::KeyType;
2073 using Traits =
typename MapA::KeyTraits;
2075 typename MapA::const_iterator posA;
2076 typename MapB::const_iterator posB;
2085 if (Traits::stopLess(posA.stop(), posB.start())) {
2088 if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2090 }
else if (Traits::stopLess(posB.stop(), posA.start())) {
2092 posB.advanceTo(posA.start());
2093 if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2101 posA.advanceTo(posB.start());
2102 if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2105 posB.advanceTo(posA.start());
2106 if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2119 return posA.valid() && posB.valid();
2123 const typename MapA::const_iterator &
a()
const {
return posA; }
2126 const typename MapB::const_iterator &
b()
const {
return posB; }
2130 KeyType ak =
a().start();
2131 KeyType bk =
b().start();
2132 return Traits::startLess(ak, bk) ? bk : ak;
2137 KeyType ak =
a().stop();
2138 KeyType bk =
b().stop();
2139 return Traits::startLess(ak, bk) ? ak : bk;
2157 if (Traits::startLess(posB.stop(), posA.stop()))
2170 if (Traits::stopLess(posA.stop(),
x))
2172 if (Traits::stopLess(posB.stop(),
x))
2180 #endif // LLVM_ADT_INTERVALMAP_H
void setRoot(unsigned Offset)
bool overlaps(KeyT a, KeyT b) const
overlaps(a, b) - Return true if the intervals in this map overlap with the interval [a;b].
static bool nonEmpty(const T &a, const T &b)
nonEmpty - Return true if [a;b] is non-empty.
void clear()
clear - Remove all entries.
This is an optimization pass for GlobalISel generic memory operations.
void insert(KeyT a, KeyT b, ValT y)
insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
const KeyT & stop() const
stop - Return the end of the current interval.
void setInt(IntType IntVal) &
NodeRef & subtree(unsigned i)
unsigned leafSize() const
static bool adjacent(const T &a, const T &b)
adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.
void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop)
insert - Insert a new (subtree, stop) pair.
NodeRef getLeftSibling(unsigned Level) const
getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
const ValT & operator*() const
void setSize(unsigned Level, unsigned Size)
setSize - Set the size of a node both in the path and in the tree.
bool valid() const
valid - Return true if path is at a valid node, not at end().
IntervalMap(Allocator &a)
IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, const unsigned *CurSize, unsigned NewSize[], unsigned Position, bool Grow)
IntervalMapImpl::distribute - Compute a new distribution of node elements after an overflow or underf...
void erase(unsigned i, unsigned j, unsigned Size)
erase - Erase elements [i;j).
void erase(unsigned i, unsigned Size)
erase - Erase element at i.
void setRoot(void *Node, unsigned Size, unsigned Offset)
setRoot - Clear the path and set a new root node.
bool empty() const
empty - Return true when no intervals are mapped.
NodeRef & subtree(unsigned Level) const
subtree - Get the subtree referenced from Level.
bool operator!=(const NodeRef &RHS) const
const_iterator(const IntervalMap &map)
unsigned & offset(unsigned Level)
void treeAdvanceTo(KeyT x)
treeAdvanceTo - Find position after the current one.
std::pair< unsigned, unsigned > IdxPair
ValT safeLookup(KeyT x, ValT NotFound) const
safeLookup - Lookup mapped value for a safe key.
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
const ValT & value(unsigned i) const
static bool stopLess(const T &b, const T &x)
stopLess - Return true if x is not in [a;b].
unsigned size() const
size - Return the number of elements in the referenced node.
the resulting code requires compare and branches when and if * p
unsigned offset(unsigned Level) const
const KeyT & stop(unsigned i) const
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
void adjustSiblingSizes(NodeT *Node[], unsigned Nodes, unsigned CurSize[], const unsigned NewSize[])
IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
unsigned safeFind(unsigned i, KeyT x) const
safeFind - Find an interval that is known to exist.
void goToBegin()
goToBegin - Move to the first interval in map.
ValT & unsafeValue() const
unsafeValue - Writable access to value() for iterator.
unsigned safeFind(unsigned i, KeyT x) const
safeFind - Find a subtree that is known to exist.
const KeyT & start() const
start - Return the beginning of the current interval.
const_iterator & operator++()
preincrement - Move to the next interval.
Itanium Name Demangler i e convert the string _Z1fv into f()". You can also use the CRTP base ManglingParser to perform some simple analysis on the mangled name
unsigned findFrom(unsigned i, unsigned Size, KeyT x) const
findFrom - Find the first interval after i that may contain x.
bool valid() const
valid - Return true if iterator is at an overlap.
void setSize(unsigned n)
setSize - Update the node size.
unsigned leafOffset() const
void setStart(KeyT a)
setStart - Move the start of the current interval.
void setStartUnchecked(KeyT a)
setStartUnchecked - Move the start of the current interval without checking for coalescing or overlap...
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
This requires reassociating to forms of expressions that are already something that reassoc doesn t think about yet These two functions should generate the same code on big endian int * l
KeyT start() const
start - Return the smallest mapped key in a non-empty map.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
const_iterator operator++(int)
postincrement - Don't do that!
std::pair< NodeId, LaneBitmask > NodeRef
unsigned findFrom(unsigned i, unsigned Size, KeyT x) const
findFrom - Find the first subtree after i that may contain x.
void setValueUnchecked(ValT x)
setValueUnchecked - Change the mapped value of the current interval without checking for coalescing.
int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add)
adjustFromLeftSib - Adjust the number if elements in this node by moving elements to or from a left s...
void moveRight(unsigned Level)
moveRight - Move path to the left sibling at Level.
void goToEnd()
goToEnd - Move beyond the last interval in map.
typename Sizer::Allocator Allocator
void advanceTo(KeyType x)
advanceTo - Move to the first overlapping interval with stopLess(x, stop()).
static bool adjacent(const T &a, const T &b)
adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
PointerTy getPointer() const
bool valid() const
valid - Return true if the current position is valid, false for end().
bool atBegin() const
atBegin - Return true if path is at begin().
void setMap(const IntervalMap &m)
setMap - Change the map iterated over.
IntervalMapImpl::Path path
void advanceTo(KeyT x)
advanceTo - Move to the first interval with stop >= x, or end().
NodeRef(NodeT *p, unsigned n)
NodeRef - Create a reference to the node p with n elements.
IntervalMap & operator=(const IntervalMap &Other)=delete
void fillLeft(unsigned Height)
fillLeft - Grow path to Height by taking leftmost branches.
KeyT & unsafeStart() const
unsafeStart - Writable access to start() for iterator.
KeyType start() const
start - Beginning of the overlapping interval.
void push(NodeRef Node, unsigned Offset)
push - Add entry to path.
multiplies can be turned into SHL s
bool operator==(const const_iterator &RHS) const
RootBranchData branchData
const ValT & value() const
value - Return the mapped value at the current interval.
void shift(unsigned i, unsigned Size)
shift - Shift elements [i;size) 1 position to the right.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper node
std::bidirectional_iterator_tag iterator_category
void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count)
transferToRightSib - Transfer elements to a right sibling node.
ValT lookup(KeyT x, ValT NotFound=ValT()) const
lookup - Return the mapped value at x or NotFound.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool startLess(const T &x, const T &a)
startLess - Return true if x is not in [a;b).
const_iterator find(KeyT x) const
find - Return an iterator pointing to the first interval ending at or after x, or end().
const NodeRef & subtree(unsigned i) const
static bool stopLess(const T &b, const T &x)
stopLess - Return true if x is not in [a;b).
static bool startLess(const T &x, const T &a)
startLess - Return true if x is not in [a;b].
void copy(const NodeBase< T1, T2, M > &Other, unsigned i, unsigned j, unsigned Count)
copy - Copy elements from another node.
bool operator==(uint64_t V1, const APInt &V2)
const KeyT & stop(unsigned i) const
IntervalMapOverlaps(const MapA &a, const MapB &b)
IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
bool atBegin() const
atBegin - Return true if the current position is the first map entry.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
void insert(KeyT a, KeyT b, ValT y)
insert - Insert mapping [a;b] -> y before the current position.
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
const_iterator end() const
Analysis the ScalarEvolution expression for r is this
NodeBase< std::pair< KeyT, KeyT >, ValT, LeafSize > LeafBase
const_iterator & operator--()
predecrement - Move to the previous interval.
bool operator==(const NodeRef &RHS) const
void setValue(ValT x)
setValue - Change the mapped value of the current interval.
KeyType stop() const
stop - End of the overlapping interval.
static bool nonEmpty(const T &a, const T &b)
nonEmpty - Return true if [a;b) is non-empty.
void moveRight(unsigned i, unsigned j, unsigned Count)
moveRight - Move elements to the right.
RecyclingAllocator - This class wraps an Allocator, adding the functionality of recycling deleted obj...
IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two IntervalMaps.
void legalizeForInsert(unsigned Level)
legalizeForInsert - Prepare the path for an insertion at Level.
const KeyT & start(unsigned i) const
void skipA()
skipA - Move to the next overlap that doesn't involve a().
void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count)
transferToLeftSib - Transfer elements to a left sibling node.
const MapA::const_iterator & a() const
a - access the left hand side in the overlap.
void reset(unsigned Level)
reset - Reset cached information about node(Level) from subtree(Level -1).
RecyclingAllocator< BumpPtrAllocator, char, AllocBytes, CacheLineBytes > Allocator
Allocator - The recycling allocator used for both branch and leaf nodes.
into llvm powi allowing the code generator to produce balanced multiplication trees the intrinsic needs to be extended to support and second the code generator needs to be enhanced to lower these to multiplication trees Interesting testcase for add shift mul int y
const MapB::const_iterator & b() const
b - access the right hand side in the overlap.
void * getOpaqueValue() const
void find(KeyT x)
find - Move to the first interval with stop >= x, or end().
unsigned height() const
height - Return the height of the tree corresponding to this path.
std::ptrdiff_t difference_type
void setStopUnchecked(KeyT b)
setStopUnchecked - Move the end of the current interval without checking for coalescing or overlaps.
void pop()
pop - Remove the last path entry.
void skipB()
skipB - Move to the next overlap that doesn't involve b().
void moveLeft(unsigned Level)
moveLeft - Move path to the left sibling at Level.
unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y)
insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as possible.
NodeRef getRightSibling(unsigned Level) const
getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
IntervalMapOverlaps & operator++()
Preincrement - Move to the next overlap.
NodeRef & subtree(unsigned i) const
subtree - Access the i'th subtree reference in a branch node.
const_iterator begin() const
NodeT & node(unsigned Level) const
http eax xorl edx cl sete al setne dl sall eax sall edx But that requires good bit subreg support this might be better It s an extra shift
void moveLeft(unsigned i, unsigned j, unsigned Count)
moveLeft - Move elements to the left.
unsigned size(unsigned Level) const
friend class const_iterator
the multiplication has a latency of four as opposed to two cycles for the movl lea variant It appears gcc place string data with linkonce linkage in section coalesced instead of section coalesced Take a look at darwin h
void replaceRoot(void *Root, unsigned Size, IdxPair Offsets)
replaceRoot - Replace the current root node with two new entries after the tree height has increased.
NodeT & get() const
get - Dereference as a NodeT reference.
NodeRef()=default
NodeRef - Create a null ref.
bool atLastEntry(unsigned Level) const
atLastEntry - Return true if the path is at the last entry of the node at Level.
const_iterator operator--(int)
postdecrement - Don't do that!
void pathFillFind(KeyT x)
pathFillFind - Complete path by searching for x.
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int int d
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
KeyT & unsafeStop() const
unsafeStop - Writable access to stop() for iterator.
@ NotFound
Sentinel value for when no action was found in the specified table.
LLVM Value Representation.
bool operator!=(const const_iterator &RHS) const
void erase()
erase - Erase the current interval.
void treeFind(KeyT x)
treeFind - Find in a branched tree.
void setStop(KeyT b)
setStop - Move the end of the current interval.
NodeRef safeLookup(KeyT x) const
safeLookup - Get the subtree containing x, Assuming that x is in range.
Optional< std::vector< StOtherPiece > > Other
KeyT stop() const
stop - Return the largest mapped key in a non-empty map.