blob: 1a88066d124a68798960ad023f62e82e2f17af3d [file] [log] [blame]
/*
* Copyright (C) 2011 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.
*/
#include "config.h"
#include "DFGCFAPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGAbstractState.h"
#include "DFGGraph.h"
#include "DFGPhase.h"
namespace JSC { namespace DFG {
class CFAPhase : public Phase {
public:
CFAPhase(Graph& graph)
: Phase(graph, "control flow analysis")
, m_state(graph)
{
}
bool run()
{
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
m_count = 0;
#endif
// This implements a pseudo-worklist-based forward CFA, except that the visit order
// of blocks is the bytecode program order (which is nearly topological), and
// instead of a worklist we just walk all basic blocks checking if cfaShouldRevisit
// is set to true. This is likely to balance the efficiency properties of both
// worklist-based and forward fixpoint-based approaches. Like a worklist-based
// approach, it won't visit code if it's meaningless to do so (nothing changed at
// the head of the block or the predecessors have not been visited). Like a forward
// fixpoint-based approach, it has a high probability of only visiting a block
// after all predecessors have been visited. Only loops will cause this analysis to
// revisit blocks, and the amount of revisiting is proportional to loop depth.
AbstractState::initialize(m_graph);
do {
m_changed = false;
performForwardCFA();
} while (m_changed);
return true;
}
private:
void performBlockCFA(BlockIndex blockIndex)
{
BasicBlock* block = m_graph.m_blocks[blockIndex].get();
if (!block)
return;
if (!block->cfaShouldRevisit)
return;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLogF(" Block #%u (bc#%u):\n", blockIndex, block->bytecodeBegin);
#endif
m_state.beginBasicBlock(block);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLogF(" head vars: ");
dumpOperands(block->valuesAtHead, WTF::dataFile());
dataLogF("\n");
#endif
for (unsigned i = 0; i < block->size(); ++i) {
NodeIndex nodeIndex = block->at(i);
if (!m_graph[nodeIndex].shouldGenerate())
continue;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLogF(" %s @%u: ", Graph::opName(m_graph[nodeIndex].op()), nodeIndex);
m_state.dump(WTF::dataFile());
dataLogF("\n");
#endif
if (!m_state.execute(i)) {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLogF(" Expect OSR exit.\n");
#endif
break;
}
}
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLogF(" tail regs: ");
m_state.dump(WTF::dataFile());
dataLogF("\n");
#endif
m_changed |= m_state.endBasicBlock(AbstractState::MergeToSuccessors);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLogF(" tail vars: ");
dumpOperands(block->valuesAtTail, WTF::dataFile());
dataLogF("\n");
#endif
}
void performForwardCFA()
{
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
dataLogF("CFA [%u]\n", ++m_count);
#endif
for (BlockIndex block = 0; block < m_graph.m_blocks.size(); ++block)
performBlockCFA(block);
}
private:
AbstractState m_state;
bool m_changed;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
unsigned m_count;
#endif
};
bool performCFA(Graph& graph)
{
SamplingRegion samplingRegion("DFG CFA Phase");
return runPhase<CFAPhase>(graph);
}
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)