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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
|
/*
* Copyright (C) 2015-2019 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.
*/
#pragma once
#if ENABLE(DFG_JIT)
#include "DFGCombinedLiveness.h"
#include "DFGGraph.h"
#include "DFGOSRAvailabilityAnalysisPhase.h"
#include "FullBytecodeLiveness.h"
namespace JSC { namespace DFG {
namespace ForAllKillsInternal {
constexpr bool verbose = false;
}
// 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;
Operand alreadyNoted;
// If we MovHint something that is live at the time, then we kill the old value.
if (nodeAfter->containsMovHint()) {
Operand operand = nodeAfter->unlinkedOperand();
if (graph.isLiveInBytecode(operand, after)) {
functor(operand);
alreadyNoted = operand;
}
}
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.
auto* beforeInlineCallFrame = before.inlineCallFrame();
if (beforeInlineCallFrame == after.inlineCallFrame()) {
CodeBlock* codeBlock = graph.baselineCodeBlockFor(beforeInlineCallFrame);
if (after.bytecodeIndex().checkpoint()) {
ASSERT(before.bytecodeIndex().checkpoint() != after.bytecodeIndex().checkpoint());
ASSERT_WITH_MESSAGE(before.bytecodeIndex().offset() == after.bytecodeIndex().offset() || nodeAfter->op() == ExitOK || nodeAfter->op() == InvalidationPoint, "When the DFG does code motion it should change the forExit origin to match the surrounding bytecodes.");
auto liveBefore = tmpLivenessForCheckpoint(*codeBlock, before.bytecodeIndex());
auto liveAfter = tmpLivenessForCheckpoint(*codeBlock, after.bytecodeIndex());
liveAfter.invert();
liveBefore.filter(liveAfter);
liveBefore.forEachSetBit([&] (size_t tmp) {
functor(remapOperand(beforeInlineCallFrame, Operand::tmp(tmp)));
});
} else if (before.bytecodeIndex().checkpoint()) {
// We are moving on to another bytecode, all temps should be dead now.
auto liveBefore = tmpLivenessForCheckpoint(*codeBlock, before.bytecodeIndex());
liveBefore.forEachSetBit([&] (size_t tmp) {
functor(remapOperand(beforeInlineCallFrame, Operand::tmp(tmp)));
});
}
FullBytecodeLiveness& fullLiveness = graph.livenessFor(codeBlock);
const FastBitVector& liveBefore = fullLiveness.getLiveness(before.bytecodeIndex(), LivenessCalculationPoint::BeforeUse);
const FastBitVector& liveAfter = fullLiveness.getLiveness(after.bytecodeIndex(), LivenessCalculationPoint::BeforeUse);
(liveBefore & ~liveAfter).forEachSetBit(
[&] (size_t relativeLocal) {
functor(remapOperand(beforeInlineCallFrame, virtualRegisterForLocal(relativeLocal)));
});
return;
}
// Detect kills the super conservative way: it is killed if it was live before and dead after.
BitVector liveAfter = graph.localsAndTmpsLiveInBytecode(after);
unsigned numLocals = graph.block(0)->variablesAtHead.numberOfLocals();
graph.forAllLocalsAndTmpsLiveInBytecode(
before,
[&] (Operand operand) {
if (operand == alreadyNoted)
return;
unsigned offset = operand.isTmp() ? numLocals + operand.value() : operand.toLocal();
if (liveAfter.get(offset))
return;
functor(operand);
});
}
// 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 constexpr unsigned seenInClosureFlag = 1;
static constexpr unsigned calledFunctorFlag = 2;
UncheckedKeyHashMap<Node*, unsigned> flags;
ASSERT(nodeIndex);
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 = block->at(nodeIndex - 1);
forAllKilledOperands(
graph, before, node,
[&] (Operand operand) {
availabilityMap.closeStartingWithLocal(
operand,
[&] (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(graph);
localAvailability.beginBlock(block);
// Start running functor 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 = 0; nodeIndex < block->size(); ++nodeIndex) {
dataLogLnIf(ForAllKillsInternal::verbose, "local availability at index: ", nodeIndex, " ", localAvailability.m_availability);
if (nodeIndex) {
forAllKilledNodesAtNodeIndex(
graph, localAvailability.m_availability, block, nodeIndex,
[&] (Node* node) {
functor(nodeIndex, node);
});
}
localAvailability.executeNode(block->at(nodeIndex));
}
}
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)
|
