]> git.saurik.com Git - apple/javascriptcore.git/blame - dfg/DFGCFAPhase.cpp
JavaScriptCore-1097.13.tar.gz
[apple/javascriptcore.git] / dfg / DFGCFAPhase.cpp
CommitLineData
6fe7ccc8
A
1/*
2 * Copyright (C) 2011 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
35namespace JSC { namespace DFG {
36
37class CFAPhase : public Phase {
38public:
39 CFAPhase(Graph& graph)
40 : Phase(graph, "control flow analysis")
41 , m_state(graph)
42 {
43 }
44
45 void run()
46 {
47#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
48 m_count = 0;
49#endif
50
51 // This implements a pseudo-worklist-based forward CFA, except that the visit order
52 // of blocks is the bytecode program order (which is nearly topological), and
53 // instead of a worklist we just walk all basic blocks checking if cfaShouldRevisit
54 // is set to true. This is likely to balance the efficiency properties of both
55 // worklist-based and forward fixpoint-based approaches. Like a worklist-based
56 // approach, it won't visit code if it's meaningless to do so (nothing changed at
57 // the head of the block or the predecessors have not been visited). Like a forward
58 // fixpoint-based approach, it has a high probability of only visiting a block
59 // after all predecessors have been visited. Only loops will cause this analysis to
60 // revisit blocks, and the amount of revisiting is proportional to loop depth.
61
62 AbstractState::initialize(m_graph);
63
64 do {
65 m_changed = false;
66 performForwardCFA();
67 } while (m_changed);
68 }
69
70private:
71 void performBlockCFA(BlockIndex blockIndex)
72 {
73 BasicBlock* block = m_graph.m_blocks[blockIndex].get();
74 if (!block->cfaShouldRevisit)
75 return;
76#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
77 dataLog(" Block #%u (bc#%u):\n", blockIndex, block->bytecodeBegin);
78#endif
79 m_state.beginBasicBlock(block);
80#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
81 dataLog(" head vars: ");
82 dumpOperands(block->valuesAtHead, WTF::dataFile());
83 dataLog("\n");
84#endif
85 for (unsigned i = 0; i < block->size(); ++i) {
86 NodeIndex nodeIndex = block->at(i);
87 if (!m_graph[nodeIndex].shouldGenerate())
88 continue;
89#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
90 dataLog(" %s @%u: ", Graph::opName(m_graph[nodeIndex].op()), nodeIndex);
91 m_state.dump(WTF::dataFile());
92 dataLog("\n");
93#endif
94 if (!m_state.execute(i))
95 break;
96 }
97#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
98 dataLog(" tail regs: ");
99 m_state.dump(WTF::dataFile());
100 dataLog("\n");
101#endif
102 m_changed |= m_state.endBasicBlock(AbstractState::MergeToSuccessors);
103#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
104 dataLog(" tail vars: ");
105 dumpOperands(block->valuesAtTail, WTF::dataFile());
106 dataLog("\n");
107#endif
108 }
109
110 void performForwardCFA()
111 {
112#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
113 dataLog("CFA [%u]\n", ++m_count);
114#endif
115
116 for (BlockIndex block = 0; block < m_graph.m_blocks.size(); ++block)
117 performBlockCFA(block);
118 }
119
120private:
121 AbstractState m_state;
122
123 bool m_changed;
124#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
125 unsigned m_count;
126#endif
127};
128
129void performCFA(Graph& graph)
130{
131 runPhase<CFAPhase>(graph);
132}
133
134} } // namespace JSC::DFG
135
136#endif // ENABLE(DFG_JIT)