]>
Commit | Line | Data |
---|---|---|
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 | ||
35 | namespace JSC { namespace DFG { | |
36 | ||
37 | class CFAPhase : public Phase { | |
38 | public: | |
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 | ||
70 | private: | |
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 | ||
120 | private: | |
121 | AbstractState m_state; | |
122 | ||
123 | bool m_changed; | |
124 | #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) | |
125 | unsigned m_count; | |
126 | #endif | |
127 | }; | |
128 | ||
129 | void performCFA(Graph& graph) | |
130 | { | |
131 | runPhase<CFAPhase>(graph); | |
132 | } | |
133 | ||
134 | } } // namespace JSC::DFG | |
135 | ||
136 | #endif // ENABLE(DFG_JIT) |