Bmalloc and GC should put auxiliaries (butterflies, typed array backing stores) in...
[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 GetButterflyWithoutCaging:
252                 case GetByVal:
253                 case PutByValDirect:
254                 case PutByVal:
255                 case PutByValAlias:
256                 case GetArrayLength:
257                 case CheckArray:
258                 case GetIndexedPropertyStorage:
259                 case GetTypedArrayByteOffset:
260                 case Phantom:
261                 case MovHint:
262                 case MultiGetByOffset:
263                 case MultiPutByOffset:
264                     // Don't count these uses.
265                     break;
266                     
267                 case SetLocal: {
268                     // Find all uses of the source of the SetLocal. If any of them are a
269                     // kind of CheckStructure, then we should notice them to ensure that
270                     // we're not hoisting a check that would contravene checks that are
271                     // already being performed.
272                     VariableAccessData* variable = node->variableAccessData();
273                     if (!shouldConsiderForHoisting<StructureTypeCheck>(variable))
274                         break;
275                     Node* source = node->child1().node();
276                     for (auto* subNode : *block) {
277                         switch (subNode->op()) {
278                         case CheckStructure: {
279                             if (subNode->child1() != source)
280                                 break;
281                             
282                             noticeStructureCheck(variable, subNode->structureSet());
283                             break;
284                         }
285                         default:
286                             break;
287                         }
288                     }
289                     
290                     m_graph.voteChildren(node, VoteOther);
291                     break;
292                 }
293                     
294                 default:
295                     m_graph.voteChildren(node, VoteOther);
296                     break;
297                 }
298             }
299         }
300     }
301         
302     void identifyRedundantArrayChecks()
303     {
304         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
305             BasicBlock* block = m_graph.block(blockIndex);
306             if (!block)
307                 continue;
308             for (auto* node : *block) {
309                 switch (node->op()) {
310                 case CheckArray: {
311                     Node* child = node->child1().node();
312                     if (child->op() != GetLocal)
313                         break;
314                     VariableAccessData* variable = child->variableAccessData();
315                     variable->vote(VoteCheckArray);
316                     if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
317                         break;
318                     noticeCheckArray(variable, node->arrayMode());
319                     break;
320                 }
321
322                 case CheckStructure:
323                 case GetByOffset:
324                 case PutByOffset:
325                 case PutStructure:
326                 case ReallocatePropertyStorage:
327                 case GetButterfly:
328                 case GetButterflyWithoutCaging:
329                 case GetByVal:
330                 case PutByValDirect:
331                 case PutByVal:
332                 case PutByValAlias:
333                 case GetArrayLength:
334                 case GetIndexedPropertyStorage:
335                 case Phantom:
336                 case MovHint:
337                 case MultiGetByOffset:
338                 case MultiPutByOffset:
339                     // Don't count these uses.
340                     break;
341                     
342                 case AllocatePropertyStorage:
343                 case ArrayifyToStructure:
344                 case Arrayify: {
345                     // Any Arrayify could change our indexing type, so disable
346                     // all CheckArray hoisting.
347                     Node* child = node->child1().node();
348                     if (child->op() != GetLocal)
349                         break;
350                     VariableAccessData* variable = child->variableAccessData();
351                     variable->vote(VoteOther);
352                     if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
353                         break;
354                     disableCheckArrayHoisting(variable);
355                     break;
356                 }
357                     
358                 case SetLocal: {
359                     // Find all uses of the source of the SetLocal. If any of them are a
360                     // kind of CheckStructure, then we should notice them to ensure that
361                     // we're not hoisting a check that would contravene checks that are
362                     // already being performed.
363                     VariableAccessData* variable = node->variableAccessData();
364                     if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
365                         break;
366                     Node* source = node->child1().node();
367                     for (auto subNode : *block) {
368                         switch (subNode->op()) {
369                         case CheckStructure: {
370                             if (subNode->child1() != source)
371                                 break;
372                             
373                             noticeStructureCheckAccountingForArrayMode(variable, subNode->structureSet());
374                             break;
375                         }
376                         case CheckArray: {
377                             if (subNode->child1() != source)
378                                 break;
379                             noticeCheckArray(variable, subNode->arrayMode());
380                             break;
381                         }
382                         default:
383                             break;
384                         }
385                     }
386                     
387                     m_graph.voteChildren(node, VoteOther);
388                     break;
389                 }
390                     
391                 default:
392                     m_graph.voteChildren(node, VoteOther);
393                     break;
394                 }
395             }
396         }
397     }
398
399     // Disable hoisting on variables that appear to mostly be used in
400     // contexts where it doesn't make sense.
401     template <typename TypeCheck>
402     void disableHoistingForVariablesWithInsufficientVotes()
403     {    
404         for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
405             VariableAccessData* variable = &m_graph.m_variableAccessData[i];
406             if (!variable->isRoot())
407                 continue;
408             if (TypeCheck::hasEnoughVotesToHoist(variable))
409                 continue;
410             HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
411             if (iter == m_map.end())
412                 continue;
413             TypeCheck::disableHoisting(iter->value);
414         }
415     }
416
417     // Disable check hoisting for variables that cross the OSR entry that
418     // we're currently taking, and where the value currently does not have the
419     // particular form we want (e.g. a contradictory ArrayMode or Struture).
420     template <typename TypeCheck>
421     void disableHoistingAcrossOSREntries()
422     {
423         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
424             BasicBlock* block = m_graph.block(blockIndex);
425             if (!block)
426                 continue;
427             ASSERT(block->isReachable);
428             if (!block->isOSRTarget)
429                 continue;
430             if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex)
431                 continue;
432             for (size_t i = 0; i < m_graph.m_plan.mustHandleValues.size(); ++i) {
433                 int operand = m_graph.m_plan.mustHandleValues.operandForIndex(i);
434                 Node* node = block->variablesAtHead.operand(operand);
435                 if (!node)
436                     continue;
437                 VariableAccessData* variable = node->variableAccessData();
438                 HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
439                 if (iter == m_map.end())
440                     continue;
441                 if (!TypeCheck::isValidToHoist(iter->value))
442                     continue;
443                 JSValue value = m_graph.m_plan.mustHandleValues[i];
444                 if (!value || !value.isCell() || TypeCheck::isContravenedByValue(iter->value, value)) {
445                     TypeCheck::disableHoisting(iter->value);
446                     continue;
447                 }
448             }
449         }
450     }
451
452     void disableCheckArrayHoisting(VariableAccessData* variable)
453     {
454         HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData());
455         result.iterator->value.disableCheckArrayHoisting();
456     }
457
458     template <typename TypeCheck>
459     bool shouldConsiderForHoisting(VariableAccessData* variable)
460     {
461         if (!variable->shouldUnboxIfPossible())
462             return false;
463         if (TypeCheck::hoistingPreviouslyFailed(variable))
464             return false;
465         if (!isCellSpeculation(variable->prediction()))
466             return false;
467         return true;
468     }
469     
470     void noticeStructureCheck(VariableAccessData* variable, RegisteredStructure structure)
471     {
472         HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData(structure.get()));
473         if (result.isNewEntry)
474             return;
475         if (result.iterator->value.m_structure == structure.get())
476             return;
477         result.iterator->value.m_structure = 0;
478     }
479     
480     void noticeStructureCheck(VariableAccessData* variable, RegisteredStructureSet set)
481     {
482         if (set.size() != 1) {
483             noticeStructureCheck(variable, RegisteredStructure());
484             return;
485         }
486         noticeStructureCheck(variable, set.at(0));
487     }
488
489     void noticeCheckArray(VariableAccessData* variable, ArrayMode arrayMode)
490     {
491         HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData(arrayMode));
492         if (result.isNewEntry)
493             return;
494         if (!result.iterator->value.m_arrayModeHoistingOkay)
495             return;
496         if (result.iterator->value.m_arrayMode == arrayMode)
497             return;
498         if (!result.iterator->value.m_arrayModeIsValid) {
499             result.iterator->value.m_arrayMode = arrayMode;
500             result.iterator->value.m_arrayModeIsValid = true;
501             return;
502         }
503         result.iterator->value.disableCheckArrayHoisting();
504     }
505
506     void noticeStructureCheckAccountingForArrayMode(VariableAccessData* variable, RegisteredStructure structure)
507     {
508         HashMap<VariableAccessData*, CheckData>::iterator result = m_map.find(variable);
509         if (result == m_map.end())
510             return;
511         if (!result->value.m_arrayModeHoistingOkay || !result->value.m_arrayModeIsValid)
512             return;
513         if (result->value.m_arrayMode.structureWouldPassArrayModeFiltering(structure.get()))
514             return;
515         result->value.disableCheckArrayHoisting();
516     }
517
518     void noticeStructureCheckAccountingForArrayMode(VariableAccessData* variable, RegisteredStructureSet set)
519     {
520         for (unsigned i = 0; i < set.size(); i++)
521             noticeStructureCheckAccountingForArrayMode(variable, set.at(i));
522     }
523
524     HashMap<VariableAccessData*, CheckData> m_map;
525 };
526
527 bool performTypeCheckHoisting(Graph& graph)
528 {
529     return runPhase<TypeCheckHoistingPhase>(graph);
530 }
531
532 struct ArrayTypeCheck {
533     static bool isValidToHoist(CheckData& checkData)
534     {
535         return checkData.m_arrayModeIsValid;
536     }
537
538     static void disableHoisting(CheckData& checkData)
539     {
540         checkData.disableCheckArrayHoisting();
541     }
542
543     static bool isContravenedByValue(CheckData& checkData, JSValue value)
544     {
545         ASSERT(value.isCell());
546         return !checkData.m_arrayMode.structureWouldPassArrayModeFiltering(value.asCell()->structure());
547     }
548
549     static bool hasEnoughVotesToHoist(VariableAccessData* variable)
550     {
551         return variable->voteRatio() >= Options::checkArrayVoteRatioForHoisting();
552     }
553
554     static bool hoistingPreviouslyFailed(VariableAccessData* variable)
555     {
556         return variable->checkArrayHoistingFailed();
557     }
558 };
559
560 struct StructureTypeCheck {
561     static bool isValidToHoist(CheckData& checkData)
562     {
563         return checkData.m_structure;
564     }
565
566     static void disableHoisting(CheckData& checkData)
567     {
568         checkData.m_structure = 0;
569     }
570
571     static bool isContravenedByValue(CheckData& checkData, JSValue value)
572     {
573         ASSERT(value.isCell());
574         return checkData.m_structure != value.asCell()->structure();
575     }
576
577     static bool hasEnoughVotesToHoist(VariableAccessData* variable)
578     {
579         return variable->voteRatio() >= Options::structureCheckVoteRatioForHoisting();
580     }
581
582     static bool hoistingPreviouslyFailed(VariableAccessData* variable)
583     {
584         return variable->structureCheckHoistingFailed();
585     }
586 };
587
588 } } // namespace JSC::DFG
589
590 #endif // ENABLE(DFG_JIT)
591
592