8a261ad2bb13535012dc0ea82fac6464c7de60a9
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGConstantFoldingPhase.cpp
1 /*
2  * Copyright (C) 2012 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 "DFGConstantFoldingPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGAbstractState.h"
32 #include "DFGBasicBlock.h"
33 #include "DFGGraph.h"
34 #include "DFGInsertionSet.h"
35 #include "DFGPhase.h"
36
37 namespace JSC { namespace DFG {
38
39 class ConstantFoldingPhase : public Phase {
40 public:
41     ConstantFoldingPhase(Graph& graph)
42         : Phase(graph, "constant folding")
43         , m_state(graph)
44     {
45     }
46     
47     bool run()
48     {
49         bool changed = false;
50         
51         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
52             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
53             if (!block)
54                 continue;
55             if (!block->cfaDidFinish)
56                 changed |= paintUnreachableCode(blockIndex);
57             if (block->cfaFoundConstants)
58                 changed |= foldConstants(blockIndex);
59         }
60         
61         return changed;
62     }
63
64 private:
65     bool foldConstants(BlockIndex blockIndex)
66     {
67 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
68         dataLog("Constant folding considering Block #%u.\n", blockIndex);
69 #endif
70         BasicBlock* block = m_graph.m_blocks[blockIndex].get();
71         bool changed = false;
72         m_state.beginBasicBlock(block);
73         for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
74             NodeIndex nodeIndex = block->at(indexInBlock);
75             Node& node = m_graph[nodeIndex];
76                 
77             if (!m_state.isValid())
78                 break;
79             
80             bool eliminated = false;
81                     
82             switch (node.op()) {
83             case CheckArgumentsNotCreated: {
84                 if (!isEmptySpeculation(
85                         m_state.variables().operand(
86                             m_graph.argumentsRegisterFor(node.codeOrigin)).m_type))
87                     break;
88                 ASSERT(node.refCount() == 1);
89                 node.setOpAndDefaultFlags(Phantom);
90                 eliminated = true;
91                 break;
92             }
93                     
94             case CheckStructure:
95             case ForwardCheckStructure: {
96                 AbstractValue& value = m_state.forNode(node.child1());
97                 StructureAbstractValue& structureValue = value.m_futurePossibleStructure;
98                 if (structureValue.isSubsetOf(node.structureSet())
99                     && structureValue.hasSingleton()
100                     && isCellSpeculation(value.m_type))
101                     node.convertToStructureTransitionWatchpoint(structureValue.singleton());
102                 break;
103             }
104                 
105             case CheckArray: {
106                 if (!modeAlreadyChecked(m_state.forNode(node.child1()), node.arrayMode()))
107                     break;
108                 ASSERT(node.refCount() == 1);
109                 node.setOpAndDefaultFlags(Phantom);
110                 eliminated = true;
111                 break;
112             }
113                 
114             default:
115                 break;
116             }
117                 
118             if (eliminated) {
119                 changed = true;
120                 continue;
121             }
122                 
123             m_state.execute(indexInBlock);
124             if (!node.shouldGenerate() || m_state.didClobber() || node.hasConstant())
125                 continue;
126             JSValue value = m_state.forNode(nodeIndex).value();
127             if (!value)
128                 continue;
129                 
130             Node phantom(Phantom, node.codeOrigin);
131                 
132             if (node.op() == GetLocal) {
133                 NodeIndex previousLocalAccess = NoNode;
134                 if (block->variablesAtHead.operand(node.local()) == nodeIndex
135                     && m_graph[node.child1()].op() == Phi) {
136                     // We expect this to be the common case.
137                     ASSERT(block->isInPhis(node.child1().index()));
138                     previousLocalAccess = node.child1().index();
139                     block->variablesAtHead.operand(node.local()) = previousLocalAccess;
140                 } else {
141                     ASSERT(indexInBlock > 0);
142                     // Must search for the previous access to this local.
143                     for (BlockIndex subIndexInBlock = indexInBlock; subIndexInBlock--;) {
144                         NodeIndex subNodeIndex = block->at(subIndexInBlock);
145                         Node& subNode = m_graph[subNodeIndex];
146                         if (!subNode.shouldGenerate())
147                             continue;
148                         if (!subNode.hasVariableAccessData())
149                             continue;
150                         if (subNode.local() != node.local())
151                             continue;
152                         // The two must have been unified.
153                         ASSERT(subNode.variableAccessData() == node.variableAccessData());
154                         previousLocalAccess = subNodeIndex;
155                         break;
156                     }
157                     if (previousLocalAccess == NoNode) {
158                         // The previous access must have been a Phi.
159                         for (BlockIndex phiIndexInBlock = block->phis.size(); phiIndexInBlock--;) {
160                             NodeIndex phiNodeIndex = block->phis[phiIndexInBlock];
161                             Node& phiNode = m_graph[phiNodeIndex];
162                             if (!phiNode.shouldGenerate())
163                                 continue;
164                             if (phiNode.local() != node.local())
165                                 continue;
166                             // The two must have been unified.
167                             ASSERT(phiNode.variableAccessData() == node.variableAccessData());
168                             previousLocalAccess = phiNodeIndex;
169                             break;
170                         }
171                         ASSERT(previousLocalAccess != NoNode);
172                     }
173                 }
174                     
175                 ASSERT(previousLocalAccess != NoNode);
176                 
177                 NodeIndex tailNodeIndex = block->variablesAtTail.operand(node.local());
178                 if (tailNodeIndex == nodeIndex)
179                     block->variablesAtTail.operand(node.local()) = previousLocalAccess;
180                 else {
181                     ASSERT(m_graph[tailNodeIndex].op() == Flush
182                         || m_graph[tailNodeIndex].op() == SetLocal
183                         || node.variableAccessData()->isCaptured());
184                 }
185             }
186                 
187             phantom.children = node.children;
188             phantom.ref();
189             
190             m_graph.convertToConstant(nodeIndex, value);
191             NodeIndex phantomNodeIndex = m_graph.size();
192             m_graph.append(phantom);
193             m_insertionSet.append(indexInBlock, phantomNodeIndex);
194                 
195             changed = true;
196         }
197         m_state.reset();
198         m_insertionSet.execute(*block);
199         
200         return changed;
201     }
202     
203     // This is necessary because the CFA may reach conclusions about constants based on its
204     // assumption that certain code must exit, but then those constants may lead future
205     // reexecutions of the CFA to believe that the same code will now no longer exit. Thus
206     // to ensure soundness, we must paint unreachable code as such, by inserting an
207     // unconditional ForceOSRExit wherever we find that a node would have always exited.
208     // This will only happen in cases where we are making static speculations, or we're
209     // making totally wrong speculations due to imprecision on the prediction propagator.
210     bool paintUnreachableCode(BlockIndex blockIndex)
211     {
212         bool changed = false;
213         
214 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
215         dataLog("Painting unreachable code in Block #%u.\n", blockIndex);
216 #endif
217         BasicBlock* block = m_graph.m_blocks[blockIndex].get();
218         m_state.beginBasicBlock(block);
219         
220         for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
221             m_state.execute(indexInBlock);
222             if (m_state.isValid())
223                 continue;
224             
225             NodeIndex nodeIndex = block->at(indexInBlock);
226             Node& node = m_graph[nodeIndex];
227             switch (node.op()) {
228             case Return:
229             case Throw:
230             case ThrowReferenceError:
231             case ForceOSRExit:
232                 // Do nothing. These nodes will already do the right thing.
233                 break;
234                 
235             default:
236                 Node forceOSRExit(ForceOSRExit, node.codeOrigin);
237                 forceOSRExit.ref();
238                 NodeIndex forceOSRExitIndex = m_graph.size();
239                 m_graph.append(forceOSRExit);
240                 m_insertionSet.append(indexInBlock, forceOSRExitIndex);
241                 changed = true;
242                 break;
243             }
244             break;
245         }
246         m_state.reset();
247         m_insertionSet.execute(*block);
248         
249         return changed;
250     }
251
252     AbstractState m_state;
253     InsertionSet<NodeIndex> m_insertionSet;
254 };
255
256 bool performConstantFolding(Graph& graph)
257 {
258     SamplingRegion samplingRegion("DFG Constant Folding Phase");
259     return runPhase<ConstantFoldingPhase>(graph);
260 }
261
262 } } // namespace JSC::DFG
263
264 #endif // ENABLE(DFG_JIT)
265
266