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