2017-03-27 04:17:52 +00:00
|
|
|
/*
|
|
|
|
* Copyright (C) 2015-2017 Apple Inc. All rights reserved.
|
|
|
|
*
|
|
|
|
* Redistribution and use in source and binary forms, with or without
|
|
|
|
* modification, are permitted provided that the following conditions
|
|
|
|
* are met:
|
|
|
|
* 1. Redistributions of source code must retain the above copyright
|
|
|
|
* notice, this list of conditions and the following disclaimer.
|
|
|
|
* 2. Redistributions in binary form must reproduce the above copyright
|
|
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
|
|
* documentation and/or other materials provided with the distribution.
|
|
|
|
*
|
|
|
|
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
|
|
|
|
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
|
|
|
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
|
|
|
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
|
|
|
|
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
|
|
|
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
|
|
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
|
|
|
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
|
|
|
|
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
|
|
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
|
|
|
|
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
|
|
*/
|
|
|
|
|
|
|
|
#pragma once
|
|
|
|
|
|
|
|
#include <wtf/BitVector.h>
|
|
|
|
#include <wtf/IndexSparseSet.h>
|
|
|
|
#include <wtf/StdLibExtras.h>
|
|
|
|
|
|
|
|
namespace WTF {
|
|
|
|
|
|
|
|
// HEADS UP: The algorithm here is duplicated in AirRegLiveness.h. That one uses sets rather
|
|
|
|
// than fancy vectors, because that's better for register liveness analysis.
|
|
|
|
template<typename Adapter>
|
|
|
|
class Liveness : public Adapter {
|
|
|
|
public:
|
|
|
|
typedef typename Adapter::CFG CFG;
|
|
|
|
typedef typename Adapter::Thing Thing;
|
|
|
|
typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
|
2017-04-05 00:25:02 +00:00
|
|
|
typedef IndexSparseSet<unsigned, DefaultIndexSparseSetTraits<unsigned>, UnsafeVectorOverflow> Workset;
|
2017-03-27 04:17:52 +00:00
|
|
|
|
|
|
|
template<typename... Arguments>
|
|
|
|
Liveness(CFG& cfg, Arguments&&... arguments)
|
|
|
|
: Adapter(std::forward<Arguments>(arguments)...)
|
|
|
|
, m_cfg(cfg)
|
|
|
|
, m_workset(Adapter::numIndices())
|
|
|
|
, m_liveAtHead(cfg.template newMap<IndexVector>())
|
|
|
|
, m_liveAtTail(cfg.template newMap<IndexVector>())
|
|
|
|
{
|
|
|
|
}
|
Don't need to Air::reportUsedRegisters for wasm at -O1
https://bugs.webkit.org/show_bug.cgi?id=170459
Reviewed by Saam Barati.
Source/JavaScriptCore:
I did some refactorings to Liveness<> to try to understand its performance. Based on
this I concluded that the bigger immediate issue is just removing unnecessary phases
from -O1.
This removes Air::reportUsedRegisters() from -O1 if the user has indicated that he is
not interested in StackmapGenerationParams::usedRegisters(). The logic here is a bit
weird because of how Air does spill code generation. The register allocator's spiller
will emit spill code using identifiable spill slots, which allows subsequent phases to
register-allocate the spill slots. We do this by a forward flow CSE phase called
fixObviousSpills (which is a terrible name since there is no longer anything obvious
about some of the spills that this phase can fix!). As is most natural for CSEs over
3AC, it rewires the uses of redundant computations rather than removing the redundant
computations. This means that if a spill got "fixed", there may be either or both of
the following:
- Dead loads from the stack.
- Dead stores to the stack.
We know that a load from the stack is dead if the register is dead at the point of the
load. We know that a store to the stack is dead if the spill slot is dead at the point
of the store.
Unfortunately, liveness analysis - over either registers or spill slots - is expensive.
Fortunately, allocateStack() already does liveness analysis over spill slots. So, we
baked elimination of stores to the stack into that phase. That aspect of clean-up after
the spill CSE comes for free.
Also fortunately for the FTL, we have to do reportUsedRegisters() anyway. This is a
phase that enables StackmapGenerationParams::usedRegisters() to work, which then
enables the FTL's patchpoints to do crazy slow-path live range splitting. So, Air's
strategy for the load fix-up after spill CSE is to do it as part of
reportUsedRegisters().
This patch introduces the Procedure::setNeedsUsedRegisters() API. But if you set
needsUsedRegisters to false then we will still run reportUsedRegisters() at -O2 as an
optimization - it removes dead loads from the stack that are left behind from
fixObviousSpills().
This is a ~6% compile time progression at -O1.
* b3/B3Procedure.h:
(JSC::B3::Procedure::setNeedsUsedRegisters):
(JSC::B3::Procedure::needsUsedRegisters):
* b3/B3StackmapGenerationParams.h:
* b3/B3VariableLiveness.cpp:
(JSC::B3::VariableLiveness::VariableLiveness):
* b3/air/AirCode.cpp:
(JSC::B3::Air::Code::needsUsedRegisters):
* b3/air/AirCode.h:
* b3/air/AirGenerate.cpp:
(JSC::B3::Air::prepareForGeneration):
* b3/air/AirLiveness.h:
(JSC::B3::Air::Liveness::Liveness):
* wasm/WasmB3IRGenerator.cpp:
(JSC::Wasm::parseAndCompile):
Source/WTF:
Just moved the liveness computation into a method, which enabled me to do the profiling
that I used to write this patch.
* wtf/Liveness.h:
(WTF::Liveness::Liveness):
(WTF::Liveness::compute):
Canonical link: https://commits.webkit.org/187373@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@214887 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2017-04-04 19:09:03 +00:00
|
|
|
|
2017-03-27 04:17:52 +00:00
|
|
|
// This calculator has to be run in reverse.
|
|
|
|
class LocalCalc {
|
2019-08-12 20:57:15 +00:00
|
|
|
WTF_MAKE_FAST_ALLOCATED;
|
2017-03-27 04:17:52 +00:00
|
|
|
public:
|
|
|
|
LocalCalc(Liveness& liveness, typename CFG::Node block)
|
|
|
|
: m_liveness(liveness)
|
|
|
|
, m_block(block)
|
|
|
|
{
|
|
|
|
auto& workset = liveness.m_workset;
|
|
|
|
workset.clear();
|
|
|
|
IndexVector& liveAtTail = liveness.m_liveAtTail[block];
|
|
|
|
for (unsigned index : liveAtTail)
|
|
|
|
workset.add(index);
|
|
|
|
}
|
|
|
|
|
|
|
|
class Iterable {
|
2019-08-12 20:57:15 +00:00
|
|
|
WTF_MAKE_FAST_ALLOCATED;
|
2017-03-27 04:17:52 +00:00
|
|
|
public:
|
|
|
|
Iterable(Liveness& liveness)
|
|
|
|
: m_liveness(liveness)
|
|
|
|
{
|
|
|
|
}
|
|
|
|
|
|
|
|
class iterator {
|
2019-08-12 20:57:15 +00:00
|
|
|
WTF_MAKE_FAST_ALLOCATED;
|
2017-03-27 04:17:52 +00:00
|
|
|
public:
|
2017-04-05 00:25:02 +00:00
|
|
|
iterator(Adapter& adapter, Workset::const_iterator sparceSetIterator)
|
2017-03-27 04:17:52 +00:00
|
|
|
: m_adapter(adapter)
|
|
|
|
, m_sparceSetIterator(sparceSetIterator)
|
|
|
|
{
|
|
|
|
}
|
|
|
|
|
|
|
|
iterator& operator++()
|
|
|
|
{
|
|
|
|
++m_sparceSetIterator;
|
|
|
|
return *this;
|
|
|
|
}
|
|
|
|
|
|
|
|
typename Adapter::Thing operator*() const
|
|
|
|
{
|
|
|
|
return m_adapter.indexToValue(*m_sparceSetIterator);
|
|
|
|
}
|
|
|
|
|
|
|
|
bool operator==(const iterator& other) { return m_sparceSetIterator == other.m_sparceSetIterator; }
|
|
|
|
bool operator!=(const iterator& other) { return m_sparceSetIterator != other.m_sparceSetIterator; }
|
|
|
|
|
|
|
|
private:
|
|
|
|
Adapter& m_adapter;
|
2017-04-05 00:25:02 +00:00
|
|
|
Workset::const_iterator m_sparceSetIterator;
|
2017-03-27 04:17:52 +00:00
|
|
|
};
|
|
|
|
|
|
|
|
iterator begin() const { return iterator(m_liveness, m_liveness.m_workset.begin()); }
|
|
|
|
iterator end() const { return iterator(m_liveness, m_liveness.m_workset.end()); }
|
|
|
|
|
|
|
|
bool contains(const typename Adapter::Thing& thing) const
|
|
|
|
{
|
2017-04-07 00:11:16 +00:00
|
|
|
return m_liveness.m_workset.contains(m_liveness.valueToIndex(thing));
|
2017-03-27 04:17:52 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
private:
|
|
|
|
Liveness& m_liveness;
|
|
|
|
};
|
|
|
|
|
|
|
|
Iterable live() const
|
|
|
|
{
|
|
|
|
return Iterable(m_liveness);
|
|
|
|
}
|
|
|
|
|
|
|
|
bool isLive(const typename Adapter::Thing& thing) const
|
|
|
|
{
|
|
|
|
return live().contains(thing);
|
|
|
|
}
|
|
|
|
|
|
|
|
void execute(unsigned instIndex)
|
|
|
|
{
|
|
|
|
auto& workset = m_liveness.m_workset;
|
|
|
|
|
2017-04-03 20:50:33 +00:00
|
|
|
// Want an easy example to help you visualize how this works?
|
|
|
|
// Check out B3VariableLiveness.h.
|
|
|
|
//
|
|
|
|
// Want a hard example to help you understand the hard cases?
|
|
|
|
// Check out AirLiveness.h.
|
|
|
|
|
|
|
|
m_liveness.forEachDef(
|
2017-03-27 04:17:52 +00:00
|
|
|
m_block, instIndex + 1,
|
|
|
|
[&] (unsigned index) {
|
|
|
|
workset.remove(index);
|
|
|
|
});
|
|
|
|
|
2017-04-03 20:50:33 +00:00
|
|
|
m_liveness.forEachUse(
|
2017-03-27 04:17:52 +00:00
|
|
|
m_block, instIndex,
|
|
|
|
[&] (unsigned index) {
|
|
|
|
workset.add(index);
|
|
|
|
});
|
|
|
|
}
|
|
|
|
|
|
|
|
private:
|
|
|
|
Liveness& m_liveness;
|
|
|
|
typename CFG::Node m_block;
|
|
|
|
};
|
|
|
|
|
|
|
|
const IndexVector& rawLiveAtHead(typename CFG::Node block)
|
|
|
|
{
|
|
|
|
return m_liveAtHead[block];
|
|
|
|
}
|
|
|
|
|
|
|
|
template<typename UnderlyingIterable>
|
|
|
|
class Iterable {
|
2019-08-12 20:57:15 +00:00
|
|
|
WTF_MAKE_FAST_ALLOCATED;
|
2017-03-27 04:17:52 +00:00
|
|
|
public:
|
|
|
|
Iterable(Liveness& liveness, const UnderlyingIterable& iterable)
|
|
|
|
: m_liveness(liveness)
|
|
|
|
, m_iterable(iterable)
|
|
|
|
{
|
|
|
|
}
|
|
|
|
|
|
|
|
class iterator {
|
2019-08-12 20:57:15 +00:00
|
|
|
WTF_MAKE_FAST_ALLOCATED;
|
2017-03-27 04:17:52 +00:00
|
|
|
public:
|
|
|
|
iterator()
|
|
|
|
: m_liveness(nullptr)
|
|
|
|
, m_iter()
|
|
|
|
{
|
|
|
|
}
|
|
|
|
|
|
|
|
iterator(Liveness& liveness, typename UnderlyingIterable::const_iterator iter)
|
|
|
|
: m_liveness(&liveness)
|
|
|
|
, m_iter(iter)
|
|
|
|
{
|
|
|
|
}
|
|
|
|
|
|
|
|
typename Adapter::Thing operator*()
|
|
|
|
{
|
|
|
|
return m_liveness->indexToValue(*m_iter);
|
|
|
|
}
|
|
|
|
|
|
|
|
iterator& operator++()
|
|
|
|
{
|
|
|
|
++m_iter;
|
|
|
|
return *this;
|
|
|
|
}
|
|
|
|
|
|
|
|
bool operator==(const iterator& other) const
|
|
|
|
{
|
|
|
|
ASSERT(m_liveness == other.m_liveness);
|
|
|
|
return m_iter == other.m_iter;
|
|
|
|
}
|
|
|
|
|
|
|
|
bool operator!=(const iterator& other) const
|
|
|
|
{
|
|
|
|
return !(*this == other);
|
|
|
|
}
|
|
|
|
|
|
|
|
private:
|
|
|
|
Liveness* m_liveness;
|
|
|
|
typename UnderlyingIterable::const_iterator m_iter;
|
|
|
|
};
|
|
|
|
|
|
|
|
iterator begin() const { return iterator(m_liveness, m_iterable.begin()); }
|
|
|
|
iterator end() const { return iterator(m_liveness, m_iterable.end()); }
|
|
|
|
|
|
|
|
bool contains(const typename Adapter::Thing& thing) const
|
|
|
|
{
|
2017-04-07 00:11:16 +00:00
|
|
|
return m_liveness.m_workset.contains(m_liveness.valueToIndex(thing));
|
2017-03-27 04:17:52 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
private:
|
|
|
|
Liveness& m_liveness;
|
|
|
|
const UnderlyingIterable& m_iterable;
|
|
|
|
};
|
|
|
|
|
|
|
|
Iterable<IndexVector> liveAtHead(typename CFG::Node block)
|
|
|
|
{
|
|
|
|
return Iterable<IndexVector>(*this, m_liveAtHead[block]);
|
|
|
|
}
|
|
|
|
|
|
|
|
Iterable<IndexVector> liveAtTail(typename CFG::Node block)
|
|
|
|
{
|
|
|
|
return Iterable<IndexVector>(*this, m_liveAtTail[block]);
|
|
|
|
}
|
|
|
|
|
2017-04-05 00:25:02 +00:00
|
|
|
Workset& workset() { return m_workset; }
|
2017-03-27 04:17:52 +00:00
|
|
|
|
|
|
|
class LiveAtHead {
|
2019-08-12 20:57:15 +00:00
|
|
|
WTF_MAKE_FAST_ALLOCATED;
|
2017-03-27 04:17:52 +00:00
|
|
|
public:
|
|
|
|
LiveAtHead(Liveness& liveness)
|
|
|
|
: m_liveness(liveness)
|
|
|
|
{
|
|
|
|
for (unsigned blockIndex = m_liveness.m_cfg.numNodes(); blockIndex--;) {
|
|
|
|
typename CFG::Node block = m_liveness.m_cfg.node(blockIndex);
|
|
|
|
if (!block)
|
|
|
|
continue;
|
|
|
|
|
|
|
|
std::sort(m_liveness.m_liveAtHead[block].begin(), m_liveness.m_liveAtHead[block].end());
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
bool isLiveAtHead(typename CFG::Node block, const typename Adapter::Thing& thing)
|
|
|
|
{
|
|
|
|
return !!tryBinarySearch<unsigned>(m_liveness.m_liveAtHead[block], m_liveness.m_liveAtHead[block].size(), m_liveness.valueToIndex(thing), [] (unsigned* value) { return *value; });
|
|
|
|
}
|
|
|
|
|
|
|
|
private:
|
|
|
|
Liveness& m_liveness;
|
|
|
|
};
|
|
|
|
|
|
|
|
LiveAtHead liveAtHead() { return LiveAtHead(*this); }
|
|
|
|
|
Don't need to Air::reportUsedRegisters for wasm at -O1
https://bugs.webkit.org/show_bug.cgi?id=170459
Reviewed by Saam Barati.
Source/JavaScriptCore:
I did some refactorings to Liveness<> to try to understand its performance. Based on
this I concluded that the bigger immediate issue is just removing unnecessary phases
from -O1.
This removes Air::reportUsedRegisters() from -O1 if the user has indicated that he is
not interested in StackmapGenerationParams::usedRegisters(). The logic here is a bit
weird because of how Air does spill code generation. The register allocator's spiller
will emit spill code using identifiable spill slots, which allows subsequent phases to
register-allocate the spill slots. We do this by a forward flow CSE phase called
fixObviousSpills (which is a terrible name since there is no longer anything obvious
about some of the spills that this phase can fix!). As is most natural for CSEs over
3AC, it rewires the uses of redundant computations rather than removing the redundant
computations. This means that if a spill got "fixed", there may be either or both of
the following:
- Dead loads from the stack.
- Dead stores to the stack.
We know that a load from the stack is dead if the register is dead at the point of the
load. We know that a store to the stack is dead if the spill slot is dead at the point
of the store.
Unfortunately, liveness analysis - over either registers or spill slots - is expensive.
Fortunately, allocateStack() already does liveness analysis over spill slots. So, we
baked elimination of stores to the stack into that phase. That aspect of clean-up after
the spill CSE comes for free.
Also fortunately for the FTL, we have to do reportUsedRegisters() anyway. This is a
phase that enables StackmapGenerationParams::usedRegisters() to work, which then
enables the FTL's patchpoints to do crazy slow-path live range splitting. So, Air's
strategy for the load fix-up after spill CSE is to do it as part of
reportUsedRegisters().
This patch introduces the Procedure::setNeedsUsedRegisters() API. But if you set
needsUsedRegisters to false then we will still run reportUsedRegisters() at -O2 as an
optimization - it removes dead loads from the stack that are left behind from
fixObviousSpills().
This is a ~6% compile time progression at -O1.
* b3/B3Procedure.h:
(JSC::B3::Procedure::setNeedsUsedRegisters):
(JSC::B3::Procedure::needsUsedRegisters):
* b3/B3StackmapGenerationParams.h:
* b3/B3VariableLiveness.cpp:
(JSC::B3::VariableLiveness::VariableLiveness):
* b3/air/AirCode.cpp:
(JSC::B3::Air::Code::needsUsedRegisters):
* b3/air/AirCode.h:
* b3/air/AirGenerate.cpp:
(JSC::B3::Air::prepareForGeneration):
* b3/air/AirLiveness.h:
(JSC::B3::Air::Liveness::Liveness):
* wasm/WasmB3IRGenerator.cpp:
(JSC::Wasm::parseAndCompile):
Source/WTF:
Just moved the liveness computation into a method, which enabled me to do the profiling
that I used to write this patch.
* wtf/Liveness.h:
(WTF::Liveness::Liveness):
(WTF::Liveness::compute):
Canonical link: https://commits.webkit.org/187373@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@214887 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2017-04-04 19:09:03 +00:00
|
|
|
protected:
|
|
|
|
void compute()
|
|
|
|
{
|
2017-04-07 00:11:16 +00:00
|
|
|
Adapter::prepareToCompute();
|
|
|
|
|
Don't need to Air::reportUsedRegisters for wasm at -O1
https://bugs.webkit.org/show_bug.cgi?id=170459
Reviewed by Saam Barati.
Source/JavaScriptCore:
I did some refactorings to Liveness<> to try to understand its performance. Based on
this I concluded that the bigger immediate issue is just removing unnecessary phases
from -O1.
This removes Air::reportUsedRegisters() from -O1 if the user has indicated that he is
not interested in StackmapGenerationParams::usedRegisters(). The logic here is a bit
weird because of how Air does spill code generation. The register allocator's spiller
will emit spill code using identifiable spill slots, which allows subsequent phases to
register-allocate the spill slots. We do this by a forward flow CSE phase called
fixObviousSpills (which is a terrible name since there is no longer anything obvious
about some of the spills that this phase can fix!). As is most natural for CSEs over
3AC, it rewires the uses of redundant computations rather than removing the redundant
computations. This means that if a spill got "fixed", there may be either or both of
the following:
- Dead loads from the stack.
- Dead stores to the stack.
We know that a load from the stack is dead if the register is dead at the point of the
load. We know that a store to the stack is dead if the spill slot is dead at the point
of the store.
Unfortunately, liveness analysis - over either registers or spill slots - is expensive.
Fortunately, allocateStack() already does liveness analysis over spill slots. So, we
baked elimination of stores to the stack into that phase. That aspect of clean-up after
the spill CSE comes for free.
Also fortunately for the FTL, we have to do reportUsedRegisters() anyway. This is a
phase that enables StackmapGenerationParams::usedRegisters() to work, which then
enables the FTL's patchpoints to do crazy slow-path live range splitting. So, Air's
strategy for the load fix-up after spill CSE is to do it as part of
reportUsedRegisters().
This patch introduces the Procedure::setNeedsUsedRegisters() API. But if you set
needsUsedRegisters to false then we will still run reportUsedRegisters() at -O2 as an
optimization - it removes dead loads from the stack that are left behind from
fixObviousSpills().
This is a ~6% compile time progression at -O1.
* b3/B3Procedure.h:
(JSC::B3::Procedure::setNeedsUsedRegisters):
(JSC::B3::Procedure::needsUsedRegisters):
* b3/B3StackmapGenerationParams.h:
* b3/B3VariableLiveness.cpp:
(JSC::B3::VariableLiveness::VariableLiveness):
* b3/air/AirCode.cpp:
(JSC::B3::Air::Code::needsUsedRegisters):
* b3/air/AirCode.h:
* b3/air/AirGenerate.cpp:
(JSC::B3::Air::prepareForGeneration):
* b3/air/AirLiveness.h:
(JSC::B3::Air::Liveness::Liveness):
* wasm/WasmB3IRGenerator.cpp:
(JSC::Wasm::parseAndCompile):
Source/WTF:
Just moved the liveness computation into a method, which enabled me to do the profiling
that I used to write this patch.
* wtf/Liveness.h:
(WTF::Liveness::Liveness):
(WTF::Liveness::compute):
Canonical link: https://commits.webkit.org/187373@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@214887 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2017-04-04 19:09:03 +00:00
|
|
|
// The liveAtTail of each block automatically contains the LateUse's of the terminal.
|
|
|
|
for (unsigned blockIndex = m_cfg.numNodes(); blockIndex--;) {
|
|
|
|
typename CFG::Node block = m_cfg.node(blockIndex);
|
|
|
|
if (!block)
|
|
|
|
continue;
|
|
|
|
|
|
|
|
IndexVector& liveAtTail = m_liveAtTail[block];
|
|
|
|
|
|
|
|
Adapter::forEachUse(
|
|
|
|
block, Adapter::blockSize(block),
|
|
|
|
[&] (unsigned index) {
|
|
|
|
liveAtTail.append(index);
|
|
|
|
});
|
|
|
|
|
|
|
|
std::sort(liveAtTail.begin(), liveAtTail.end());
|
|
|
|
removeRepeatedElements(liveAtTail);
|
|
|
|
}
|
|
|
|
|
|
|
|
// Blocks with new live values at tail.
|
|
|
|
BitVector dirtyBlocks;
|
|
|
|
for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;)
|
|
|
|
dirtyBlocks.set(blockIndex);
|
|
|
|
|
|
|
|
IndexVector mergeBuffer;
|
|
|
|
|
|
|
|
bool changed;
|
|
|
|
do {
|
|
|
|
changed = false;
|
|
|
|
|
|
|
|
for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;) {
|
|
|
|
typename CFG::Node block = m_cfg.node(blockIndex);
|
|
|
|
if (!block)
|
|
|
|
continue;
|
|
|
|
|
|
|
|
if (!dirtyBlocks.quickClear(blockIndex))
|
|
|
|
continue;
|
|
|
|
|
|
|
|
LocalCalc localCalc(*this, block);
|
|
|
|
for (size_t instIndex = Adapter::blockSize(block); instIndex--;)
|
|
|
|
localCalc.execute(instIndex);
|
|
|
|
|
|
|
|
// Handle the early def's of the first instruction.
|
|
|
|
Adapter::forEachDef(
|
|
|
|
block, 0,
|
|
|
|
[&] (unsigned index) {
|
|
|
|
m_workset.remove(index);
|
|
|
|
});
|
|
|
|
|
|
|
|
IndexVector& liveAtHead = m_liveAtHead[block];
|
|
|
|
|
|
|
|
// We only care about Tmps that were discovered in this iteration. It is impossible
|
|
|
|
// to remove a live value from the head.
|
|
|
|
// We remove all the values we already knew about so that we only have to deal with
|
|
|
|
// what is new in LiveAtHead.
|
|
|
|
if (m_workset.size() == liveAtHead.size())
|
|
|
|
m_workset.clear();
|
|
|
|
else {
|
|
|
|
for (unsigned liveIndexAtHead : liveAtHead)
|
|
|
|
m_workset.remove(liveIndexAtHead);
|
|
|
|
}
|
|
|
|
|
|
|
|
if (m_workset.isEmpty())
|
|
|
|
continue;
|
|
|
|
|
|
|
|
liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
|
|
|
|
for (unsigned newValue : m_workset)
|
|
|
|
liveAtHead.uncheckedAppend(newValue);
|
|
|
|
|
|
|
|
m_workset.sort();
|
|
|
|
|
|
|
|
for (typename CFG::Node predecessor : m_cfg.predecessors(block)) {
|
|
|
|
IndexVector& liveAtTail = m_liveAtTail[predecessor];
|
|
|
|
|
|
|
|
if (liveAtTail.isEmpty())
|
|
|
|
liveAtTail = m_workset.values();
|
|
|
|
else {
|
|
|
|
mergeBuffer.resize(liveAtTail.size() + m_workset.size());
|
|
|
|
auto iter = mergeDeduplicatedSorted(
|
|
|
|
liveAtTail.begin(), liveAtTail.end(),
|
|
|
|
m_workset.begin(), m_workset.end(),
|
|
|
|
mergeBuffer.begin());
|
|
|
|
mergeBuffer.resize(iter - mergeBuffer.begin());
|
|
|
|
|
|
|
|
if (mergeBuffer.size() == liveAtTail.size())
|
|
|
|
continue;
|
|
|
|
|
|
|
|
RELEASE_ASSERT(mergeBuffer.size() > liveAtTail.size());
|
|
|
|
liveAtTail = mergeBuffer;
|
|
|
|
}
|
|
|
|
|
|
|
|
dirtyBlocks.quickSet(predecessor->index());
|
|
|
|
changed = true;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
} while (changed);
|
|
|
|
}
|
|
|
|
|
2017-03-27 04:17:52 +00:00
|
|
|
private:
|
|
|
|
friend class LocalCalc;
|
|
|
|
friend class LocalCalc::Iterable;
|
|
|
|
|
|
|
|
CFG& m_cfg;
|
2017-04-05 00:25:02 +00:00
|
|
|
Workset m_workset;
|
2017-03-27 04:17:52 +00:00
|
|
|
typename CFG::template Map<IndexVector> m_liveAtHead;
|
|
|
|
typename CFG::template Map<IndexVector> m_liveAtTail;
|
|
|
|
};
|
|
|
|
|
|
|
|
} // namespace WTF
|
|
|
|
|