1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
/*
* Copyright (C) 2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef DFGForAllKills_h
#define DFGForAllKills_h
#include "DFGCombinedLiveness.h"
#include "DFGGraph.h"
#include "DFGOSRAvailabilityAnalysisPhase.h"
#include "FullBytecodeLiveness.h"
namespace JSC { namespace DFG {
// Utilities for finding the last points where a node is live in DFG SSA. This accounts for liveness due
// to OSR exit. This is usually used for enumerating over all of the program points where a node is live,
// by exploring all blocks where the node is live at tail and then exploring all program points where the
// node is killed. A prerequisite to using these utilities is having liveness and OSR availability
// computed.
// This tells you those things that die on the boundary between nodeBefore and nodeAfter. It is
// conservative in the sense that it might resort to telling you some things that are still live at
// nodeAfter.
template<typename Functor>
void forAllKilledOperands(Graph& graph, Node* nodeBefore, Node* nodeAfter, const Functor& functor)
{
CodeOrigin before = nodeBefore->origin.forExit;
if (!nodeAfter) {
graph.forAllLiveInBytecode(before, functor);
return;
}
CodeOrigin after = nodeAfter->origin.forExit;
VirtualRegister alreadyNoted;
// If we MovHint something that is live at the time, then we kill the old value.
if (nodeAfter->containsMovHint()) {
VirtualRegister reg = nodeAfter->unlinkedLocal();
if (graph.isLiveInBytecode(reg, after)) {
functor(reg);
alreadyNoted = reg;
}
}
if (before == after)
return;
// It's easier to do this if the inline call frames are the same. This is way faster than the
// other loop, below.
if (before.inlineCallFrame == after.inlineCallFrame) {
int stackOffset = before.inlineCallFrame ? before.inlineCallFrame->stackOffset : 0;
CodeBlock* codeBlock = graph.baselineCodeBlockFor(before.inlineCallFrame);
FullBytecodeLiveness& fullLiveness = graph.livenessFor(codeBlock);
const FastBitVector& liveBefore = fullLiveness.getLiveness(before.bytecodeIndex);
const FastBitVector& liveAfter = fullLiveness.getLiveness(after.bytecodeIndex);
for (unsigned relativeLocal = codeBlock->m_numCalleeLocals; relativeLocal--;) {
if (liveBefore.get(relativeLocal) && !liveAfter.get(relativeLocal))
functor(virtualRegisterForLocal(relativeLocal) + stackOffset);
}
return;
}
// Detect kills the super conservative way: it is killed if it was live before and dead after.
BitVector liveAfter = graph.localsLiveInBytecode(after);
graph.forAllLocalsLiveInBytecode(
before,
[&] (VirtualRegister reg) {
if (reg == alreadyNoted)
return;
if (liveAfter.get(reg.toLocal()))
return;
functor(reg);
});
}
// Tells you all of the nodes that would no longer be live across the node at this nodeIndex.
template<typename Functor>
void forAllKilledNodesAtNodeIndex(
Graph& graph, AvailabilityMap& availabilityMap, BasicBlock* block, unsigned nodeIndex,
const Functor& functor)
{
static const unsigned seenInClosureFlag = 1;
static const unsigned calledFunctorFlag = 2;
HashMap<Node*, unsigned> flags;
Node* node = block->at(nodeIndex);
graph.doToChildren(
node,
[&] (Edge edge) {
if (edge.doesKill()) {
auto& result = flags.add(edge.node(), 0).iterator->value;
if (!(result & calledFunctorFlag)) {
functor(edge.node());
result |= calledFunctorFlag;
}
}
});
Node* before = nullptr;
if (nodeIndex)
before = block->at(nodeIndex - 1);
forAllKilledOperands(
graph, before, node,
[&] (VirtualRegister reg) {
availabilityMap.closeStartingWithLocal(
reg,
[&] (Node* node) -> bool {
return flags.get(node) & seenInClosureFlag;
},
[&] (Node* node) -> bool {
auto& resultFlags = flags.add(node, 0).iterator->value;
bool result = resultFlags & seenInClosureFlag;
if (!(resultFlags & calledFunctorFlag))
functor(node);
resultFlags |= seenInClosureFlag | calledFunctorFlag;
return result;
});
});
}
// Tells you all of the places to start searching from in a basic block. Gives you the node index at which
// the value is either no longer live. This pretends that nodes are dead at the end of the block, so that
// you can use this to do per-basic-block analyses.
template<typename Functor>
void forAllKillsInBlock(
Graph& graph, const CombinedLiveness& combinedLiveness, BasicBlock* block,
const Functor& functor)
{
for (Node* node : combinedLiveness.liveAtTail[block])
functor(block->size(), node);
LocalOSRAvailabilityCalculator localAvailability;
localAvailability.beginBlock(block);
// Start at the second node, because the functor is expected to only inspect nodes from the start of
// the block up to nodeIndex (exclusive), so if nodeIndex is zero then the functor has nothing to do.
for (unsigned nodeIndex = 1; nodeIndex < block->size(); ++nodeIndex) {
forAllKilledNodesAtNodeIndex(
graph, localAvailability.m_availability, block, nodeIndex,
[&] (Node* node) {
functor(nodeIndex, node);
});
localAvailability.executeNode(block->at(nodeIndex));
}
}
} } // namespace JSC::DFG
#endif // DFGForAllKills_h
|
