f018e1811b3608efee869141590c57249ff1efbf
[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         if (changed && m_graph.m_form == SSA) {
66             // It's now possible that we have Upsilons pointed at JSConstants. Fix that.
67             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
68                 BasicBlock* block = m_graph.block(blockIndex);
69                 if (!block)
70                     continue;
71                 fixUpsilons(block);
72             }
73         }
74          
75         return changed;
76     }
77
78 private:
79     bool foldConstants(BasicBlock* block)
80     {
81         bool changed = false;
82         m_state.beginBasicBlock(block);
83         for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
84             if (!m_state.isValid())
85                 break;
86             
87             Node* node = block->at(indexInBlock);
88
89             bool eliminated = false;
90                     
91             switch (node->op()) {
92             case BooleanToNumber: {
93                 if (node->child1().useKind() == UntypedUse
94                     && !m_interpreter.needsTypeCheck(node->child1(), SpecBoolean))
95                     node->child1().setUseKind(BooleanUse);
96                 break;
97             }
98                 
99             case CheckArgumentsNotCreated: {
100                 if (!isEmptySpeculation(
101                         m_state.variables().operand(
102                             m_graph.argumentsRegisterFor(node->origin.semantic)).m_type))
103                     break;
104                 node->convertToPhantom();
105                 eliminated = true;
106                 break;
107             }
108                     
109             case CheckStructure:
110             case ArrayifyToStructure: {
111                 AbstractValue& value = m_state.forNode(node->child1());
112                 StructureSet set;
113                 if (node->op() == ArrayifyToStructure)
114                     set = node->structure();
115                 else
116                     set = node->structureSet();
117                 if (value.m_structure.isSubsetOf(set)) {
118                     m_interpreter.execute(indexInBlock); // Catch the fact that we may filter on cell.
119                     node->convertToPhantom();
120                     eliminated = true;
121                     break;
122                 }
123                 break;
124             }
125                 
126             case CheckArray:
127             case Arrayify: {
128                 if (!node->arrayMode().alreadyChecked(m_graph, node, m_state.forNode(node->child1())))
129                     break;
130                 node->convertToPhantom();
131                 eliminated = true;
132                 break;
133             }
134                 
135             case PutStructure: {
136                 if (m_state.forNode(node->child1()).m_structure.onlyStructure() != node->transition()->next)
137                     break;
138                 
139                 node->convertToPhantom();
140                 eliminated = true;
141                 break;
142             }
143                 
144             case CheckFunction: {
145                 if (m_state.forNode(node->child1()).value() != node->function()->value())
146                     break;
147                 node->convertToPhantom();
148                 eliminated = true;
149                 break;
150             }
151                 
152             case CheckInBounds: {
153                 JSValue left = m_state.forNode(node->child1()).value();
154                 JSValue right = m_state.forNode(node->child2()).value();
155                 if (left && right && left.isInt32() && right.isInt32()
156                     && static_cast<uint32_t>(left.asInt32()) < static_cast<uint32_t>(right.asInt32())) {
157                     node->convertToPhantom();
158                     eliminated = true;
159                     break;
160                 }
161                 
162                 break;
163             }
164                 
165             case MultiGetByOffset: {
166                 Edge baseEdge = node->child1();
167                 Node* base = baseEdge.node();
168                 MultiGetByOffsetData& data = node->multiGetByOffsetData();
169
170                 // First prune the variants, then check if the MultiGetByOffset can be
171                 // strength-reduced to a GetByOffset.
172                 
173                 AbstractValue baseValue = m_state.forNode(base);
174                 
175                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
176                 eliminated = true; // Don't allow the default constant folder to do things to this.
177                 
178                 for (unsigned i = 0; i < data.variants.size(); ++i) {
179                     GetByIdVariant& variant = data.variants[i];
180                     variant.structureSet().filter(baseValue);
181                     if (variant.structureSet().isEmpty()) {
182                         data.variants[i--] = data.variants.last();
183                         data.variants.removeLast();
184                     }
185                 }
186                 
187                 if (data.variants.size() != 1)
188                     break;
189                 
190                 emitGetByOffset(
191                     indexInBlock, node, baseValue, data.variants[0], data.identifierNumber);
192                 break;
193             }
194                 
195             case MultiPutByOffset: {
196                 Edge baseEdge = node->child1();
197                 Node* base = baseEdge.node();
198                 MultiPutByOffsetData& data = node->multiPutByOffsetData();
199                 
200                 AbstractValue baseValue = m_state.forNode(base);
201
202                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
203                 eliminated = true; // Don't allow the default constant folder to do things to this.
204                 
205
206                 for (unsigned i = 0; i < data.variants.size(); ++i) {
207                     PutByIdVariant& variant = data.variants[i];
208                     variant.oldStructure().filter(baseValue);
209                     
210                     if (variant.oldStructure().isEmpty()) {
211                         data.variants[i--] = data.variants.last();
212                         data.variants.removeLast();
213                         continue;
214                     }
215                     
216                     if (variant.kind() == PutByIdVariant::Transition
217                         && variant.oldStructure().onlyStructure() == variant.newStructure()) {
218                         variant = PutByIdVariant::replace(
219                             variant.oldStructure(),
220                             variant.offset());
221                     }
222                 }
223
224                 if (data.variants.size() != 1)
225                     break;
226                 
227                 emitPutByOffset(
228                     indexInBlock, node, baseValue, data.variants[0], data.identifierNumber);
229                 break;
230             }
231         
232             case GetById:
233             case GetByIdFlush: {
234                 Edge childEdge = node->child1();
235                 Node* child = childEdge.node();
236                 unsigned identifierNumber = node->identifierNumber();
237                 
238                 AbstractValue baseValue = m_state.forNode(child);
239
240                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
241                 eliminated = true; // Don't allow the default constant folder to do things to this.
242
243                 if (baseValue.m_structure.isTop() || baseValue.m_structure.isClobbered()
244                     || (node->child1().useKind() == UntypedUse || (baseValue.m_type & ~SpecCell)))
245                     break;
246                 
247                 GetByIdStatus status = GetByIdStatus::computeFor(
248                     vm(), baseValue.m_structure.set(), m_graph.identifiers()[identifierNumber]);
249                 if (!status.isSimple())
250                     break;
251                 
252                 for (unsigned i = status.numVariants(); i--;) {
253                     if (!status[i].constantChecks().isEmpty()
254                         || status[i].alternateBase()) {
255                         // FIXME: We could handle prototype cases.
256                         // https://bugs.webkit.org/show_bug.cgi?id=110386
257                         break;
258                     }
259                 }
260                 
261                 if (status.numVariants() == 1) {
262                     emitGetByOffset(indexInBlock, node, baseValue, status[0], identifierNumber);
263                     break;
264                 }
265                 
266                 if (!isFTL(m_graph.m_plan.mode))
267                     break;
268                 
269                 MultiGetByOffsetData* data = m_graph.m_multiGetByOffsetData.add();
270                 data->variants = status.variants();
271                 data->identifierNumber = identifierNumber;
272                 node->convertToMultiGetByOffset(data);
273                 break;
274             }
275                 
276             case PutById:
277             case PutByIdDirect:
278             case PutByIdFlush: {
279                 NodeOrigin origin = node->origin;
280                 Edge childEdge = node->child1();
281                 Node* child = childEdge.node();
282                 unsigned identifierNumber = node->identifierNumber();
283                 
284                 ASSERT(childEdge.useKind() == CellUse);
285                 
286                 AbstractValue baseValue = m_state.forNode(child);
287
288                 m_interpreter.execute(indexInBlock); // Push CFA over this node after we get the state before.
289                 eliminated = true; // Don't allow the default constant folder to do things to this.
290
291                 if (baseValue.m_structure.isTop() || baseValue.m_structure.isClobbered())
292                     break;
293                 
294                 PutByIdStatus status = PutByIdStatus::computeFor(
295                     vm(),
296                     m_graph.globalObjectFor(origin.semantic),
297                     baseValue.m_structure.set(),
298                     m_graph.identifiers()[identifierNumber],
299                     node->op() == PutByIdDirect);
300                 
301                 if (!status.isSimple())
302                     break;
303                 
304                 for (unsigned i = status.numVariants(); i--;)
305                     addChecks(origin, indexInBlock, status[i].constantChecks());
306                 
307                 if (status.numVariants() == 1) {
308                     emitPutByOffset(indexInBlock, node, baseValue, status[0], identifierNumber);
309                     break;
310                 }
311                 
312                 if (!isFTL(m_graph.m_plan.mode))
313                     break;
314
315                 MultiPutByOffsetData* data = m_graph.m_multiPutByOffsetData.add();
316                 data->variants = status.variants();
317                 data->identifierNumber = identifierNumber;
318                 node->convertToMultiPutByOffset(data);
319                 break;
320             }
321
322             case ToPrimitive: {
323                 if (m_state.forNode(node->child1()).m_type & ~(SpecFullNumber | SpecBoolean | SpecString))
324                     break;
325                 
326                 node->convertToIdentity();
327                 break;
328             }
329                 
330             case GetMyArgumentByVal: {
331                 InlineCallFrame* inlineCallFrame = node->origin.semantic.inlineCallFrame;
332                 JSValue value = m_state.forNode(node->child1()).m_value;
333                 if (inlineCallFrame && value && value.isInt32()) {
334                     int32_t index = value.asInt32();
335                     if (index >= 0
336                         && static_cast<size_t>(index + 1) < inlineCallFrame->arguments.size()) {
337                         // Roll the interpreter over this.
338                         m_interpreter.execute(indexInBlock);
339                         eliminated = true;
340                         
341                         int operand =
342                             inlineCallFrame->stackOffset +
343                             m_graph.baselineCodeBlockFor(inlineCallFrame)->argumentIndexAfterCapture(index);
344                         
345                         m_insertionSet.insertNode(
346                             indexInBlock, SpecNone, CheckArgumentsNotCreated, node->origin);
347                         m_insertionSet.insertNode(
348                             indexInBlock, SpecNone, Phantom, node->origin, node->children);
349                         
350                         node->convertToGetLocalUnlinked(VirtualRegister(operand));
351                         break;
352                     }
353                 }
354                 
355                 break;
356             }
357
358             default:
359                 break;
360             }
361                 
362             if (eliminated) {
363                 changed = true;
364                 continue;
365             }
366                 
367             m_interpreter.execute(indexInBlock);
368             if (!m_state.isValid()) {
369                 // If we invalidated then we shouldn't attempt to constant-fold. Here's an
370                 // example:
371                 //
372                 //     c: JSConstant(4.2)
373                 //     x: ValueToInt32(Check:Int32:@const)
374                 //
375                 // It would be correct for an analysis to assume that execution cannot
376                 // proceed past @x. Therefore, constant-folding @x could be rather bad. But,
377                 // the CFA may report that it found a constant even though it also reported
378                 // that everything has been invalidated. This will only happen in a couple of
379                 // the constant folding cases; most of them are also separately defensive
380                 // about such things.
381                 break;
382             }
383             if (!node->shouldGenerate() || m_state.didClobber() || node->hasConstant())
384                 continue;
385             
386             // Interesting fact: this freezing that we do right here may turn an fragile value into
387             // a weak value. See DFGValueStrength.h.
388             FrozenValue* value = m_graph.freeze(m_state.forNode(node).value());
389             if (!*value)
390                 continue;
391             
392             NodeOrigin origin = node->origin;
393             AdjacencyList children = node->children;
394             
395             m_graph.convertToConstant(node, value);
396             if (!children.isEmpty()) {
397                 m_insertionSet.insertNode(
398                     indexInBlock, SpecNone, Phantom, origin, children);
399             }
400             
401             changed = true;
402         }
403         m_state.reset();
404         m_insertionSet.execute(block);
405         
406         return changed;
407     }
408         
409     void emitGetByOffset(unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const GetByIdVariant& variant, unsigned identifierNumber)
410     {
411         NodeOrigin origin = node->origin;
412         Edge childEdge = node->child1();
413         Node* child = childEdge.node();
414
415         addBaseCheck(indexInBlock, node, baseValue, variant.structureSet());
416         
417         JSValue baseForLoad;
418         if (variant.alternateBase())
419             baseForLoad = variant.alternateBase();
420         else
421             baseForLoad = baseValue.m_value;
422         if (JSValue value = m_graph.tryGetConstantProperty(baseForLoad, variant.baseStructure(), variant.offset())) {
423             m_graph.convertToConstant(node, m_graph.freeze(value));
424             return;
425         }
426         
427         if (variant.alternateBase()) {
428             child = m_insertionSet.insertConstant(indexInBlock, origin, variant.alternateBase());
429             childEdge = Edge(child, KnownCellUse);
430         } else
431             childEdge.setUseKind(KnownCellUse);
432         
433         Edge propertyStorage;
434         
435         if (isInlineOffset(variant.offset()))
436             propertyStorage = childEdge;
437         else {
438             propertyStorage = Edge(m_insertionSet.insertNode(
439                 indexInBlock, SpecNone, GetButterfly, origin, childEdge));
440         }
441         
442         node->convertToGetByOffset(m_graph.m_storageAccessData.size(), propertyStorage);
443         
444         StorageAccessData storageAccessData;
445         storageAccessData.offset = variant.offset();
446         storageAccessData.identifierNumber = identifierNumber;
447         m_graph.m_storageAccessData.append(storageAccessData);
448     }
449
450     void emitPutByOffset(unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const PutByIdVariant& variant, unsigned identifierNumber)
451     {
452         NodeOrigin origin = node->origin;
453         Edge childEdge = node->child1();
454         
455         addBaseCheck(indexInBlock, node, baseValue, variant.oldStructure());
456
457         childEdge.setUseKind(KnownCellUse);
458
459         Transition* transition = 0;
460         if (variant.kind() == PutByIdVariant::Transition) {
461             transition = m_graph.m_transitions.add(
462                 variant.oldStructureForTransition(), variant.newStructure());
463         }
464
465         Edge propertyStorage;
466
467         if (isInlineOffset(variant.offset()))
468             propertyStorage = childEdge;
469         else if (!variant.reallocatesStorage()) {
470             propertyStorage = Edge(m_insertionSet.insertNode(
471                 indexInBlock, SpecNone, GetButterfly, origin, childEdge));
472         } else if (!variant.oldStructureForTransition()->outOfLineCapacity()) {
473             ASSERT(variant.newStructure()->outOfLineCapacity());
474             ASSERT(!isInlineOffset(variant.offset()));
475             Node* allocatePropertyStorage = m_insertionSet.insertNode(
476                 indexInBlock, SpecNone, AllocatePropertyStorage,
477                 origin, OpInfo(transition), childEdge);
478             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
479             propertyStorage = Edge(allocatePropertyStorage);
480         } else {
481             ASSERT(variant.oldStructureForTransition()->outOfLineCapacity());
482             ASSERT(variant.newStructure()->outOfLineCapacity() > variant.oldStructureForTransition()->outOfLineCapacity());
483             ASSERT(!isInlineOffset(variant.offset()));
484
485             Node* reallocatePropertyStorage = m_insertionSet.insertNode(
486                 indexInBlock, SpecNone, ReallocatePropertyStorage, origin,
487                 OpInfo(transition), childEdge,
488                 Edge(m_insertionSet.insertNode(
489                     indexInBlock, SpecNone, GetButterfly, origin, childEdge)));
490             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
491             propertyStorage = Edge(reallocatePropertyStorage);
492         }
493
494         if (variant.kind() == PutByIdVariant::Transition) {
495             Node* putStructure = m_graph.addNode(SpecNone, PutStructure, origin, OpInfo(transition), childEdge);
496             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
497             m_insertionSet.insert(indexInBlock, putStructure);
498         }
499
500         node->convertToPutByOffset(m_graph.m_storageAccessData.size(), propertyStorage);
501         m_insertionSet.insertNode(
502             indexInBlock, SpecNone, StoreBarrier, origin, 
503             Edge(node->child2().node(), KnownCellUse));
504
505         StorageAccessData storageAccessData;
506         storageAccessData.offset = variant.offset();
507         storageAccessData.identifierNumber = identifierNumber;
508         m_graph.m_storageAccessData.append(storageAccessData);
509     }
510     
511     void addBaseCheck(
512         unsigned indexInBlock, Node* node, const AbstractValue& baseValue, const StructureSet& set)
513     {
514         if (!baseValue.m_structure.isSubsetOf(set)) {
515             // Arises when we prune MultiGetByOffset. We could have a
516             // MultiGetByOffset with a single variant that checks for structure S,
517             // and the input has structures S and T, for example.
518             m_insertionSet.insertNode(
519                 indexInBlock, SpecNone, CheckStructure, node->origin,
520                 OpInfo(m_graph.addStructureSet(set)), node->child1());
521             return;
522         }
523         
524         if (baseValue.m_type & ~SpecCell) {
525             m_insertionSet.insertNode(
526                 indexInBlock, SpecNone, Phantom, node->origin, node->child1());
527         }
528     }
529     
530     void addChecks(
531         NodeOrigin origin, unsigned indexInBlock, const ConstantStructureCheckVector& checks)
532     {
533         for (unsigned i = 0; i < checks.size(); ++i) {
534             addStructureTransitionCheck(
535                 origin, indexInBlock, checks[i].constant(), checks[i].structure());
536         }
537     }
538
539     void addStructureTransitionCheck(NodeOrigin origin, unsigned indexInBlock, JSCell* cell, Structure* structure)
540     {
541         if (m_graph.watchpoints().consider(cell->structure()))
542             return;
543
544         Node* weakConstant = m_insertionSet.insertNode(
545             indexInBlock, speculationFromValue(cell), JSConstant, origin,
546             OpInfo(m_graph.freeze(cell)));
547         
548         m_insertionSet.insertNode(
549             indexInBlock, SpecNone, CheckStructure, origin,
550             OpInfo(m_graph.addStructureSet(structure)), Edge(weakConstant, CellUse));
551     }
552     
553     void fixUpsilons(BasicBlock* block)
554     {
555         for (unsigned nodeIndex = block->size(); nodeIndex--;) {
556             Node* node = block->at(nodeIndex);
557             if (node->op() != Upsilon)
558                 continue;
559             switch (node->phi()->op()) {
560             case Phi:
561                 break;
562             case JSConstant:
563             case DoubleConstant:
564             case Int52Constant:
565                 node->convertToPhantom();
566                 break;
567             default:
568                 DFG_CRASH(m_graph, node, "Bad Upsilon phi() pointer");
569                 break;
570             }
571         }
572     }
573     
574     InPlaceAbstractState m_state;
575     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
576     InsertionSet m_insertionSet;
577 };
578
579 bool performConstantFolding(Graph& graph)
580 {
581     SamplingRegion samplingRegion("DFG Constant Folding Phase");
582     return runPhase<ConstantFoldingPhase>(graph);
583 }
584
585 } } // namespace JSC::DFG
586
587 #endif // ENABLE(DFG_JIT)
588
589