33dafb8a5936c009873f06b4143cff1fdd526c10
[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     graph.forAllLocalsLiveInBytecode(
55         block->terminal()->origin.forExit,
56         [&] (VirtualRegister reg) {
57             availabilityMap.closeStartingWithLocal(
58                 reg,
59                 [&] (Node* node) -> bool {
60                     return seen.contains(node);
61                 },
62                 [&] (Node* node) -> bool {
63                     if (!seen.add(node).isNewEntry)
64                         return false;
65                     functor(node);
66                     return true;
67                 });
68         });
69 }
70
71 // This tells you those things that die on the boundary between nodeBefore and nodeAfter. It is
72 // conservative in the sense that it might resort to telling you some things that are still live at
73 // nodeAfter.
74 template<typename Functor>
75 void forAllKilledOperands(Graph& graph, Node* nodeBefore, Node* nodeAfter, const Functor& functor)
76 {
77     CodeOrigin before = nodeBefore->origin.forExit;
78     CodeOrigin after = nodeAfter->origin.forExit;
79     
80     VirtualRegister alreadyNoted;
81     if (!!after) {
82         // If we MovHint something that is live at the time, then we kill the old value.
83         if (nodeAfter->containsMovHint()) {
84             VirtualRegister reg = nodeAfter->unlinkedLocal();
85             if (graph.isLiveInBytecode(reg, after)) {
86                 functor(reg);
87                 alreadyNoted = reg;
88             }
89         }
90     }
91     
92     if (!before) {
93         if (!after)
94             return;
95         // The true before-origin is the origin at predecessors that jump to us. But there can be
96         // many such predecessors and they will likely all have a different origin. So, it's better
97         // to do the conservative thing.
98         graph.forAllLocalsLiveInBytecode(after, functor);
99         return;
100     }
101     
102     if (before == after)
103         return;
104     
105     // before could be unset even if after is, but the opposite cannot happen.
106     ASSERT(!!after);
107     
108     // It's easier to do this if the inline call frames are the same. This is way faster than the
109     // other loop, below.
110     if (before.inlineCallFrame == after.inlineCallFrame) {
111         int stackOffset = before.inlineCallFrame ? before.inlineCallFrame->stackOffset : 0;
112         CodeBlock* codeBlock = graph.baselineCodeBlockFor(before.inlineCallFrame);
113         FullBytecodeLiveness& fullLiveness = graph.livenessFor(codeBlock);
114         const FastBitVector& liveBefore = fullLiveness.getLiveness(before.bytecodeIndex);
115         const FastBitVector& liveAfter = fullLiveness.getLiveness(after.bytecodeIndex);
116         
117         for (unsigned relativeLocal = codeBlock->m_numCalleeRegisters; relativeLocal--;) {
118             if (liveBefore.get(relativeLocal) && !liveAfter.get(relativeLocal))
119                 functor(virtualRegisterForLocal(relativeLocal) + stackOffset);
120         }
121         
122         return;
123     }
124     
125     // Detect kills the super conservative way: it is killed if it was live before and dead after.
126     BitVector liveAfter = graph.localsLiveInBytecode(after);
127     graph.forAllLocalsLiveInBytecode(
128         before,
129         [&] (VirtualRegister reg) {
130             if (reg == alreadyNoted)
131                 return;
132             if (liveAfter.get(reg.toLocal()))
133                 return;
134             functor(reg);
135         });
136 }
137     
138 // Tells you all of the nodes that would no longer be live across the node at this nodeIndex.
139 template<typename Functor>
140 void forAllKilledNodesAtNodeIndex(
141     Graph& graph, AvailabilityMap& availabilityMap, BasicBlock* block, unsigned nodeIndex,
142     const Functor& functor)
143 {
144     static const unsigned seenInClosureFlag = 1;
145     static const unsigned calledFunctorFlag = 2;
146     HashMap<Node*, unsigned> flags;
147     
148     Node* node = block->at(nodeIndex);
149     
150     graph.doToChildren(
151         node,
152         [&] (Edge edge) {
153             if (edge.doesKill()) {
154                 auto& result = flags.add(edge.node(), 0).iterator->value;
155                 if (!(result & calledFunctorFlag)) {
156                     functor(edge.node());
157                     result |= calledFunctorFlag;
158                 }
159             }
160         });
161
162     Node* before = nullptr;
163     if (nodeIndex)
164         before = block->at(nodeIndex - 1);
165
166     forAllKilledOperands(
167         graph, before, node,
168         [&] (VirtualRegister reg) {
169             availabilityMap.closeStartingWithLocal(
170                 reg,
171                 [&] (Node* node) -> bool {
172                     return flags.get(node) & seenInClosureFlag;
173                 },
174                 [&] (Node* node) -> bool {
175                     auto& resultFlags = flags.add(node, 0).iterator->value;
176                     bool result = resultFlags & seenInClosureFlag;
177                     if (!(resultFlags & calledFunctorFlag))
178                         functor(node);
179                     resultFlags |= seenInClosureFlag | calledFunctorFlag;
180                     return result;
181                 });
182         });
183 }
184
185 // Tells you all of the places to start searching from in a basic block. Gives you the node index at which
186 // the value is either no longer live. This pretends that nodes are dead at the end of the block, so that
187 // you can use this to do per-basic-block analyses.
188 template<typename Functor>
189 void forAllKillsInBlock(Graph& graph, BasicBlock* block, const Functor& functor)
190 {
191     forAllLiveNodesAtTail(
192         graph, block,
193         [&] (Node* node) {
194             functor(block->size(), node);
195         });
196     
197     LocalOSRAvailabilityCalculator localAvailability;
198     localAvailability.beginBlock(block);
199     // Start at the second node, because the functor is expected to only inspect nodes from the start of
200     // the block up to nodeIndex (exclusive), so if nodeIndex is zero then the functor has nothing to do.
201     for (unsigned nodeIndex = 1; nodeIndex < block->size(); ++nodeIndex) {
202         forAllKilledNodesAtNodeIndex(
203             graph, localAvailability.m_availability, block, nodeIndex,
204             [&] (Node* node) {
205                 functor(nodeIndex, node);
206             });
207         localAvailability.executeNode(block->at(nodeIndex));
208     }
209 }
210
211 } } // namespace JSC::DFG
212
213 #endif // DFGForAllKills_h
214