Renaming SpecInt32, SpecInt52, MachineInt to SpecInt32Only, SpecInt52Only, AnyInt.
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGInPlaceAbstractState.cpp
1 /*
2  * Copyright (C) 2013-2015 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 "DFGInPlaceAbstractState.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "CodeBlock.h"
32 #include "DFGBasicBlock.h"
33 #include "GetByIdStatus.h"
34 #include "JSCInlines.h"
35 #include "PutByIdStatus.h"
36 #include "StringObject.h"
37
38 namespace JSC { namespace DFG {
39
40 static const bool verbose = false;
41
42 InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
43     : m_graph(graph)
44     , m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
45     , m_block(0)
46 {
47 }
48
49 InPlaceAbstractState::~InPlaceAbstractState() { }
50
51 void InPlaceAbstractState::beginBasicBlock(BasicBlock* basicBlock)
52 {
53     ASSERT(!m_block);
54     
55     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
56     ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
57     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
58     
59     for (size_t i = 0; i < basicBlock->size(); i++)
60         forNode(basicBlock->at(i)).clear();
61
62     m_variables = basicBlock->valuesAtHead;
63     
64     if (m_graph.m_form == SSA) {
65         for (auto& entry : basicBlock->ssa->valuesAtHead)
66             forNode(entry.node) = entry.value;
67     }
68     basicBlock->cfaShouldRevisit = false;
69     basicBlock->cfaHasVisited = true;
70     m_block = basicBlock;
71     m_isValid = true;
72     m_foundConstants = false;
73     m_branchDirection = InvalidBranchDirection;
74     m_structureClobberState = basicBlock->cfaStructureClobberStateAtHead;
75 }
76
77 static void setLiveValues(HashMap<Node*, AbstractValue>& values, HashSet<Node*>& live)
78 {
79     values.clear();
80     
81     HashSet<Node*>::iterator iter = live.begin();
82     HashSet<Node*>::iterator end = live.end();
83     for (; iter != end; ++iter)
84         values.add(*iter, AbstractValue());
85 }
86
87 static void setLiveValues(Vector<BasicBlock::SSAData::NodeAbstractValuePair>& values, HashSet<Node*>& live)
88 {
89     values.resize(0);
90     values.reserveCapacity(live.size());
91     for (Node* node : live)
92         values.uncheckedAppend(BasicBlock::SSAData::NodeAbstractValuePair { node, AbstractValue() });
93 }
94
95 void InPlaceAbstractState::initialize()
96 {
97     BasicBlock* root = m_graph.block(0);
98     root->cfaShouldRevisit = true;
99     root->cfaHasVisited = false;
100     root->cfaFoundConstants = false;
101     root->cfaStructureClobberStateAtHead = StructuresAreWatched;
102     root->cfaStructureClobberStateAtTail = StructuresAreWatched;
103     for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
104         root->valuesAtTail.argument(i).clear();
105
106         FlushFormat format;
107         if (m_graph.m_form == SSA)
108             format = m_graph.m_argumentFormats[i];
109         else {
110             Node* node = m_graph.m_arguments[i];
111             if (!node)
112                 format = FlushedJSValue;
113             else {
114                 ASSERT(node->op() == SetArgument);
115                 format = node->variableAccessData()->flushFormat();
116             }
117         }
118         
119         switch (format) {
120         case FlushedInt32:
121             root->valuesAtHead.argument(i).setType(SpecInt32Only);
122             break;
123         case FlushedBoolean:
124             root->valuesAtHead.argument(i).setType(SpecBoolean);
125             break;
126         case FlushedCell:
127             root->valuesAtHead.argument(i).setType(m_graph, SpecCell);
128             break;
129         case FlushedJSValue:
130             root->valuesAtHead.argument(i).makeBytecodeTop();
131             break;
132         default:
133             DFG_CRASH(m_graph, nullptr, "Bad flush format for argument");
134             break;
135         }
136     }
137     for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
138         root->valuesAtHead.local(i).clear();
139         root->valuesAtTail.local(i).clear();
140     }
141     for (BlockIndex blockIndex = 1 ; blockIndex < m_graph.numBlocks(); ++blockIndex) {
142         BasicBlock* block = m_graph.block(blockIndex);
143         if (!block)
144             continue;
145         ASSERT(block->isReachable);
146         block->cfaShouldRevisit = false;
147         block->cfaHasVisited = false;
148         block->cfaFoundConstants = false;
149         block->cfaStructureClobberStateAtHead = StructuresAreWatched;
150         block->cfaStructureClobberStateAtTail = StructuresAreWatched;
151         for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
152             block->valuesAtHead.argument(i).clear();
153             block->valuesAtTail.argument(i).clear();
154         }
155         for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
156             block->valuesAtHead.local(i).clear();
157             block->valuesAtTail.local(i).clear();
158         }
159     }
160     if (m_graph.m_form == SSA) {
161         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
162             BasicBlock* block = m_graph.block(blockIndex);
163             if (!block)
164                 continue;
165             setLiveValues(block->ssa->valuesAtHead, block->ssa->liveAtHead);
166             setLiveValues(block->ssa->valuesAtTail, block->ssa->liveAtTail);
167         }
168     }
169 }
170
171 bool InPlaceAbstractState::endBasicBlock()
172 {
173     ASSERT(m_block);
174     
175     BasicBlock* block = m_block; // Save the block for successor merging.
176     
177     block->cfaFoundConstants = m_foundConstants;
178     block->cfaDidFinish = m_isValid;
179     block->cfaBranchDirection = m_branchDirection;
180     
181     if (!m_isValid) {
182         reset();
183         return false;
184     }
185     
186     bool changed = checkAndSet(block->cfaStructureClobberStateAtTail, m_structureClobberState);
187     
188     switch (m_graph.m_form) {
189     case ThreadedCPS: {
190         for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
191             AbstractValue& destination = block->valuesAtTail.argument(argument);
192             changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
193         }
194
195         for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
196             AbstractValue& destination = block->valuesAtTail.local(local);
197             changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
198         }
199         break;
200     }
201
202     case SSA: {
203         for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
204             changed |= block->valuesAtTail[i].merge(m_variables[i]);
205
206         HashSet<Node*>::iterator iter = block->ssa->liveAtTail.begin();
207         HashSet<Node*>::iterator end = block->ssa->liveAtTail.end();
208         for (; iter != end; ++iter) {
209             Node* node = *iter;
210             changed |= block->ssa->valuesAtTail.find(node)->value.merge(forNode(node));
211         }
212         break;
213     }
214
215     default:
216         RELEASE_ASSERT_NOT_REACHED();
217     }
218
219     reset();
220     
221     return mergeToSuccessors(block);
222 }
223
224 void InPlaceAbstractState::reset()
225 {
226     m_block = 0;
227     m_isValid = false;
228     m_branchDirection = InvalidBranchDirection;
229     m_structureClobberState = StructuresAreWatched;
230 }
231
232 bool InPlaceAbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
233 {
234     if (!node)
235         return false;
236         
237     AbstractValue source;
238     
239     switch (node->op()) {
240     case Phi:
241     case SetArgument:
242     case PhantomLocal:
243     case Flush:
244         // The block transfers the value from head to tail.
245         source = inVariable;
246         break;
247             
248     case GetLocal:
249         // The block refines the value with additional speculations.
250         source = forNode(node);
251         break;
252             
253     case SetLocal:
254         // The block sets the variable, and potentially refines it, both
255         // before and after setting it.
256         source = forNode(node->child1());
257         if (node->variableAccessData()->flushFormat() == FlushedDouble)
258             RELEASE_ASSERT(!(source.m_type & ~SpecFullDouble));
259         break;
260         
261     default:
262         RELEASE_ASSERT_NOT_REACHED();
263         break;
264     }
265     
266     if (destination == source) {
267         // Abstract execution did not change the output value of the variable, for this
268         // basic block, on this iteration.
269         return false;
270     }
271     
272     // Abstract execution reached a new conclusion about the speculations reached about
273     // this variable after execution of this basic block. Update the state, and return
274     // true to indicate that the fixpoint must go on!
275     destination = source;
276     return true;
277 }
278
279 bool InPlaceAbstractState::merge(BasicBlock* from, BasicBlock* to)
280 {
281     if (verbose)
282         dataLog("   Merging from ", pointerDump(from), " to ", pointerDump(to), "\n");
283     ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
284     ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
285     
286     bool changed = false;
287     
288     changed |= checkAndSet(
289         to->cfaStructureClobberStateAtHead,
290         DFG::merge(from->cfaStructureClobberStateAtTail, to->cfaStructureClobberStateAtHead));
291     
292     switch (m_graph.m_form) {
293     case ThreadedCPS: {
294         for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
295             AbstractValue& destination = to->valuesAtHead.argument(argument);
296             changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
297         }
298         
299         for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
300             AbstractValue& destination = to->valuesAtHead.local(local);
301             changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
302         }
303         break;
304     }
305         
306     case SSA: {
307         for (size_t i = from->valuesAtTail.size(); i--;)
308             changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
309
310         for (auto& entry : to->ssa->valuesAtHead) {
311             Node* node = entry.node;
312             if (verbose)
313                 dataLog("      Merging for ", node, ": from ", from->ssa->valuesAtTail.find(node)->value, " to ", entry.value, "\n");
314             changed |= entry.value.merge(
315                 from->ssa->valuesAtTail.find(node)->value);
316
317             if (verbose)
318                 dataLog("         Result: ", entry.value, "\n");
319         }
320         break;
321     }
322         
323     default:
324         RELEASE_ASSERT_NOT_REACHED();
325         break;
326     }
327
328     if (!to->cfaHasVisited)
329         changed = true;
330     
331     if (verbose)
332         dataLog("      Will revisit: ", changed, "\n");
333     to->cfaShouldRevisit |= changed;
334     
335     return changed;
336 }
337
338 inline bool InPlaceAbstractState::mergeToSuccessors(BasicBlock* basicBlock)
339 {
340     Node* terminal = basicBlock->terminal();
341     
342     ASSERT(terminal->isTerminal());
343     
344     switch (terminal->op()) {
345     case Jump: {
346         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
347         return merge(basicBlock, terminal->targetBlock());
348     }
349         
350     case Branch: {
351         ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
352         bool changed = false;
353         if (basicBlock->cfaBranchDirection != TakeFalse)
354             changed |= merge(basicBlock, terminal->branchData()->taken.block);
355         if (basicBlock->cfaBranchDirection != TakeTrue)
356             changed |= merge(basicBlock, terminal->branchData()->notTaken.block);
357         return changed;
358     }
359         
360     case Switch: {
361         // FIXME: It would be cool to be sparse conditional for Switch's. Currently
362         // we're not. However I somehow doubt that this will ever be a big deal.
363         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
364         SwitchData* data = terminal->switchData();
365         bool changed = merge(basicBlock, data->fallThrough.block);
366         for (unsigned i = data->cases.size(); i--;)
367             changed |= merge(basicBlock, data->cases[i].target.block);
368         return changed;
369     }
370         
371     case Return:
372     case TailCall:
373     case TailCallVarargs:
374     case TailCallForwardVarargs:
375     case Unreachable:
376         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
377         return false;
378
379     default:
380         RELEASE_ASSERT_NOT_REACHED();
381         return false;
382     }
383 }
384
385 inline bool InPlaceAbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
386 {
387     if (!destinationNode)
388         return false;
389     
390     ASSERT_UNUSED(sourceNode, sourceNode);
391     
392     // FIXME: We could do some sparse conditional propagation here!
393     
394     return destination.merge(source);
395 }
396
397 } } // namespace JSC::DFG
398
399 #endif // ENABLE(DFG_JIT)
400