1/* 2 * Copyright (C) 2011, 2013 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#include "config.h" 27#include "DFGCFAPhase.h" 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGAbstractState.h" 32#include "DFGGraph.h" 33#include "DFGPhase.h" 34#include "Operations.h" 35 36namespace JSC { namespace DFG { 37 38class CFAPhase : public Phase { 39public: 40 CFAPhase(Graph& graph) 41 : Phase(graph, "control flow analysis") 42 , m_state(graph) 43 { 44 } 45 46 bool run() 47 { 48 ASSERT(m_graph.m_form == ThreadedCPS); 49 ASSERT(m_graph.m_unificationState == GloballyUnified); 50 ASSERT(m_graph.m_refCountState == EverythingIsLive); 51 52#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) 53 m_count = 0; 54#endif 55 56 // This implements a pseudo-worklist-based forward CFA, except that the visit order 57 // of blocks is the bytecode program order (which is nearly topological), and 58 // instead of a worklist we just walk all basic blocks checking if cfaShouldRevisit 59 // is set to true. This is likely to balance the efficiency properties of both 60 // worklist-based and forward fixpoint-based approaches. Like a worklist-based 61 // approach, it won't visit code if it's meaningless to do so (nothing changed at 62 // the head of the block or the predecessors have not been visited). Like a forward 63 // fixpoint-based approach, it has a high probability of only visiting a block 64 // after all predecessors have been visited. Only loops will cause this analysis to 65 // revisit blocks, and the amount of revisiting is proportional to loop depth. 66 67 AbstractState::initialize(m_graph); 68 69 do { 70 m_changed = false; 71 performForwardCFA(); 72 } while (m_changed); 73 74 return true; 75 } 76 77private: 78 void performBlockCFA(BlockIndex blockIndex) 79 { 80 BasicBlock* block = m_graph.m_blocks[blockIndex].get(); 81 if (!block) 82 return; 83 if (!block->cfaShouldRevisit) 84 return; 85#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) 86 dataLogF(" Block #%u (bc#%u):\n", blockIndex, block->bytecodeBegin); 87#endif 88 m_state.beginBasicBlock(block); 89#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) 90 dataLogF(" head vars: "); 91 dumpOperands(block->valuesAtHead, WTF::dataFile()); 92 dataLogF("\n"); 93#endif 94 for (unsigned i = 0; i < block->size(); ++i) { 95#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) 96 Node* node = block->at(i); 97 dataLogF(" %s @%u: ", Graph::opName(node->op()), node->index()); 98 m_state.dump(WTF::dataFile()); 99 dataLogF("\n"); 100#endif 101 if (!m_state.execute(i)) { 102#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) 103 dataLogF(" Expect OSR exit.\n"); 104#endif 105 break; 106 } 107 } 108#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) 109 dataLogF(" tail regs: "); 110 m_state.dump(WTF::dataFile()); 111 dataLogF("\n"); 112#endif 113 m_changed |= m_state.endBasicBlock(AbstractState::MergeToSuccessors); 114#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) 115 dataLogF(" tail vars: "); 116 dumpOperands(block->valuesAtTail, WTF::dataFile()); 117 dataLogF("\n"); 118#endif 119 } 120 121 void performForwardCFA() 122 { 123#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) 124 dataLogF("CFA [%u]\n", ++m_count); 125#endif 126 127 for (BlockIndex block = 0; block < m_graph.m_blocks.size(); ++block) 128 performBlockCFA(block); 129 } 130 131private: 132 AbstractState m_state; 133 134 bool m_changed; 135#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) 136 unsigned m_count; 137#endif 138}; 139 140bool performCFA(Graph& graph) 141{ 142 SamplingRegion samplingRegion("DFG CFA Phase"); 143 return runPhase<CFAPhase>(graph); 144} 145 146} } // namespace JSC::DFG 147 148#endif // ENABLE(DFG_JIT) 149