fourthTier: Decouple the way that CFA stores its state from the way it does abstract...
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGCFAPhase.cpp
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 "DFGAbstractInterpreterInlines.h"
32 #include "DFGGraph.h"
33 #include "DFGInPlaceAbstractState.h"
34 #include "DFGPhase.h"
35 #include "Operations.h"
36
37 namespace JSC { namespace DFG {
38
39 class CFAPhase : public Phase {
40 public:
41 #if DFG_ENABLE(DFG_PROPAGATION_VERBOSE)
42     static const bool verbose = true;
43 #else
44     static const bool verbose = false;
45 #endif
46
47     CFAPhase(Graph& graph)
48         : Phase(graph, "control flow analysis")
49         , m_state(graph)
50         , m_interpreter(graph, m_state)
51     {
52     }
53     
54     bool run()
55     {
56         ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
57         ASSERT(m_graph.m_unificationState == GloballyUnified);
58         ASSERT(m_graph.m_refCountState == EverythingIsLive);
59         
60         m_count = 0;
61         
62         // This implements a pseudo-worklist-based forward CFA, except that the visit order
63         // of blocks is the bytecode program order (which is nearly topological), and
64         // instead of a worklist we just walk all basic blocks checking if cfaShouldRevisit
65         // is set to true. This is likely to balance the efficiency properties of both
66         // worklist-based and forward fixpoint-based approaches. Like a worklist-based
67         // approach, it won't visit code if it's meaningless to do so (nothing changed at
68         // the head of the block or the predecessors have not been visited). Like a forward
69         // fixpoint-based approach, it has a high probability of only visiting a block
70         // after all predecessors have been visited. Only loops will cause this analysis to
71         // revisit blocks, and the amount of revisiting is proportional to loop depth.
72         
73         m_state.initialize();
74         
75         do {
76             m_changed = false;
77             performForwardCFA();
78         } while (m_changed);
79         
80         return true;
81     }
82     
83 private:
84     void performBlockCFA(BasicBlock* block)
85     {
86         if (!block)
87             return;
88         if (!block->cfaShouldRevisit)
89             return;
90         if (verbose)
91             dataLog("   Block ", *block, ":\n");
92         m_state.beginBasicBlock(block);
93         if (verbose) {
94             dataLogF("      head vars: ");
95             dumpOperands(block->valuesAtHead, WTF::dataFile());
96             dataLogF("\n");
97         }
98         for (unsigned i = 0; i < block->size(); ++i) {
99             if (verbose) {
100                 Node* node = block->at(i);
101                 dataLogF("      %s @%u: ", Graph::opName(node->op()), node->index());
102                 m_interpreter.dump(WTF::dataFile());
103                 dataLogF("\n");
104             }
105             if (!m_interpreter.execute(i)) {
106                 if (verbose)
107                     dataLogF("         Expect OSR exit.\n");
108                 break;
109             }
110         }
111         if (verbose) {
112             dataLogF("      tail regs: ");
113             m_interpreter.dump(WTF::dataFile());
114             dataLogF("\n");
115         }
116         m_changed |= m_state.endBasicBlock(MergeToSuccessors);
117         
118         if (verbose) {
119             dataLogF("      tail vars: ");
120             dumpOperands(block->valuesAtTail, WTF::dataFile());
121             dataLogF("\n");
122         }
123     }
124     
125     void performForwardCFA()
126     {
127         ++m_count;
128         if (verbose)
129             dataLogF("CFA [%u]\n", ++m_count);
130         
131         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
132             performBlockCFA(m_graph.block(blockIndex));
133     }
134
135 private:
136     InPlaceAbstractState m_state;
137     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
138     
139     bool m_changed;
140     unsigned m_count;
141 };
142
143 bool performCFA(Graph& graph)
144 {
145     SamplingRegion samplingRegion("DFG CFA Phase");
146     return runPhase<CFAPhase>(graph);
147 }
148
149 } } // namespace JSC::DFG
150
151 #endif // ENABLE(DFG_JIT)