Skip to content

Commit 95cec22

Browse files
ConstellationConstellation
committed
[JSC] Use Vector+InlineCapacity in LiveRange in AirAllocateRegistersByGreedy
https://bugs.webkit.org/show_bug.cgi?id=324009 rdar://187246753 Reviewed by Keith Miller. Use Vector with InlineCapacity in AirAllocateRegistersByGreedy's LiveRange construction. 1. Use InlineCapacity to avoid repeated alloc & free calls. Most of cases, this size 4 is enough. 2. Use Vector instead of Deque. And during construction, we append instead of prepend, and then when finalizing, we just reverse it. Deque is faster for this prepend, but Vector iteration etc. is faster than Deque due to Deque's iterator handles round-trip. And read-side is more heavy in this LiveRange data structure. * Source/JavaScriptCore/b3/air/AirAllocateRegistersByGreedy.cpp: (JSC::B3::Air::Greedy::LiveRange::validate): (JSC::B3::Air::Greedy::LiveRange::prependDescending): (JSC::B3::Air::Greedy::LiveRange::lowestSoFar const): (JSC::B3::Air::Greedy::LiveRange::finishDescendingBuild): (JSC::B3::Air::Greedy::LiveRange::intervals const): (JSC::B3::Air::Greedy::GreedyAllocator::buildLiveRanges): (JSC::B3::Air::Greedy::GreedyAllocator::addTmpImpl): (JSC::B3::Air::Greedy::LiveRange::prepend): Deleted. * Source/JavaScriptCore/b3/air/AirTmpMap.h: (JSC::B3::Air::TmpMap::forEachValue): Canonical link: https://commits.webkit.org/321011@main
1 parent 6b58d86 commit 95cec22

2 files changed

Lines changed: 53 additions & 17 deletions

File tree

‎Source/JavaScriptCore/b3/air/AirAllocateRegistersByGreedy.cpp‎

Lines changed: 45 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -199,34 +199,56 @@ static constexpr unsigned spillCostSizeBias = 25000 * PointOffsets::PointsPerIns
199199

200200
class LiveRange {
201201
public:
202+
// Nearly every Tmp gets a live range and nearly every range is a handful of intervals, so an
203+
// out-of-line buffer here would be one malloc per Tmp. A contiguous buffer also suits the
204+
// conflict queries, which iterate the intervals and are by far the hottest reader.
205+
using Intervals = Vector<Interval, 4>;
206+
202207
LiveRange() = default;
203208

204-
inline void NODELETE validate()
209+
inline void NODELETE validate(bool isDescending = false)
205210
{
206211
#if ASSERT_ENABLED
207212
size_t size = 0;
208213
Interval* prevInterval = nullptr;
209214
for (auto& interval : m_intervals) {
210215
ASSERT(interval.begin() < interval.end());
211-
ASSERT(!prevInterval || prevInterval->end() < interval.begin());
216+
if (prevInterval)
217+
ASSERT(isDescending ? interval.end() < prevInterval->begin() : prevInterval->end() < interval.begin());
212218
size += interval.distance();
213219
prevInterval = &interval;
214220
}
215221
ASSERT(size == m_size);
222+
#else
223+
UNUSED_PARAM(isDescending);
216224
#endif
217225
}
218226

219-
// interval must come before all the intervals already in this LiveRange.
220-
void prepend(Interval interval)
227+
// Adds an interval to a range being built by a backwards walk over the code. The intervals are
228+
// held in descending order until finishDescendingBuild() puts them the right way round, so that
229+
// what would be a front insertion is an append. Only lowestSoFar() may read the range while it
230+
// is in this state.
231+
void prependDescending(Interval interval)
221232
{
222233
ASSERT(interval);
223-
if (m_intervals.isEmpty() || interval.end() < m_intervals.first().begin())
224-
m_intervals.prepend(interval);
234+
if (m_intervals.isEmpty() || interval.end() < m_intervals.last().begin())
235+
m_intervals.append(interval);
225236
else {
226-
ASSERT(interval.end() == m_intervals.first().begin());
227-
m_intervals.first() |= interval;
237+
ASSERT(interval.end() == m_intervals.last().begin());
238+
m_intervals.last() |= interval;
228239
}
229240
m_size += interval.distance();
241+
validate(true);
242+
}
243+
244+
const Interval& NODELETE lowestSoFar() const
245+
{
246+
return m_intervals.last();
247+
}
248+
249+
void finishDescendingBuild()
250+
{
251+
m_intervals.reverse();
230252
validate();
231253
}
232254

@@ -244,7 +266,7 @@ class LiveRange {
244266
validate();
245267
}
246268

247-
const Deque<Interval>& NODELETE intervals() const
269+
const Intervals& NODELETE intervals() const
248270
{
249271
return m_intervals;
250272
}
@@ -370,7 +392,7 @@ class LiveRange {
370392
}
371393

372394
private:
373-
Deque<Interval> m_intervals;
395+
Intervals m_intervals;
374396
size_t m_size { 0 }; // Sum of the distances over m_intervals
375397
};
376398

@@ -676,7 +698,9 @@ class Coalescables {
676698
}
677699
};
678700

679-
Vector<Entry> m_entries;
701+
// Most Tmps that are coalescable at all have just one or two partners, and this list lives in
702+
// the per-Tmp map, so an out-of-line buffer here is another malloc per Tmp.
703+
Vector<Entry, 2> m_entries;
680704
#if ASSERT_ENABLED
681705
bool m_isSorted { false };
682706
#endif
@@ -1340,10 +1364,10 @@ class GreedyAllocator {
13401364
if (activeEnds[tmp])
13411365
return true;
13421366
// Tmp may have had a dead def at point (e.g. clobber).
1343-
auto& intervals = m_map[tmp].liveRange.intervals();
1344-
if (intervals.isEmpty())
1367+
const LiveRange& liveRange = m_map[tmp].liveRange;
1368+
if (liveRange.intervals().isEmpty())
13451369
return false;
1346-
return intervals.first().contains(point);
1370+
return liveRange.lowestSoFar().contains(point);
13471371
};
13481372

13491373
auto assertPinnedRegsAreLive = [&]() {
@@ -1385,7 +1409,7 @@ class GreedyAllocator {
13851409
Point end = activeEnds[tmp];
13861410
if (!end) [[unlikely]]
13871411
end = point + 1; // Dead def / clobber
1388-
m_map[tmp].liveRange.prepend({ point, end });
1412+
m_map[tmp].liveRange.prependDescending({ point, end });
13891413
activeEnds[tmp] = 0;
13901414
};
13911415

@@ -1554,7 +1578,11 @@ class GreedyAllocator {
15541578
m_code.pinnedRegisters().forEachReg([&](Reg reg) {
15551579
Tmp tmp = Tmp(reg);
15561580
ASSERT(activeEnds[tmp] == funcEndPoint + 1 && !m_map[tmp].liveRange.size());
1557-
m_map[tmp].liveRange.prepend({ 0, activeEnds[tmp] });
1581+
m_map[tmp].liveRange.prependDescending({ 0, activeEnds[tmp] });
1582+
});
1583+
1584+
m_map.forEachValue([](TmpData& data) {
1585+
data.liveRange.finishDescendingBuild();
15581586
});
15591587

15601588
#if ASSERT_ENABLED
@@ -2216,7 +2244,7 @@ class GreedyAllocator {
22162244
m_map.append(tmp, TmpData());
22172245
TmpData& tmpData = m_map[tmp];
22182246
if (interval)
2219-
tmpData.liveRange.prepend(interval);
2247+
tmpData.liveRange.append(interval);
22202248
tmpData.useDefCost = useDefCost;
22212249
tmpData.validate();
22222250
return tmp;

‎Source/JavaScriptCore/b3/air/AirTmpMap.h‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,14 @@ class TmpMap {
9797
m_fp.append(tmp, std::forward<PassedValue>(value));
9898
}
9999

100+
void forEachValue(NOESCAPE const Invocable<void(Value&)> auto& func)
101+
{
102+
for (size_t i = 0; i < m_gp.size(); ++i)
103+
func(m_gp[i]);
104+
for (size_t i = 0; i < m_fp.size(); ++i)
105+
func(m_fp[i]);
106+
}
107+
100108
private:
101109
IndexMap<Tmp::AbsolutelyIndexed<GP>, Value> m_gp;
102110
IndexMap<Tmp::AbsolutelyIndexed<FP>, Value> m_fp;

0 commit comments

Comments
 (0)