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 "DFGCPSRethreadingPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGBasicBlockInlines.h"
32#include "DFGGraph.h"
33#include "DFGPhase.h"
34#include "JSCInlines.h"
35
36namespace JSC { namespace DFG {
37
38class CPSRethreadingPhase : public Phase {
39public:
40    CPSRethreadingPhase(Graph& graph)
41        : Phase(graph, "CPS rethreading")
42    {
43    }
44
45    bool run()
46    {
47        RELEASE_ASSERT(m_graph.m_refCountState == EverythingIsLive);
48
49        if (m_graph.m_form == ThreadedCPS)
50            return false;
51
52        clearIsLoadedFrom();
53        freeUnnecessaryNodes();
54        m_graph.clearReplacements();
55        canonicalizeLocalsInBlocks();
56        propagatePhis<LocalOperand>();
57        propagatePhis<ArgumentOperand>();
58        computeIsFlushed();
59
60        m_graph.m_form = ThreadedCPS;
61        return true;
62    }
63
64private:
65
66    void clearIsLoadedFrom()
67    {
68        for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
69            m_graph.m_variableAccessData[i].setIsLoadedFrom(false);
70    }
71
72    void freeUnnecessaryNodes()
73    {
74        SamplingRegion samplingRegion("DFG CPS Rethreading: freeUnnecessaryNodes");
75
76        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
77            BasicBlock* block = m_graph.block(blockIndex);
78            if (!block)
79                continue;
80            ASSERT(block->isReachable);
81
82            unsigned fromIndex = 0;
83            unsigned toIndex = 0;
84            while (fromIndex < block->size()) {
85                Node* node = block->at(fromIndex++);
86                switch (node->op()) {
87                case GetLocal:
88                case Flush:
89                case PhantomLocal:
90                    node->children.setChild1(Edge());
91                    break;
92                case Phantom:
93                    if (!node->child1())
94                        continue;
95                    switch (node->child1()->op()) {
96                    case Phi:
97                    case SetArgument:
98                    case SetLocal:
99                        node->convertToPhantomLocal();
100                        break;
101                    default:
102                        ASSERT(node->child1()->hasResult());
103                        break;
104                    }
105                    break;
106                default:
107                    break;
108                }
109                block->at(toIndex++) = node;
110            }
111            block->resize(toIndex);
112
113            for (unsigned phiIndex = block->phis.size(); phiIndex--;)
114                m_graph.m_allocator.free(block->phis[phiIndex]);
115            block->phis.resize(0);
116        }
117    }
118
119    template<OperandKind operandKind>
120    void clearVariablesAtHeadAndTail()
121    {
122        ASSERT(
123            m_block->variablesAtHead.sizeFor<operandKind>()
124            == m_block->variablesAtTail.sizeFor<operandKind>());
125
126        for (unsigned i = m_block->variablesAtHead.sizeFor<operandKind>(); i--;) {
127            m_block->variablesAtHead.atFor<operandKind>(i) = 0;
128            m_block->variablesAtTail.atFor<operandKind>(i) = 0;
129        }
130    }
131
132    ALWAYS_INLINE Node* addPhiSilently(BasicBlock* block, const NodeOrigin& origin, VariableAccessData* variable)
133    {
134        Node* result = m_graph.addNode(SpecNone, Phi, origin, OpInfo(variable));
135        block->phis.append(result);
136        return result;
137    }
138
139    template<OperandKind operandKind>
140    ALWAYS_INLINE Node* addPhi(BasicBlock* block, const NodeOrigin& origin, VariableAccessData* variable, size_t index)
141    {
142        Node* result = addPhiSilently(block, origin, variable);
143        phiStackFor<operandKind>().append(PhiStackEntry(block, index, result));
144        return result;
145    }
146
147    template<OperandKind operandKind>
148    ALWAYS_INLINE Node* addPhi(const NodeOrigin& origin, VariableAccessData* variable, size_t index)
149    {
150        return addPhi<operandKind>(m_block, origin, variable, index);
151    }
152
153    template<OperandKind operandKind>
154    void canonicalizeGetLocalFor(Node* node, VariableAccessData* variable, size_t idx)
155    {
156        ASSERT(!node->child1());
157
158        if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
159            ASSERT(otherNode->variableAccessData() == variable);
160
161            switch (otherNode->op()) {
162            case Flush:
163            case PhantomLocal:
164                otherNode = otherNode->child1().node();
165                if (otherNode->op() == Phi) {
166                    // We need to have a GetLocal, so this might as well be the one.
167                    node->children.setChild1(Edge(otherNode));
168                    m_block->variablesAtTail.atFor<operandKind>(idx) = node;
169                    return;
170                }
171                ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument);
172                break;
173            default:
174                break;
175            }
176
177            ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument || otherNode->op() == GetLocal);
178            ASSERT(otherNode->variableAccessData() == variable);
179
180            if (otherNode->op() == SetArgument) {
181                variable->setIsLoadedFrom(true);
182                node->children.setChild1(Edge(otherNode));
183                m_block->variablesAtTail.atFor<operandKind>(idx) = node;
184                return;
185            }
186
187            if (variable->isCaptured()) {
188                variable->setIsLoadedFrom(true);
189                if (otherNode->op() == GetLocal)
190                    otherNode = otherNode->child1().node();
191                else
192                    ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument);
193
194                ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgument);
195
196                // Keep this GetLocal but link it to the prior ones.
197                node->children.setChild1(Edge(otherNode));
198                m_block->variablesAtTail.atFor<operandKind>(idx) = node;
199                return;
200            }
201
202            if (otherNode->op() == GetLocal) {
203                // Replace all references to this GetLocal with otherNode.
204                node->misc.replacement = otherNode;
205                return;
206            }
207
208            ASSERT(otherNode->op() == SetLocal);
209            node->misc.replacement = otherNode->child1().node();
210            return;
211        }
212
213        variable->setIsLoadedFrom(true);
214        Node* phi = addPhi<operandKind>(node->origin, variable, idx);
215        node->children.setChild1(Edge(phi));
216        m_block->variablesAtHead.atFor<operandKind>(idx) = phi;
217        m_block->variablesAtTail.atFor<operandKind>(idx) = node;
218    }
219
220    void canonicalizeGetLocal(Node* node)
221    {
222        VariableAccessData* variable = node->variableAccessData();
223        if (variable->local().isArgument())
224            canonicalizeGetLocalFor<ArgumentOperand>(node, variable, variable->local().toArgument());
225        else
226            canonicalizeGetLocalFor<LocalOperand>(node, variable, variable->local().toLocal());
227    }
228
229    void canonicalizeSetLocal(Node* node)
230    {
231        m_block->variablesAtTail.setOperand(node->local(), node);
232    }
233
234    template<NodeType nodeType, OperandKind operandKind>
235    void canonicalizeFlushOrPhantomLocalFor(Node* node, VariableAccessData* variable, size_t idx)
236    {
237        ASSERT(!node->child1());
238
239        if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
240            ASSERT(otherNode->variableAccessData() == variable);
241
242            switch (otherNode->op()) {
243            case Flush:
244            case PhantomLocal:
245            case GetLocal:
246                otherNode = otherNode->child1().node();
247                break;
248            default:
249                break;
250            }
251
252            ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgument);
253
254            if (nodeType == PhantomLocal && otherNode->op() == SetLocal) {
255                // PhantomLocal(SetLocal) doesn't make sense. PhantomLocal means: at this
256                // point I know I would have been interested in the value of this variable
257                // for the purpose of OSR. PhantomLocal(SetLocal) means: at this point I
258                // know that I would have read the value written by that SetLocal. This is
259                // redundant and inefficient, since really it just means that we want to
260                // be keeping the operand to the SetLocal alive. The SetLocal may die, and
261                // we'll be fine because OSR tracks dead SetLocals.
262
263                // So we turn this into a Phantom on the child of the SetLocal.
264
265                node->convertToPhantom();
266                node->children.setChild1(otherNode->child1());
267                return;
268            }
269
270            variable->setIsLoadedFrom(true);
271            // There is nothing wrong with having redundant Flush's. It just needs to
272            // be linked appropriately. Note that if there had already been a previous
273            // use at tail then we don't override it. It's fine for variablesAtTail to
274            // omit Flushes and PhantomLocals. On the other hand, having it refer to a
275            // Flush or a PhantomLocal if just before it the last use was a GetLocal would
276            // seriously confuse the CFA.
277            node->children.setChild1(Edge(otherNode));
278            return;
279        }
280
281        variable->setIsLoadedFrom(true);
282        node->children.setChild1(Edge(addPhi<operandKind>(node->origin, variable, idx)));
283        m_block->variablesAtHead.atFor<operandKind>(idx) = node;
284        m_block->variablesAtTail.atFor<operandKind>(idx) = node;
285    }
286
287    template<NodeType nodeType>
288    void canonicalizeFlushOrPhantomLocal(Node* node)
289    {
290        VariableAccessData* variable = node->variableAccessData();
291        if (variable->local().isArgument())
292            canonicalizeFlushOrPhantomLocalFor<nodeType, ArgumentOperand>(node, variable, variable->local().toArgument());
293        else
294            canonicalizeFlushOrPhantomLocalFor<nodeType, LocalOperand>(node, variable, variable->local().toLocal());
295    }
296
297    void canonicalizeSetArgument(Node* node)
298    {
299        VirtualRegister local = node->local();
300        ASSERT(local.isArgument());
301        int argument = local.toArgument();
302        m_block->variablesAtHead.setArgumentFirstTime(argument, node);
303        m_block->variablesAtTail.setArgumentFirstTime(argument, node);
304    }
305
306    void canonicalizeLocalsInBlock()
307    {
308        if (!m_block)
309            return;
310        ASSERT(m_block->isReachable);
311
312        clearVariablesAtHeadAndTail<ArgumentOperand>();
313        clearVariablesAtHeadAndTail<LocalOperand>();
314
315        // Assumes that all phi references have been removed. Assumes that things that
316        // should be live have a non-zero ref count, but doesn't assume that the ref
317        // counts are correct beyond that (more formally !!logicalRefCount == !!actualRefCount
318        // but not logicalRefCount == actualRefCount). Assumes that it can break ref
319        // counts.
320
321        for (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
322            Node* node = m_block->at(nodeIndex);
323
324            m_graph.performSubstitution(node);
325
326            // The rules for threaded CPS form:
327            //
328            // Head variable: describes what is live at the head of the basic block.
329            // Head variable links may refer to Flush, PhantomLocal, Phi, or SetArgument.
330            // SetArgument may only appear in the root block.
331            //
332            // Tail variable: the last thing that happened to the variable in the block.
333            // It may be a Flush, PhantomLocal, GetLocal, SetLocal, SetArgument, or Phi.
334            // SetArgument may only appear in the root block. Note that if there ever
335            // was a GetLocal to the variable, and it was followed by PhantomLocals and
336            // Flushes but not SetLocals, then the tail variable will be the GetLocal.
337            // This reflects the fact that you only care that the tail variable is a
338            // Flush or PhantomLocal if nothing else interesting happened. Likewise, if
339            // there ever was a SetLocal and it was followed by Flushes, then the tail
340            // variable will be a SetLocal and not those subsequent Flushes.
341            //
342            // Child of GetLocal: the operation that the GetLocal keeps alive. For
343            // uncaptured locals, it may be a Phi from the current block. For arguments,
344            // it may be a SetArgument. For captured locals and arguments it may also be
345            // a SetLocal.
346            //
347            // Child of SetLocal: must be a value producing node.
348            //
349            // Child of Flush: it may be a Phi from the current block or a SetLocal. For
350            // arguments it may also be a SetArgument.
351            //
352            // Child of PhantomLocal: it may be a Phi from the current block. For
353            // arguments it may also be a SetArgument.
354            //
355            // Children of Phi: other Phis in the same basic block, or any of the
356            // following from predecessor blocks: SetLocal, Phi, or SetArgument. These
357            // are computed by looking at the tail variables of the predecessor  blocks
358            // and either using it directly (if it's a SetLocal, Phi, or SetArgument) or
359            // loading that nodes child (if it's a GetLocal, PhanomLocal, or Flush - all
360            // of these will have children that are SetLocal, Phi, or SetArgument).
361
362            switch (node->op()) {
363            case GetLocal:
364                canonicalizeGetLocal(node);
365                break;
366
367            case SetLocal:
368                canonicalizeSetLocal(node);
369                break;
370
371            case Flush:
372                canonicalizeFlushOrPhantomLocal<Flush>(node);
373                break;
374
375            case PhantomLocal:
376                canonicalizeFlushOrPhantomLocal<PhantomLocal>(node);
377                break;
378
379            case SetArgument:
380                canonicalizeSetArgument(node);
381                break;
382
383            default:
384                break;
385            }
386        }
387    }
388
389    void canonicalizeLocalsInBlocks()
390    {
391        SamplingRegion samplingRegion("DFG CPS Rethreading: canonicalizeLocalsInBlocks");
392
393        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
394            m_block = m_graph.block(blockIndex);
395            canonicalizeLocalsInBlock();
396        }
397    }
398
399    template<OperandKind operandKind>
400    void propagatePhis()
401    {
402        Vector<PhiStackEntry, 128>& phiStack = operandKind == ArgumentOperand ? m_argumentPhiStack : m_localPhiStack;
403
404        SamplingRegion samplingRegion("DFG CPS Rethreading: propagatePhis");
405
406        // Ensure that attempts to use this fail instantly.
407        m_block = 0;
408
409        while (!phiStack.isEmpty()) {
410            PhiStackEntry entry = phiStack.last();
411            phiStack.removeLast();
412
413            BasicBlock* block = entry.m_block;
414            PredecessorList& predecessors = block->predecessors;
415            Node* currentPhi = entry.m_phi;
416            VariableAccessData* variable = currentPhi->variableAccessData();
417            size_t index = entry.m_index;
418
419            for (size_t i = predecessors.size(); i--;) {
420                BasicBlock* predecessorBlock = predecessors[i];
421
422                Node* variableInPrevious = predecessorBlock->variablesAtTail.atFor<operandKind>(index);
423                if (!variableInPrevious) {
424                    variableInPrevious = addPhi<operandKind>(predecessorBlock, currentPhi->origin, variable, index);
425                    predecessorBlock->variablesAtTail.atFor<operandKind>(index) = variableInPrevious;
426                    predecessorBlock->variablesAtHead.atFor<operandKind>(index) = variableInPrevious;
427                } else {
428                    switch (variableInPrevious->op()) {
429                    case GetLocal:
430                    case PhantomLocal:
431                    case Flush:
432                        ASSERT(variableInPrevious->variableAccessData() == variableInPrevious->child1()->variableAccessData());
433                        variableInPrevious = variableInPrevious->child1().node();
434                        break;
435                    default:
436                        break;
437                    }
438                }
439
440                ASSERT(
441                    variableInPrevious->op() == SetLocal
442                    || variableInPrevious->op() == Phi
443                    || variableInPrevious->op() == SetArgument);
444
445                if (!currentPhi->child1()) {
446                    currentPhi->children.setChild1(Edge(variableInPrevious));
447                    continue;
448                }
449                if (!currentPhi->child2()) {
450                    currentPhi->children.setChild2(Edge(variableInPrevious));
451                    continue;
452                }
453                if (!currentPhi->child3()) {
454                    currentPhi->children.setChild3(Edge(variableInPrevious));
455                    continue;
456                }
457
458                Node* newPhi = addPhiSilently(block, currentPhi->origin, variable);
459                newPhi->children = currentPhi->children;
460                currentPhi->children.initialize(newPhi, variableInPrevious, 0);
461            }
462        }
463    }
464
465    struct PhiStackEntry {
466        PhiStackEntry(BasicBlock* block, size_t index, Node* phi)
467            : m_block(block)
468            , m_index(index)
469            , m_phi(phi)
470        {
471        }
472
473        BasicBlock* m_block;
474        size_t m_index;
475        Node* m_phi;
476    };
477
478    template<OperandKind operandKind>
479    Vector<PhiStackEntry, 128>& phiStackFor()
480    {
481        if (operandKind == ArgumentOperand)
482            return m_argumentPhiStack;
483        return m_localPhiStack;
484    }
485
486    void computeIsFlushed()
487    {
488        m_graph.clearFlagsOnAllNodes(NodeIsFlushed);
489
490        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
491            BasicBlock* block = m_graph.block(blockIndex);
492            if (!block)
493                continue;
494            for (unsigned nodeIndex = block->size(); nodeIndex--;) {
495                Node* node = block->at(nodeIndex);
496                if (node->op() != Flush)
497                    continue;
498                addFlushedLocalOp(node);
499            }
500        }
501        while (!m_flushedLocalOpWorklist.isEmpty()) {
502            Node* node = m_flushedLocalOpWorklist.takeLast();
503            ASSERT(node->flags() & NodeIsFlushed);
504            DFG_NODE_DO_TO_CHILDREN(m_graph, node, addFlushedLocalEdge);
505        }
506    }
507
508    void addFlushedLocalOp(Node* node)
509    {
510        if (node->mergeFlags(NodeIsFlushed))
511            m_flushedLocalOpWorklist.append(node);
512    }
513
514    void addFlushedLocalEdge(Node*, Edge edge)
515    {
516        addFlushedLocalOp(edge.node());
517    }
518
519    BasicBlock* m_block;
520    Vector<PhiStackEntry, 128> m_argumentPhiStack;
521    Vector<PhiStackEntry, 128> m_localPhiStack;
522    Vector<Node*, 128> m_flushedLocalOpWorklist;
523};
524
525bool performCPSRethreading(Graph& graph)
526{
527    SamplingRegion samplingRegion("DFG CPS Rethreading Phase");
528    return runPhase<CPSRethreadingPhase>(graph);
529}
530
531} } // namespace JSC::DFG
532
533#endif // ENABLE(DFG_JIT)
534
535