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