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