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