blob: 4c58c9c5e784f85d9828159fbf0bdd4713cc9aba [file] [log] [blame]
/*
* Copyright (C) 2011, 2013-2016 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
#if ENABLE(DFG_JIT)
#include "DFGAbstractValue.h"
#include "DFGAvailabilityMap.h"
#include "DFGBranchDirection.h"
#include "DFGNode.h"
#include "DFGNodeAbstractValuePair.h"
#include "DFGStructureClobberState.h"
#include "Operands.h"
#include <wtf/Vector.h>
namespace JSC { namespace DFG {
class Graph;
class InsertionSet;
typedef Vector<BasicBlock*, 2> PredecessorList;
typedef Vector<Node*, 8> BlockNodeList;
struct BasicBlock : RefCounted<BasicBlock> {
BasicBlock(
unsigned bytecodeBegin, unsigned numArguments, unsigned numLocals,
float executionCount);
~BasicBlock();
void ensureLocals(unsigned newNumLocals);
size_t size() const { return m_nodes.size(); }
bool isEmpty() const { return !size(); }
Node*& at(size_t i) { return m_nodes[i]; }
Node* at(size_t i) const { return m_nodes[i]; }
Node* tryAt(size_t i) const
{
if (i >= size())
return nullptr;
return at(i);
}
Node*& operator[](size_t i) { return at(i); }
Node* operator[](size_t i) const { return at(i); }
Node* last() const
{
RELEASE_ASSERT(!!size());
return at(size() - 1);
}
// Use this to find both the index of the terminal and the terminal itself in one go. May
// return a clear NodeAndIndex if the basic block currently lacks a terminal. That may happen
// in the middle of IR transformations within a phase but should never be the case in between
// phases.
//
// The reason why this is more than just "at(size() - 1)" is that we may place non-terminal
// liveness marking instructions after the terminal. This is supposed to happen infrequently
// but some basic blocks - most notably return blocks - will have liveness markers for all of
// the flushed variables right after the return.
//
// It turns out that doing this linear search is basically perf-neutral, so long as we force
// the method to be inlined. Hence the ALWAYS_INLINE.
ALWAYS_INLINE NodeAndIndex findTerminal() const
{
size_t i = size();
while (i--) {
Node* node = at(i);
if (node->isTerminal())
return NodeAndIndex(node, i);
switch (node->op()) {
// The bitter end can contain Phantoms and the like. There will probably only be one or two nodes after the terminal. They are all no-ops and will not have any checked children.
case Check: // This is here because it's our universal no-op.
case CheckVarargs:
case Phantom:
case PhantomLocal:
case Flush:
break;
default:
return NodeAndIndex();
}
}
return NodeAndIndex();
}
ALWAYS_INLINE Node* terminal() const
{
return findTerminal().node;
}
void resize(size_t size) { m_nodes.resize(size); }
void grow(size_t size) { m_nodes.grow(size); }
void append(Node* node) { m_nodes.append(node); }
void insertBeforeTerminal(Node* node)
{
NodeAndIndex result = findTerminal();
if (!result)
append(node);
else
m_nodes.insert(result.index, node);
}
void replaceTerminal(Graph&, Node*);
size_t numNodes() const { return phis.size() + size(); }
Node* node(size_t i) const
{
if (i < phis.size())
return phis[i];
return at(i - phis.size());
}
bool isPhiIndex(size_t i) const { return i < phis.size(); }
bool isInPhis(Node* node) const;
bool isInBlock(Node* myNode) const;
BlockNodeList::iterator begin() { return m_nodes.begin(); }
BlockNodeList::iterator end() { return m_nodes.end(); }
unsigned numSuccessors() { return terminal()->numSuccessors(); }
BasicBlock*& successor(unsigned index)
{
return terminal()->successor(index);
}
BasicBlock*& successorForCondition(bool condition)
{
return terminal()->successorForCondition(condition);
}
Node::SuccessorsIterable successors()
{
return terminal()->successors();
}
void removePredecessor(BasicBlock* block);
void replacePredecessor(BasicBlock* from, BasicBlock* to);
template<typename... Params>
Node* appendNode(Graph&, SpeculatedType, Params...);
template<typename... Params>
Node* appendNonTerminal(Graph&, SpeculatedType, Params...);
template<typename... Params>
Node* replaceTerminal(Graph&, SpeculatedType, Params...);
void dump(PrintStream& out) const;
void didLink()
{
#if !ASSERT_DISABLED
isLinked = true;
#endif
}
// This value is used internally for block linking and OSR entry. It is mostly meaningless
// for other purposes due to inlining.
unsigned bytecodeBegin;
BlockIndex index;
StructureClobberState cfaStructureClobberStateAtHead;
StructureClobberState cfaStructureClobberStateAtTail;
BranchDirection cfaBranchDirection;
bool cfaHasVisited;
bool cfaShouldRevisit;
bool cfaFoundConstants;
bool cfaDidFinish;
bool intersectionOfCFAHasVisited;
bool isOSRTarget;
bool isCatchEntrypoint;
#if !ASSERT_DISABLED
bool isLinked;
#endif
bool isReachable;
Vector<Node*> phis;
PredecessorList predecessors;
Operands<Node*> variablesAtHead;
Operands<Node*> variablesAtTail;
Operands<AbstractValue> valuesAtHead;
Operands<AbstractValue> valuesAtTail;
// The intersection of assumptions we have made previously at the head of this block. Note
// that under normal circumstances, each time we run the CFA, we will get strictly more precise
// results. But we don't actually require this to be the case. It's fine for the CFA to loosen
// up for any odd reason. It's fine when this happens, because anything that the CFA proves
// must be true from that point forward, except if some registered watchpoint fires, in which
// case the code won't ever run. So, the CFA proving something less precise later on is just an
// outcome of the CFA being imperfect; the more precise thing that it had proved earlier is no
// less true.
//
// But for the purpose of OSR entry, we need to make sure that we remember what assumptions we
// had used for optimizing any given basic block. That's what this is for.
//
// It's interesting that we could use this to make the CFA more precise: all future CFAs could
// filter their results with this thing to sort of maintain maximal precision. Because we
// expect CFA to usually be monotonically more precise each time we run it to fixpoint, this
// would not be a productive optimization: it would make setting up a basic block more
// expensive and would only benefit bizarre pathological cases.
Operands<AbstractValue> intersectionOfPastValuesAtHead;
float executionCount;
struct SSAData {
WTF_MAKE_FAST_ALLOCATED;
public:
void invalidate()
{
liveAtTail.clear();
liveAtHead.clear();
valuesAtHead.clear();
valuesAtTail.clear();
}
AvailabilityMap availabilityAtHead;
AvailabilityMap availabilityAtTail;
Vector<NodeFlowProjection> liveAtHead;
Vector<NodeFlowProjection> liveAtTail;
Vector<NodeAbstractValuePair> valuesAtHead;
Vector<NodeAbstractValuePair> valuesAtTail;
SSAData(BasicBlock*);
~SSAData();
};
std::unique_ptr<SSAData> ssa;
private:
friend class InsertionSet;
BlockNodeList m_nodes;
};
typedef Vector<BasicBlock*> BlockList;
static inline unsigned getBytecodeBeginForBlock(BasicBlock** basicBlock)
{
return (*basicBlock)->bytecodeBegin;
}
static inline BasicBlock* blockForBytecodeOffset(Vector<BasicBlock*>& linkingTargets, unsigned bytecodeBegin)
{
return *binarySearch<BasicBlock*, unsigned>(linkingTargets, linkingTargets.size(), bytecodeBegin, getBytecodeBeginForBlock);
}
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)