#include "config.h"
#include "DFGCSEPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGAbstractHeap.h"
#include "DFGBlockMapInlines.h"
#include "DFGClobberSet.h"
#include "DFGClobberize.h"
#include "DFGEdgeUsesStructure.h"
#include "DFGGraph.h"
#include "DFGPhase.h"
#include "JSCInlines.h"
#include <array>
#include <wtf/FastBitVector.h>
namespace JSC { namespace DFG {
namespace {
const bool verbose = false;
class ClobberFilter {
public:
ClobberFilter(AbstractHeap heap)
: m_heap(heap)
{
}
bool operator()(const ImpureMap::KeyValuePairType& pair) const
{
return m_heap.overlaps(pair.key.heap());
}
private:
AbstractHeap m_heap;
};
inline void clobber(ImpureMap& map, AbstractHeap heap)
{
ClobberFilter filter(heap);
map.removeIf(filter);
}
class LocalCSEPhase : public Phase {
public:
LocalCSEPhase(Graph& graph)
: Phase(graph, "local common subexpression elimination")
, m_smallBlock(graph)
, m_largeBlock(graph)
{
}
bool run()
{
ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == LoadStore);
bool changed = false;
m_graph.clearReplacements();
for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
if (block->size() <= SmallMaps::capacity)
changed |= m_smallBlock.run(block);
else
changed |= m_largeBlock.run(block);
}
return changed;
}
private:
class SmallMaps {
public:
static const unsigned capacity = 100;
SmallMaps()
: m_pureLength(0)
, m_impureLength(0)
{
}
void clear()
{
m_pureLength = 0;
m_impureLength = 0;
}
void write(AbstractHeap heap)
{
for (unsigned i = 0; i < m_impureLength; ++i) {
if (heap.overlaps(m_impureMap[i].key.heap()))
m_impureMap[i--] = m_impureMap[--m_impureLength];
}
}
Node* addPure(PureValue value, Node* node)
{
for (unsigned i = m_pureLength; i--;) {
if (m_pureMap[i].key == value)
return m_pureMap[i].value;
}
ASSERT(m_pureLength < capacity);
m_pureMap[m_pureLength++] = WTF::KeyValuePair<PureValue, Node*>(value, node);
return nullptr;
}
LazyNode findReplacement(HeapLocation location)
{
for (unsigned i = m_impureLength; i--;) {
if (m_impureMap[i].key == location)
return m_impureMap[i].value;
}
return nullptr;
}
LazyNode addImpure(HeapLocation location, LazyNode node)
{
if (location.index() && !location.index().isNode())
return nullptr;
if (LazyNode result = findReplacement(location))
return result;
ASSERT(m_impureLength < capacity);
m_impureMap[m_impureLength++] = WTF::KeyValuePair<HeapLocation, LazyNode>(location, node);
return nullptr;
}
private:
WTF::KeyValuePair<PureValue, Node*> m_pureMap[capacity];
WTF::KeyValuePair<HeapLocation, LazyNode> m_impureMap[capacity];
unsigned m_pureLength;
unsigned m_impureLength;
};
class LargeMaps {
public:
LargeMaps()
{
}
void clear()
{
m_pureMap.clear();
m_impureMap.clear();
}
void write(AbstractHeap heap)
{
clobber(m_impureMap, heap);
}
Node* addPure(PureValue value, Node* node)
{
auto result = m_pureMap.add(value, node);
if (result.isNewEntry)
return nullptr;
return result.iterator->value;
}
LazyNode findReplacement(HeapLocation location)
{
return m_impureMap.get(location);
}
LazyNode addImpure(HeapLocation location, LazyNode node)
{
auto result = m_impureMap.add(location, node);
if (result.isNewEntry)
return nullptr;
return result.iterator->value;
}
private:
HashMap<PureValue, Node*> m_pureMap;
HashMap<HeapLocation, LazyNode> m_impureMap;
};
template<typename Maps>
class BlockCSE {
public:
BlockCSE(Graph& graph)
: m_graph(graph)
, m_insertionSet(graph)
{
}
bool run(BasicBlock* block)
{
m_maps.clear();
m_changed = false;
m_block = block;
for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
m_node = block->at(nodeIndex);
m_graph.performSubstitution(m_node);
if (m_node->op() == Identity) {
m_node->replaceWith(m_node->child1().node());
m_changed = true;
} else {
if (m_node->op() == PutByVal || m_node->op() == PutByValDirect) {
HeapLocation heap;
Node* base = m_graph.varArgChild(m_node, 0).node();
Node* index = m_graph.varArgChild(m_node, 1).node();
ArrayMode mode = m_node->arrayMode();
switch (mode.type()) {
case Array::Int32:
if (!mode.isInBounds())
break;
heap = HeapLocation(
IndexedPropertyLoc, IndexedInt32Properties, base, index);
break;
case Array::Double:
if (!mode.isInBounds())
break;
heap = HeapLocation(
IndexedPropertyLoc, IndexedDoubleProperties, base, index);
break;
case Array::Contiguous:
if (!mode.isInBounds())
break;
heap = HeapLocation(
IndexedPropertyLoc, IndexedContiguousProperties, base, index);
break;
case Array::Int8Array:
case Array::Int16Array:
case Array::Int32Array:
case Array::Uint8Array:
case Array::Uint8ClampedArray:
case Array::Uint16Array:
case Array::Uint32Array:
case Array::Float32Array:
case Array::Float64Array:
if (!mode.isInBounds())
break;
heap = HeapLocation(
IndexedPropertyLoc, TypedArrayProperties, base, index);
break;
default:
break;
}
if (!!heap && m_maps.findReplacement(heap))
m_node->setOp(PutByValAlias);
}
clobberize(m_graph, m_node, *this);
}
}
m_insertionSet.execute(block);
return m_changed;
}
void read(AbstractHeap) { }
void write(AbstractHeap heap)
{
m_maps.write(heap);
}
void def(PureValue value)
{
Node* match = m_maps.addPure(value, m_node);
if (!match)
return;
m_node->replaceWith(match);
m_changed = true;
}
void def(HeapLocation location, LazyNode value)
{
LazyNode match = m_maps.addImpure(location, value);
if (!match)
return;
if (m_node->op() == GetLocal) {
m_node->child1() = Edge();
m_graph.dethread();
}
if (value.isNode() && value.asNode() == m_node) {
match.ensureIsNode(m_insertionSet, m_block, 0)->owner = m_block;
ASSERT(match.isNode());
m_node->replaceWith(match.asNode());
m_changed = true;
}
}
private:
Graph& m_graph;
bool m_changed;
Node* m_node;
BasicBlock* m_block;
Maps m_maps;
InsertionSet m_insertionSet;
};
BlockCSE<SmallMaps> m_smallBlock;
BlockCSE<LargeMaps> m_largeBlock;
};
class GlobalCSEPhase : public Phase {
public:
GlobalCSEPhase(Graph& graph)
: Phase(graph, "global common subexpression elimination")
, m_impureDataMap(graph)
, m_insertionSet(graph)
{
}
bool run()
{
ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
ASSERT(m_graph.m_form == SSA);
m_graph.initializeNodeOwners();
m_graph.m_dominators.computeIfNecessary(m_graph);
m_preOrder = m_graph.blocksInPreOrder();
for (unsigned i = m_preOrder.size(); i--;) {
m_block = m_preOrder[i];
m_impureData = &m_impureDataMap[m_block];
for (unsigned nodeIndex = m_block->size(); nodeIndex--;)
addWrites(m_graph, m_block->at(nodeIndex), m_impureData->writes);
}
bool changed = iterate();
return changed;
}
bool iterate()
{
if (verbose)
dataLog("Performing iteration.\n");
m_changed = false;
m_graph.clearReplacements();
for (unsigned i = 0; i < m_preOrder.size(); ++i) {
m_block = m_preOrder[i];
m_impureData = &m_impureDataMap[m_block];
m_writesSoFar.clear();
if (verbose)
dataLog("Processing block ", *m_block, ":\n");
for (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
m_nodeIndex = nodeIndex;
m_node = m_block->at(nodeIndex);
if (verbose)
dataLog(" Looking at node ", m_node, ":\n");
m_graph.performSubstitution(m_node);
if (m_node->op() == Identity) {
m_node->replaceWith(m_node->child1().node());
m_changed = true;
} else
clobberize(m_graph, m_node, *this);
}
m_insertionSet.execute(m_block);
m_impureData->didVisit = true;
}
return m_changed;
}
void read(AbstractHeap) { }
void write(AbstractHeap heap)
{
clobber(m_impureData->availableAtTail, heap);
m_writesSoFar.add(heap);
if (verbose)
dataLog(" Clobbered, new tail map: ", mapDump(m_impureData->availableAtTail), "\n");
}
void def(PureValue value)
{
auto result = m_pureValues.add(value, Vector<Node*>());
if (result.isNewEntry) {
result.iterator->value.append(m_node);
return;
}
for (unsigned i = result.iterator->value.size(); i--;) {
Node* candidate = result.iterator->value[i];
if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
m_node->replaceWith(candidate);
m_changed = true;
return;
}
}
result.iterator->value.append(m_node);
}
LazyNode findReplacement(HeapLocation location)
{
LazyNode match = m_impureData->availableAtTail.get(location);
if (!!match) {
if (verbose)
dataLog(" Found local match: ", match, "\n");
return match;
}
if (m_writesSoFar.overlaps(location.heap())) {
if (verbose)
dataLog(" Not looking globally because of local clobber: ", m_writesSoFar, "\n");
return nullptr;
}
Vector<BasicBlock*, 8> worklist;
Vector<BasicBlock*, 8> seenList;
BitVector seen;
for (unsigned i = m_block->predecessors.size(); i--;) {
BasicBlock* predecessor = m_block->predecessors[i];
if (!seen.get(predecessor->index)) {
worklist.append(predecessor);
seen.set(predecessor->index);
}
}
while (!worklist.isEmpty()) {
BasicBlock* block = worklist.takeLast();
seenList.append(block);
if (verbose)
dataLog(" Searching in block ", *block, "\n");
ImpureBlockData& data = m_impureDataMap[block];
if (m_graph.m_dominators.strictlyDominates(block, m_block)) {
if (verbose)
dataLog(" It strictly dominates.\n");
DFG_ASSERT(m_graph, m_node, data.didVisit);
DFG_ASSERT(m_graph, m_node, !match);
if (verbose)
dataLog(" Availability map: ", mapDump(data.availableAtTail), "\n");
match = data.availableAtTail.get(location);
if (verbose)
dataLog(" Availability: ", match, "\n");
if (!!match) {
continue;
}
}
if (verbose)
dataLog(" Dealing with write set ", data.writes, "\n");
if (data.writes.overlaps(location.heap())) {
if (verbose)
dataLog(" Clobbered.\n");
return nullptr;
}
for (unsigned i = block->predecessors.size(); i--;) {
BasicBlock* predecessor = block->predecessors[i];
if (!seen.get(predecessor->index)) {
worklist.append(predecessor);
seen.set(predecessor->index);
}
}
}
if (!match)
return nullptr;
for (BasicBlock* block : seenList)
m_impureDataMap[block].availableAtTail.add(location, match);
m_impureData->availableAtTail.add(location, match);
return match;
}
void def(HeapLocation location, LazyNode value)
{
if (verbose)
dataLog(" Got heap location def: ", location, " -> ", value, "\n");
LazyNode match = findReplacement(location);
if (verbose)
dataLog(" Got match: ", match, "\n");
if (!match) {
if (verbose)
dataLog(" Adding at-tail mapping: ", location, " -> ", value, "\n");
auto result = m_impureData->availableAtTail.add(location, value);
ASSERT_UNUSED(result, result.isNewEntry);
return;
}
if (value.isNode() && value.asNode() == m_node) {
if (!match.isNode()) {
match.ensureIsNode(m_insertionSet, m_block, m_nodeIndex)->owner = m_block;
auto result = m_pureValues.add(PureValue(match.asNode(), match->constant()), Vector<Node*>());
bool replaced = false;
if (!result.isNewEntry) {
for (unsigned i = result.iterator->value.size(); i--;) {
Node* candidate = result.iterator->value[i];
if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
ASSERT(candidate);
match->replaceWith(candidate);
match.setNode(candidate);
replaced = true;
break;
}
}
}
if (!replaced)
result.iterator->value.append(match.asNode());
}
ASSERT(match.asNode());
m_node->replaceWith(match.asNode());
m_changed = true;
}
}
struct ImpureBlockData {
ImpureBlockData()
: didVisit(false)
{
}
ClobberSet writes;
ImpureMap availableAtTail;
bool didVisit;
};
Vector<BasicBlock*> m_preOrder;
PureMultiMap m_pureValues;
BlockMap<ImpureBlockData> m_impureDataMap;
BasicBlock* m_block;
Node* m_node;
unsigned m_nodeIndex;
ImpureBlockData* m_impureData;
ClobberSet m_writesSoFar;
InsertionSet m_insertionSet;
bool m_changed;
};
}
bool performLocalCSE(Graph& graph)
{
SamplingRegion samplingRegion("DFG LocalCSE Phase");
return runPhase<LocalCSEPhase>(graph);
}
bool performGlobalCSE(Graph& graph)
{
SamplingRegion samplingRegion("DFG GlobalCSE Phase");
return runPhase<GlobalCSEPhase>(graph);
}
} }
#endif // ENABLE(DFG_JIT)