1/*
2 * Copyright (C) 2012, 2013 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 "DFGAbstractState.h"
32#include "DFGBasicBlock.h"
33#include "DFGGraph.h"
34#include "DFGInsertionSet.h"
35#include "DFGPhase.h"
36#include "GetByIdStatus.h"
37#include "Operations.h"
38#include "PutByIdStatus.h"
39
40namespace JSC { namespace DFG {
41
42class ConstantFoldingPhase : public Phase {
43public:
44    ConstantFoldingPhase(Graph& graph)
45        : Phase(graph, "constant folding")
46        , m_state(graph)
47        , m_insertionSet(graph)
48    {
49    }
50
51    bool run()
52    {
53        bool changed = false;
54
55        for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
56            BasicBlock* block = m_graph.m_blocks[blockIndex].get();
57            if (!block)
58                continue;
59            if (!block->cfaDidFinish)
60                changed |= paintUnreachableCode(blockIndex);
61            if (block->cfaFoundConstants)
62                changed |= foldConstants(blockIndex);
63        }
64
65        return changed;
66    }
67
68private:
69    bool foldConstants(BlockIndex blockIndex)
70    {
71#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
72        dataLogF("Constant folding considering Block #%u.\n", blockIndex);
73#endif
74        BasicBlock* block = m_graph.m_blocks[blockIndex].get();
75        bool changed = false;
76        m_state.beginBasicBlock(block);
77        for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
78            if (!m_state.isValid())
79                break;
80
81            Node* node = block->at(indexInBlock);
82
83            bool eliminated = false;
84
85            switch (node->op()) {
86            case CheckArgumentsNotCreated: {
87                if (!isEmptySpeculation(
88                        m_state.variables().operand(
89                            m_graph.argumentsRegisterFor(node->codeOrigin)).m_type))
90                    break;
91                node->convertToPhantom();
92                eliminated = true;
93                break;
94            }
95
96            case CheckStructure:
97            case ForwardCheckStructure:
98            case ArrayifyToStructure: {
99                AbstractValue& value = m_state.forNode(node->child1());
100                StructureSet set;
101                if (node->op() == ArrayifyToStructure)
102                    set = node->structure();
103                else
104                    set = node->structureSet();
105                if (value.m_currentKnownStructure.isSubsetOf(set)) {
106                    m_state.execute(indexInBlock); // Catch the fact that we may filter on cell.
107                    node->convertToPhantom();
108                    eliminated = true;
109                    break;
110                }
111                StructureAbstractValue& structureValue = value.m_futurePossibleStructure;
112                if (structureValue.isSubsetOf(set)
113                    && structureValue.hasSingleton()) {
114                    Structure* structure = structureValue.singleton();
115                    m_state.execute(indexInBlock); // Catch the fact that we may filter on cell.
116                    node->convertToStructureTransitionWatchpoint(structure);
117                    eliminated = true;
118                    break;
119                }
120                break;
121            }
122
123            case CheckArray:
124            case Arrayify: {
125                if (!node->arrayMode().alreadyChecked(m_graph, node, m_state.forNode(node->child1())))
126                    break;
127                node->convertToPhantom();
128                eliminated = true;
129                break;
130            }
131
132            case CheckFunction: {
133                if (m_state.forNode(node->child1()).value() != node->function())
134                    break;
135                node->convertToPhantom();
136                eliminated = true;
137                break;
138            }
139
140            case GetById:
141            case GetByIdFlush: {
142                CodeOrigin codeOrigin = node->codeOrigin;
143                Edge childEdge = node->child1();
144                Node* child = childEdge.node();
145                unsigned identifierNumber = node->identifierNumber();
146
147                if (childEdge.useKind() != CellUse)
148                    break;
149
150                Structure* structure = m_state.forNode(child).bestProvenStructure();
151                if (!structure)
152                    break;
153
154                bool needsWatchpoint = !m_state.forNode(child).m_currentKnownStructure.hasSingleton();
155                bool needsCellCheck = m_state.forNode(child).m_type & ~SpecCell;
156
157                GetByIdStatus status = GetByIdStatus::computeFor(
158                    vm(), structure, codeBlock()->identifier(identifierNumber));
159
160                if (!status.isSimple()) {
161                    // FIXME: We could handle prototype cases.
162                    // https://bugs.webkit.org/show_bug.cgi?id=110386
163                    break;
164                }
165
166                ASSERT(status.structureSet().size() == 1);
167                ASSERT(status.chain().isEmpty());
168                ASSERT(status.structureSet().singletonStructure() == structure);
169
170                // Now before we do anything else, push the CFA forward over the GetById
171                // and make sure we signal to the loop that it should continue and not
172                // do any eliminations.
173                m_state.execute(indexInBlock);
174                eliminated = true;
175
176                if (needsWatchpoint) {
177                    ASSERT(m_state.forNode(child).m_futurePossibleStructure.isSubsetOf(StructureSet(structure)));
178                    m_insertionSet.insertNode(
179                        indexInBlock, SpecNone, StructureTransitionWatchpoint, codeOrigin,
180                        OpInfo(structure), childEdge);
181                } else if (needsCellCheck) {
182                    m_insertionSet.insertNode(
183                        indexInBlock, SpecNone, Phantom, codeOrigin, childEdge);
184                }
185
186                childEdge.setUseKind(KnownCellUse);
187
188                Edge propertyStorage;
189
190                if (isInlineOffset(status.offset()))
191                    propertyStorage = childEdge;
192                else {
193                    propertyStorage = Edge(m_insertionSet.insertNode(
194                        indexInBlock, SpecNone, GetButterfly, codeOrigin, childEdge));
195                }
196
197                node->convertToGetByOffset(m_graph.m_storageAccessData.size(), propertyStorage);
198
199                StorageAccessData storageAccessData;
200                storageAccessData.offset = indexRelativeToBase(status.offset());
201                storageAccessData.identifierNumber = identifierNumber;
202                m_graph.m_storageAccessData.append(storageAccessData);
203                break;
204            }
205
206            case PutById:
207            case PutByIdDirect: {
208                CodeOrigin codeOrigin = node->codeOrigin;
209                Edge childEdge = node->child1();
210                Node* child = childEdge.node();
211                unsigned identifierNumber = node->identifierNumber();
212
213                ASSERT(childEdge.useKind() == CellUse);
214
215                Structure* structure = m_state.forNode(child).bestProvenStructure();
216                if (!structure)
217                    break;
218
219                bool needsWatchpoint = !m_state.forNode(child).m_currentKnownStructure.hasSingleton();
220                bool needsCellCheck = m_state.forNode(child).m_type & ~SpecCell;
221
222                PutByIdStatus status = PutByIdStatus::computeFor(
223                    vm(),
224                    m_graph.globalObjectFor(codeOrigin),
225                    structure,
226                    codeBlock()->identifier(identifierNumber),
227                    node->op() == PutByIdDirect);
228
229                if (!status.isSimpleReplace() && !status.isSimpleTransition())
230                    break;
231
232                ASSERT(status.oldStructure() == structure);
233
234                // Now before we do anything else, push the CFA forward over the PutById
235                // and make sure we signal to the loop that it should continue and not
236                // do any eliminations.
237                m_state.execute(indexInBlock);
238                eliminated = true;
239
240                if (needsWatchpoint) {
241                    ASSERT(m_state.forNode(child).m_futurePossibleStructure.isSubsetOf(StructureSet(structure)));
242                    m_insertionSet.insertNode(
243                        indexInBlock, SpecNone, StructureTransitionWatchpoint, codeOrigin,
244                        OpInfo(structure), childEdge);
245                } else if (needsCellCheck) {
246                    m_insertionSet.insertNode(
247                        indexInBlock, SpecNone, Phantom, codeOrigin, childEdge);
248                }
249
250                childEdge.setUseKind(KnownCellUse);
251
252                StructureTransitionData* transitionData = 0;
253                if (status.isSimpleTransition()) {
254                    transitionData = m_graph.addStructureTransitionData(
255                        StructureTransitionData(structure, status.newStructure()));
256
257                    if (node->op() == PutById) {
258                        if (!structure->storedPrototype().isNull()) {
259                            addStructureTransitionCheck(
260                                codeOrigin, indexInBlock,
261                                structure->storedPrototype().asCell());
262                        }
263
264                        for (WriteBarrier<Structure>* it = status.structureChain()->head(); *it; ++it) {
265                            JSValue prototype = (*it)->storedPrototype();
266                            if (prototype.isNull())
267                                continue;
268                            ASSERT(prototype.isCell());
269                            addStructureTransitionCheck(
270                                codeOrigin, indexInBlock, prototype.asCell());
271                        }
272                    }
273                }
274
275                Edge propertyStorage;
276
277                if (isInlineOffset(status.offset()))
278                    propertyStorage = childEdge;
279                else if (status.isSimpleReplace() || structure->outOfLineCapacity() == status.newStructure()->outOfLineCapacity()) {
280                    propertyStorage = Edge(m_insertionSet.insertNode(
281                        indexInBlock, SpecNone, GetButterfly, codeOrigin, childEdge));
282                } else if (!structure->outOfLineCapacity()) {
283                    ASSERT(status.newStructure()->outOfLineCapacity());
284                    ASSERT(!isInlineOffset(status.offset()));
285                    propertyStorage = Edge(m_insertionSet.insertNode(
286                        indexInBlock, SpecNone, AllocatePropertyStorage,
287                        codeOrigin, OpInfo(transitionData), childEdge));
288                } else {
289                    ASSERT(structure->outOfLineCapacity());
290                    ASSERT(status.newStructure()->outOfLineCapacity() > structure->outOfLineCapacity());
291                    ASSERT(!isInlineOffset(status.offset()));
292
293                    propertyStorage = Edge(m_insertionSet.insertNode(
294                        indexInBlock, SpecNone, ReallocatePropertyStorage, codeOrigin,
295                        OpInfo(transitionData), childEdge,
296                        Edge(m_insertionSet.insertNode(
297                            indexInBlock, SpecNone, GetButterfly, codeOrigin, childEdge))));
298                }
299
300                if (status.isSimpleTransition()) {
301                    m_insertionSet.insertNode(
302                        indexInBlock, SpecNone, PutStructure, codeOrigin,
303                        OpInfo(transitionData), childEdge);
304                }
305
306                node->convertToPutByOffset(m_graph.m_storageAccessData.size(), propertyStorage);
307
308                StorageAccessData storageAccessData;
309                storageAccessData.offset = indexRelativeToBase(status.offset());
310                storageAccessData.identifierNumber = identifierNumber;
311                m_graph.m_storageAccessData.append(storageAccessData);
312                break;
313            }
314
315            default:
316                break;
317            }
318
319            if (eliminated) {
320                changed = true;
321                continue;
322            }
323
324            m_state.execute(indexInBlock);
325            if (!node->shouldGenerate() || m_state.didClobber() || node->hasConstant())
326                continue;
327            JSValue value = m_state.forNode(node).value();
328            if (!value)
329                continue;
330
331            CodeOrigin codeOrigin = node->codeOrigin;
332            AdjacencyList children = node->children;
333
334            if (node->op() == GetLocal) {
335                // GetLocals without a Phi child are guaranteed dead. We don't have to
336                // do anything about them.
337                if (!node->child1())
338                    continue;
339
340                if (m_graph.m_form != LoadStore) {
341                    VariableAccessData* variable = node->variableAccessData();
342                    Node* phi = node->child1().node();
343                    if (phi->op() == Phi
344                        && block->variablesAtHead.operand(variable->local()) == phi
345                        && block->variablesAtTail.operand(variable->local()) == node) {
346
347                        // Keep the graph threaded for easy cases. This is improves compile
348                        // times. It would be correct to just dethread here.
349
350                        m_graph.convertToConstant(node, value);
351                        Node* phantom = m_insertionSet.insertNode(
352                            indexInBlock, SpecNone, PhantomLocal,  codeOrigin,
353                            OpInfo(variable), Edge(phi));
354                        block->variablesAtHead.operand(variable->local()) = phantom;
355                        block->variablesAtTail.operand(variable->local()) = phantom;
356
357                        changed = true;
358
359                        continue;
360                    }
361
362                    m_graph.dethread();
363                }
364            } else
365                ASSERT(!node->hasVariableAccessData());
366
367            m_graph.convertToConstant(node, value);
368            m_insertionSet.insertNode(
369                indexInBlock, SpecNone, Phantom, codeOrigin, children);
370
371            changed = true;
372        }
373        m_state.reset();
374        m_insertionSet.execute(block);
375
376        return changed;
377    }
378
379#if !ASSERT_DISABLED
380    bool isCapturedAtOrAfter(BasicBlock* block, unsigned indexInBlock, int operand)
381    {
382        for (; indexInBlock < block->size(); ++indexInBlock) {
383            Node* node = block->at(indexInBlock);
384            if (!node->hasLocal())
385                continue;
386            if (node->local() != operand)
387                continue;
388            if (node->variableAccessData()->isCaptured())
389                return true;
390        }
391        return false;
392    }
393#endif // !ASSERT_DISABLED
394
395    void addStructureTransitionCheck(CodeOrigin codeOrigin, unsigned indexInBlock, JSCell* cell)
396    {
397        Node* weakConstant = m_insertionSet.insertNode(
398            indexInBlock, speculationFromValue(cell), WeakJSConstant, codeOrigin, OpInfo(cell));
399
400        if (cell->structure()->transitionWatchpointSetIsStillValid()) {
401            m_insertionSet.insertNode(
402                indexInBlock, SpecNone, StructureTransitionWatchpoint, codeOrigin,
403                OpInfo(cell->structure()), Edge(weakConstant, CellUse));
404            return;
405        }
406
407        m_insertionSet.insertNode(
408            indexInBlock, SpecNone, CheckStructure, codeOrigin,
409            OpInfo(m_graph.addStructureSet(cell->structure())), Edge(weakConstant, CellUse));
410    }
411
412    // This is necessary because the CFA may reach conclusions about constants based on its
413    // assumption that certain code must exit, but then those constants may lead future
414    // reexecutions of the CFA to believe that the same code will now no longer exit. Thus
415    // to ensure soundness, we must paint unreachable code as such, by inserting an
416    // unconditional ForceOSRExit wherever we find that a node would have always exited.
417    // This will only happen in cases where we are making static speculations, or we're
418    // making totally wrong speculations due to imprecision on the prediction propagator.
419    bool paintUnreachableCode(BlockIndex blockIndex)
420    {
421        bool changed = false;
422
423#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
424        dataLogF("Painting unreachable code in Block #%u.\n", blockIndex);
425#endif
426        BasicBlock* block = m_graph.m_blocks[blockIndex].get();
427        m_state.beginBasicBlock(block);
428
429        for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
430            m_state.execute(indexInBlock);
431            if (m_state.isValid())
432                continue;
433
434            Node* node = block->at(indexInBlock);
435            switch (node->op()) {
436            case Return:
437            case Unreachable:
438            case ForceOSRExit:
439                // Do nothing. These nodes will already do the right thing.
440                break;
441
442            default:
443                m_insertionSet.insertNode(
444                    indexInBlock, SpecNone, ForceOSRExit, node->codeOrigin);
445                changed = true;
446                break;
447            }
448            break;
449        }
450        m_state.reset();
451        m_insertionSet.execute(block);
452
453        return changed;
454    }
455
456    AbstractState m_state;
457    InsertionSet m_insertionSet;
458};
459
460bool performConstantFolding(Graph& graph)
461{
462    SamplingRegion samplingRegion("DFG Constant Folding Phase");
463    return runPhase<ConstantFoldingPhase>(graph);
464}
465
466} } // namespace JSC::DFG
467
468#endif // ENABLE(DFG_JIT)
469
470
471