Merge r169148, r169185, r169188, r169578, r169582, r169584, r169588, r169753 from...
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGConstantFoldingPhase.cpp
1 /*
2  * Copyright (C) 2012, 2013, 2014 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 "DFGAbstractInterpreterInlines.h"
32 #include "DFGBasicBlock.h"
33 #include "DFGGraph.h"
34 #include "DFGInPlaceAbstractState.h"
35 #include "DFGInsertionSet.h"
36 #include "DFGPhase.h"
37 #include "GetByIdStatus.h"
38 #include "JSCInlines.h"
39 #include "PutByIdStatus.h"
40
41 namespace JSC { namespace DFG {
42
43 class ConstantFoldingPhase : public Phase {
44 public:
45     ConstantFoldingPhase(Graph& graph)
46         : Phase(graph, "constant folding")
47         , m_state(graph)
48         , m_interpreter(graph, m_state)
49         , m_insertionSet(graph)
50     {
51     }
52     
53     bool run()
54     {
55         bool changed = false;
56         
57         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
58             BasicBlock* block = m_graph.block(blockIndex);
59             if (!block)
60                 continue;
61             if (block->cfaFoundConstants)
62                 changed |= foldConstants(block);
63         }
64         
65         return changed;
66     }
67
68 private:
69     bool foldConstants(BasicBlock* block)
70     {
71         bool changed = false;
72         m_state.beginBasicBlock(block);
73         for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
74             if (!m_state.isValid())
75                 break;
76             
77             Node* node = block->at(indexInBlock);
78
79             bool eliminated = false;
80                     
81             switch (node->op()) {
82             case BooleanToNumber: {
83                 if (node->child1().useKind() == UntypedUse
84                     && !m_interpreter.needsTypeCheck(node->child1(), SpecBoolean))
85                     node->child1().setUseKind(BooleanUse);
86                 break;
87             }
88                 
89             case CheckArgumentsNotCreated: {
90                 if (!isEmptySpeculation(
91                         m_state.variables().operand(
92                             m_graph.argumentsRegisterFor(node->origin.semantic)).m_type))
93                     break;
94                 node->convertToPhantom();
95                 eliminated = true;
96                 break;
97             }
98                     
99             case CheckStructure:
100             case ArrayifyToStructure: {
101                 AbstractValue& value = m_state.forNode(node->child1());
102                 StructureSet set;
103                 if (node->op() == ArrayifyToStructure)
104                     set = node->structure();
105                 else
106                     set = node->structureSet();
107                 if (value.m_structure.isSubsetOf(set)) {
108                     m_interpreter.execute(indexInBlock); // Catch the fact that we may filter on cell.
109                     node->convertToPhantom();
110                     eliminated = true;
111                     break;
112                 }
113                 break;
114             }
115                 
116             case CheckArray:
117             case Arrayify: {
118                 if (!node->arrayMode().alreadyChecked(m_graph, node, m_state.forNode(node->child1())))
119                     break;
120                 node->convertToPhantom();
121                 eliminated = true;
122                 break;
123             }
124                 
125             case CheckFunction: {
126                 if (m_state.forNode(node->child1()).value() != node->function())
127                     break;
128                 node->convertToPhantom();
129                 eliminated = true;
130                 break;
131             }
132                 
133             case CheckInBounds: {
134                 JSValue left = m_state.forNode(node->child1()).value();
135                 JSValue right = m_state.forNode(node->child2()).value();
136                 if (left && right && left.isInt32() && right.isInt32()
137                     && static_cast<uint32_t>(left.asInt32()) < static_cast<uint32_t>(right.asInt32())) {
138                     node->convertToPhantom();
139                     eliminated = true;
140                     break;
141                 }
142                 
143                 break;
144             }
145                 
146             case MultiGetByOffset: {
147                 Edge childEdge = node->child1();
148                 Node* child = childEdge.node();
149                 MultiGetByOffsetData& data = node->multiGetByOffsetData();
150
151                 Structure* structure = m_state.forNode(child).m_structure.onlyStructure();
152                 if (!structure)
153                     break;
154                 
155                 for (unsigned i = data.variants.size(); i--;) {
156                     const GetByIdVariant& variant = data.variants[i];
157                     if (!variant.structureSet().contains(structure))
158                         continue;
159                     
160                     if (variant.chain())
161                         break;
162                     
163                     emitGetByOffset(indexInBlock, node, structure, variant, data.identifierNumber);
164                     eliminated = true;
165                     break;
166                 }
167                 break;
168             }
169                 
170             case MultiPutByOffset: {
171                 Edge childEdge = node->child1();
172                 Node* child = childEdge.node();
173                 MultiPutByOffsetData& data = node->multiPutByOffsetData();
174
175                 Structure* structure = m_state.forNode(child).m_structure.onlyStructure();
176                 if (!structure)
177                     break;
178                 
179                 for (unsigned i = data.variants.size(); i--;) {
180                     const PutByIdVariant& variant = data.variants[i];
181                     if (variant.oldStructure() != structure)
182                         continue;
183                     
184                     emitPutByOffset(indexInBlock, node, structure, variant, data.identifierNumber);
185                     eliminated = true;
186                     break;
187                 }
188                 break;
189             }
190         
191             case GetById:
192             case GetByIdFlush: {
193                 Edge childEdge = node->child1();
194                 Node* child = childEdge.node();
195                 unsigned identifierNumber = node->identifierNumber();
196                 
197                 if (childEdge.useKind() != CellUse)
198                     break;
199                 
200                 Structure* structure = m_state.forNode(child).m_structure.onlyStructure();
201                 if (!structure)
202                     break;
203
204                 GetByIdStatus status = GetByIdStatus::computeFor(
205                     vm(), structure, m_graph.identifiers()[identifierNumber]);
206                 
207                 if (!status.isSimple() || status.numVariants() != 1) {
208                     // FIXME: We could handle prototype cases.
209                     // https://bugs.webkit.org/show_bug.cgi?id=110386
210                     break;
211                 }
212                 
213                 emitGetByOffset(indexInBlock, node, structure, status[0], identifierNumber);
214                 eliminated = true;
215                 break;
216             }
217                 
218             case PutById:
219             case PutByIdDirect: {
220                 NodeOrigin origin = node->origin;
221                 Edge childEdge = node->child1();
222                 Node* child = childEdge.node();
223                 unsigned identifierNumber = node->identifierNumber();
224                 
225                 ASSERT(childEdge.useKind() == CellUse);
226                 
227                 Structure* structure = m_state.forNode(child).m_structure.onlyStructure();
228                 if (!structure)
229                     break;
230                 
231                 PutByIdStatus status = PutByIdStatus::computeFor(
232                     vm(),
233                     m_graph.globalObjectFor(origin.semantic),
234                     structure,
235                     m_graph.identifiers()[identifierNumber],
236                     node->op() == PutByIdDirect);
237                 
238                 if (!status.isSimple())
239                     break;
240                 if (status.numVariants() != 1)
241                     break;
242                 
243                 emitPutByOffset(indexInBlock, node, structure, status[0], identifierNumber);
244                 eliminated = true;
245                 break;
246             }
247
248             case ToPrimitive: {
249                 if (m_state.forNode(node->child1()).m_type & ~(SpecFullNumber | SpecBoolean | SpecString))
250                     break;
251                 
252                 node->convertToIdentity();
253                 break;
254             }
255
256             default:
257                 break;
258             }
259                 
260             if (eliminated) {
261                 changed = true;
262                 continue;
263             }
264                 
265             m_interpreter.execute(indexInBlock);
266             if (!m_state.isValid()) {
267                 // If we invalidated then we shouldn't attempt to constant-fold. Here's an
268                 // example:
269                 //
270                 //     c: JSConstant(4.2)
271                 //     x: ValueToInt32(Check:Int32:@const)
272                 //
273                 // It would be correct for an analysis to assume that execution cannot
274                 // proceed past @x. Therefore, constant-folding @x could be rather bad. But,
275                 // the CFA may report that it found a constant even though it also reported
276                 // that everything has been invalidated. This will only happen in a couple of
277                 // the constant folding cases; most of them are also separately defensive
278                 // about such things.
279                 break;
280             }
281             if (!node->shouldGenerate() || m_state.didClobber() || node->hasConstant())
282                 continue;
283             JSValue value = m_state.forNode(node).value();
284             if (!value)
285                 continue;
286             
287             // Check if merging the abstract value of the constant into the abstract value
288             // we've proven for this node wouldn't widen the proof. If it widens the proof
289             // (i.e. says that the set contains more things in it than it previously did)
290             // then we refuse to fold.
291             AbstractValue oldValue = m_state.forNode(node);
292             AbstractValue constantValue;
293             constantValue.set(m_graph, value, m_state.structureClobberState());
294             constantValue.fixTypeForRepresentation(node);
295             if (oldValue.merge(constantValue))
296                 continue;
297                 
298             NodeOrigin origin = node->origin;
299             AdjacencyList children = node->children;
300             
301             if (node->op() == GetLocal)
302                 m_graph.dethread();
303             else
304                 ASSERT(!node->hasVariableAccessData(m_graph));
305             
306             m_graph.convertToConstant(node, value);
307             m_insertionSet.insertNode(
308                 indexInBlock, SpecNone, Phantom, origin, children);
309             
310             changed = true;
311         }
312         m_state.reset();
313         m_insertionSet.execute(block);
314         
315         return changed;
316     }
317         
318     void emitGetByOffset(unsigned indexInBlock, Node* node, Structure* structure, const GetByIdVariant& variant, unsigned identifierNumber)
319     {
320         NodeOrigin origin = node->origin;
321         Edge childEdge = node->child1();
322         Node* child = childEdge.node();
323
324         bool needsCellCheck = m_state.forNode(child).m_type & ~SpecCell;
325         
326         ASSERT(!variant.chain());
327         ASSERT_UNUSED(structure, variant.structureSet().contains(structure));
328         
329         // Now before we do anything else, push the CFA forward over the GetById
330         // and make sure we signal to the loop that it should continue and not
331         // do any eliminations.
332         m_interpreter.execute(indexInBlock);
333         
334         if (needsCellCheck) {
335             m_insertionSet.insertNode(
336                 indexInBlock, SpecNone, Phantom, origin, childEdge);
337         }
338         
339         if (variant.specificValue()) {
340             m_graph.convertToConstant(node, variant.specificValue());
341             return;
342         }
343         
344         childEdge.setUseKind(KnownCellUse);
345         
346         Edge propertyStorage;
347         
348         if (isInlineOffset(variant.offset()))
349             propertyStorage = childEdge;
350         else {
351             propertyStorage = Edge(m_insertionSet.insertNode(
352                 indexInBlock, SpecNone, GetButterfly, origin, childEdge));
353         }
354         
355         node->convertToGetByOffset(m_graph.m_storageAccessData.size(), propertyStorage);
356         
357         StorageAccessData storageAccessData;
358         storageAccessData.offset = variant.offset();
359         storageAccessData.identifierNumber = identifierNumber;
360         m_graph.m_storageAccessData.append(storageAccessData);
361     }
362
363     void emitPutByOffset(unsigned indexInBlock, Node* node, Structure* structure, const PutByIdVariant& variant, unsigned identifierNumber)
364     {
365         NodeOrigin origin = node->origin;
366         Edge childEdge = node->child1();
367         Node* child = childEdge.node();
368
369         ASSERT(variant.oldStructure() == structure);
370         
371         bool needsCellCheck = m_state.forNode(child).m_type & ~SpecCell;
372         
373         // Now before we do anything else, push the CFA forward over the PutById
374         // and make sure we signal to the loop that it should continue and not
375         // do any eliminations.
376         m_interpreter.execute(indexInBlock);
377
378         if (needsCellCheck) {
379             m_insertionSet.insertNode(
380                 indexInBlock, SpecNone, Phantom, origin, childEdge);
381         }
382
383         childEdge.setUseKind(KnownCellUse);
384
385         Transition* transition = 0;
386         if (variant.kind() == PutByIdVariant::Transition) {
387             transition = m_graph.m_transitions.add(structure, variant.newStructure());
388
389             if (node->op() == PutById) {
390                 if (!structure->storedPrototype().isNull()) {
391                     addStructureTransitionCheck(
392                         origin, indexInBlock,
393                         structure->storedPrototype().asCell());
394                 }
395
396                 m_graph.chains().addLazily(variant.structureChain());
397
398                 for (unsigned i = 0; i < variant.structureChain()->size(); ++i) {
399                     JSValue prototype = variant.structureChain()->at(i)->storedPrototype();
400                     if (prototype.isNull())
401                         continue;
402                     ASSERT(prototype.isCell());
403                     addStructureTransitionCheck(
404                         origin, indexInBlock, prototype.asCell());
405                 }
406             }
407         }
408
409         Edge propertyStorage;
410
411         if (isInlineOffset(variant.offset()))
412             propertyStorage = childEdge;
413         else if (
414             variant.kind() == PutByIdVariant::Replace
415             || structure->outOfLineCapacity() == variant.newStructure()->outOfLineCapacity()) {
416             propertyStorage = Edge(m_insertionSet.insertNode(
417                 indexInBlock, SpecNone, GetButterfly, origin, childEdge));
418         } else if (!structure->outOfLineCapacity()) {
419             ASSERT(variant.newStructure()->outOfLineCapacity());
420             ASSERT(!isInlineOffset(variant.offset()));
421             Node* allocatePropertyStorage = m_insertionSet.insertNode(
422                 indexInBlock, SpecNone, AllocatePropertyStorage,
423                 origin, OpInfo(transition), childEdge);
424             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
425             propertyStorage = Edge(allocatePropertyStorage);
426         } else {
427             ASSERT(structure->outOfLineCapacity());
428             ASSERT(variant.newStructure()->outOfLineCapacity() > structure->outOfLineCapacity());
429             ASSERT(!isInlineOffset(variant.offset()));
430
431             Node* reallocatePropertyStorage = m_insertionSet.insertNode(
432                 indexInBlock, SpecNone, ReallocatePropertyStorage, origin,
433                 OpInfo(transition), childEdge,
434                 Edge(m_insertionSet.insertNode(
435                     indexInBlock, SpecNone, GetButterfly, origin, childEdge)));
436             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
437             propertyStorage = Edge(reallocatePropertyStorage);
438         }
439
440         if (variant.kind() == PutByIdVariant::Transition) {
441             Node* putStructure = m_graph.addNode(SpecNone, PutStructure, origin, OpInfo(transition), childEdge);
442             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
443             m_insertionSet.insert(indexInBlock, putStructure);
444         }
445
446         node->convertToPutByOffset(m_graph.m_storageAccessData.size(), propertyStorage);
447         m_insertionSet.insertNode(
448             indexInBlock, SpecNone, StoreBarrier, origin, 
449             Edge(node->child2().node(), KnownCellUse));
450
451         StorageAccessData storageAccessData;
452         storageAccessData.offset = variant.offset();
453         storageAccessData.identifierNumber = identifierNumber;
454         m_graph.m_storageAccessData.append(storageAccessData);
455     }
456
457     void addStructureTransitionCheck(NodeOrigin origin, unsigned indexInBlock, JSCell* cell)
458     {
459         if (m_graph.watchpoints().consider(cell->structure()))
460             return;
461
462         Node* weakConstant = m_insertionSet.insertNode(
463             indexInBlock, speculationFromValue(cell), WeakJSConstant, origin, OpInfo(cell));
464         
465         m_insertionSet.insertNode(
466             indexInBlock, SpecNone, CheckStructure, origin,
467             OpInfo(m_graph.addStructureSet(cell->structure())), Edge(weakConstant, CellUse));
468     }
469     
470     InPlaceAbstractState m_state;
471     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
472     InsertionSet m_insertionSet;
473 };
474
475 bool performConstantFolding(Graph& graph)
476 {
477     SamplingRegion samplingRegion("DFG Constant Folding Phase");
478     return runPhase<ConstantFoldingPhase>(graph);
479 }
480
481 } } // namespace JSC::DFG
482
483 #endif // ENABLE(DFG_JIT)
484
485