Air should support linear scan for optLevel<2
[WebKit-https.git] / Source / WTF / wtf / RangeSet.h
1 /*
2  * Copyright (C) 2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef WTF_RangeSet_h
27 #define WTF_RangeSet_h
28
29 #include <wtf/ListDump.h>
30 #include <wtf/MathExtras.h>
31 #include <wtf/StdLibExtras.h>
32 #include <wtf/Vector.h>
33
34 namespace WTF {
35
36 // A RangeSet is a set of numerical ranges. A value belongs to the set if it is within any of the
37 // ranges. A range belongs to the set if every value in the range belongs to the set. A range overlaps
38 // the set if any value in the range belongs to the set. You can add ranges and query range
39 // membership. The internal representation is a list of ranges that gets periodically compacted. This
40 // representation is optimal so long as the number of distinct ranges tends to be small, and the
41 // number of range sets tends to be small as well. This works reasonably well in a bunch of compiler
42 // algorithms, where the top range ends up being used a lot.
43 //
44 // The initial user of this is JSC::B3::HeapRange, which is used to perform alias analysis. You can
45 // model new users on that class. Basically, you need to define:
46 //
47 // T::Type - the type of the members of the range. HeapRange uses unsigned.
48 // T(T::Type begin, T::Type end) - construct a new range.
49 // T::Type T::begin() const - instance method giving the inclusive beginning of the range.
50 // T::Type T::end() const - instance method giving the exclusive end of the range.
51 // void T::dump(PrintStream&) const - some kind of dumping.
52
53 template<typename RangeType>
54 class RangeSet {
55 public:
56     typedef RangeType Range;
57     typedef typename Range::Type Type;
58
59     RangeSet()
60     {
61     }
62
63     ~RangeSet()
64     {
65     }
66
67     void add(const Range& range)
68     {
69         if (range.begin() == range.end())
70             return;
71         
72         // We expect the range set to become top in a lot of cases. We also expect the same range to
73         // be added repeatedly. That's why this is here.
74         if (!m_ranges.isEmpty() && subsumesNonEmpty(m_ranges.last(), range))
75             return;
76
77         m_isCompact = false;
78
79         // We append without compacting only if doing so is guaranteed not to resize the vector.
80         // FIXME: This heuristic is almost certainly wrong, because we don't control the capacity. I
81         // think that this means that we will sometimes be rage-compacting when we are just shy of the
82         // capacity.
83         // https://bugs.webkit.org/show_bug.cgi?id=170308
84         if (m_ranges.size() + 1 < m_ranges.capacity()) {
85             m_ranges.append(range);
86             return;
87         }
88
89         m_ranges.append(range);
90         compact();
91     }
92
93     bool contains(const Range& range) const
94     {
95         if (range.begin() == range.end())
96             return false;
97         
98         unsigned index = findRange(range);
99         if (index != UINT_MAX)
100             return subsumesNonEmpty(m_ranges[index], range);
101         return false;
102     }
103
104     bool overlaps(const Range& range) const
105     {
106         if (range.begin() == range.end())
107             return false;
108         
109         return findRange(range) != UINT_MAX;
110     }
111
112     void clear()
113     {
114         m_ranges.clear();
115         m_isCompact = true;
116     }
117
118     void dump(PrintStream& out) const
119     {
120         const_cast<RangeSet*>(this)->compact();
121         out.print(listDump(m_ranges));
122     }
123
124     void dumpRaw(PrintStream& out) const
125     {
126         out.print("{", listDump(m_ranges), ", isCompact = ", m_isCompact, "}");
127     }
128
129 private:
130     void compact()
131     {
132         if (m_isCompact)
133             return;
134
135         if (m_ranges.isEmpty()) {
136             m_isCompact = true;
137             return;
138         }
139
140         std::sort(
141             m_ranges.begin(), m_ranges.end(),
142             [&] (const Range& a, const Range& b) -> bool {
143                 return a.begin() < b.begin();
144             });
145
146         unsigned srcIndex = 1;
147         unsigned dstIndex = 1;
148         Range* lastRange = &m_ranges[0];
149         while (srcIndex < m_ranges.size()) {
150             Range range = m_ranges[srcIndex++];
151             ASSERT(range.begin() >= lastRange->begin());
152             if (range.end() <= lastRange->end())
153                 continue;
154             if (range.begin() <= lastRange->end()) {
155                 *lastRange = Range(lastRange->begin(), range.end());
156                 continue;
157             }
158             ASSERT(!overlapsNonEmpty(*lastRange, range));
159             lastRange = &m_ranges[dstIndex++];
160             *lastRange = range;
161         }
162         m_ranges.resize(dstIndex);
163
164         m_isCompact = true;
165     }
166     
167     static bool overlapsNonEmpty(const Range& a, const Range& b)
168     {
169         return nonEmptyRangesOverlap(a.begin(), a.end(), b.begin(), b.end());
170     }
171
172     static bool subsumesNonEmpty(const Range& a, const Range& b)
173     {
174         return a.begin() <= b.begin() && a.end() >= b.end();
175     }
176
177     unsigned findRange(const Range& range) const
178     {
179         const_cast<RangeSet*>(this)->compact();
180
181         // FIXME: Once we start using this in anger, we will want this to be a binary search.
182         for (unsigned i = 0; i < m_ranges.size(); ++i) {
183             if (overlapsNonEmpty(m_ranges[i], range))
184                 return i;
185         }
186         
187         return UINT_MAX;
188     }
189     
190     Vector<Range, 8> m_ranges;
191     bool m_isCompact { true };
192 };
193
194 } // namespace WTF
195
196 using WTF::RangeSet;
197
198 #endif // WTF_RangeSet_h
199