43972
|
1 |
/*
|
52910
|
2 |
* Copyright (c) 2011, 2018, Oracle and/or its affiliates. All rights reserved.
|
43972
|
3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
|
4 |
*
|
|
5 |
* This code is free software; you can redistribute it and/or modify it
|
|
6 |
* under the terms of the GNU General Public License version 2 only, as
|
|
7 |
* published by the Free Software Foundation.
|
|
8 |
*
|
|
9 |
* This code is distributed in the hope that it will be useful, but WITHOUT
|
|
10 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
11 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
12 |
* version 2 for more details (a copy is included in the LICENSE file that
|
|
13 |
* accompanied this code).
|
|
14 |
*
|
|
15 |
* You should have received a copy of the GNU General Public License version
|
|
16 |
* 2 along with this work; if not, write to the Free Software Foundation,
|
|
17 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
|
18 |
*
|
|
19 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
|
|
20 |
* or visit www.oracle.com if you need additional information or have any
|
|
21 |
* questions.
|
|
22 |
*/
|
50858
|
23 |
|
|
24 |
|
43972
|
25 |
package org.graalvm.compiler.virtual.phases.ea;
|
|
26 |
|
|
27 |
import java.util.ArrayList;
|
46371
|
28 |
import java.util.BitSet;
|
46344
|
29 |
import java.util.Iterator;
|
43972
|
30 |
import java.util.List;
|
46509
|
31 |
import java.util.function.IntUnaryOperator;
|
43972
|
32 |
|
49873
|
33 |
import jdk.internal.vm.compiler.collections.EconomicMap;
|
|
34 |
import jdk.internal.vm.compiler.collections.EconomicSet;
|
|
35 |
import jdk.internal.vm.compiler.collections.Equivalence;
|
43972
|
36 |
import org.graalvm.compiler.core.common.GraalOptions;
|
|
37 |
import org.graalvm.compiler.core.common.cfg.Loop;
|
|
38 |
import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
|
|
39 |
import org.graalvm.compiler.core.common.type.Stamp;
|
|
40 |
import org.graalvm.compiler.core.common.type.StampFactory;
|
46640
|
41 |
import org.graalvm.compiler.debug.CounterKey;
|
|
42 |
import org.graalvm.compiler.debug.DebugContext;
|
43972
|
43 |
import org.graalvm.compiler.graph.Node;
|
|
44 |
import org.graalvm.compiler.graph.NodeBitMap;
|
|
45 |
import org.graalvm.compiler.graph.Position;
|
|
46 |
import org.graalvm.compiler.graph.spi.Canonicalizable;
|
|
47 |
import org.graalvm.compiler.nodes.AbstractEndNode;
|
|
48 |
import org.graalvm.compiler.nodes.CallTargetNode;
|
|
49 |
import org.graalvm.compiler.nodes.ConstantNode;
|
|
50 |
import org.graalvm.compiler.nodes.ControlSinkNode;
|
|
51 |
import org.graalvm.compiler.nodes.FixedNode;
|
|
52 |
import org.graalvm.compiler.nodes.FixedWithNextNode;
|
|
53 |
import org.graalvm.compiler.nodes.FrameState;
|
|
54 |
import org.graalvm.compiler.nodes.Invoke;
|
|
55 |
import org.graalvm.compiler.nodes.LoopBeginNode;
|
|
56 |
import org.graalvm.compiler.nodes.LoopExitNode;
|
48190
|
57 |
import org.graalvm.compiler.nodes.NodeView;
|
43972
|
58 |
import org.graalvm.compiler.nodes.PhiNode;
|
|
59 |
import org.graalvm.compiler.nodes.ProxyNode;
|
|
60 |
import org.graalvm.compiler.nodes.StructuredGraph;
|
|
61 |
import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
|
54328
|
62 |
import org.graalvm.compiler.nodes.UnwindNode;
|
43972
|
63 |
import org.graalvm.compiler.nodes.ValueNode;
|
|
64 |
import org.graalvm.compiler.nodes.ValuePhiNode;
|
|
65 |
import org.graalvm.compiler.nodes.ValueProxyNode;
|
|
66 |
import org.graalvm.compiler.nodes.VirtualState;
|
|
67 |
import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
|
|
68 |
import org.graalvm.compiler.nodes.cfg.Block;
|
|
69 |
import org.graalvm.compiler.nodes.spi.LoweringProvider;
|
|
70 |
import org.graalvm.compiler.nodes.spi.NodeWithState;
|
|
71 |
import org.graalvm.compiler.nodes.spi.Virtualizable;
|
|
72 |
import org.graalvm.compiler.nodes.spi.VirtualizableAllocation;
|
|
73 |
import org.graalvm.compiler.nodes.spi.VirtualizerTool;
|
46344
|
74 |
import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode;
|
43972
|
75 |
import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
|
46344
|
76 |
import org.graalvm.compiler.virtual.nodes.VirtualObjectState;
|
43972
|
77 |
|
|
78 |
import jdk.vm.ci.meta.ConstantReflectionProvider;
|
|
79 |
import jdk.vm.ci.meta.JavaConstant;
|
|
80 |
import jdk.vm.ci.meta.JavaKind;
|
|
81 |
import jdk.vm.ci.meta.MetaAccessProvider;
|
|
82 |
|
|
83 |
public abstract class PartialEscapeClosure<BlockT extends PartialEscapeBlockState<BlockT>> extends EffectsClosure<BlockT> {
|
|
84 |
|
46640
|
85 |
public static final CounterKey COUNTER_MATERIALIZATIONS = DebugContext.counter("Materializations");
|
|
86 |
public static final CounterKey COUNTER_MATERIALIZATIONS_PHI = DebugContext.counter("MaterializationsPhi");
|
|
87 |
public static final CounterKey COUNTER_MATERIALIZATIONS_MERGE = DebugContext.counter("MaterializationsMerge");
|
|
88 |
public static final CounterKey COUNTER_MATERIALIZATIONS_UNHANDLED = DebugContext.counter("MaterializationsUnhandled");
|
|
89 |
public static final CounterKey COUNTER_MATERIALIZATIONS_LOOP_REITERATION = DebugContext.counter("MaterializationsLoopReiteration");
|
|
90 |
public static final CounterKey COUNTER_MATERIALIZATIONS_LOOP_END = DebugContext.counter("MaterializationsLoopEnd");
|
|
91 |
public static final CounterKey COUNTER_ALLOCATION_REMOVED = DebugContext.counter("AllocationsRemoved");
|
|
92 |
public static final CounterKey COUNTER_MEMORYCHECKPOINT = DebugContext.counter("MemoryCheckpoint");
|
43972
|
93 |
|
46344
|
94 |
/**
|
|
95 |
* Nodes with inputs that were modified during analysis are marked in this bitset - this way
|
|
96 |
* nodes that are not influenced at all by analysis can be rejected quickly.
|
|
97 |
*/
|
43972
|
98 |
private final NodeBitMap hasVirtualInputs;
|
|
99 |
|
46344
|
100 |
/**
|
|
101 |
* This is handed out to implementers of {@link Virtualizable}.
|
|
102 |
*/
|
|
103 |
protected final VirtualizerToolImpl tool;
|
|
104 |
|
|
105 |
/**
|
|
106 |
* The indexes into this array correspond to {@link VirtualObjectNode#getObjectId()}.
|
|
107 |
*/
|
43972
|
108 |
public final ArrayList<VirtualObjectNode> virtualObjects = new ArrayList<>();
|
|
109 |
|
46344
|
110 |
@Override
|
|
111 |
public boolean needsApplyEffects() {
|
|
112 |
if (hasChanged()) {
|
|
113 |
return true;
|
|
114 |
}
|
|
115 |
/*
|
|
116 |
* If there is a mismatch between the number of materializations and the number of
|
|
117 |
* virtualizations, we need to apply effects, even if there were no other significant
|
51436
|
118 |
* changes to the graph. This applies to each block, since moving from one block to the
|
|
119 |
* other can also be important (if the probabilities of the block differ).
|
46344
|
120 |
*/
|
|
121 |
for (Block block : cfg.getBlocks()) {
|
|
122 |
GraphEffectList effects = blockEffects.get(block);
|
|
123 |
if (effects != null) {
|
51436
|
124 |
if (effects.getVirtualizationDelta() != 0) {
|
|
125 |
return true;
|
|
126 |
}
|
46344
|
127 |
}
|
|
128 |
}
|
51436
|
129 |
return false;
|
46344
|
130 |
}
|
|
131 |
|
43972
|
132 |
private final class CollectVirtualObjectsClosure extends NodeClosure<ValueNode> {
|
46344
|
133 |
private final EconomicSet<VirtualObjectNode> virtual;
|
43972
|
134 |
private final GraphEffectList effects;
|
|
135 |
private final BlockT state;
|
|
136 |
|
46344
|
137 |
private CollectVirtualObjectsClosure(EconomicSet<VirtualObjectNode> virtual, GraphEffectList effects, BlockT state) {
|
43972
|
138 |
this.virtual = virtual;
|
|
139 |
this.effects = effects;
|
|
140 |
this.state = state;
|
|
141 |
}
|
|
142 |
|
|
143 |
@Override
|
|
144 |
public void apply(Node usage, ValueNode value) {
|
|
145 |
if (value instanceof VirtualObjectNode) {
|
|
146 |
VirtualObjectNode object = (VirtualObjectNode) value;
|
|
147 |
if (object.getObjectId() != -1 && state.getObjectStateOptional(object) != null) {
|
|
148 |
virtual.add(object);
|
|
149 |
}
|
|
150 |
} else {
|
|
151 |
ValueNode alias = getAlias(value);
|
|
152 |
if (alias instanceof VirtualObjectNode) {
|
|
153 |
VirtualObjectNode object = (VirtualObjectNode) alias;
|
|
154 |
virtual.add(object);
|
|
155 |
effects.replaceFirstInput(usage, value, object);
|
|
156 |
}
|
|
157 |
}
|
|
158 |
}
|
|
159 |
}
|
|
160 |
|
|
161 |
/**
|
|
162 |
* Final subclass of PartialEscapeClosure, for performance and to make everything behave nicely
|
|
163 |
* with generics.
|
|
164 |
*/
|
|
165 |
public static final class Final extends PartialEscapeClosure<PartialEscapeBlockState.Final> {
|
|
166 |
|
|
167 |
public Final(ScheduleResult schedule, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider,
|
|
168 |
LoweringProvider loweringProvider) {
|
|
169 |
super(schedule, metaAccess, constantReflection, constantFieldProvider, loweringProvider);
|
|
170 |
}
|
|
171 |
|
|
172 |
@Override
|
|
173 |
protected PartialEscapeBlockState.Final getInitialState() {
|
46640
|
174 |
return new PartialEscapeBlockState.Final(tool.getOptions(), tool.getDebug());
|
43972
|
175 |
}
|
|
176 |
|
|
177 |
@Override
|
|
178 |
protected PartialEscapeBlockState.Final cloneState(PartialEscapeBlockState.Final oldState) {
|
|
179 |
return new PartialEscapeBlockState.Final(oldState);
|
|
180 |
}
|
|
181 |
}
|
|
182 |
|
|
183 |
public PartialEscapeClosure(ScheduleResult schedule, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider) {
|
|
184 |
this(schedule, metaAccess, constantReflection, constantFieldProvider, null);
|
|
185 |
}
|
|
186 |
|
|
187 |
public PartialEscapeClosure(ScheduleResult schedule, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider,
|
|
188 |
LoweringProvider loweringProvider) {
|
|
189 |
super(schedule, schedule.getCFG());
|
|
190 |
StructuredGraph graph = schedule.getCFG().graph;
|
|
191 |
this.hasVirtualInputs = graph.createNodeBitMap();
|
46640
|
192 |
this.tool = new VirtualizerToolImpl(metaAccess, constantReflection, constantFieldProvider, this, graph.getAssumptions(), graph.getOptions(), debug, loweringProvider);
|
43972
|
193 |
}
|
|
194 |
|
|
195 |
/**
|
|
196 |
* @return true if the node was deleted, false otherwise
|
|
197 |
*/
|
|
198 |
@Override
|
|
199 |
protected boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
|
|
200 |
/*
|
|
201 |
* These checks make up for the fact that an earliest schedule moves CallTargetNodes upwards
|
|
202 |
* and thus materializes virtual objects needlessly. Also, FrameStates and ConstantNodes are
|
|
203 |
* scheduled, but can safely be ignored.
|
|
204 |
*/
|
|
205 |
if (node instanceof CallTargetNode || node instanceof FrameState || node instanceof ConstantNode) {
|
|
206 |
return false;
|
|
207 |
} else if (node instanceof Invoke) {
|
|
208 |
processNodeInternal(((Invoke) node).callTarget(), state, effects, lastFixedNode);
|
|
209 |
}
|
|
210 |
return processNodeInternal(node, state, effects, lastFixedNode);
|
|
211 |
}
|
|
212 |
|
|
213 |
private boolean processNodeInternal(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
|
|
214 |
FixedNode nextFixedNode = lastFixedNode == null ? null : lastFixedNode.next();
|
46640
|
215 |
VirtualUtil.trace(node.getOptions(), debug, "%s", node);
|
43972
|
216 |
|
|
217 |
if (requiresProcessing(node)) {
|
|
218 |
if (processVirtualizable((ValueNode) node, nextFixedNode, state, effects) == false) {
|
|
219 |
return false;
|
|
220 |
}
|
|
221 |
if (tool.isDeleted()) {
|
46640
|
222 |
VirtualUtil.trace(node.getOptions(), debug, "deleted virtualizable allocation %s", node);
|
43972
|
223 |
return true;
|
|
224 |
}
|
|
225 |
}
|
|
226 |
if (hasVirtualInputs.isMarked(node) && node instanceof ValueNode) {
|
|
227 |
if (node instanceof Virtualizable) {
|
|
228 |
if (processVirtualizable((ValueNode) node, nextFixedNode, state, effects) == false) {
|
|
229 |
return false;
|
|
230 |
}
|
|
231 |
if (tool.isDeleted()) {
|
46640
|
232 |
VirtualUtil.trace(node.getOptions(), debug, "deleted virtualizable node %s", node);
|
43972
|
233 |
return true;
|
|
234 |
}
|
|
235 |
}
|
|
236 |
processNodeInputs((ValueNode) node, nextFixedNode, state, effects);
|
|
237 |
}
|
|
238 |
|
|
239 |
if (hasScalarReplacedInputs(node) && node instanceof ValueNode) {
|
|
240 |
if (processNodeWithScalarReplacedInputs((ValueNode) node, nextFixedNode, state, effects)) {
|
|
241 |
return true;
|
|
242 |
}
|
|
243 |
}
|
|
244 |
return false;
|
|
245 |
}
|
|
246 |
|
|
247 |
protected boolean requiresProcessing(Node node) {
|
|
248 |
return node instanceof VirtualizableAllocation;
|
|
249 |
}
|
|
250 |
|
46344
|
251 |
private boolean processVirtualizable(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
|
|
252 |
tool.reset(state, node, insertBefore, effects);
|
|
253 |
return virtualize(node, tool);
|
|
254 |
}
|
|
255 |
|
|
256 |
protected boolean virtualize(ValueNode node, VirtualizerTool vt) {
|
|
257 |
((Virtualizable) node).virtualize(vt);
|
|
258 |
return true; // request further processing
|
|
259 |
}
|
|
260 |
|
|
261 |
/**
|
|
262 |
* This tries to canonicalize the node based on improved (replaced) inputs.
|
|
263 |
*/
|
46807
|
264 |
@SuppressWarnings("unchecked")
|
43972
|
265 |
private boolean processNodeWithScalarReplacedInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
|
|
266 |
ValueNode canonicalizedValue = node;
|
|
267 |
if (node instanceof Canonicalizable.Unary<?>) {
|
|
268 |
Canonicalizable.Unary<ValueNode> canonicalizable = (Canonicalizable.Unary<ValueNode>) node;
|
|
269 |
ObjectState valueObj = getObjectState(state, canonicalizable.getValue());
|
|
270 |
ValueNode valueAlias = valueObj != null ? valueObj.getMaterializedValue() : getScalarAlias(canonicalizable.getValue());
|
|
271 |
if (valueAlias != canonicalizable.getValue()) {
|
|
272 |
canonicalizedValue = (ValueNode) canonicalizable.canonical(tool, valueAlias);
|
|
273 |
}
|
|
274 |
} else if (node instanceof Canonicalizable.Binary<?>) {
|
|
275 |
Canonicalizable.Binary<ValueNode> canonicalizable = (Canonicalizable.Binary<ValueNode>) node;
|
|
276 |
ObjectState xObj = getObjectState(state, canonicalizable.getX());
|
|
277 |
ValueNode xAlias = xObj != null ? xObj.getMaterializedValue() : getScalarAlias(canonicalizable.getX());
|
|
278 |
ObjectState yObj = getObjectState(state, canonicalizable.getY());
|
|
279 |
ValueNode yAlias = yObj != null ? yObj.getMaterializedValue() : getScalarAlias(canonicalizable.getY());
|
|
280 |
if (xAlias != canonicalizable.getX() || yAlias != canonicalizable.getY()) {
|
|
281 |
canonicalizedValue = (ValueNode) canonicalizable.canonical(tool, xAlias, yAlias);
|
|
282 |
}
|
|
283 |
} else {
|
|
284 |
return false;
|
|
285 |
}
|
|
286 |
if (canonicalizedValue != node && canonicalizedValue != null) {
|
|
287 |
if (canonicalizedValue.isAlive()) {
|
|
288 |
ValueNode alias = getAliasAndResolve(state, canonicalizedValue);
|
|
289 |
if (alias instanceof VirtualObjectNode) {
|
46344
|
290 |
addVirtualAlias((VirtualObjectNode) alias, node);
|
43972
|
291 |
effects.deleteNode(node);
|
|
292 |
} else {
|
46344
|
293 |
effects.replaceAtUsages(node, alias, insertBefore);
|
43972
|
294 |
addScalarAlias(node, alias);
|
|
295 |
}
|
|
296 |
} else {
|
|
297 |
if (!prepareCanonicalNode(canonicalizedValue, state, effects)) {
|
46640
|
298 |
VirtualUtil.trace(node.getOptions(), debug, "replacement via canonicalization too complex: %s -> %s", node, canonicalizedValue);
|
43972
|
299 |
return false;
|
|
300 |
}
|
|
301 |
if (canonicalizedValue instanceof ControlSinkNode) {
|
|
302 |
effects.replaceWithSink((FixedWithNextNode) node, (ControlSinkNode) canonicalizedValue);
|
|
303 |
state.markAsDead();
|
|
304 |
} else {
|
46344
|
305 |
effects.replaceAtUsages(node, canonicalizedValue, insertBefore);
|
43972
|
306 |
addScalarAlias(node, canonicalizedValue);
|
|
307 |
}
|
|
308 |
}
|
46640
|
309 |
VirtualUtil.trace(node.getOptions(), debug, "replaced via canonicalization: %s -> %s", node, canonicalizedValue);
|
43972
|
310 |
return true;
|
|
311 |
}
|
|
312 |
return false;
|
|
313 |
}
|
|
314 |
|
46344
|
315 |
/**
|
|
316 |
* Nodes created during canonicalizations need to be scanned for values that were replaced.
|
|
317 |
*/
|
43972
|
318 |
private boolean prepareCanonicalNode(ValueNode node, BlockT state, GraphEffectList effects) {
|
|
319 |
assert !node.isAlive();
|
|
320 |
for (Position pos : node.inputPositions()) {
|
|
321 |
Node input = pos.get(node);
|
|
322 |
if (input instanceof ValueNode) {
|
|
323 |
if (input.isAlive()) {
|
46344
|
324 |
if (!(input instanceof VirtualObjectNode)) {
|
|
325 |
ObjectState obj = getObjectState(state, (ValueNode) input);
|
|
326 |
if (obj != null) {
|
|
327 |
if (obj.isVirtual()) {
|
|
328 |
return false;
|
|
329 |
} else {
|
|
330 |
pos.initialize(node, obj.getMaterializedValue());
|
|
331 |
}
|
43972
|
332 |
} else {
|
46344
|
333 |
pos.initialize(node, getScalarAlias((ValueNode) input));
|
43972
|
334 |
}
|
|
335 |
}
|
|
336 |
} else {
|
|
337 |
if (!prepareCanonicalNode((ValueNode) input, state, effects)) {
|
|
338 |
return false;
|
|
339 |
}
|
|
340 |
}
|
|
341 |
}
|
|
342 |
}
|
|
343 |
return true;
|
|
344 |
}
|
|
345 |
|
46344
|
346 |
/**
|
|
347 |
* This replaces all inputs that point to virtual or materialized values with the actual value,
|
|
348 |
* materializing if necessary. Also takes care of frame states, adding the necessary
|
|
349 |
* {@link VirtualObjectState}.
|
|
350 |
*/
|
43972
|
351 |
private void processNodeInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
|
46640
|
352 |
VirtualUtil.trace(node.getOptions(), debug, "processing nodewithstate: %s", node);
|
43972
|
353 |
for (Node input : node.inputs()) {
|
|
354 |
if (input instanceof ValueNode) {
|
|
355 |
ValueNode alias = getAlias((ValueNode) input);
|
|
356 |
if (alias instanceof VirtualObjectNode) {
|
|
357 |
int id = ((VirtualObjectNode) alias).getObjectId();
|
|
358 |
ensureMaterialized(state, id, insertBefore, effects, COUNTER_MATERIALIZATIONS_UNHANDLED);
|
|
359 |
effects.replaceFirstInput(node, input, state.getObjectState(id).getMaterializedValue());
|
46640
|
360 |
VirtualUtil.trace(node.getOptions(), debug, "replacing input %s at %s", input, node);
|
43972
|
361 |
}
|
|
362 |
}
|
|
363 |
}
|
|
364 |
if (node instanceof NodeWithState) {
|
|
365 |
processNodeWithState((NodeWithState) node, state, effects);
|
|
366 |
}
|
|
367 |
}
|
|
368 |
|
|
369 |
private void processNodeWithState(NodeWithState nodeWithState, BlockT state, GraphEffectList effects) {
|
|
370 |
for (FrameState fs : nodeWithState.states()) {
|
|
371 |
FrameState frameState = getUniqueFramestate(nodeWithState, fs);
|
46344
|
372 |
EconomicSet<VirtualObjectNode> virtual = EconomicSet.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE);
|
43972
|
373 |
frameState.applyToNonVirtual(new CollectVirtualObjectsClosure(virtual, effects, state));
|
|
374 |
collectLockedVirtualObjects(state, virtual);
|
|
375 |
collectReferencedVirtualObjects(state, virtual);
|
|
376 |
addVirtualMappings(frameState, virtual, state, effects);
|
|
377 |
}
|
|
378 |
}
|
|
379 |
|
|
380 |
private static FrameState getUniqueFramestate(NodeWithState nodeWithState, FrameState frameState) {
|
46344
|
381 |
if (frameState.hasMoreThanOneUsage()) {
|
43972
|
382 |
// Can happen for example from inlined snippets with multiple state split nodes.
|
|
383 |
FrameState copy = (FrameState) frameState.copyWithInputs();
|
|
384 |
nodeWithState.asNode().replaceFirstInput(frameState, copy);
|
|
385 |
return copy;
|
|
386 |
}
|
|
387 |
return frameState;
|
|
388 |
}
|
|
389 |
|
46344
|
390 |
private void addVirtualMappings(FrameState frameState, EconomicSet<VirtualObjectNode> virtual, BlockT state, GraphEffectList effects) {
|
43972
|
391 |
for (VirtualObjectNode obj : virtual) {
|
46640
|
392 |
effects.addVirtualMapping(frameState, state.getObjectState(obj).createEscapeObjectState(debug, obj));
|
43972
|
393 |
}
|
|
394 |
}
|
|
395 |
|
46344
|
396 |
private void collectReferencedVirtualObjects(BlockT state, EconomicSet<VirtualObjectNode> virtual) {
|
|
397 |
Iterator<VirtualObjectNode> iterator = virtual.iterator();
|
|
398 |
while (iterator.hasNext()) {
|
|
399 |
VirtualObjectNode object = iterator.next();
|
43972
|
400 |
int id = object.getObjectId();
|
|
401 |
if (id != -1) {
|
|
402 |
ObjectState objState = state.getObjectStateOptional(id);
|
|
403 |
if (objState != null && objState.isVirtual()) {
|
|
404 |
for (ValueNode entry : objState.getEntries()) {
|
|
405 |
if (entry instanceof VirtualObjectNode) {
|
|
406 |
VirtualObjectNode entryVirtual = (VirtualObjectNode) entry;
|
|
407 |
if (!virtual.contains(entryVirtual)) {
|
|
408 |
virtual.add(entryVirtual);
|
|
409 |
}
|
|
410 |
}
|
|
411 |
}
|
|
412 |
}
|
|
413 |
}
|
|
414 |
}
|
|
415 |
}
|
|
416 |
|
46344
|
417 |
private void collectLockedVirtualObjects(BlockT state, EconomicSet<VirtualObjectNode> virtual) {
|
43972
|
418 |
for (int i = 0; i < state.getStateCount(); i++) {
|
|
419 |
ObjectState objState = state.getObjectStateOptional(i);
|
|
420 |
if (objState != null && objState.isVirtual() && objState.hasLocks()) {
|
|
421 |
virtual.add(virtualObjects.get(i));
|
|
422 |
}
|
|
423 |
}
|
|
424 |
}
|
|
425 |
|
|
426 |
/**
|
|
427 |
* @return true if materialization happened, false if not.
|
|
428 |
*/
|
46640
|
429 |
protected boolean ensureMaterialized(PartialEscapeBlockState<?> state, int object, FixedNode materializeBefore, GraphEffectList effects, CounterKey counter) {
|
43972
|
430 |
if (state.getObjectState(object).isVirtual()) {
|
46640
|
431 |
counter.increment(debug);
|
43972
|
432 |
VirtualObjectNode virtual = virtualObjects.get(object);
|
|
433 |
state.materializeBefore(materializeBefore, virtual, effects);
|
46371
|
434 |
assert !updateStatesForMaterialized(state, virtual, state.getObjectState(object).getMaterializedValue()) : "method must already have been called before";
|
43972
|
435 |
return true;
|
|
436 |
} else {
|
|
437 |
return false;
|
|
438 |
}
|
|
439 |
}
|
|
440 |
|
46371
|
441 |
public static boolean updateStatesForMaterialized(PartialEscapeBlockState<?> state, VirtualObjectNode virtual, ValueNode materializedValue) {
|
43972
|
442 |
// update all existing states with the newly materialized object
|
46371
|
443 |
boolean change = false;
|
43972
|
444 |
for (int i = 0; i < state.getStateCount(); i++) {
|
|
445 |
ObjectState objState = state.getObjectStateOptional(i);
|
|
446 |
if (objState != null && objState.isVirtual()) {
|
|
447 |
ValueNode[] entries = objState.getEntries();
|
|
448 |
for (int i2 = 0; i2 < entries.length; i2++) {
|
|
449 |
if (entries[i2] == virtual) {
|
|
450 |
state.setEntry(i, i2, materializedValue);
|
46371
|
451 |
change = true;
|
43972
|
452 |
}
|
|
453 |
}
|
|
454 |
}
|
|
455 |
}
|
46371
|
456 |
return change;
|
43972
|
457 |
}
|
|
458 |
|
|
459 |
@Override
|
|
460 |
protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT originalInitialState) {
|
|
461 |
BlockT initialState = super.stripKilledLoopLocations(loop, originalInitialState);
|
46344
|
462 |
if (loop.getDepth() > GraalOptions.EscapeAnalysisLoopCutoff.getValue(cfg.graph.getOptions())) {
|
43972
|
463 |
/*
|
|
464 |
* After we've reached the maximum loop nesting, we'll simply materialize everything we
|
|
465 |
* can to make sure that the loops only need to be iterated one time. Care is taken here
|
|
466 |
* to not materialize virtual objects that have the "ensureVirtualized" flag set.
|
|
467 |
*/
|
|
468 |
LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode();
|
|
469 |
AbstractEndNode end = loopBegin.forwardEnd();
|
|
470 |
Block loopPredecessor = loop.getHeader().getFirstPredecessor();
|
|
471 |
assert loopPredecessor.getEndNode() == end;
|
|
472 |
int length = initialState.getStateCount();
|
|
473 |
|
|
474 |
boolean change;
|
46371
|
475 |
BitSet ensureVirtualized = new BitSet(length);
|
43972
|
476 |
for (int i = 0; i < length; i++) {
|
|
477 |
ObjectState state = initialState.getObjectStateOptional(i);
|
|
478 |
if (state != null && state.isVirtual() && state.getEnsureVirtualized()) {
|
46371
|
479 |
ensureVirtualized.set(i);
|
43972
|
480 |
}
|
|
481 |
}
|
|
482 |
do {
|
|
483 |
// propagate "ensureVirtualized" flag
|
|
484 |
change = false;
|
|
485 |
for (int i = 0; i < length; i++) {
|
46371
|
486 |
if (!ensureVirtualized.get(i)) {
|
43972
|
487 |
ObjectState state = initialState.getObjectStateOptional(i);
|
|
488 |
if (state != null && state.isVirtual()) {
|
|
489 |
for (ValueNode entry : state.getEntries()) {
|
|
490 |
if (entry instanceof VirtualObjectNode) {
|
46371
|
491 |
if (ensureVirtualized.get(((VirtualObjectNode) entry).getObjectId())) {
|
43972
|
492 |
change = true;
|
46371
|
493 |
ensureVirtualized.set(i);
|
43972
|
494 |
break;
|
|
495 |
}
|
|
496 |
}
|
|
497 |
}
|
|
498 |
}
|
|
499 |
}
|
|
500 |
}
|
|
501 |
} while (change);
|
|
502 |
|
|
503 |
for (int i = 0; i < length; i++) {
|
|
504 |
ObjectState state = initialState.getObjectStateOptional(i);
|
46371
|
505 |
if (state != null && state.isVirtual() && !ensureVirtualized.get(i)) {
|
43972
|
506 |
initialState.materializeBefore(end, virtualObjects.get(i), blockEffects.get(loopPredecessor));
|
|
507 |
}
|
|
508 |
}
|
|
509 |
}
|
|
510 |
return initialState;
|
|
511 |
}
|
|
512 |
|
|
513 |
@Override
|
|
514 |
protected void processInitialLoopState(Loop<Block> loop, BlockT initialState) {
|
|
515 |
for (PhiNode phi : ((LoopBeginNode) loop.getHeader().getBeginNode()).phis()) {
|
|
516 |
if (phi.valueAt(0) != null) {
|
|
517 |
ValueNode alias = getAliasAndResolve(initialState, phi.valueAt(0));
|
|
518 |
if (alias instanceof VirtualObjectNode) {
|
|
519 |
VirtualObjectNode virtual = (VirtualObjectNode) alias;
|
46344
|
520 |
addVirtualAlias(virtual, phi);
|
43972
|
521 |
} else {
|
|
522 |
aliases.set(phi, null);
|
|
523 |
}
|
|
524 |
}
|
|
525 |
}
|
|
526 |
}
|
|
527 |
|
|
528 |
@Override
|
|
529 |
protected void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects) {
|
|
530 |
if (exitNode.graph().hasValueProxies()) {
|
46344
|
531 |
EconomicMap<Integer, ProxyNode> proxies = EconomicMap.create(Equivalence.DEFAULT);
|
43972
|
532 |
for (ProxyNode proxy : exitNode.proxies()) {
|
|
533 |
ValueNode alias = getAlias(proxy.value());
|
|
534 |
if (alias instanceof VirtualObjectNode) {
|
|
535 |
VirtualObjectNode virtual = (VirtualObjectNode) alias;
|
|
536 |
proxies.put(virtual.getObjectId(), proxy);
|
|
537 |
}
|
|
538 |
}
|
|
539 |
for (int i = 0; i < exitState.getStateCount(); i++) {
|
|
540 |
ObjectState exitObjState = exitState.getObjectStateOptional(i);
|
|
541 |
if (exitObjState != null) {
|
|
542 |
ObjectState initialObjState = initialState.getObjectStateOptional(i);
|
|
543 |
|
|
544 |
if (exitObjState.isVirtual()) {
|
|
545 |
processVirtualAtLoopExit(exitNode, effects, i, exitObjState, initialObjState, exitState);
|
|
546 |
} else {
|
|
547 |
processMaterializedAtLoopExit(exitNode, effects, proxies, i, exitObjState, initialObjState, exitState);
|
|
548 |
}
|
|
549 |
}
|
|
550 |
}
|
|
551 |
}
|
|
552 |
}
|
|
553 |
|
46344
|
554 |
private static void processMaterializedAtLoopExit(LoopExitNode exitNode, GraphEffectList effects, EconomicMap<Integer, ProxyNode> proxies, int object, ObjectState exitObjState,
|
43972
|
555 |
ObjectState initialObjState, PartialEscapeBlockState<?> exitState) {
|
|
556 |
if (initialObjState == null || initialObjState.isVirtual()) {
|
|
557 |
ProxyNode proxy = proxies.get(object);
|
|
558 |
if (proxy == null) {
|
|
559 |
proxy = new ValueProxyNode(exitObjState.getMaterializedValue(), exitNode);
|
|
560 |
effects.addFloatingNode(proxy, "proxy");
|
|
561 |
} else {
|
|
562 |
effects.replaceFirstInput(proxy, proxy.value(), exitObjState.getMaterializedValue());
|
|
563 |
// nothing to do - will be handled in processNode
|
|
564 |
}
|
|
565 |
exitState.updateMaterializedValue(object, proxy);
|
|
566 |
} else {
|
|
567 |
if (initialObjState.getMaterializedValue() != exitObjState.getMaterializedValue()) {
|
46640
|
568 |
exitNode.getDebug().log("materialized value changes within loop: %s vs. %s at %s", initialObjState.getMaterializedValue(), exitObjState.getMaterializedValue(), exitNode);
|
43972
|
569 |
}
|
|
570 |
}
|
|
571 |
}
|
|
572 |
|
|
573 |
private static void processVirtualAtLoopExit(LoopExitNode exitNode, GraphEffectList effects, int object, ObjectState exitObjState, ObjectState initialObjState,
|
|
574 |
PartialEscapeBlockState<?> exitState) {
|
|
575 |
for (int i = 0; i < exitObjState.getEntries().length; i++) {
|
|
576 |
ValueNode value = exitState.getObjectState(object).getEntry(i);
|
|
577 |
if (!(value instanceof VirtualObjectNode || value.isConstant())) {
|
|
578 |
if (exitNode.loopBegin().isPhiAtMerge(value) || initialObjState == null || !initialObjState.isVirtual() || initialObjState.getEntry(i) != value) {
|
|
579 |
ProxyNode proxy = new ValueProxyNode(value, exitNode);
|
|
580 |
exitState.setEntry(object, i, proxy);
|
|
581 |
effects.addFloatingNode(proxy, "virtualProxy");
|
|
582 |
}
|
|
583 |
}
|
|
584 |
}
|
|
585 |
}
|
|
586 |
|
|
587 |
@Override
|
|
588 |
protected MergeProcessor createMergeProcessor(Block merge) {
|
|
589 |
return new MergeProcessor(merge);
|
|
590 |
}
|
|
591 |
|
|
592 |
protected class MergeProcessor extends EffectsClosure<BlockT>.MergeProcessor {
|
|
593 |
|
46344
|
594 |
private EconomicMap<Object, ValuePhiNode> materializedPhis;
|
|
595 |
private EconomicMap<ValueNode, ValuePhiNode[]> valuePhis;
|
|
596 |
private EconomicMap<ValuePhiNode, VirtualObjectNode> valueObjectVirtuals;
|
43972
|
597 |
private final boolean needsCaching;
|
|
598 |
|
|
599 |
public MergeProcessor(Block mergeBlock) {
|
|
600 |
super(mergeBlock);
|
46344
|
601 |
// merge will only be called multiple times for loop headers
|
43972
|
602 |
needsCaching = mergeBlock.isLoopHeader();
|
|
603 |
}
|
|
604 |
|
|
605 |
protected <T> PhiNode getPhi(T virtual, Stamp stamp) {
|
|
606 |
if (needsCaching) {
|
|
607 |
return getPhiCached(virtual, stamp);
|
|
608 |
} else {
|
|
609 |
return createValuePhi(stamp);
|
|
610 |
}
|
|
611 |
}
|
|
612 |
|
|
613 |
private <T> PhiNode getPhiCached(T virtual, Stamp stamp) {
|
|
614 |
if (materializedPhis == null) {
|
46344
|
615 |
materializedPhis = EconomicMap.create(Equivalence.DEFAULT);
|
43972
|
616 |
}
|
|
617 |
ValuePhiNode result = materializedPhis.get(virtual);
|
|
618 |
if (result == null) {
|
|
619 |
result = createValuePhi(stamp);
|
|
620 |
materializedPhis.put(virtual, result);
|
|
621 |
}
|
|
622 |
return result;
|
|
623 |
}
|
|
624 |
|
|
625 |
private PhiNode[] getValuePhis(ValueNode key, int entryCount) {
|
|
626 |
if (needsCaching) {
|
|
627 |
return getValuePhisCached(key, entryCount);
|
|
628 |
} else {
|
|
629 |
return new ValuePhiNode[entryCount];
|
|
630 |
}
|
|
631 |
}
|
|
632 |
|
|
633 |
private PhiNode[] getValuePhisCached(ValueNode key, int entryCount) {
|
|
634 |
if (valuePhis == null) {
|
46344
|
635 |
valuePhis = EconomicMap.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE);
|
43972
|
636 |
}
|
|
637 |
ValuePhiNode[] result = valuePhis.get(key);
|
|
638 |
if (result == null) {
|
|
639 |
result = new ValuePhiNode[entryCount];
|
|
640 |
valuePhis.put(key, result);
|
|
641 |
}
|
|
642 |
assert result.length == entryCount;
|
|
643 |
return result;
|
|
644 |
}
|
|
645 |
|
|
646 |
private VirtualObjectNode getValueObjectVirtual(ValuePhiNode phi, VirtualObjectNode virtual) {
|
|
647 |
if (needsCaching) {
|
|
648 |
return getValueObjectVirtualCached(phi, virtual);
|
|
649 |
} else {
|
50330
|
650 |
VirtualObjectNode duplicate = virtual.duplicate();
|
|
651 |
duplicate.setNodeSourcePosition(virtual.getNodeSourcePosition());
|
|
652 |
return duplicate;
|
43972
|
653 |
}
|
|
654 |
}
|
|
655 |
|
|
656 |
private VirtualObjectNode getValueObjectVirtualCached(ValuePhiNode phi, VirtualObjectNode virtual) {
|
|
657 |
if (valueObjectVirtuals == null) {
|
46344
|
658 |
valueObjectVirtuals = EconomicMap.create(Equivalence.IDENTITY);
|
43972
|
659 |
}
|
|
660 |
VirtualObjectNode result = valueObjectVirtuals.get(phi);
|
|
661 |
if (result == null) {
|
|
662 |
result = virtual.duplicate();
|
50330
|
663 |
result.setNodeSourcePosition(virtual.getNodeSourcePosition());
|
43972
|
664 |
valueObjectVirtuals.put(phi, result);
|
|
665 |
}
|
|
666 |
return result;
|
|
667 |
}
|
|
668 |
|
|
669 |
/**
|
|
670 |
* Merge all predecessor block states into one block state. This is an iterative process,
|
|
671 |
* because merging states can lead to materializations which make previous parts of the
|
|
672 |
* merging operation invalid. The merging process is executed until a stable state has been
|
|
673 |
* reached. This method needs to be careful to place the effects of the merging operation
|
|
674 |
* into the correct blocks.
|
|
675 |
*
|
|
676 |
* @param statesList the predecessor block states of the merge
|
|
677 |
*/
|
|
678 |
@Override
|
|
679 |
protected void merge(List<BlockT> statesList) {
|
|
680 |
|
|
681 |
PartialEscapeBlockState<?>[] states = new PartialEscapeBlockState<?>[statesList.size()];
|
|
682 |
for (int i = 0; i < statesList.size(); i++) {
|
|
683 |
states[i] = statesList.get(i);
|
|
684 |
}
|
|
685 |
|
|
686 |
// calculate the set of virtual objects that exist in all predecessors
|
|
687 |
int[] virtualObjTemp = intersectVirtualObjects(states);
|
|
688 |
|
54328
|
689 |
boolean forceMaterialization = false;
|
|
690 |
ValueNode forcedMaterializationValue = null;
|
|
691 |
FrameState frameState = merge.stateAfter();
|
|
692 |
if (frameState != null && frameState.isExceptionHandlingBCI()) {
|
|
693 |
// We can not go below merges with an exception handling bci
|
|
694 |
// it could create allocations whose slow-path has an invalid framestate
|
|
695 |
forceMaterialization = true;
|
|
696 |
// check if we can reduce the scope of forced materialization to one phi node
|
|
697 |
if (frameState.stackSize() == 1 && merge.next() instanceof UnwindNode) {
|
|
698 |
assert frameState.outerFrameState() == null;
|
|
699 |
UnwindNode unwind = (UnwindNode) merge.next();
|
|
700 |
if (unwind.exception() == frameState.stackAt(0)) {
|
|
701 |
boolean nullLocals = true;
|
|
702 |
for (int i = 0; i < frameState.localsSize(); i++) {
|
|
703 |
if (frameState.localAt(i) != null) {
|
|
704 |
nullLocals = false;
|
|
705 |
break;
|
|
706 |
}
|
|
707 |
}
|
|
708 |
if (nullLocals) {
|
|
709 |
// We found that the merge is directly followed by an unwind
|
|
710 |
// the Framestate only has the thrown value on the stack and no locals
|
|
711 |
forcedMaterializationValue = unwind.exception();
|
|
712 |
}
|
|
713 |
}
|
|
714 |
}
|
|
715 |
}
|
|
716 |
|
43972
|
717 |
boolean materialized;
|
|
718 |
do {
|
|
719 |
materialized = false;
|
|
720 |
|
54328
|
721 |
if (!forceMaterialization && PartialEscapeBlockState.identicalObjectStates(states)) {
|
43972
|
722 |
newState.adoptAddObjectStates(states[0]);
|
|
723 |
} else {
|
|
724 |
|
|
725 |
for (int object : virtualObjTemp) {
|
54328
|
726 |
if (!forceMaterialization && PartialEscapeBlockState.identicalObjectStates(states, object)) {
|
43972
|
727 |
newState.addObject(object, states[0].getObjectState(object).share());
|
|
728 |
continue;
|
|
729 |
}
|
|
730 |
|
|
731 |
// determine if all inputs are virtual or the same materialized value
|
|
732 |
int virtualCount = 0;
|
|
733 |
ObjectState startObj = states[0].getObjectState(object);
|
|
734 |
boolean locksMatch = true;
|
|
735 |
boolean ensureVirtual = true;
|
|
736 |
ValueNode uniqueMaterializedValue = startObj.isVirtual() ? null : startObj.getMaterializedValue();
|
|
737 |
for (int i = 0; i < states.length; i++) {
|
|
738 |
ObjectState obj = states[i].getObjectState(object);
|
|
739 |
ensureVirtual &= obj.getEnsureVirtualized();
|
54328
|
740 |
if (forceMaterialization) {
|
|
741 |
if (forcedMaterializationValue == null) {
|
|
742 |
uniqueMaterializedValue = null;
|
|
743 |
continue;
|
|
744 |
} else {
|
|
745 |
ValueNode value = forcedMaterializationValue;
|
|
746 |
if (merge.isPhiAtMerge(value)) {
|
|
747 |
value = ((ValuePhiNode) value).valueAt(i);
|
|
748 |
}
|
|
749 |
ValueNode alias = getAlias(value);
|
|
750 |
if (alias instanceof VirtualObjectNode && ((VirtualObjectNode) alias).getObjectId() == object) {
|
|
751 |
uniqueMaterializedValue = null;
|
|
752 |
continue;
|
|
753 |
}
|
|
754 |
}
|
|
755 |
}
|
43972
|
756 |
if (obj.isVirtual()) {
|
|
757 |
virtualCount++;
|
|
758 |
uniqueMaterializedValue = null;
|
|
759 |
locksMatch &= obj.locksEqual(startObj);
|
|
760 |
} else if (obj.getMaterializedValue() != uniqueMaterializedValue) {
|
|
761 |
uniqueMaterializedValue = null;
|
|
762 |
}
|
|
763 |
}
|
|
764 |
|
|
765 |
if (virtualCount == states.length && locksMatch) {
|
|
766 |
materialized |= mergeObjectStates(object, null, states);
|
|
767 |
} else {
|
|
768 |
if (uniqueMaterializedValue != null) {
|
|
769 |
newState.addObject(object, new ObjectState(uniqueMaterializedValue, null, ensureVirtual));
|
|
770 |
} else {
|
|
771 |
PhiNode materializedValuePhi = getPhi(object, StampFactory.forKind(JavaKind.Object));
|
|
772 |
mergeEffects.addFloatingNode(materializedValuePhi, "materializedPhi");
|
|
773 |
for (int i = 0; i < states.length; i++) {
|
|
774 |
ObjectState obj = states[i].getObjectState(object);
|
|
775 |
if (obj.isVirtual()) {
|
|
776 |
Block predecessor = getPredecessor(i);
|
|
777 |
if (!ensureVirtual && obj.isVirtual()) {
|
|
778 |
// we can materialize if not all inputs are
|
|
779 |
// "ensureVirtualized"
|
|
780 |
obj.setEnsureVirtualized(false);
|
|
781 |
}
|
|
782 |
materialized |= ensureMaterialized(states[i], object, predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_MERGE);
|
|
783 |
obj = states[i].getObjectState(object);
|
|
784 |
}
|
|
785 |
setPhiInput(materializedValuePhi, i, obj.getMaterializedValue());
|
|
786 |
}
|
|
787 |
newState.addObject(object, new ObjectState(materializedValuePhi, null, false));
|
|
788 |
}
|
|
789 |
}
|
|
790 |
}
|
|
791 |
}
|
|
792 |
|
|
793 |
for (PhiNode phi : getPhis()) {
|
|
794 |
aliases.set(phi, null);
|
|
795 |
if (hasVirtualInputs.isMarked(phi) && phi instanceof ValuePhiNode) {
|
46371
|
796 |
materialized |= processPhi((ValuePhiNode) phi, states);
|
43972
|
797 |
}
|
|
798 |
}
|
|
799 |
if (materialized) {
|
|
800 |
newState.resetObjectStates(virtualObjects.size());
|
|
801 |
mergeEffects.clear();
|
|
802 |
afterMergeEffects.clear();
|
|
803 |
}
|
|
804 |
} while (materialized);
|
|
805 |
}
|
|
806 |
|
|
807 |
private int[] intersectVirtualObjects(PartialEscapeBlockState<?>[] states) {
|
|
808 |
int length = states[0].getStateCount();
|
|
809 |
for (int i = 1; i < states.length; i++) {
|
|
810 |
length = Math.min(length, states[i].getStateCount());
|
|
811 |
}
|
46371
|
812 |
|
|
813 |
int count = 0;
|
|
814 |
for (int objectIndex = 0; objectIndex < length; objectIndex++) {
|
|
815 |
if (intersectObjectState(states, objectIndex)) {
|
|
816 |
count++;
|
43972
|
817 |
}
|
|
818 |
}
|
46371
|
819 |
|
43972
|
820 |
int index = 0;
|
46371
|
821 |
int[] resultInts = new int[count];
|
|
822 |
for (int objectIndex = 0; objectIndex < length; objectIndex++) {
|
|
823 |
if (intersectObjectState(states, objectIndex)) {
|
|
824 |
resultInts[index++] = objectIndex;
|
43972
|
825 |
}
|
|
826 |
}
|
|
827 |
assert index == count;
|
|
828 |
return resultInts;
|
|
829 |
}
|
|
830 |
|
46371
|
831 |
private boolean intersectObjectState(PartialEscapeBlockState<?>[] states, int objectIndex) {
|
|
832 |
for (int i = 0; i < states.length; i++) {
|
|
833 |
PartialEscapeBlockState<?> state = states[i];
|
|
834 |
if (state.getObjectStateOptional(objectIndex) == null) {
|
|
835 |
return false;
|
|
836 |
}
|
|
837 |
}
|
|
838 |
return true;
|
|
839 |
}
|
|
840 |
|
43972
|
841 |
/**
|
|
842 |
* Try to merge multiple virtual object states into a single object state. If the incoming
|
|
843 |
* object states are compatible, then this method will create PhiNodes for the object's
|
|
844 |
* entries where needed. If they are incompatible, then all incoming virtual objects will be
|
|
845 |
* materialized, and a PhiNode for the materialized values will be created. Object states
|
|
846 |
* can be incompatible if they contain {@code long} or {@code double} values occupying two
|
|
847 |
* {@code int} slots in such a way that that their values cannot be merged using PhiNodes.
|
|
848 |
*
|
|
849 |
* @param states the predecessor block states of the merge
|
|
850 |
* @return true if materialization happened during the merge, false otherwise
|
|
851 |
*/
|
|
852 |
private boolean mergeObjectStates(int resultObject, int[] sourceObjects, PartialEscapeBlockState<?>[] states) {
|
|
853 |
boolean compatible = true;
|
|
854 |
boolean ensureVirtual = true;
|
46509
|
855 |
IntUnaryOperator getObject = index -> sourceObjects == null ? resultObject : sourceObjects[index];
|
43972
|
856 |
|
|
857 |
VirtualObjectNode virtual = virtualObjects.get(resultObject);
|
|
858 |
int entryCount = virtual.entryCount();
|
|
859 |
|
|
860 |
// determine all entries that have a two-slot value
|
|
861 |
JavaKind[] twoSlotKinds = null;
|
|
862 |
outer: for (int i = 0; i < states.length; i++) {
|
46509
|
863 |
ObjectState objectState = states[i].getObjectState(getObject.applyAsInt(i));
|
43972
|
864 |
ValueNode[] entries = objectState.getEntries();
|
|
865 |
int valueIndex = 0;
|
|
866 |
ensureVirtual &= objectState.getEnsureVirtualized();
|
|
867 |
while (valueIndex < entryCount) {
|
|
868 |
JavaKind otherKind = entries[valueIndex].getStackKind();
|
|
869 |
JavaKind entryKind = virtual.entryKind(valueIndex);
|
|
870 |
if (entryKind == JavaKind.Int && otherKind.needsTwoSlots()) {
|
|
871 |
if (twoSlotKinds == null) {
|
|
872 |
twoSlotKinds = new JavaKind[entryCount];
|
|
873 |
}
|
|
874 |
if (twoSlotKinds[valueIndex] != null && twoSlotKinds[valueIndex] != otherKind) {
|
|
875 |
compatible = false;
|
|
876 |
break outer;
|
|
877 |
}
|
|
878 |
twoSlotKinds[valueIndex] = otherKind;
|
|
879 |
// skip the next entry
|
|
880 |
valueIndex++;
|
|
881 |
} else {
|
|
882 |
assert entryKind.getStackKind() == otherKind.getStackKind() || (entryKind == JavaKind.Int && otherKind == JavaKind.Illegal) ||
|
|
883 |
entryKind.getBitCount() >= otherKind.getBitCount() : entryKind + " vs " + otherKind;
|
|
884 |
}
|
|
885 |
valueIndex++;
|
|
886 |
}
|
|
887 |
}
|
|
888 |
if (compatible && twoSlotKinds != null) {
|
|
889 |
// if there are two-slot values then make sure the incoming states can be merged
|
|
890 |
outer: for (int valueIndex = 0; valueIndex < entryCount; valueIndex++) {
|
|
891 |
if (twoSlotKinds[valueIndex] != null) {
|
|
892 |
assert valueIndex < virtual.entryCount() - 1 && virtual.entryKind(valueIndex) == JavaKind.Int && virtual.entryKind(valueIndex + 1) == JavaKind.Int;
|
|
893 |
for (int i = 0; i < states.length; i++) {
|
46509
|
894 |
int object = getObject.applyAsInt(i);
|
43972
|
895 |
ObjectState objectState = states[i].getObjectState(object);
|
|
896 |
ValueNode value = objectState.getEntry(valueIndex);
|
|
897 |
JavaKind valueKind = value.getStackKind();
|
|
898 |
if (valueKind != twoSlotKinds[valueIndex]) {
|
|
899 |
ValueNode nextValue = objectState.getEntry(valueIndex + 1);
|
|
900 |
if (value.isConstant() && value.asConstant().equals(JavaConstant.INT_0) && nextValue.isConstant() && nextValue.asConstant().equals(JavaConstant.INT_0)) {
|
|
901 |
// rewrite to a zero constant of the larger kind
|
47798
|
902 |
debug.log("Rewriting entry %s to constant of larger size", valueIndex);
|
43972
|
903 |
states[i].setEntry(object, valueIndex, ConstantNode.defaultForKind(twoSlotKinds[valueIndex], graph()));
|
52578
|
904 |
states[i].setEntry(object, valueIndex + 1, ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccess(), graph()));
|
43972
|
905 |
} else {
|
|
906 |
compatible = false;
|
|
907 |
break outer;
|
|
908 |
}
|
|
909 |
}
|
|
910 |
}
|
|
911 |
}
|
|
912 |
}
|
|
913 |
}
|
|
914 |
|
|
915 |
if (compatible) {
|
|
916 |
// virtual objects are compatible: create phis for all entries that need them
|
46509
|
917 |
ValueNode[] values = states[0].getObjectState(getObject.applyAsInt(0)).getEntries().clone();
|
43972
|
918 |
PhiNode[] phis = getValuePhis(virtual, virtual.entryCount());
|
|
919 |
int valueIndex = 0;
|
|
920 |
while (valueIndex < values.length) {
|
|
921 |
for (int i = 1; i < states.length; i++) {
|
|
922 |
if (phis[valueIndex] == null) {
|
46509
|
923 |
ValueNode field = states[i].getObjectState(getObject.applyAsInt(i)).getEntry(valueIndex);
|
43972
|
924 |
if (values[valueIndex] != field) {
|
48190
|
925 |
phis[valueIndex] = createValuePhi(values[valueIndex].stamp(NodeView.DEFAULT).unrestricted());
|
43972
|
926 |
}
|
|
927 |
}
|
|
928 |
}
|
48190
|
929 |
if (phis[valueIndex] != null && !phis[valueIndex].stamp(NodeView.DEFAULT).isCompatible(values[valueIndex].stamp(NodeView.DEFAULT))) {
|
|
930 |
phis[valueIndex] = createValuePhi(values[valueIndex].stamp(NodeView.DEFAULT).unrestricted());
|
43972
|
931 |
}
|
|
932 |
if (twoSlotKinds != null && twoSlotKinds[valueIndex] != null) {
|
|
933 |
// skip an entry after a long/double value that occupies two int slots
|
|
934 |
valueIndex++;
|
|
935 |
phis[valueIndex] = null;
|
52578
|
936 |
values[valueIndex] = ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccess(), graph());
|
43972
|
937 |
}
|
|
938 |
valueIndex++;
|
|
939 |
}
|
|
940 |
|
|
941 |
boolean materialized = false;
|
|
942 |
for (int i = 0; i < values.length; i++) {
|
|
943 |
PhiNode phi = phis[i];
|
|
944 |
if (phi != null) {
|
|
945 |
mergeEffects.addFloatingNode(phi, "virtualMergePhi");
|
|
946 |
if (virtual.entryKind(i) == JavaKind.Object) {
|
|
947 |
materialized |= mergeObjectEntry(getObject, states, phi, i);
|
|
948 |
} else {
|
|
949 |
for (int i2 = 0; i2 < states.length; i2++) {
|
46509
|
950 |
ObjectState state = states[i2].getObjectState(getObject.applyAsInt(i2));
|
43972
|
951 |
if (!state.isVirtual()) {
|
|
952 |
break;
|
|
953 |
}
|
|
954 |
setPhiInput(phi, i2, state.getEntry(i));
|
|
955 |
}
|
|
956 |
}
|
|
957 |
values[i] = phi;
|
|
958 |
}
|
|
959 |
}
|
46509
|
960 |
newState.addObject(resultObject, new ObjectState(values, states[0].getObjectState(getObject.applyAsInt(0)).getLocks(), ensureVirtual));
|
43972
|
961 |
return materialized;
|
|
962 |
} else {
|
|
963 |
// not compatible: materialize in all predecessors
|
|
964 |
PhiNode materializedValuePhi = getPhi(resultObject, StampFactory.forKind(JavaKind.Object));
|
|
965 |
for (int i = 0; i < states.length; i++) {
|
|
966 |
Block predecessor = getPredecessor(i);
|
46509
|
967 |
if (!ensureVirtual && states[i].getObjectState(getObject.applyAsInt(i)).isVirtual()) {
|
43972
|
968 |
// we can materialize if not all inputs are "ensureVirtualized"
|
46509
|
969 |
states[i].getObjectState(getObject.applyAsInt(i)).setEnsureVirtualized(false);
|
43972
|
970 |
}
|
46509
|
971 |
ensureMaterialized(states[i], getObject.applyAsInt(i), predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_MERGE);
|
|
972 |
setPhiInput(materializedValuePhi, i, states[i].getObjectState(getObject.applyAsInt(i)).getMaterializedValue());
|
43972
|
973 |
}
|
|
974 |
newState.addObject(resultObject, new ObjectState(materializedValuePhi, null, ensureVirtual));
|
|
975 |
return true;
|
|
976 |
}
|
|
977 |
}
|
|
978 |
|
|
979 |
/**
|
|
980 |
* Fill the inputs of the PhiNode corresponding to one {@link JavaKind#Object} entry in the
|
|
981 |
* virtual object.
|
|
982 |
*
|
|
983 |
* @return true if materialization happened during the merge, false otherwise
|
|
984 |
*/
|
46509
|
985 |
private boolean mergeObjectEntry(IntUnaryOperator objectIdFunc, PartialEscapeBlockState<?>[] states, PhiNode phi, int entryIndex) {
|
43972
|
986 |
boolean materialized = false;
|
|
987 |
for (int i = 0; i < states.length; i++) {
|
46509
|
988 |
int object = objectIdFunc.applyAsInt(i);
|
43972
|
989 |
ObjectState objectState = states[i].getObjectState(object);
|
|
990 |
if (!objectState.isVirtual()) {
|
|
991 |
break;
|
|
992 |
}
|
|
993 |
ValueNode entry = objectState.getEntry(entryIndex);
|
|
994 |
if (entry instanceof VirtualObjectNode) {
|
|
995 |
VirtualObjectNode entryVirtual = (VirtualObjectNode) entry;
|
|
996 |
Block predecessor = getPredecessor(i);
|
|
997 |
materialized |= ensureMaterialized(states[i], entryVirtual.getObjectId(), predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_MERGE);
|
|
998 |
objectState = states[i].getObjectState(object);
|
|
999 |
if (objectState.isVirtual()) {
|
|
1000 |
states[i].setEntry(object, entryIndex, entry = states[i].getObjectState(entryVirtual.getObjectId()).getMaterializedValue());
|
|
1001 |
}
|
|
1002 |
}
|
|
1003 |
setPhiInput(phi, i, entry);
|
|
1004 |
}
|
|
1005 |
return materialized;
|
|
1006 |
}
|
|
1007 |
|
|
1008 |
/**
|
|
1009 |
* Examine a PhiNode and try to replace it with merging of virtual objects if all its inputs
|
|
1010 |
* refer to virtual object states. In order for the merging to happen, all incoming object
|
|
1011 |
* states need to be compatible and without object identity (meaning that their object
|
|
1012 |
* identity if not used later on).
|
|
1013 |
*
|
|
1014 |
* @param phi the PhiNode that should be processed
|
|
1015 |
* @param states the predecessor block states of the merge
|
|
1016 |
* @return true if materialization happened during the merge, false otherwise
|
|
1017 |
*/
|
46371
|
1018 |
private boolean processPhi(ValuePhiNode phi, PartialEscapeBlockState<?>[] states) {
|
43972
|
1019 |
|
|
1020 |
// determine how many inputs are virtual and if they're all the same virtual object
|
|
1021 |
int virtualInputs = 0;
|
|
1022 |
boolean uniqueVirtualObject = true;
|
|
1023 |
boolean ensureVirtual = true;
|
|
1024 |
VirtualObjectNode[] virtualObjs = new VirtualObjectNode[states.length];
|
|
1025 |
for (int i = 0; i < states.length; i++) {
|
|
1026 |
ValueNode alias = getAlias(getPhiValueAt(phi, i));
|
|
1027 |
if (alias instanceof VirtualObjectNode) {
|
|
1028 |
VirtualObjectNode virtual = (VirtualObjectNode) alias;
|
|
1029 |
virtualObjs[i] = virtual;
|
|
1030 |
ObjectState objectState = states[i].getObjectStateOptional(virtual);
|
|
1031 |
if (objectState == null) {
|
|
1032 |
assert getPhiValueAt(phi, i) instanceof PhiNode : "this should only happen for phi nodes";
|
|
1033 |
return false;
|
|
1034 |
}
|
|
1035 |
if (objectState.isVirtual()) {
|
|
1036 |
if (virtualObjs[0] != alias) {
|
|
1037 |
uniqueVirtualObject = false;
|
|
1038 |
}
|
|
1039 |
ensureVirtual &= objectState.getEnsureVirtualized();
|
|
1040 |
virtualInputs++;
|
|
1041 |
}
|
|
1042 |
}
|
|
1043 |
}
|
|
1044 |
if (virtualInputs == states.length) {
|
|
1045 |
if (uniqueVirtualObject) {
|
|
1046 |
// all inputs refer to the same object: just make the phi node an alias
|
46344
|
1047 |
addVirtualAlias(virtualObjs[0], phi);
|
43972
|
1048 |
mergeEffects.deleteNode(phi);
|
|
1049 |
return false;
|
|
1050 |
} else {
|
|
1051 |
// all inputs are virtual: check if they're compatible and without identity
|
|
1052 |
boolean compatible = true;
|
|
1053 |
VirtualObjectNode firstVirtual = virtualObjs[0];
|
|
1054 |
for (int i = 0; i < states.length; i++) {
|
|
1055 |
VirtualObjectNode virtual = virtualObjs[i];
|
46344
|
1056 |
|
46762
|
1057 |
if (!firstVirtual.type().equals(virtual.type()) || firstVirtual.entryCount() != virtual.entryCount()) {
|
43972
|
1058 |
compatible = false;
|
|
1059 |
break;
|
|
1060 |
}
|
|
1061 |
if (!states[0].getObjectState(firstVirtual).locksEqual(states[i].getObjectState(virtual))) {
|
|
1062 |
compatible = false;
|
|
1063 |
break;
|
|
1064 |
}
|
|
1065 |
}
|
46344
|
1066 |
if (compatible) {
|
46762
|
1067 |
for (int i = 0; i < states.length; i++) {
|
|
1068 |
VirtualObjectNode virtual = virtualObjs[i];
|
|
1069 |
/*
|
|
1070 |
* check whether we trivially see that this is the only reference to
|
|
1071 |
* this allocation
|
|
1072 |
*/
|
|
1073 |
if (virtual.hasIdentity() && !isSingleUsageAllocation(getPhiValueAt(phi, i), virtualObjs, states[i])) {
|
|
1074 |
compatible = false;
|
54328
|
1075 |
break;
|
46762
|
1076 |
}
|
|
1077 |
}
|
|
1078 |
}
|
|
1079 |
if (compatible) {
|
43972
|
1080 |
VirtualObjectNode virtual = getValueObjectVirtual(phi, virtualObjs[0]);
|
|
1081 |
mergeEffects.addFloatingNode(virtual, "valueObjectNode");
|
|
1082 |
mergeEffects.deleteNode(phi);
|
|
1083 |
if (virtual.getObjectId() == -1) {
|
|
1084 |
int id = virtualObjects.size();
|
|
1085 |
virtualObjects.add(virtual);
|
|
1086 |
virtual.setObjectId(id);
|
|
1087 |
}
|
|
1088 |
|
|
1089 |
int[] virtualObjectIds = new int[states.length];
|
|
1090 |
for (int i = 0; i < states.length; i++) {
|
|
1091 |
virtualObjectIds[i] = virtualObjs[i].getObjectId();
|
|
1092 |
}
|
|
1093 |
boolean materialized = mergeObjectStates(virtual.getObjectId(), virtualObjectIds, states);
|
46344
|
1094 |
addVirtualAlias(virtual, virtual);
|
|
1095 |
addVirtualAlias(virtual, phi);
|
43972
|
1096 |
return materialized;
|
|
1097 |
}
|
|
1098 |
}
|
|
1099 |
}
|
|
1100 |
|
|
1101 |
// otherwise: materialize all phi inputs
|
|
1102 |
boolean materialized = false;
|
|
1103 |
if (virtualInputs > 0) {
|
|
1104 |
for (int i = 0; i < states.length; i++) {
|
|
1105 |
VirtualObjectNode virtual = virtualObjs[i];
|
|
1106 |
if (virtual != null) {
|
|
1107 |
Block predecessor = getPredecessor(i);
|
|
1108 |
if (!ensureVirtual && states[i].getObjectState(virtual).isVirtual()) {
|
|
1109 |
// we can materialize if not all inputs are "ensureVirtualized"
|
|
1110 |
states[i].getObjectState(virtual).setEnsureVirtualized(false);
|
|
1111 |
}
|
|
1112 |
materialized |= ensureMaterialized(states[i], virtual.getObjectId(), predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_PHI);
|
|
1113 |
}
|
|
1114 |
}
|
|
1115 |
}
|
|
1116 |
for (int i = 0; i < states.length; i++) {
|
|
1117 |
VirtualObjectNode virtual = virtualObjs[i];
|
|
1118 |
if (virtual != null) {
|
|
1119 |
setPhiInput(phi, i, getAliasAndResolve(states[i], virtual));
|
|
1120 |
}
|
|
1121 |
}
|
|
1122 |
return materialized;
|
|
1123 |
}
|
46344
|
1124 |
|
46762
|
1125 |
private boolean isSingleUsageAllocation(ValueNode value, VirtualObjectNode[] virtualObjs, PartialEscapeBlockState<?> state) {
|
46344
|
1126 |
/*
|
|
1127 |
* If the phi input is an allocation, we know that it is a "fresh" value, i.e., that
|
|
1128 |
* this is a value that will only appear through this source, and cannot appear anywhere
|
|
1129 |
* else. If the phi is also the only usage of this input, we know that no other place
|
|
1130 |
* can check object identity against it, so it is safe to lose the object identity here.
|
|
1131 |
*/
|
46762
|
1132 |
if (!(value instanceof AllocatedObjectNode && value.hasExactlyOneUsage())) {
|
|
1133 |
return false;
|
|
1134 |
}
|
|
1135 |
|
|
1136 |
/*
|
|
1137 |
* Check that the state only references the one virtual object from the Phi.
|
|
1138 |
*/
|
|
1139 |
VirtualObjectNode singleVirtual = null;
|
|
1140 |
for (int v = 0; v < virtualObjs.length; v++) {
|
|
1141 |
if (state.contains(virtualObjs[v])) {
|
|
1142 |
if (singleVirtual == null) {
|
|
1143 |
singleVirtual = virtualObjs[v];
|
|
1144 |
} else if (singleVirtual != virtualObjs[v]) {
|
|
1145 |
/*
|
|
1146 |
* More than one virtual object is visible in the object state.
|
|
1147 |
*/
|
|
1148 |
return false;
|
|
1149 |
}
|
|
1150 |
}
|
|
1151 |
}
|
|
1152 |
return true;
|
46344
|
1153 |
}
|
43972
|
1154 |
}
|
|
1155 |
|
|
1156 |
public ObjectState getObjectState(PartialEscapeBlockState<?> state, ValueNode value) {
|
|
1157 |
if (value == null) {
|
|
1158 |
return null;
|
|
1159 |
}
|
|
1160 |
if (value.isAlive() && !aliases.isNew(value)) {
|
|
1161 |
ValueNode object = aliases.get(value);
|
|
1162 |
return object instanceof VirtualObjectNode ? state.getObjectStateOptional((VirtualObjectNode) object) : null;
|
|
1163 |
} else {
|
|
1164 |
if (value instanceof VirtualObjectNode) {
|
|
1165 |
return state.getObjectStateOptional((VirtualObjectNode) value);
|
|
1166 |
}
|
|
1167 |
return null;
|
|
1168 |
}
|
|
1169 |
}
|
|
1170 |
|
|
1171 |
public ValueNode getAlias(ValueNode value) {
|
|
1172 |
if (value != null && !(value instanceof VirtualObjectNode)) {
|
|
1173 |
if (value.isAlive() && !aliases.isNew(value)) {
|
|
1174 |
ValueNode result = aliases.get(value);
|
|
1175 |
if (result != null) {
|
|
1176 |
return result;
|
|
1177 |
}
|
|
1178 |
}
|
|
1179 |
}
|
|
1180 |
return value;
|
|
1181 |
}
|
|
1182 |
|
|
1183 |
public ValueNode getAliasAndResolve(PartialEscapeBlockState<?> state, ValueNode value) {
|
|
1184 |
ValueNode result = getAlias(value);
|
|
1185 |
if (result instanceof VirtualObjectNode) {
|
|
1186 |
int id = ((VirtualObjectNode) result).getObjectId();
|
|
1187 |
if (id != -1 && !state.getObjectState(id).isVirtual()) {
|
|
1188 |
result = state.getObjectState(id).getMaterializedValue();
|
|
1189 |
}
|
|
1190 |
}
|
|
1191 |
return result;
|
|
1192 |
}
|
|
1193 |
|
46344
|
1194 |
void addVirtualAlias(VirtualObjectNode virtual, ValueNode node) {
|
43972
|
1195 |
if (node.isAlive()) {
|
|
1196 |
aliases.set(node, virtual);
|
|
1197 |
for (Node usage : node.usages()) {
|
|
1198 |
markVirtualUsages(usage);
|
|
1199 |
}
|
|
1200 |
}
|
|
1201 |
}
|
|
1202 |
|
|
1203 |
private void markVirtualUsages(Node node) {
|
|
1204 |
if (!hasVirtualInputs.isNew(node) && !hasVirtualInputs.isMarked(node)) {
|
|
1205 |
hasVirtualInputs.mark(node);
|
|
1206 |
if (node instanceof VirtualState) {
|
|
1207 |
for (Node usage : node.usages()) {
|
|
1208 |
markVirtualUsages(usage);
|
|
1209 |
}
|
|
1210 |
}
|
|
1211 |
}
|
|
1212 |
}
|
|
1213 |
}
|