Rename SetArgument to SetArgumentDefinitely
[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() == SetArgumentDefinitely);
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 SetArgumentDefinitely:
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. Since the SetLocal already did
269                 // a type check based on the flush format's type, we're only interested
270                 // in refinements within that type hierarchy. Otherwise, we may end up
271                 // saying that any GetLocals reachable from this basic block load something
272                 // outside of that hierarchy, e.g:
273                 //
274                 // a: JSConstant(jsNumber(0))
275                 // b: SetLocal(Int32:@a, loc1, FlushedInt32)
276                 // c: ArrayifyToStructure(Cell:@a)
277                 // d: Jump(...)
278                 //
279                 // In this example, we can't trust whatever type ArrayifyToStructure sets
280                 // @a to. We're only interested in the subset of that type that intersects
281                 // with Int32.
282                 AbstractValue value = forNode(node->child1());
283                 value.filter(typeFilterFor(node->variableAccessData()->flushFormat()));
284                 destination = value;
285                 break;
286             }
287                 
288             default:
289                 RELEASE_ASSERT_NOT_REACHED();
290                 break;
291             }
292         }
293         break;
294     }
295
296     case SSA: {
297         for (size_t i = 0; i < block->valuesAtTail.size(); ++i) {
298             AbstractValue& destination = block->valuesAtTail[i];
299
300             if (!m_activeVariables[i]) {
301                 destination = block->valuesAtHead[i];
302                 destination.fastForwardFromTo(epochAtHead, currentEpoch);
303                 continue;
304             }
305             
306             block->valuesAtTail[i] = variableAt(i);
307         }
308
309         for (NodeAbstractValuePair& valueAtTail : block->ssa->valuesAtTail)
310             valueAtTail.value = forNode(valueAtTail.node);
311         break;
312     }
313
314     default:
315         RELEASE_ASSERT_NOT_REACHED();
316     }
317
318     reset();
319     
320     return mergeToSuccessors(block);
321 }
322
323 void InPlaceAbstractState::reset()
324 {
325     m_block = 0;
326     m_isValid = false;
327     m_branchDirection = InvalidBranchDirection;
328     m_structureClobberState = StructuresAreWatched;
329 }
330
331 void InPlaceAbstractState::activateVariable(size_t variableIndex)
332 {
333     AbstractValue& value = m_variables[variableIndex];
334     value = m_block->valuesAtHead[variableIndex];
335     value.m_effectEpoch = m_epochAtHead;
336     m_activeVariables[variableIndex] = true;
337 }
338
339 bool InPlaceAbstractState::merge(BasicBlock* from, BasicBlock* to)
340 {
341     if (DFGInPlaceAbstractStateInternal::verbose)
342         dataLog("   Merging from ", pointerDump(from), " to ", pointerDump(to), "\n");
343     ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
344     ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
345     
346     bool changed = false;
347     
348     changed |= checkAndSet(
349         to->cfaStructureClobberStateAtHead,
350         DFG::merge(from->cfaStructureClobberStateAtTail, to->cfaStructureClobberStateAtHead));
351     
352     switch (m_graph.m_form) {
353     case ThreadedCPS: {
354         for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
355             AbstractValue& destination = to->valuesAtHead.argument(argument);
356             changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
357         }
358         
359         for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
360             AbstractValue& destination = to->valuesAtHead.local(local);
361             changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
362         }
363         break;
364     }
365         
366     case SSA: {
367         for (size_t i = from->valuesAtTail.size(); i--;)
368             changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
369
370         for (NodeAbstractValuePair& entry : to->ssa->valuesAtHead) {
371             NodeFlowProjection node = entry.node;
372             if (DFGInPlaceAbstractStateInternal::verbose)
373                 dataLog("      Merging for ", node, ": from ", forNode(node), " to ", entry.value, "\n");
374 #ifndef NDEBUG
375             unsigned valueCountInFromBlock = 0;
376             for (NodeAbstractValuePair& fromBlockValueAtTail : from->ssa->valuesAtTail) {
377                 if (fromBlockValueAtTail.node == node) {
378                     ASSERT(fromBlockValueAtTail.value == forNode(node));
379                     ++valueCountInFromBlock;
380                 }
381             }
382             ASSERT(valueCountInFromBlock == 1);
383 #endif
384
385             changed |= entry.value.merge(forNode(node));
386
387             if (DFGInPlaceAbstractStateInternal::verbose)
388                 dataLog("         Result: ", entry.value, "\n");
389         }
390         break;
391     }
392         
393     default:
394         RELEASE_ASSERT_NOT_REACHED();
395         break;
396     }
397
398     if (!to->cfaHasVisited)
399         changed = true;
400     
401     if (DFGInPlaceAbstractStateInternal::verbose)
402         dataLog("      Will revisit: ", changed, "\n");
403     to->cfaShouldRevisit |= changed;
404     
405     return changed;
406 }
407
408 inline bool InPlaceAbstractState::mergeToSuccessors(BasicBlock* basicBlock)
409 {
410     Node* terminal = basicBlock->terminal();
411     
412     ASSERT(terminal->isTerminal());
413     
414     switch (terminal->op()) {
415     case Jump: {
416         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
417         return merge(basicBlock, terminal->targetBlock());
418     }
419         
420     case Branch: {
421         ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
422         bool changed = false;
423         if (basicBlock->cfaBranchDirection != TakeFalse)
424             changed |= merge(basicBlock, terminal->branchData()->taken.block);
425         if (basicBlock->cfaBranchDirection != TakeTrue)
426             changed |= merge(basicBlock, terminal->branchData()->notTaken.block);
427         return changed;
428     }
429         
430     case Switch: {
431         // FIXME: It would be cool to be sparse conditional for Switch's. Currently
432         // we're not. However I somehow doubt that this will ever be a big deal.
433         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
434         SwitchData* data = terminal->switchData();
435         bool changed = merge(basicBlock, data->fallThrough.block);
436         for (unsigned i = data->cases.size(); i--;)
437             changed |= merge(basicBlock, data->cases[i].target.block);
438         return changed;
439     }
440     
441     case EntrySwitch: {
442         EntrySwitchData* data = terminal->entrySwitchData();
443         bool changed = false;
444         for (unsigned i = data->cases.size(); i--;)
445             changed |= merge(basicBlock, data->cases[i]);
446         return changed;
447     }
448
449     case Return:
450     case TailCall:
451     case DirectTailCall:
452     case TailCallVarargs:
453     case TailCallForwardVarargs:
454     case Unreachable:
455     case Throw:
456     case ThrowStaticError:
457         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
458         return false;
459
460     default:
461         RELEASE_ASSERT_NOT_REACHED();
462         return false;
463     }
464 }
465
466 inline bool InPlaceAbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
467 {
468     if (!destinationNode)
469         return false;
470     
471     ASSERT_UNUSED(sourceNode, sourceNode);
472     
473     // FIXME: We could do some sparse conditional propagation here!
474     
475     return destination.merge(source);
476 }
477
478 } } // namespace JSC::DFG
479
480 #endif // ENABLE(DFG_JIT)
481