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