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