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
41namespace JSC { namespace DFG {
42
43class ConstantFoldingPhase : public Phase {
44public:
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
68private:
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
505bool 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
516