blob: c2f8f9626b8ba35617368188bad4ed71b1b273d5 [file] [log] [blame]
/*
* 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;
typedef IndexSparseSet<unsigned, DefaultIndexSparseSetTraits<unsigned>, UnsafeVectorOverflow> Workset;
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>())
{
}
// This calculator has to be run in reverse.
class LocalCalc {
WTF_MAKE_FAST_ALLOCATED;
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 {
WTF_MAKE_FAST_ALLOCATED;
public:
Iterable(Liveness& liveness)
: m_liveness(liveness)
{
}
class iterator {
WTF_MAKE_FAST_ALLOCATED;
public:
iterator(Adapter& adapter, Workset::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) const { return m_sparceSetIterator == other.m_sparceSetIterator; }
bool operator!=(const iterator& other) const { return m_sparceSetIterator != other.m_sparceSetIterator; }
private:
Adapter& m_adapter;
Workset::const_iterator m_sparceSetIterator;
};
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(m_liveness.valueToIndex(thing));
}
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;
// 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(
m_block, instIndex + 1,
[&] (unsigned index) {
workset.remove(index);
});
m_liveness.forEachUse(
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 {
WTF_MAKE_FAST_ALLOCATED;
public:
Iterable(Liveness& liveness, const UnderlyingIterable& iterable)
: m_liveness(liveness)
, m_iterable(iterable)
{
}
class iterator {
WTF_MAKE_FAST_ALLOCATED;
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
{
return m_liveness.m_workset.contains(m_liveness.valueToIndex(thing));
}
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]);
}
Workset& workset() { return m_workset; }
class LiveAtHead {
WTF_MAKE_FAST_ALLOCATED;
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); }
protected:
void compute()
{
Adapter::prepareToCompute();
// 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);
}
private:
friend class LocalCalc;
friend class LocalCalc::Iterable;
CFG& m_cfg;
Workset m_workset;
typename CFG::template Map<IndexVector> m_liveAtHead;
typename CFG::template Map<IndexVector> m_liveAtTail;
};
} // namespace WTF