Heap variables shouldn't end up in the stack frame
[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->last(), block->last()->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->last()->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 forAllDirectlyKilledOperands(Graph& graph, CodeOrigin origin, const Functor& functor)
76 {
77     graph.killsFor(origin.inlineCallFrame).forEachOperandKilledAt(origin.bytecodeIndex, functor);
78 }
79
80 template<typename Functor>
81 void forAllKilledOperands(Graph& graph, CodeOrigin before, CodeOrigin after, const Functor& functor)
82 {
83     // The philosophy here is that if we're on the boundary between exiting to origin A and exiting
84     // to origin B, then we note the kills for A. Kills for A are the bytecode kills plus the things
85     // that were live at whatever callsites are popped between A and B. It's legal to conservatively
86     // just consider everything live at A.
87     
88     if (!before) {
89         if (!after)
90             return;
91         // The true before-origin is the origin at predecessors that jump to us. But there can be
92         // many such predecessors and they will likely all have a different origin. So, it's better
93         // to do the conservative thing.
94         for (unsigned i = graph.block(0)->variablesAtHead.numberOfLocals(); i--;) {
95             VirtualRegister reg = virtualRegisterForLocal(i);
96             if (graph.isLiveInBytecode(reg, after))
97                 functor(reg);
98         }
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     if (before.inlineCallFrame != after.inlineCallFrame) {
109         // Is before deeper than after?
110         bool beforeIsDeeper;
111         if (!after.inlineCallFrame)
112             beforeIsDeeper = true;
113         else {
114             beforeIsDeeper = false;
115             for (InlineCallFrame* current = before.inlineCallFrame; current; current = current->caller.inlineCallFrame) {
116                 if (current == after.inlineCallFrame) {
117                     beforeIsDeeper = true;
118                     break;
119                 }
120             }
121         }
122         if (beforeIsDeeper) {
123             ASSERT(before.inlineCallFrame);
124             for (CodeOrigin current = before; current.inlineCallFrame != after.inlineCallFrame; current = current.inlineCallFrame->caller) {
125                 ASSERT(current.inlineCallFrame);
126                 CodeBlock* codeBlock = graph.baselineCodeBlockFor(current.inlineCallFrame);
127                 FullBytecodeLiveness& liveness = graph.livenessFor(codeBlock);
128                 for (unsigned i = codeBlock->m_numCalleeRegisters; i--;) {
129                     VirtualRegister reg = virtualRegisterForLocal(i);
130                     if (liveness.operandIsLive(reg.offset(), current.bytecodeIndex))
131                         functor(reg + current.inlineCallFrame->stackOffset);
132                 }
133                 forAllDirectlyKilledOperands(graph, current.inlineCallFrame->caller, functor);
134             }
135         }
136     }
137     
138     forAllDirectlyKilledOperands(graph, before, functor);
139 }
140     
141 // Tells you all of the nodes that would no longer be live across the node at this nodeIndex.
142 template<typename Functor>
143 void forAllKilledNodesAtNodeIndex(
144     Graph& graph, AvailabilityMap& availabilityMap, BasicBlock* block, unsigned nodeIndex,
145     const Functor& functor)
146 {
147     static const unsigned seenInClosureFlag = 1;
148     static const unsigned calledFunctorFlag = 2;
149     HashMap<Node*, unsigned> flags;
150     
151     Node* node = block->at(nodeIndex);
152     
153     graph.doToChildren(
154         node,
155         [&] (Edge edge) {
156             if (edge.doesKill()) {
157                 auto& result = flags.add(edge.node(), 0).iterator->value;
158                 if (!(result & calledFunctorFlag)) {
159                     functor(edge.node());
160                     result |= calledFunctorFlag;
161                 }
162             }
163         });
164
165     CodeOrigin before;
166     if (nodeIndex)
167         before = block->at(nodeIndex - 1)->origin.forExit;
168
169     forAllKilledOperands(
170         graph, before, node->origin.forExit,
171         [&] (VirtualRegister reg) {
172             availabilityMap.closeStartingWithLocal(
173                 reg,
174                 [&] (Node* node) -> bool {
175                     return flags.get(node) & seenInClosureFlag;
176                 },
177                 [&] (Node* node) -> bool {
178                     auto& resultFlags = flags.add(node, 0).iterator->value;
179                     bool result = resultFlags & seenInClosureFlag;
180                     if (!(resultFlags & calledFunctorFlag))
181                         functor(node);
182                     resultFlags |= seenInClosureFlag | calledFunctorFlag;
183                     return result;
184                 });
185         });
186 }
187
188 // Tells you all of the places to start searching from in a basic block. Gives you the node index at which
189 // the value is either no longer live. This pretends that nodes are dead at the end of the block, so that
190 // you can use this to do per-basic-block analyses.
191 template<typename Functor>
192 void forAllKillsInBlock(Graph& graph, BasicBlock* block, const Functor& functor)
193 {
194     forAllLiveNodesAtTail(
195         graph, block,
196         [&] (Node* node) {
197             functor(block->size(), node);
198         });
199     
200     LocalOSRAvailabilityCalculator localAvailability;
201     localAvailability.beginBlock(block);
202     // Start at the second node, because the functor is expected to only inspect nodes from the start of
203     // the block up to nodeIndex (exclusive), so if nodeIndex is zero then the functor has nothing to do.
204     for (unsigned nodeIndex = 1; nodeIndex < block->size(); ++nodeIndex) {
205         forAllKilledNodesAtNodeIndex(
206             graph, localAvailability.m_availability, block, nodeIndex,
207             [&] (Node* node) {
208                 functor(nodeIndex, node);
209             });
210         localAvailability.executeNode(block->at(nodeIndex));
211     }
212 }
213
214 } } // namespace JSC::DFG
215
216 #endif // DFGForAllKills_h
217