d0059a8362da0e383ba518513ecd3a4dafea28a7
[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_currentKnownStructure.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                 StructureAbstractValue& structureValue = value.m_futurePossibleStructure;
114                 if (structureValue.isSubsetOf(set)
115                     && structureValue.hasSingleton()) {
116                     Structure* structure = structureValue.singleton();
117                     m_interpreter.execute(indexInBlock); // Catch the fact that we may filter on cell.
118                     AdjacencyList children = node->children;
119                     children.removeEdge(0);
120                     if (!!children.child1())
121                         m_insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->origin, children);
122                     node->children.setChild2(Edge());
123                     node->children.setChild3(Edge());
124                     node->convertToStructureTransitionWatchpoint(structure);
125                     eliminated = true;
126                     break;
127                 }
128                 break;
129             }
130                 
131             case CheckArray:
132             case Arrayify: {
133                 if (!node->arrayMode().alreadyChecked(m_graph, node, m_state.forNode(node->child1())))
134                     break;
135                 node->convertToPhantom();
136                 eliminated = true;
137                 break;
138             }
139                 
140             case CheckFunction: {
141                 if (m_state.forNode(node->child1()).value() != node->function())
142                     break;
143                 node->convertToPhantom();
144                 eliminated = true;
145                 break;
146             }
147                 
148             case CheckInBounds: {
149                 JSValue left = m_state.forNode(node->child1()).value();
150                 JSValue right = m_state.forNode(node->child2()).value();
151                 if (left && right && left.isInt32() && right.isInt32()
152                     && static_cast<uint32_t>(left.asInt32()) < static_cast<uint32_t>(right.asInt32())) {
153                     node->convertToPhantom();
154                     eliminated = true;
155                     break;
156                 }
157                 
158                 break;
159             }
160                 
161             case MultiGetByOffset: {
162                 Edge childEdge = node->child1();
163                 Node* child = childEdge.node();
164                 MultiGetByOffsetData& data = node->multiGetByOffsetData();
165
166                 Structure* structure = m_state.forNode(child).bestProvenStructure();
167                 if (!structure)
168                     break;
169                 
170                 for (unsigned i = data.variants.size(); i--;) {
171                     const GetByIdVariant& variant = data.variants[i];
172                     if (!variant.structureSet().contains(structure))
173                         continue;
174                     
175                     if (variant.chain())
176                         break;
177                     
178                     emitGetByOffset(indexInBlock, node, structure, variant, data.identifierNumber);
179                     eliminated = true;
180                     break;
181                 }
182                 break;
183             }
184                 
185             case MultiPutByOffset: {
186                 Edge childEdge = node->child1();
187                 Node* child = childEdge.node();
188                 MultiPutByOffsetData& data = node->multiPutByOffsetData();
189
190                 Structure* structure = m_state.forNode(child).bestProvenStructure();
191                 if (!structure)
192                     break;
193                 
194                 for (unsigned i = data.variants.size(); i--;) {
195                     const PutByIdVariant& variant = data.variants[i];
196                     if (variant.oldStructure() != structure)
197                         continue;
198                     
199                     emitPutByOffset(indexInBlock, node, structure, variant, data.identifierNumber);
200                     eliminated = true;
201                     break;
202                 }
203                 break;
204             }
205         
206             case GetById:
207             case GetByIdFlush: {
208                 Edge childEdge = node->child1();
209                 Node* child = childEdge.node();
210                 unsigned identifierNumber = node->identifierNumber();
211                 
212                 if (childEdge.useKind() != CellUse)
213                     break;
214                 
215                 Structure* structure = m_state.forNode(child).bestProvenStructure();
216                 if (!structure)
217                     break;
218
219                 GetByIdStatus status = GetByIdStatus::computeFor(
220                     vm(), structure, m_graph.identifiers()[identifierNumber]);
221                 
222                 if (!status.isSimple() || status.numVariants() != 1) {
223                     // FIXME: We could handle prototype cases.
224                     // https://bugs.webkit.org/show_bug.cgi?id=110386
225                     break;
226                 }
227                 
228                 emitGetByOffset(indexInBlock, node, structure, status[0], identifierNumber);
229                 eliminated = true;
230                 break;
231             }
232                 
233             case PutById:
234             case PutByIdDirect: {
235                 NodeOrigin origin = node->origin;
236                 Edge childEdge = node->child1();
237                 Node* child = childEdge.node();
238                 unsigned identifierNumber = node->identifierNumber();
239                 
240                 ASSERT(childEdge.useKind() == CellUse);
241                 
242                 Structure* structure = m_state.forNode(child).bestProvenStructure();
243                 if (!structure)
244                     break;
245                 
246                 PutByIdStatus status = PutByIdStatus::computeFor(
247                     vm(),
248                     m_graph.globalObjectFor(origin.semantic),
249                     structure,
250                     m_graph.identifiers()[identifierNumber],
251                     node->op() == PutByIdDirect);
252                 
253                 if (!status.isSimple())
254                     break;
255                 if (status.numVariants() != 1)
256                     break;
257                 
258                 emitPutByOffset(indexInBlock, node, structure, status[0], identifierNumber);
259                 eliminated = true;
260                 break;
261             }
262
263             case ToPrimitive: {
264                 if (m_state.forNode(node->child1()).m_type & ~(SpecFullNumber | SpecBoolean | SpecString))
265                     break;
266                 
267                 node->convertToIdentity();
268                 break;
269             }
270
271             default:
272                 break;
273             }
274                 
275             if (eliminated) {
276                 changed = true;
277                 continue;
278             }
279                 
280             m_interpreter.execute(indexInBlock);
281             if (!m_state.isValid()) {
282                 // If we invalidated then we shouldn't attempt to constant-fold. Here's an
283                 // example:
284                 //
285                 //     c: JSConstant(4.2)
286                 //     x: ValueToInt32(Check:Int32:@const)
287                 //
288                 // It would be correct for an analysis to assume that execution cannot
289                 // proceed past @x. Therefore, constant-folding @x could be rather bad. But,
290                 // the CFA may report that it found a constant even though it also reported
291                 // that everything has been invalidated. This will only happen in a couple of
292                 // the constant folding cases; most of them are also separately defensive
293                 // about such things.
294                 break;
295             }
296             if (!node->shouldGenerate() || m_state.didClobber() || node->hasConstant())
297                 continue;
298             JSValue value = m_state.forNode(node).value();
299             if (!value)
300                 continue;
301             
302             // Check if merging the abstract value of the constant into the abstract value
303             // we've proven for this node wouldn't widen the proof. If it widens the proof
304             // (i.e. says that the set contains more things in it than it previously did)
305             // then we refuse to fold.
306             AbstractValue oldValue = m_state.forNode(node);
307             AbstractValue constantValue;
308             constantValue.set(m_graph, value);
309             constantValue.fixTypeForRepresentation(node);
310             if (oldValue.merge(constantValue))
311                 continue;
312                 
313             NodeOrigin origin = node->origin;
314             AdjacencyList children = node->children;
315             
316             if (node->op() == GetLocal)
317                 m_graph.dethread();
318             else
319                 ASSERT(!node->hasVariableAccessData(m_graph));
320             
321             m_graph.convertToConstant(node, value);
322             m_insertionSet.insertNode(
323                 indexInBlock, SpecNone, Phantom, origin, children);
324             
325             changed = true;
326         }
327         m_state.reset();
328         m_insertionSet.execute(block);
329         
330         return changed;
331     }
332         
333     void emitGetByOffset(unsigned indexInBlock, Node* node, Structure* structure, const GetByIdVariant& variant, unsigned identifierNumber)
334     {
335         NodeOrigin origin = node->origin;
336         Edge childEdge = node->child1();
337         Node* child = childEdge.node();
338
339         bool needsWatchpoint = !m_state.forNode(child).m_currentKnownStructure.hasSingleton();
340         bool needsCellCheck = m_state.forNode(child).m_type & ~SpecCell;
341         
342         ASSERT(!variant.chain());
343         ASSERT(variant.structureSet().contains(structure));
344         
345         // Now before we do anything else, push the CFA forward over the GetById
346         // and make sure we signal to the loop that it should continue and not
347         // do any eliminations.
348         m_interpreter.execute(indexInBlock);
349         
350         if (needsWatchpoint) {
351             m_insertionSet.insertNode(
352                 indexInBlock, SpecNone, StructureTransitionWatchpoint, origin,
353                 OpInfo(structure), childEdge);
354         } else if (needsCellCheck) {
355             m_insertionSet.insertNode(
356                 indexInBlock, SpecNone, Phantom, origin, childEdge);
357         }
358         
359         if (variant.specificValue()) {
360             m_graph.convertToConstant(node, variant.specificValue());
361             return;
362         }
363         
364         childEdge.setUseKind(KnownCellUse);
365         
366         Edge propertyStorage;
367         
368         if (isInlineOffset(variant.offset()))
369             propertyStorage = childEdge;
370         else {
371             propertyStorage = Edge(m_insertionSet.insertNode(
372                 indexInBlock, SpecNone, GetButterfly, origin, childEdge));
373         }
374         
375         node->convertToGetByOffset(m_graph.m_storageAccessData.size(), propertyStorage);
376         
377         StorageAccessData storageAccessData;
378         storageAccessData.offset = variant.offset();
379         storageAccessData.identifierNumber = identifierNumber;
380         m_graph.m_storageAccessData.append(storageAccessData);
381     }
382
383     void emitPutByOffset(unsigned indexInBlock, Node* node, Structure* structure, const PutByIdVariant& variant, unsigned identifierNumber)
384     {
385         NodeOrigin origin = node->origin;
386         Edge childEdge = node->child1();
387         Node* child = childEdge.node();
388
389         ASSERT(variant.oldStructure() == structure);
390         
391         bool needsWatchpoint = !m_state.forNode(child).m_currentKnownStructure.hasSingleton();
392         bool needsCellCheck = m_state.forNode(child).m_type & ~SpecCell;
393         
394         // Now before we do anything else, push the CFA forward over the PutById
395         // and make sure we signal to the loop that it should continue and not
396         // do any eliminations.
397         m_interpreter.execute(indexInBlock);
398
399         if (needsWatchpoint) {
400             m_insertionSet.insertNode(
401                 indexInBlock, SpecNone, StructureTransitionWatchpoint, origin,
402                 OpInfo(structure), childEdge);
403         } else if (needsCellCheck) {
404             m_insertionSet.insertNode(
405                 indexInBlock, SpecNone, Phantom, origin, childEdge);
406         }
407
408         childEdge.setUseKind(KnownCellUse);
409
410         StructureTransitionData* transitionData = 0;
411         if (variant.kind() == PutByIdVariant::Transition) {
412             transitionData = m_graph.addStructureTransitionData(
413                 StructureTransitionData(structure, variant.newStructure()));
414
415             if (node->op() == PutById) {
416                 if (!structure->storedPrototype().isNull()) {
417                     addStructureTransitionCheck(
418                         origin, indexInBlock,
419                         structure->storedPrototype().asCell());
420                 }
421
422                 m_graph.chains().addLazily(variant.structureChain());
423
424                 for (unsigned i = 0; i < variant.structureChain()->size(); ++i) {
425                     JSValue prototype = variant.structureChain()->at(i)->storedPrototype();
426                     if (prototype.isNull())
427                         continue;
428                     ASSERT(prototype.isCell());
429                     addStructureTransitionCheck(
430                         origin, indexInBlock, prototype.asCell());
431                 }
432             }
433         }
434
435         Edge propertyStorage;
436
437         if (isInlineOffset(variant.offset()))
438             propertyStorage = childEdge;
439         else if (
440             variant.kind() == PutByIdVariant::Replace
441             || structure->outOfLineCapacity() == variant.newStructure()->outOfLineCapacity()) {
442             propertyStorage = Edge(m_insertionSet.insertNode(
443                 indexInBlock, SpecNone, GetButterfly, origin, childEdge));
444         } else if (!structure->outOfLineCapacity()) {
445             ASSERT(variant.newStructure()->outOfLineCapacity());
446             ASSERT(!isInlineOffset(variant.offset()));
447             Node* allocatePropertyStorage = m_insertionSet.insertNode(
448                 indexInBlock, SpecNone, AllocatePropertyStorage,
449                 origin, OpInfo(transitionData), childEdge);
450             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
451             propertyStorage = Edge(allocatePropertyStorage);
452         } else {
453             ASSERT(structure->outOfLineCapacity());
454             ASSERT(variant.newStructure()->outOfLineCapacity() > structure->outOfLineCapacity());
455             ASSERT(!isInlineOffset(variant.offset()));
456
457             Node* reallocatePropertyStorage = m_insertionSet.insertNode(
458                 indexInBlock, SpecNone, ReallocatePropertyStorage, origin,
459                 OpInfo(transitionData), childEdge,
460                 Edge(m_insertionSet.insertNode(
461                     indexInBlock, SpecNone, GetButterfly, origin, childEdge)));
462             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
463             propertyStorage = Edge(reallocatePropertyStorage);
464         }
465
466         if (variant.kind() == PutByIdVariant::Transition) {
467             Node* putStructure = m_graph.addNode(SpecNone, PutStructure, origin, OpInfo(transitionData), childEdge);
468             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
469             m_insertionSet.insert(indexInBlock, putStructure);
470         }
471
472         node->convertToPutByOffset(m_graph.m_storageAccessData.size(), propertyStorage);
473         m_insertionSet.insertNode(
474             indexInBlock, SpecNone, StoreBarrier, origin, 
475             Edge(node->child2().node(), KnownCellUse));
476
477         StorageAccessData storageAccessData;
478         storageAccessData.offset = variant.offset();
479         storageAccessData.identifierNumber = identifierNumber;
480         m_graph.m_storageAccessData.append(storageAccessData);
481     }
482
483     void addStructureTransitionCheck(NodeOrigin origin, unsigned indexInBlock, JSCell* cell)
484     {
485         Node* weakConstant = m_insertionSet.insertNode(
486             indexInBlock, speculationFromValue(cell), WeakJSConstant, origin, OpInfo(cell));
487         
488         if (m_graph.watchpoints().isStillValid(cell->structure()->transitionWatchpointSet())) {
489             m_insertionSet.insertNode(
490                 indexInBlock, SpecNone, StructureTransitionWatchpoint, origin,
491                 OpInfo(cell->structure()), Edge(weakConstant, CellUse));
492             return;
493         }
494
495         m_insertionSet.insertNode(
496             indexInBlock, SpecNone, CheckStructure, origin,
497             OpInfo(m_graph.addStructureSet(cell->structure())), Edge(weakConstant, CellUse));
498     }
499     
500     InPlaceAbstractState m_state;
501     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
502     InsertionSet m_insertionSet;
503 };
504
505 bool performConstantFolding(Graph& graph)
506 {
507     SamplingRegion samplingRegion("DFG Constant Folding Phase");
508     return runPhase<ConstantFoldingPhase>(graph);
509 }
510
511 } } // namespace JSC::DFG
512
513 #endif // ENABLE(DFG_JIT)
514
515