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