8295eaed16c2eb8ba3497a6de745087c4d03eeec
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGInPlaceAbstractState.cpp
1 /*
2  * Copyright (C) 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
28 #if ENABLE(DFG_JIT)
29
30 #include "DFGInPlaceAbstractState.h"
31
32 #include "CodeBlock.h"
33 #include "DFGBasicBlock.h"
34 #include "GetByIdStatus.h"
35 #include "JSCInlines.h"
36 #include "PutByIdStatus.h"
37 #include "StringObject.h"
38
39 namespace JSC { namespace DFG {
40
41 InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
42     : m_graph(graph)
43     , m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
44     , m_block(0)
45 {
46 }
47
48 InPlaceAbstractState::~InPlaceAbstractState() { }
49
50 void InPlaceAbstractState::beginBasicBlock(BasicBlock* basicBlock)
51 {
52     ASSERT(!m_block);
53     
54     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
55     ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
56     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
57     
58     for (size_t i = 0; i < basicBlock->size(); i++)
59         forNode(basicBlock->at(i)).clear();
60
61     m_variables = basicBlock->valuesAtHead;
62     m_haveStructures = false;
63     for (size_t i = 0; i < m_variables.numberOfArguments(); ++i) {
64         if (m_variables.argument(i).hasClobberableState()) {
65             m_haveStructures = true;
66             break;
67         }
68     }
69     for (size_t i = 0; i < m_variables.numberOfLocals(); ++i) {
70         if (m_variables.local(i).hasClobberableState()) {
71             m_haveStructures = true;
72             break;
73         }
74     }
75     
76     if (m_graph.m_form == SSA) {
77         HashMap<Node*, AbstractValue>::iterator iter = basicBlock->ssa->valuesAtHead.begin();
78         HashMap<Node*, AbstractValue>::iterator end = basicBlock->ssa->valuesAtHead.end();
79         for (; iter != end; ++iter) {
80             forNode(iter->key) = iter->value;
81             if (iter->value.hasClobberableState())
82                 m_haveStructures = true;
83         }
84     }
85     
86     basicBlock->cfaShouldRevisit = false;
87     basicBlock->cfaHasVisited = true;
88     m_block = basicBlock;
89     m_isValid = true;
90     m_foundConstants = false;
91     m_branchDirection = InvalidBranchDirection;
92 }
93
94 static void setLiveValues(HashMap<Node*, AbstractValue>& values, HashSet<Node*>& live)
95 {
96     values.clear();
97     
98     HashSet<Node*>::iterator iter = live.begin();
99     HashSet<Node*>::iterator end = live.end();
100     for (; iter != end; ++iter)
101         values.add(*iter, AbstractValue());
102 }
103
104 void InPlaceAbstractState::initialize()
105 {
106     BasicBlock* root = m_graph.block(0);
107     root->cfaShouldRevisit = true;
108     root->cfaHasVisited = false;
109     root->cfaFoundConstants = false;
110     for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
111         root->valuesAtTail.argument(i).clear();
112         if (m_graph.m_form == SSA) {
113             root->valuesAtHead.argument(i).makeHeapTop();
114             continue;
115         }
116         
117         Node* node = root->variablesAtHead.argument(i);
118         ASSERT(node->op() == SetArgument);
119         if (!node->variableAccessData()->shouldUnboxIfPossible()) {
120             root->valuesAtHead.argument(i).makeHeapTop();
121             continue;
122         }
123         
124         SpeculatedType prediction =
125             node->variableAccessData()->argumentAwarePrediction();
126         if (isInt32Speculation(prediction))
127             root->valuesAtHead.argument(i).setType(SpecInt32);
128         else if (isBooleanSpeculation(prediction))
129             root->valuesAtHead.argument(i).setType(SpecBoolean);
130         else if (isCellSpeculation(prediction))
131             root->valuesAtHead.argument(i).setType(SpecCell);
132         else
133             root->valuesAtHead.argument(i).makeHeapTop();
134     }
135     for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
136         Node* node = root->variablesAtHead.local(i);
137         if (node && node->variableAccessData()->isCaptured())
138             root->valuesAtHead.local(i).makeHeapTop();
139         else
140             root->valuesAtHead.local(i).clear();
141         root->valuesAtTail.local(i).clear();
142     }
143     for (BlockIndex blockIndex = 1 ; blockIndex < m_graph.numBlocks(); ++blockIndex) {
144         BasicBlock* block = m_graph.block(blockIndex);
145         if (!block)
146             continue;
147         ASSERT(block->isReachable);
148         block->cfaShouldRevisit = false;
149         block->cfaHasVisited = false;
150         block->cfaFoundConstants = false;
151         for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
152             block->valuesAtHead.argument(i).clear();
153             block->valuesAtTail.argument(i).clear();
154         }
155         for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
156             block->valuesAtHead.local(i).clear();
157             block->valuesAtTail.local(i).clear();
158         }
159         if (!block->isOSRTarget)
160             continue;
161         if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex)
162             continue;
163         for (size_t i = 0; i < m_graph.m_mustHandleAbstractValues.size(); ++i) {
164             AbstractValue value = m_graph.m_mustHandleAbstractValues[i];
165             int operand = m_graph.m_mustHandleAbstractValues.operandForIndex(i);
166             block->valuesAtHead.operand(operand).merge(value);
167         }
168         block->cfaShouldRevisit = true;
169     }
170     if (m_graph.m_form == SSA) {
171         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
172             BasicBlock* block = m_graph.block(blockIndex);
173             if (!block)
174                 continue;
175             setLiveValues(block->ssa->valuesAtHead, block->ssa->liveAtHead);
176             setLiveValues(block->ssa->valuesAtTail, block->ssa->liveAtTail);
177         }
178     }
179 }
180
181 bool InPlaceAbstractState::endBasicBlock(MergeMode mergeMode)
182 {
183     ASSERT(m_block);
184     
185     BasicBlock* block = m_block; // Save the block for successor merging.
186     
187     block->cfaFoundConstants = m_foundConstants;
188     block->cfaDidFinish = m_isValid;
189     block->cfaBranchDirection = m_branchDirection;
190     
191     if (!m_isValid) {
192         reset();
193         return false;
194     }
195     
196     bool changed = false;
197     
198     if (mergeMode != DontMerge || !ASSERT_DISABLED) {
199         switch (m_graph.m_form) {
200         case ThreadedCPS: {
201             for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
202                 AbstractValue& destination = block->valuesAtTail.argument(argument);
203                 changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
204             }
205             
206             for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
207                 AbstractValue& destination = block->valuesAtTail.local(local);
208                 changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
209             }
210             break;
211         }
212             
213         case SSA: {
214             for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
215                 changed |= block->valuesAtTail[i].merge(m_variables[i]);
216             
217             HashSet<Node*>::iterator iter = block->ssa->liveAtTail.begin();
218             HashSet<Node*>::iterator end = block->ssa->liveAtTail.end();
219             for (; iter != end; ++iter) {
220                 Node* node = *iter;
221                 changed |= block->ssa->valuesAtTail.find(node)->value.merge(forNode(node));
222             }
223             break;
224         }
225             
226         default:
227             RELEASE_ASSERT_NOT_REACHED();
228         }
229     }
230     
231     ASSERT(mergeMode != DontMerge || !changed);
232     
233     reset();
234     
235     if (mergeMode != MergeToSuccessors)
236         return changed;
237     
238     return mergeToSuccessors(block);
239 }
240
241 void InPlaceAbstractState::reset()
242 {
243     m_block = 0;
244     m_isValid = false;
245     m_branchDirection = InvalidBranchDirection;
246 }
247
248 bool InPlaceAbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
249 {
250     if (!node)
251         return false;
252         
253     AbstractValue source;
254     
255     if (node->variableAccessData()->isCaptured()) {
256         // If it's captured then we know that whatever value was stored into the variable last is the
257         // one we care about. This is true even if the variable at tail is dead, which might happen if
258         // the last thing we did to the variable was a GetLocal and then ended up now using the
259         // GetLocal's result.
260         
261         source = inVariable;
262     } else {
263         switch (node->op()) {
264         case Phi:
265         case SetArgument:
266         case PhantomLocal:
267         case Flush:
268             // The block transfers the value from head to tail.
269             source = inVariable;
270             break;
271             
272         case GetLocal:
273             // The block refines the value with additional speculations.
274             source = forNode(node);
275             break;
276             
277         case SetLocal:
278             // The block sets the variable, and potentially refines it, both
279             // before and after setting it.
280             source = forNode(node->child1());
281             if (node->variableAccessData()->flushFormat() == FlushedDouble) {
282                 ASSERT(!(source.m_type & ~SpecFullNumber));
283                 ASSERT(!!(source.m_type & ~SpecDouble) == !!(source.m_type & SpecMachineInt));
284                 if (!(source.m_type & ~SpecDouble)) {
285                     source.merge(SpecInt52AsDouble);
286                     source.filter(SpecDouble);
287                 }
288             }
289             break;
290         
291         default:
292             RELEASE_ASSERT_NOT_REACHED();
293             break;
294         }
295     }
296     
297     if (destination == source) {
298         // Abstract execution did not change the output value of the variable, for this
299         // basic block, on this iteration.
300         return false;
301     }
302     
303     // Abstract execution reached a new conclusion about the speculations reached about
304     // this variable after execution of this basic block. Update the state, and return
305     // true to indicate that the fixpoint must go on!
306     destination = source;
307     return true;
308 }
309
310 bool InPlaceAbstractState::merge(BasicBlock* from, BasicBlock* to)
311 {
312     ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
313     ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
314     
315     bool changed = false;
316     
317     switch (m_graph.m_form) {
318     case ThreadedCPS: {
319         for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
320             AbstractValue& destination = to->valuesAtHead.argument(argument);
321             changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
322         }
323         
324         for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
325             AbstractValue& destination = to->valuesAtHead.local(local);
326             changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
327         }
328         break;
329     }
330         
331     case SSA: {
332         for (size_t i = from->valuesAtTail.size(); i--;)
333             changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
334         
335         HashSet<Node*>::iterator iter = to->ssa->liveAtHead.begin();
336         HashSet<Node*>::iterator end = to->ssa->liveAtHead.end();
337         for (; iter != end; ++iter) {
338             Node* node = *iter;
339             changed |= to->ssa->valuesAtHead.find(node)->value.merge(
340                 from->ssa->valuesAtTail.find(node)->value);
341         }
342         break;
343     }
344         
345     default:
346         RELEASE_ASSERT_NOT_REACHED();
347         break;
348     }
349
350     if (!to->cfaHasVisited)
351         changed = true;
352     
353     to->cfaShouldRevisit |= changed;
354     
355     return changed;
356 }
357
358 inline bool InPlaceAbstractState::mergeToSuccessors(BasicBlock* basicBlock)
359 {
360     Node* terminal = basicBlock->last();
361     
362     ASSERT(terminal->isTerminal());
363     
364     switch (terminal->op()) {
365     case Jump: {
366         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
367         return merge(basicBlock, terminal->takenBlock());
368     }
369         
370     case Branch: {
371         ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
372         bool changed = false;
373         if (basicBlock->cfaBranchDirection != TakeFalse)
374             changed |= merge(basicBlock, terminal->takenBlock());
375         if (basicBlock->cfaBranchDirection != TakeTrue)
376             changed |= merge(basicBlock, terminal->notTakenBlock());
377         return changed;
378     }
379         
380     case Switch: {
381         // FIXME: It would be cool to be sparse conditional for Switch's. Currently
382         // we're not. However I somehow doubt that this will ever be a big deal.
383         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
384         SwitchData* data = terminal->switchData();
385         bool changed = merge(basicBlock, data->fallThrough);
386         for (unsigned i = data->cases.size(); i--;)
387             changed |= merge(basicBlock, data->cases[i].target);
388         return changed;
389     }
390         
391     case Return:
392     case Unreachable:
393         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
394         return false;
395
396     default:
397         RELEASE_ASSERT_NOT_REACHED();
398         return false;
399     }
400 }
401
402 inline bool InPlaceAbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
403 {
404     if (!destinationNode)
405         return false;
406     
407     ASSERT_UNUSED(sourceNode, sourceNode);
408     
409     // FIXME: We could do some sparse conditional propagation here!
410     
411     return destination.merge(source);
412 }
413
414 } } // namespace JSC::DFG
415
416 #endif // ENABLE(DFG_JIT)
417