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 "DFGTypeCheckHoistingPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGBasicBlock.h"
32#include "DFGGraph.h"
33#include "DFGInsertionSet.h"
34#include "DFGPhase.h"
35#include "DFGVariableAccessDataDump.h"
36#include "JSCInlines.h"
37#include <wtf/HashMap.h>
38
39namespace JSC { namespace DFG {
40
41enum CheckBallot { VoteOther, VoteStructureCheck = 1, VoteCheckArray = 1 };
42
43struct ArrayTypeCheck;
44struct StructureTypeCheck;
45
46struct CheckData {
47    Structure* m_structure;
48    ArrayMode m_arrayMode;
49    bool m_arrayModeIsValid;
50    bool m_arrayModeHoistingOkay;
51
52    CheckData()
53        : m_structure(0)
54        , m_arrayModeIsValid(false)
55        , m_arrayModeHoistingOkay(false)
56    {
57    }
58
59    CheckData(Structure* structure)
60        : m_structure(structure)
61        , m_arrayModeIsValid(false)
62        , m_arrayModeHoistingOkay(true)
63    {
64    }
65
66    CheckData(ArrayMode arrayMode)
67        : m_structure(0)
68        , m_arrayMode(arrayMode)
69        , m_arrayModeIsValid(true)
70        , m_arrayModeHoistingOkay(true)
71    {
72    }
73
74    void disableCheckArrayHoisting()
75    {
76        m_arrayModeIsValid = false;
77        m_arrayModeHoistingOkay = false;
78    }
79};
80
81class TypeCheckHoistingPhase : public Phase {
82public:
83    TypeCheckHoistingPhase(Graph& graph)
84        : Phase(graph, "structure check hoisting")
85    {
86    }
87
88    bool run()
89    {
90        ASSERT(m_graph.m_form == ThreadedCPS);
91
92        clearVariableVotes();
93        identifyRedundantStructureChecks();
94        disableHoistingForVariablesWithInsufficientVotes<StructureTypeCheck>();
95
96        clearVariableVotes();
97        identifyRedundantArrayChecks();
98        disableHoistingForVariablesWithInsufficientVotes<ArrayTypeCheck>();
99
100        disableHoistingAcrossOSREntries<StructureTypeCheck>();
101        disableHoistingAcrossOSREntries<ArrayTypeCheck>();
102
103        bool changed = false;
104
105        // Place CheckStructure's at SetLocal sites.
106        InsertionSet insertionSet(m_graph);
107        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
108            BasicBlock* block = m_graph.block(blockIndex);
109            if (!block)
110                continue;
111            for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
112                Node* node = block->at(indexInBlock);
113                // Be careful not to use 'node' after appending to the graph. In those switch
114                // cases where we need to append, we first carefully extract everything we need
115                // from the node, before doing any appending.
116                switch (node->op()) {
117                case SetArgument: {
118                    ASSERT(!blockIndex);
119                    // Insert a GetLocal and a CheckStructure immediately following this
120                    // SetArgument, if the variable was a candidate for structure hoisting.
121                    // If the basic block previously only had the SetArgument as its
122                    // variable-at-tail, then replace it with this GetLocal.
123                    VariableAccessData* variable = node->variableAccessData();
124                    HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
125                    if (iter == m_map.end())
126                        break;
127                    if (!iter->value.m_structure && !iter->value.m_arrayModeIsValid)
128                        break;
129
130                    NodeOrigin origin = node->origin;
131
132                    Node* getLocal = insertionSet.insertNode(
133                        indexInBlock + 1, variable->prediction(), GetLocal, origin,
134                        OpInfo(variable), Edge(node));
135                    if (iter->value.m_structure) {
136                        insertionSet.insertNode(
137                            indexInBlock + 1, SpecNone, CheckStructure, origin,
138                            OpInfo(m_graph.addStructureSet(iter->value.m_structure)),
139                            Edge(getLocal, CellUse));
140                    } else if (iter->value.m_arrayModeIsValid) {
141                        ASSERT(iter->value.m_arrayModeHoistingOkay);
142                        insertionSet.insertNode(
143                            indexInBlock + 1, SpecNone, CheckArray, origin,
144                            OpInfo(iter->value.m_arrayMode.asWord()),
145                            Edge(getLocal, CellUse));
146                    } else
147                        RELEASE_ASSERT_NOT_REACHED();
148
149                    if (block->variablesAtTail.operand(variable->local()) == node)
150                        block->variablesAtTail.operand(variable->local()) = getLocal;
151
152                    m_graph.substituteGetLocal(*block, indexInBlock, variable, getLocal);
153
154                    changed = true;
155                    break;
156                }
157
158                case SetLocal: {
159                    VariableAccessData* variable = node->variableAccessData();
160                    HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
161                    if (iter == m_map.end())
162                        break;
163                    if (!iter->value.m_structure && !iter->value.m_arrayModeIsValid)
164                        break;
165
166                    NodeOrigin origin = node->origin;
167                    Edge child1 = node->child1();
168
169                    if (iter->value.m_structure) {
170                        insertionSet.insertNode(
171                            indexInBlock, SpecNone, CheckStructure, origin,
172                            OpInfo(m_graph.addStructureSet(iter->value.m_structure)),
173                            Edge(child1.node(), CellUse));
174                    } else if (iter->value.m_arrayModeIsValid) {
175                        ASSERT(iter->value.m_arrayModeHoistingOkay);
176                        insertionSet.insertNode(
177                            indexInBlock, SpecNone, CheckArray, origin,
178                            OpInfo(iter->value.m_arrayMode.asWord()),
179                            Edge(child1.node(), CellUse));
180                    } else
181                        RELEASE_ASSERT_NOT_REACHED();
182                    changed = true;
183                    break;
184                }
185
186                default:
187                    break;
188                }
189            }
190            insertionSet.execute(block);
191        }
192
193        return changed;
194    }
195
196private:
197    void clearVariableVotes()
198    {
199        for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
200            VariableAccessData* variable = &m_graph.m_variableAccessData[i];
201            if (!variable->isRoot())
202                continue;
203            variable->clearVotes();
204        }
205    }
206
207    // Identify the set of variables that are always subject to the same structure
208    // checks. For now, only consider monomorphic structure checks (one structure).
209    void identifyRedundantStructureChecks()
210    {
211        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
212            BasicBlock* block = m_graph.block(blockIndex);
213            if (!block)
214                continue;
215            for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
216                Node* node = block->at(indexInBlock);
217                switch (node->op()) {
218                case CheckStructure:
219                case StructureTransitionWatchpoint: {
220                    Node* child = node->child1().node();
221                    if (child->op() != GetLocal)
222                        break;
223                    VariableAccessData* variable = child->variableAccessData();
224                    variable->vote(VoteStructureCheck);
225                    if (!shouldConsiderForHoisting<StructureTypeCheck>(variable))
226                        break;
227                    noticeStructureCheck(variable, node->structureSet());
228                    break;
229                }
230
231                case GetByOffset:
232                case PutByOffset:
233                case PutStructure:
234                case AllocatePropertyStorage:
235                case ReallocatePropertyStorage:
236                case GetButterfly:
237                case GetByVal:
238                case PutByValDirect:
239                case PutByVal:
240                case PutByValAlias:
241                case GetArrayLength:
242                case CheckArray:
243                case GetIndexedPropertyStorage:
244                case GetTypedArrayByteOffset:
245                case Phantom:
246                case HardPhantom:
247                case MovHint:
248                case MultiGetByOffset:
249                case MultiPutByOffset:
250                    // Don't count these uses.
251                    break;
252
253                case ArrayifyToStructure:
254                case Arrayify:
255                    if (node->arrayMode().conversion() == Array::RageConvert) {
256                        // Rage conversion changes structures. We should avoid tying to do
257                        // any kind of hoisting when rage conversion is in play.
258                        Node* child = node->child1().node();
259                        if (child->op() != GetLocal)
260                            break;
261                        VariableAccessData* variable = child->variableAccessData();
262                        variable->vote(VoteOther);
263                        if (!shouldConsiderForHoisting<StructureTypeCheck>(variable))
264                            break;
265                        noticeStructureCheck(variable, 0);
266                    }
267                    break;
268
269                case SetLocal: {
270                    // Find all uses of the source of the SetLocal. If any of them are a
271                    // kind of CheckStructure, then we should notice them to ensure that
272                    // we're not hoisting a check that would contravene checks that are
273                    // already being performed.
274                    VariableAccessData* variable = node->variableAccessData();
275                    if (!shouldConsiderForHoisting<StructureTypeCheck>(variable))
276                        break;
277                    Node* source = node->child1().node();
278                    for (unsigned subIndexInBlock = 0; subIndexInBlock < block->size(); ++subIndexInBlock) {
279                        Node* subNode = block->at(subIndexInBlock);
280                        switch (subNode->op()) {
281                        case CheckStructure: {
282                            if (subNode->child1() != source)
283                                break;
284
285                            noticeStructureCheck(variable, subNode->structureSet());
286                            break;
287                        }
288                        case StructureTransitionWatchpoint: {
289                            if (subNode->child1() != source)
290                                break;
291
292                            noticeStructureCheck(variable, subNode->structure());
293                            break;
294                        }
295                        default:
296                            break;
297                        }
298                    }
299
300                    m_graph.voteChildren(node, VoteOther);
301                    break;
302                }
303
304                default:
305                    m_graph.voteChildren(node, VoteOther);
306                    break;
307                }
308            }
309        }
310    }
311
312    void identifyRedundantArrayChecks()
313    {
314        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
315            BasicBlock* block = m_graph.block(blockIndex);
316            if (!block)
317                continue;
318            for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
319                Node* node = block->at(indexInBlock);
320                switch (node->op()) {
321                case CheckArray: {
322                    Node* child = node->child1().node();
323                    if (child->op() != GetLocal)
324                        break;
325                    VariableAccessData* variable = child->variableAccessData();
326                    variable->vote(VoteCheckArray);
327                    if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
328                        break;
329                    noticeCheckArray(variable, node->arrayMode());
330                    break;
331                }
332
333                case CheckStructure:
334                case StructureTransitionWatchpoint:
335                case GetByOffset:
336                case PutByOffset:
337                case PutStructure:
338                case ReallocatePropertyStorage:
339                case GetButterfly:
340                case GetByVal:
341                case PutByValDirect:
342                case PutByVal:
343                case PutByValAlias:
344                case GetArrayLength:
345                case GetIndexedPropertyStorage:
346                case Phantom:
347                case HardPhantom:
348                case MovHint:
349                case MultiGetByOffset:
350                case MultiPutByOffset:
351                    // Don't count these uses.
352                    break;
353
354                case AllocatePropertyStorage:
355                case ArrayifyToStructure:
356                case Arrayify: {
357                    // Any Arrayify could change our indexing type, so disable
358                    // all CheckArray hoisting.
359                    Node* child = node->child1().node();
360                    if (child->op() != GetLocal)
361                        break;
362                    VariableAccessData* variable = child->variableAccessData();
363                    variable->vote(VoteOther);
364                    if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
365                        break;
366                    disableCheckArrayHoisting(variable);
367                    break;
368                }
369
370                case SetLocal: {
371                    // Find all uses of the source of the SetLocal. If any of them are a
372                    // kind of CheckStructure, then we should notice them to ensure that
373                    // we're not hoisting a check that would contravene checks that are
374                    // already being performed.
375                    VariableAccessData* variable = node->variableAccessData();
376                    if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
377                        break;
378                    Node* source = node->child1().node();
379                    for (unsigned subIndexInBlock = 0; subIndexInBlock < block->size(); ++subIndexInBlock) {
380                        Node* subNode = block->at(subIndexInBlock);
381                        switch (subNode->op()) {
382                        case CheckStructure: {
383                            if (subNode->child1() != source)
384                                break;
385
386                            noticeStructureCheckAccountingForArrayMode(variable, subNode->structureSet());
387                            break;
388                        }
389                        case StructureTransitionWatchpoint: {
390                            if (subNode->child1() != source)
391                                break;
392
393                            noticeStructureCheckAccountingForArrayMode(variable, subNode->structure());
394                            break;
395                        }
396                        case CheckArray: {
397                            if (subNode->child1() != source)
398                                break;
399                            noticeCheckArray(variable, subNode->arrayMode());
400                            break;
401                        }
402                        default:
403                            break;
404                        }
405                    }
406
407                    m_graph.voteChildren(node, VoteOther);
408                    break;
409                }
410
411                default:
412                    m_graph.voteChildren(node, VoteOther);
413                    break;
414                }
415            }
416        }
417    }
418
419    // Disable hoisting on variables that appear to mostly be used in
420    // contexts where it doesn't make sense.
421    template <typename TypeCheck>
422    void disableHoistingForVariablesWithInsufficientVotes()
423    {
424        for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
425            VariableAccessData* variable = &m_graph.m_variableAccessData[i];
426            if (!variable->isRoot())
427                continue;
428            if (TypeCheck::hasEnoughVotesToHoist(variable))
429                continue;
430            HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
431            if (iter == m_map.end())
432                continue;
433            TypeCheck::disableHoisting(iter->value);
434        }
435    }
436
437    // Disable check hoisting for variables that cross the OSR entry that
438    // we're currently taking, and where the value currently does not have the
439    // particular form we want (e.g. a contradictory ArrayMode or Struture).
440    template <typename TypeCheck>
441    void disableHoistingAcrossOSREntries()
442    {
443        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
444            BasicBlock* block = m_graph.block(blockIndex);
445            if (!block)
446                continue;
447            ASSERT(block->isReachable);
448            if (!block->isOSRTarget)
449                continue;
450            if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex)
451                continue;
452            for (size_t i = 0; i < m_graph.m_plan.mustHandleValues.size(); ++i) {
453                int operand = m_graph.m_plan.mustHandleValues.operandForIndex(i);
454                Node* node = block->variablesAtHead.operand(operand);
455                if (!node)
456                    continue;
457                VariableAccessData* variable = node->variableAccessData();
458                HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
459                if (iter == m_map.end())
460                    continue;
461                if (!TypeCheck::isValidToHoist(iter->value))
462                    continue;
463                JSValue value = m_graph.m_plan.mustHandleValues[i];
464                if (!value || !value.isCell() || TypeCheck::isContravenedByValue(iter->value, value)) {
465                    TypeCheck::disableHoisting(iter->value);
466                    continue;
467                }
468            }
469        }
470    }
471
472    void disableCheckArrayHoisting(VariableAccessData* variable)
473    {
474        HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData());
475        result.iterator->value.disableCheckArrayHoisting();
476    }
477
478    template <typename TypeCheck>
479    bool shouldConsiderForHoisting(VariableAccessData* variable)
480    {
481        if (!variable->shouldUnboxIfPossible())
482            return false;
483        if (TypeCheck::hoistingPreviouslyFailed(variable))
484            return false;
485        if (!isCellSpeculation(variable->prediction()))
486            return false;
487        return true;
488    }
489
490    void noticeStructureCheck(VariableAccessData* variable, Structure* structure)
491    {
492        HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData(structure));
493        if (result.isNewEntry)
494            return;
495        if (result.iterator->value.m_structure == structure)
496            return;
497        result.iterator->value.m_structure = 0;
498    }
499
500    void noticeStructureCheck(VariableAccessData* variable, const StructureSet& set)
501    {
502        if (set.size() != 1) {
503            noticeStructureCheck(variable, 0);
504            return;
505        }
506        noticeStructureCheck(variable, set.singletonStructure());
507    }
508
509    void noticeCheckArray(VariableAccessData* variable, ArrayMode arrayMode)
510    {
511        HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData(arrayMode));
512        if (result.isNewEntry)
513            return;
514        if (!result.iterator->value.m_arrayModeHoistingOkay)
515            return;
516        if (result.iterator->value.m_arrayMode == arrayMode)
517            return;
518        if (!result.iterator->value.m_arrayModeIsValid) {
519            result.iterator->value.m_arrayMode = arrayMode;
520            result.iterator->value.m_arrayModeIsValid = true;
521            return;
522        }
523        result.iterator->value.disableCheckArrayHoisting();
524    }
525
526    void noticeStructureCheckAccountingForArrayMode(VariableAccessData* variable, Structure* structure)
527    {
528        HashMap<VariableAccessData*, CheckData>::iterator result = m_map.find(variable);
529        if (result == m_map.end())
530            return;
531        if (!result->value.m_arrayModeHoistingOkay || !result->value.m_arrayModeIsValid)
532            return;
533        if (result->value.m_arrayMode.structureWouldPassArrayModeFiltering(structure))
534            return;
535        result->value.disableCheckArrayHoisting();
536    }
537
538    void noticeStructureCheckAccountingForArrayMode(VariableAccessData* variable, const StructureSet& set)
539    {
540        for (unsigned i = 0; i < set.size(); i++)
541            noticeStructureCheckAccountingForArrayMode(variable, set[i]);
542    }
543
544    HashMap<VariableAccessData*, CheckData> m_map;
545};
546
547bool performTypeCheckHoisting(Graph& graph)
548{
549    SamplingRegion samplingRegion("DFG Type Check Hoisting Phase");
550    return runPhase<TypeCheckHoistingPhase>(graph);
551}
552
553struct ArrayTypeCheck {
554    static bool isValidToHoist(CheckData& checkData)
555    {
556        return checkData.m_arrayModeIsValid;
557    }
558
559    static void disableHoisting(CheckData& checkData)
560    {
561        checkData.disableCheckArrayHoisting();
562    }
563
564    static bool isContravenedByValue(CheckData& checkData, JSValue value)
565    {
566        ASSERT(value.isCell());
567        return !checkData.m_arrayMode.structureWouldPassArrayModeFiltering(value.asCell()->structure());
568    }
569
570    static bool hasEnoughVotesToHoist(VariableAccessData* variable)
571    {
572        return variable->voteRatio() >= Options::checkArrayVoteRatioForHoisting();
573    }
574
575    static bool hoistingPreviouslyFailed(VariableAccessData* variable)
576    {
577        return variable->checkArrayHoistingFailed();
578    }
579};
580
581struct StructureTypeCheck {
582    static bool isValidToHoist(CheckData& checkData)
583    {
584        return checkData.m_structure;
585    }
586
587    static void disableHoisting(CheckData& checkData)
588    {
589        checkData.m_structure = 0;
590    }
591
592    static bool isContravenedByValue(CheckData& checkData, JSValue value)
593    {
594        ASSERT(value.isCell());
595        return checkData.m_structure != value.asCell()->structure();
596    }
597
598    static bool hasEnoughVotesToHoist(VariableAccessData* variable)
599    {
600        return variable->voteRatio() >= Options::structureCheckVoteRatioForHoisting();
601    }
602
603    static bool hoistingPreviouslyFailed(VariableAccessData* variable)
604    {
605        return variable->structureCheckHoistingFailed();
606    }
607};
608
609} } // namespace JSC::DFG
610
611#endif // ENABLE(DFG_JIT)
612
613
614