DFG should allow Phantoms after terminals
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGForAllKills.h
1 /*
2  * Copyright (C) 2015 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 #ifndef DFGForAllKills_h
27 #define DFGForAllKills_h
28
29 #include "BytecodeKills.h"
30 #include "DFGGraph.h"
31 #include "DFGOSRAvailabilityAnalysisPhase.h"
32 #include "FullBytecodeLiveness.h"
33
34 namespace JSC { namespace DFG {
35
36 // Utilities for finding the last points where a node is live in DFG SSA. This accounts for liveness due
37 // to OSR exit. This is usually used for enumerating over all of the program points where a node is live,
38 // by exploring all blocks where the node is live at tail and then exploring all program points where the
39 // node is killed. A prerequisite to using these utilities is having liveness and OSR availability
40 // computed.
41
42 template<typename Functor>
43 void forAllLiveNodesAtTail(Graph& graph, BasicBlock* block, const Functor& functor)
44 {
45     HashSet<Node*> seen;
46     for (Node* node : block->ssa->liveAtTail) {
47         if (seen.add(node).isNewEntry)
48             functor(node);
49     }
50     
51     DFG_ASSERT(graph, block->terminal(), block->terminal()->origin.forExit.isSet());
52     
53     AvailabilityMap& availabilityMap = block->ssa->availabilityAtTail;
54     for (unsigned i = availabilityMap.m_locals.size(); i--;) {
55         VirtualRegister reg = availabilityMap.m_locals.virtualRegisterForIndex(i);
56         
57         if (!graph.isLiveInBytecode(reg, block->terminal()->origin.forExit))
58             continue;
59         
60         availabilityMap.closeStartingWithLocal(
61             reg,
62             [&] (Node* node) -> bool {
63                 return seen.contains(node);
64             },
65             [&] (Node* node) -> bool {
66                 if (!seen.add(node).isNewEntry)
67                     return false;
68                 functor(node);
69                 return true;
70             });
71     }
72 }
73
74 template<typename Functor>
75 void forAllKilledOperands(Graph& graph, CodeOrigin before, Node* nodeAfter, const Functor& functor)
76 {
77     CodeOrigin after = nodeAfter->origin.forExit;
78     
79     if (!before) {
80         if (!after)
81             return;
82         // The true before-origin is the origin at predecessors that jump to us. But there can be
83         // many such predecessors and they will likely all have a different origin. So, it's better
84         // to do the conservative thing.
85         for (unsigned i = graph.block(0)->variablesAtHead.numberOfLocals(); i--;) {
86             VirtualRegister reg = virtualRegisterForLocal(i);
87             if (graph.isLiveInBytecode(reg, after))
88                 functor(reg);
89         }
90         return;
91     }
92     
93     // If we MovHint something that is live at the time, then we kill the old value.
94     VirtualRegister alreadyNoted;
95     if (nodeAfter->containsMovHint()) {
96         VirtualRegister reg = nodeAfter->unlinkedLocal();
97         if (graph.isLiveInBytecode(reg, after)) {
98             functor(reg);
99             alreadyNoted = reg;
100         }
101     }
102     
103     if (before == after)
104         return;
105     
106     // before could be unset even if after is, but the opposite cannot happen.
107     ASSERT(!!after);
108     
109     // Detect kills the super conservative way: it is killed if it was live before and dead after.
110     for (unsigned i = graph.block(0)->variablesAtHead.numberOfLocals(); i--;) {
111         VirtualRegister reg = virtualRegisterForLocal(i);
112         if (reg == alreadyNoted)
113             continue;
114         if (graph.isLiveInBytecode(reg, before) && !graph.isLiveInBytecode(reg, after))
115             functor(reg);
116     }
117 }
118     
119 // Tells you all of the nodes that would no longer be live across the node at this nodeIndex.
120 template<typename Functor>
121 void forAllKilledNodesAtNodeIndex(
122     Graph& graph, AvailabilityMap& availabilityMap, BasicBlock* block, unsigned nodeIndex,
123     const Functor& functor)
124 {
125     static const unsigned seenInClosureFlag = 1;
126     static const unsigned calledFunctorFlag = 2;
127     HashMap<Node*, unsigned> flags;
128     
129     Node* node = block->at(nodeIndex);
130     
131     graph.doToChildren(
132         node,
133         [&] (Edge edge) {
134             if (edge.doesKill()) {
135                 auto& result = flags.add(edge.node(), 0).iterator->value;
136                 if (!(result & calledFunctorFlag)) {
137                     functor(edge.node());
138                     result |= calledFunctorFlag;
139                 }
140             }
141         });
142
143     CodeOrigin before;
144     if (nodeIndex)
145         before = block->at(nodeIndex - 1)->origin.forExit;
146
147     forAllKilledOperands(
148         graph, before, node,
149         [&] (VirtualRegister reg) {
150             availabilityMap.closeStartingWithLocal(
151                 reg,
152                 [&] (Node* node) -> bool {
153                     return flags.get(node) & seenInClosureFlag;
154                 },
155                 [&] (Node* node) -> bool {
156                     auto& resultFlags = flags.add(node, 0).iterator->value;
157                     bool result = resultFlags & seenInClosureFlag;
158                     if (!(resultFlags & calledFunctorFlag))
159                         functor(node);
160                     resultFlags |= seenInClosureFlag | calledFunctorFlag;
161                     return result;
162                 });
163         });
164 }
165
166 // Tells you all of the places to start searching from in a basic block. Gives you the node index at which
167 // the value is either no longer live. This pretends that nodes are dead at the end of the block, so that
168 // you can use this to do per-basic-block analyses.
169 template<typename Functor>
170 void forAllKillsInBlock(Graph& graph, BasicBlock* block, const Functor& functor)
171 {
172     forAllLiveNodesAtTail(
173         graph, block,
174         [&] (Node* node) {
175             functor(block->size(), node);
176         });
177     
178     LocalOSRAvailabilityCalculator localAvailability;
179     localAvailability.beginBlock(block);
180     // Start at the second node, because the functor is expected to only inspect nodes from the start of
181     // the block up to nodeIndex (exclusive), so if nodeIndex is zero then the functor has nothing to do.
182     for (unsigned nodeIndex = 1; nodeIndex < block->size(); ++nodeIndex) {
183         forAllKilledNodesAtNodeIndex(
184             graph, localAvailability.m_availability, block, nodeIndex,
185             [&] (Node* node) {
186                 functor(nodeIndex, node);
187             });
188         localAvailability.executeNode(block->at(nodeIndex));
189     }
190 }
191
192 } } // namespace JSC::DFG
193
194 #endif // DFGForAllKills_h
195