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