22b9395b56a1d10a4907178b61685d1278f4141e
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGStructureCheckHoistingPhase.cpp
1 /*
2  * Copyright (C) 2012 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 "DFGStructureCheckHoistingPhase.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 <wtf/HashMap.h>
36
37 namespace JSC { namespace DFG {
38
39 enum CheckBallot { VoteOther, VoteStructureCheck };
40
41 class StructureCheckHoistingPhase : public Phase {
42 public:
43     StructureCheckHoistingPhase(Graph& graph)
44         : Phase(graph, "structure check hoisting")
45     {
46     }
47     
48     bool run()
49     {
50         for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
51             VariableAccessData* variable = &m_graph.m_variableAccessData[i];
52             if (!variable->isRoot())
53                 continue;
54             variable->clearVotes();
55         }
56         
57         // Identify the set of variables that are always subject to the same structure
58         // checks. For now, only consider monomorphic structure checks (one structure).
59         
60         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
61             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
62             if (!block)
63                 continue;
64             for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
65                 NodeIndex nodeIndex = block->at(indexInBlock);
66                 Node& node = m_graph[nodeIndex];
67                 if (!node.shouldGenerate())
68                     continue;
69                 switch (node.op()) {
70                 case CheckStructure:
71                 case StructureTransitionWatchpoint: {
72                     Node& child = m_graph[node.child1()];
73                     if (child.op() != GetLocal)
74                         break;
75                     VariableAccessData* variable = child.variableAccessData();
76                     variable->vote(VoteStructureCheck);
77                     if (variable->isCaptured() || variable->structureCheckHoistingFailed())
78                         break;
79                     if (!isCellSpeculation(variable->prediction()))
80                         break;
81                     noticeStructureCheck(variable, node.structureSet());
82                     break;
83                 }
84                     
85                 case ForwardCheckStructure:
86                 case ForwardStructureTransitionWatchpoint:
87                     // We currently rely on the fact that we're the only ones who would
88                     // insert this node.
89                     ASSERT_NOT_REACHED();
90                     break;
91                     
92                 case GetByOffset:
93                 case PutByOffset:
94                 case PutStructure:
95                 case AllocatePropertyStorage:
96                 case ReallocatePropertyStorage:
97                 case GetButterfly:
98                 case GetByVal:
99                 case PutByVal:
100                 case PutByValAlias:
101                 case GetArrayLength:
102                 case CheckArray:
103                 case GetIndexedPropertyStorage:
104                 case Phantom:
105                     // Don't count these uses.
106                     break;
107                     
108                 case SetLocal: {
109                     // Find all uses of the source of the SetLocal. If any of them are a
110                     // kind of CheckStructure, then we should notice them to ensure that
111                     // we're not hoisting a check that would contravene checks that are
112                     // already being performed.
113                     VariableAccessData* variable = node.variableAccessData();
114                     if (variable->isCaptured() || variable->structureCheckHoistingFailed())
115                         break;
116                     if (!isCellSpeculation(variable->prediction()))
117                         break;
118                     NodeIndex source = node.child1().index();
119                     for (unsigned subIndexInBlock = 0; subIndexInBlock < block->size(); ++subIndexInBlock) {
120                         NodeIndex subNodeIndex = block->at(subIndexInBlock);
121                         Node& subNode = m_graph[subNodeIndex];
122                         if (!subNode.shouldGenerate())
123                             continue;
124                         switch (subNode.op()) {
125                         case CheckStructure: {
126                             if (subNode.child1().index() != source)
127                                 break;
128                             
129                             noticeStructureCheck(variable, subNode.structureSet());
130                             break;
131                         }
132                         case StructureTransitionWatchpoint: {
133                             if (subNode.child1().index() != source)
134                                 break;
135                             
136                             noticeStructureCheck(variable, subNode.structure());
137                             break;
138                         }
139                         default:
140                             break;
141                         }
142                     }
143                     
144                     m_graph.vote(node, VoteOther);
145                     break;
146                 }
147                 case GarbageValue:
148                     break;
149                     
150                 default:
151                     m_graph.vote(node, VoteOther);
152                     break;
153                 }
154             }
155         }
156         
157         // Disable structure hoisting on variables that appear to mostly be used in
158         // contexts where it doesn't make sense.
159         
160         for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
161             VariableAccessData* variable = &m_graph.m_variableAccessData[i];
162             if (!variable->isRoot())
163                 continue;
164             if (variable->voteRatio() >= Options::structureCheckVoteRatioForHoisting())
165                 continue;
166             HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
167             if (iter == m_map.end())
168                 continue;
169 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
170             dataLog("Zeroing the structure to hoist for %s because the ratio is %lf.\n",
171                     m_graph.nameOfVariableAccessData(variable), variable->voteRatio());
172 #endif
173             iter->value.m_structure = 0;
174         }
175         
176         // Disable structure check hoisting for variables that cross the OSR entry that
177         // we're currently taking, and where the value currently does not have the
178         // structure we want.
179         
180         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
181             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
182             if (!block)
183                 continue;
184             ASSERT(block->isReachable);
185             if (!block->isOSRTarget)
186                 continue;
187             if (block->bytecodeBegin != m_graph.m_osrEntryBytecodeIndex)
188                 continue;
189             for (size_t i = 0; i < m_graph.m_mustHandleValues.size(); ++i) {
190                 int operand = m_graph.m_mustHandleValues.operandForIndex(i);
191                 NodeIndex nodeIndex = block->variablesAtHead.operand(operand);
192                 if (nodeIndex == NoNode)
193                     continue;
194                 VariableAccessData* variable = m_graph[nodeIndex].variableAccessData();
195                 HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
196                 if (iter == m_map.end())
197                     continue;
198                 if (!iter->value.m_structure)
199                     continue;
200                 JSValue value = m_graph.m_mustHandleValues[i];
201                 if (!value || !value.isCell()) {
202 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
203                     dataLog("Zeroing the structure to hoist for %s because the OSR entry value is not a cell: %s.\n",
204                             m_graph.nameOfVariableAccessData(variable), value.description());
205 #endif
206                     iter->value.m_structure = 0;
207                     continue;
208                 }
209                 if (value.asCell()->structure() != iter->value.m_structure) {
210 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
211                     dataLog("Zeroing the structure to hoist for %s because the OSR entry value has structure %p and we wanted %p.\n",
212                             m_graph.nameOfVariableAccessData(variable), value.asCell()->structure(), iter->value.m_structure);
213 #endif
214                     iter->value.m_structure = 0;
215                     continue;
216                 }
217             }
218         }
219
220         bool changed = false;
221
222 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
223         for (HashMap<VariableAccessData*, CheckData>::iterator it = m_map.begin();
224              it != m_map.end(); ++it) {
225             if (!it->value.m_structure) {
226                 dataLog("Not hoisting checks for %s because of heuristics.\n", m_graph.nameOfVariableAccessData(it->key));
227                 continue;
228             }
229             dataLog("Hoisting checks for %s\n", m_graph.nameOfVariableAccessData(it->key));
230         }
231 #endif // DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
232         
233         // Place CheckStructure's at SetLocal sites.
234         
235         InsertionSet<NodeIndex> insertionSet;
236         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
237             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
238             if (!block)
239                 continue;
240             for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
241                 NodeIndex nodeIndex = block->at(indexInBlock);
242                 Node& node = m_graph[nodeIndex];
243                 // Be careful not to use 'node' after appending to the graph. In those switch
244                 // cases where we need to append, we first carefully extract everything we need
245                 // from the node, before doing any appending.
246                 if (!node.shouldGenerate())
247                     continue;
248                 switch (node.op()) {
249                 case SetArgument: {
250                     ASSERT(!blockIndex);
251                     // Insert a GetLocal and a CheckStructure immediately following this
252                     // SetArgument, if the variable was a candidate for structure hoisting.
253                     // If the basic block previously only had the SetArgument as its
254                     // variable-at-tail, then replace it with this GetLocal.
255                     VariableAccessData* variable = node.variableAccessData();
256                     HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
257                     if (iter == m_map.end())
258                         break;
259                     if (!iter->value.m_structure)
260                         break;
261                     
262                     node.ref();
263
264                     CodeOrigin codeOrigin = node.codeOrigin;
265                     
266                     Node getLocal(GetLocal, codeOrigin, OpInfo(variable), nodeIndex);
267                     getLocal.predict(variable->prediction());
268                     getLocal.ref();
269                     NodeIndex getLocalIndex = m_graph.size();
270                     m_graph.append(getLocal);
271                     insertionSet.append(indexInBlock + 1, getLocalIndex);
272                     
273                     Node checkStructure(CheckStructure, codeOrigin, OpInfo(m_graph.addStructureSet(iter->value.m_structure)), getLocalIndex);
274                     checkStructure.ref();
275                     NodeIndex checkStructureIndex = m_graph.size();
276                     m_graph.append(checkStructure);
277                     insertionSet.append(indexInBlock + 1, checkStructureIndex);
278                     
279                     if (block->variablesAtTail.operand(variable->local()) == nodeIndex)
280                         block->variablesAtTail.operand(variable->local()) = getLocalIndex;
281                     
282                     m_graph.substituteGetLocal(*block, indexInBlock, variable, getLocalIndex);
283                     
284                     changed = true;
285                     break;
286                 }
287                     
288                 case SetLocal: {
289                     VariableAccessData* variable = node.variableAccessData();
290                     HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
291                     if (iter == m_map.end())
292                         break;
293                     if (!iter->value.m_structure)
294                         break;
295
296                     // First insert a dead SetLocal to tell OSR that the child's value should
297                     // be dropped into this bytecode variable if the CheckStructure decides
298                     // to exit.
299                     
300                     CodeOrigin codeOrigin = node.codeOrigin;
301                     NodeIndex child1 = node.child1().index();
302                     
303                     Node setLocal(SetLocal, codeOrigin, OpInfo(variable), child1);
304                     NodeIndex setLocalIndex = m_graph.size();
305                     m_graph.append(setLocal);
306                     insertionSet.append(indexInBlock, setLocalIndex);
307                     m_graph[child1].ref();
308                     // Use a ForwardCheckStructure to indicate that we should exit to the
309                     // next bytecode instruction rather than reexecuting the current one.
310                     Node checkStructure(ForwardCheckStructure, codeOrigin, OpInfo(m_graph.addStructureSet(iter->value.m_structure)), child1);
311                     checkStructure.ref();
312                     NodeIndex checkStructureIndex = m_graph.size();
313                     m_graph.append(checkStructure);
314                     insertionSet.append(indexInBlock, checkStructureIndex);
315                     changed = true;
316                     break;
317                 }
318                     
319                 default:
320                     break;
321                 }
322             }
323             insertionSet.execute(*block);
324         }
325         
326         return changed;
327     }
328
329 private:
330     void noticeStructureCheck(VariableAccessData* variable, Structure* structure)
331     {
332         HashMap<VariableAccessData*, CheckData>::AddResult result =
333             m_map.add(variable, CheckData(structure));
334         if (result.isNewEntry)
335             return;
336         if (result.iterator->value.m_structure == structure)
337             return;
338         result.iterator->value.m_structure = 0;
339     }
340     
341     void noticeStructureCheck(VariableAccessData* variable, const StructureSet& set)
342     {
343         if (set.size() != 1) {
344             noticeStructureCheck(variable, 0);
345             return;
346         }
347         noticeStructureCheck(variable, set.singletonStructure());
348     }
349     
350     struct CheckData {
351         Structure* m_structure;
352         
353         CheckData()
354             : m_structure(0)
355         {
356         }
357         
358         CheckData(Structure* structure)
359             : m_structure(structure)
360         {
361         }
362     };
363     
364     HashMap<VariableAccessData*, CheckData> m_map;
365 };
366
367 bool performStructureCheckHoisting(Graph& graph)
368 {
369     SamplingRegion samplingRegion("DFG Structure Check Hoisting Phase");
370     return runPhase<StructureCheckHoistingPhase>(graph);
371 }
372
373 } } // namespace JSC::DFG
374
375 #endif // ENABLE(DFG_JIT)
376
377