#ifndef AirLiveness_h
#define AirLiveness_h
#if ENABLE(B3_JIT)
#include "AirBasicBlock.h"
#include "AirCode.h"
#include "AirInstInlines.h"
#include "AirStackSlot.h"
#include "AirTmpInlines.h"
#include "B3IndexMap.h"
#include "B3IndexSet.h"
#include <wtf/IndexSparseSet.h>
#include <wtf/ListDump.h>
namespace JSC { namespace B3 { namespace Air {
template<Arg::Type adapterType>
struct TmpLivenessAdapter {
typedef Tmp Thing;
typedef HashSet<unsigned> IndexSet;
TmpLivenessAdapter(Code&) { }
static unsigned maxIndex(Code& code)
{
unsigned numTmps = code.numTmps(adapterType);
return AbsoluteTmpMapper<adapterType>::absoluteIndex(numTmps);
}
static bool acceptsType(Arg::Type type) { return type == adapterType; }
static unsigned valueToIndex(Tmp tmp) { return AbsoluteTmpMapper<adapterType>::absoluteIndex(tmp); }
static Tmp indexToValue(unsigned index) { return AbsoluteTmpMapper<adapterType>::tmpFromAbsoluteIndex(index); }
};
struct StackSlotLivenessAdapter {
typedef StackSlot* Thing;
typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> IndexSet;
StackSlotLivenessAdapter(Code& code)
: m_code(code)
{
}
static unsigned maxIndex(Code& code)
{
return code.stackSlots().size() - 1;
}
static bool acceptsType(Arg::Type) { return true; }
static unsigned valueToIndex(StackSlot* stackSlot) { return stackSlot->index(); }
StackSlot* indexToValue(unsigned index) { return m_code.stackSlots()[index]; }
private:
Code& m_code;
};
struct RegLivenessAdapter {
typedef Reg Thing;
typedef BitVector IndexSet;
RegLivenessAdapter(Code&) { }
static unsigned maxIndex(Code&)
{
return Reg::maxIndex();
}
static bool acceptsType(Arg::Type) { return true; }
static unsigned valueToIndex(Reg reg) { return reg.index(); }
Reg indexToValue(unsigned index) { return Reg::fromIndex(index); }
};
template<typename Adapter>
class AbstractLiveness : public Adapter {
struct Workset;
public:
typedef typename Adapter::Thing Thing;
AbstractLiveness(Code& code)
: Adapter(code)
, m_workset(Adapter::maxIndex(code))
, m_liveAtHead(code.size())
, m_liveAtTail(code.size())
{
for (BasicBlock* block : code) {
typename Adapter::IndexSet& liveAtTail = m_liveAtTail[block];
block->last().forEach<typename Adapter::Thing>(
[&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
if (Arg::isLateUse(role) && Adapter::acceptsType(type))
liveAtTail.add(Adapter::valueToIndex(thing));
});
}
BitVector dirtyBlocks;
for (size_t blockIndex = 0; blockIndex < code.size(); ++blockIndex)
dirtyBlocks.set(blockIndex);
bool changed;
do {
changed = false;
for (size_t blockIndex = code.size(); blockIndex--;) {
BasicBlock* block = code.at(blockIndex);
if (!block)
continue;
if (!dirtyBlocks.quickClear(blockIndex))
continue;
LocalCalc localCalc(*this, block);
for (size_t instIndex = block->size(); instIndex--;)
localCalc.execute(instIndex);
block->at(0).forEach<typename Adapter::Thing>(
[&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
if (Arg::isEarlyDef(role) && Adapter::acceptsType(type))
m_workset.remove(Adapter::valueToIndex(thing));
});
Vector<unsigned>& liveAtHead = m_liveAtHead[block];
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);
for (BasicBlock* predecessor : block->predecessors()) {
typename Adapter::IndexSet& liveAtTail = m_liveAtTail[predecessor];
for (unsigned newValue : m_workset) {
if (liveAtTail.add(newValue)) {
if (!dirtyBlocks.quickSet(predecessor->index()))
changed = true;
}
}
}
}
} while (changed);
}
class LocalCalc {
public:
LocalCalc(AbstractLiveness& liveness, BasicBlock* block)
: m_liveness(liveness)
, m_block(block)
{
auto& workset = liveness.m_workset;
workset.clear();
typename Adapter::IndexSet& liveAtTail = liveness.m_liveAtTail[block];
for (unsigned index : liveAtTail)
workset.add(index);
}
struct Iterator {
Iterator(Adapter& adapter, IndexSparseSet<UnsafeVectorOverflow>::const_iterator sparceSetIterator)
: 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;
IndexSparseSet<UnsafeVectorOverflow>::const_iterator m_sparceSetIterator;
};
struct Iterable {
Iterable(AbstractLiveness& liveness)
: m_liveness(liveness)
{
}
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
{
return m_liveness.m_workset.contains(Adapter::valueToIndex(thing));
}
private:
AbstractLiveness& 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)
{
Inst& inst = m_block->at(instIndex);
auto& workset = m_liveness.m_workset;
if (instIndex + 1 < m_block->size()) {
Inst& nextInst = m_block->at(instIndex + 1);
nextInst.forEach<typename Adapter::Thing>(
[&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
if (Arg::isEarlyDef(role) && Adapter::acceptsType(type))
workset.remove(Adapter::valueToIndex(thing));
});
}
inst.forEach<typename Adapter::Thing>(
[&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
if (Arg::isLateDef(role) && Adapter::acceptsType(type))
workset.remove(Adapter::valueToIndex(thing));
});
inst.forEach<typename Adapter::Thing>(
[&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
if (Arg::isEarlyUse(role) && Adapter::acceptsType(type))
workset.add(Adapter::valueToIndex(thing));
});
if (instIndex) {
Inst& prevInst = m_block->at(instIndex - 1);
prevInst.forEach<typename Adapter::Thing>(
[&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
if (Arg::isLateUse(role) && Adapter::acceptsType(type))
workset.add(Adapter::valueToIndex(thing));
});
}
}
private:
AbstractLiveness& m_liveness;
BasicBlock* m_block;
};
const Vector<unsigned>& rawLiveAtHead(BasicBlock* block)
{
return m_liveAtHead[block];
}
template<typename UnderlyingIterable>
class Iterable {
public:
Iterable(AbstractLiveness& liveness, const UnderlyingIterable& iterable)
: m_liveness(liveness)
, m_iterable(iterable)
{
}
class iterator {
public:
iterator()
: m_liveness(nullptr)
, m_iter()
{
}
iterator(AbstractLiveness& 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:
AbstractLiveness* 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
{
return m_liveness.m_workset.contains(Adapter::valueToIndex(thing));
}
private:
AbstractLiveness& m_liveness;
const UnderlyingIterable& m_iterable;
};
Iterable<Vector<unsigned>> liveAtHead(BasicBlock* block)
{
return Iterable<Vector<unsigned>>(*this, m_liveAtHead[block]);
}
Iterable<typename Adapter::IndexSet> liveAtTail(BasicBlock* block)
{
return Iterable<typename Adapter::IndexSet>(*this, m_liveAtTail[block]);
}
IndexSparseSet<UnsafeVectorOverflow>& workset() { return m_workset; }
private:
friend class LocalCalc;
friend struct LocalCalc::Iterable;
IndexSparseSet<UnsafeVectorOverflow> m_workset;
IndexMap<BasicBlock, Vector<unsigned>> m_liveAtHead;
IndexMap<BasicBlock, typename Adapter::IndexSet> m_liveAtTail;
};
template<Arg::Type type>
using TmpLiveness = AbstractLiveness<TmpLivenessAdapter<type>>;
typedef AbstractLiveness<TmpLivenessAdapter<Arg::GP>> GPLiveness;
typedef AbstractLiveness<TmpLivenessAdapter<Arg::FP>> FPLiveness;
typedef AbstractLiveness<StackSlotLivenessAdapter> StackSlotLiveness;
typedef AbstractLiveness<RegLivenessAdapter> RegLiveness;
} } }
#endif // ENABLE(B3_JIT)
#endif // AirLiveness_h