1 /*
2 * Copyright (c) 2011, 2018, Oracle and/or its affiliates. All rights reserved.
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 */
23
24
25 package org.graalvm.compiler.virtual.phases.ea;
26
27 import java.util.ArrayList;
28 import java.util.BitSet;
29 import java.util.Iterator;
30 import java.util.List;
31 import java.util.function.IntUnaryOperator;
32
33 import jdk.internal.vm.compiler.collections.EconomicMap;
34 import jdk.internal.vm.compiler.collections.EconomicSet;
35 import jdk.internal.vm.compiler.collections.Equivalence;
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;
41 import org.graalvm.compiler.debug.CounterKey;
42 import org.graalvm.compiler.debug.DebugContext;
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;
57 import org.graalvm.compiler.nodes.NodeView;
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;
62 import org.graalvm.compiler.nodes.UnwindNode;
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;
74 import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode;
75 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
76 import org.graalvm.compiler.virtual.nodes.VirtualObjectState;
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
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");
93
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 */
98 private final NodeBitMap hasVirtualInputs;
99
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 */
108 public final ArrayList<VirtualObjectNode> virtualObjects = new ArrayList<>();
109
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
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).
120 */
121 for (Block block : cfg.getBlocks()) {
122 GraphEffectList effects = blockEffects.get(block);
123 if (effects != null) {
124 if (effects.getVirtualizationDelta() != 0) {
125 return true;
126 }
127 }
128 }
129 return false;
130 }
131
132 private final class CollectVirtualObjectsClosure extends NodeClosure<ValueNode> {
133 private final EconomicSet<VirtualObjectNode> virtual;
134 private final GraphEffectList effects;
135 private final BlockT state;
136
137 private CollectVirtualObjectsClosure(EconomicSet<VirtualObjectNode> virtual, GraphEffectList effects, BlockT state) {
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() {
174 return new PartialEscapeBlockState.Final(tool.getOptions(), tool.getDebug());
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();
192 this.tool = new VirtualizerToolImpl(metaAccess, constantReflection, constantFieldProvider, this, graph.getAssumptions(), graph.getOptions(), debug, loweringProvider);
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();
215 VirtualUtil.trace(node.getOptions(), debug, "%s", node);
216
217 if (requiresProcessing(node)) {
218 if (processVirtualizable((ValueNode) node, nextFixedNode, state, effects) == false) {
219 return false;
220 }
221 if (tool.isDeleted()) {
222 VirtualUtil.trace(node.getOptions(), debug, "deleted virtualizable allocation %s", node);
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()) {
232 VirtualUtil.trace(node.getOptions(), debug, "deleted virtualizable node %s", node);
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
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 */
264 @SuppressWarnings("unchecked")
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) {
290 addVirtualAlias((VirtualObjectNode) alias, node);
291 effects.deleteNode(node);
292 } else {
293 effects.replaceAtUsages(node, alias, insertBefore);
294 addScalarAlias(node, alias);
295 }
296 } else {
297 if (!prepareCanonicalNode(canonicalizedValue, state, effects)) {
298 VirtualUtil.trace(node.getOptions(), debug, "replacement via canonicalization too complex: %s -> %s", node, canonicalizedValue);
299 return false;
300 }
301 if (canonicalizedValue instanceof ControlSinkNode) {
302 effects.replaceWithSink((FixedWithNextNode) node, (ControlSinkNode) canonicalizedValue);
303 state.markAsDead();
304 } else {
305 effects.replaceAtUsages(node, canonicalizedValue, insertBefore);
306 addScalarAlias(node, canonicalizedValue);
307 }
308 }
309 VirtualUtil.trace(node.getOptions(), debug, "replaced via canonicalization: %s -> %s", node, canonicalizedValue);
310 return true;
311 }
312 return false;
313 }
314
315 /**
316 * Nodes created during canonicalizations need to be scanned for values that were replaced.
317 */
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()) {
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 }
332 } else {
333 pos.initialize(node, getScalarAlias((ValueNode) input));
334 }
335 }
336 } else {
337 if (!prepareCanonicalNode((ValueNode) input, state, effects)) {
338 return false;
339 }
340 }
341 }
342 }
343 return true;
344 }
345
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 */
351 private void processNodeInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
352 VirtualUtil.trace(node.getOptions(), debug, "processing nodewithstate: %s", node);
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());
360 VirtualUtil.trace(node.getOptions(), debug, "replacing input %s at %s", input, node);
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);
372 EconomicSet<VirtualObjectNode> virtual = EconomicSet.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE);
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) {
381 if (frameState.hasMoreThanOneUsage()) {
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
390 private void addVirtualMappings(FrameState frameState, EconomicSet<VirtualObjectNode> virtual, BlockT state, GraphEffectList effects) {
391 for (VirtualObjectNode obj : virtual) {
392 effects.addVirtualMapping(frameState, state.getObjectState(obj).createEscapeObjectState(debug, obj));
393 }
394 }
395
396 private void collectReferencedVirtualObjects(BlockT state, EconomicSet<VirtualObjectNode> virtual) {
397 Iterator<VirtualObjectNode> iterator = virtual.iterator();
398 while (iterator.hasNext()) {
399 VirtualObjectNode object = iterator.next();
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
417 private void collectLockedVirtualObjects(BlockT state, EconomicSet<VirtualObjectNode> virtual) {
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 */
429 protected boolean ensureMaterialized(PartialEscapeBlockState<?> state, int object, FixedNode materializeBefore, GraphEffectList effects, CounterKey counter) {
430 if (state.getObjectState(object).isVirtual()) {
431 counter.increment(debug);
432 VirtualObjectNode virtual = virtualObjects.get(object);
433 state.materializeBefore(materializeBefore, virtual, effects);
434 assert !updateStatesForMaterialized(state, virtual, state.getObjectState(object).getMaterializedValue()) : "method must already have been called before";
435 return true;
436 } else {
437 return false;
438 }
439 }
440
441 public static boolean updateStatesForMaterialized(PartialEscapeBlockState<?> state, VirtualObjectNode virtual, ValueNode materializedValue) {
442 // update all existing states with the newly materialized object
443 boolean change = false;
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);
451 change = true;
452 }
453 }
454 }
455 }
456 return change;
457 }
458
459 @Override
460 protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT originalInitialState) {
461 BlockT initialState = super.stripKilledLoopLocations(loop, originalInitialState);
462 if (loop.getDepth() > GraalOptions.EscapeAnalysisLoopCutoff.getValue(cfg.graph.getOptions())) {
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;
475 BitSet ensureVirtualized = new BitSet(length);
476 for (int i = 0; i < length; i++) {
477 ObjectState state = initialState.getObjectStateOptional(i);
478 if (state != null && state.isVirtual() && state.getEnsureVirtualized()) {
479 ensureVirtualized.set(i);
480 }
481 }
482 do {
483 // propagate "ensureVirtualized" flag
484 change = false;
485 for (int i = 0; i < length; i++) {
486 if (!ensureVirtualized.get(i)) {
487 ObjectState state = initialState.getObjectStateOptional(i);
488 if (state != null && state.isVirtual()) {
489 for (ValueNode entry : state.getEntries()) {
490 if (entry instanceof VirtualObjectNode) {
491 if (ensureVirtualized.get(((VirtualObjectNode) entry).getObjectId())) {
492 change = true;
493 ensureVirtualized.set(i);
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);
505 if (state != null && state.isVirtual() && !ensureVirtualized.get(i)) {
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;
520 addVirtualAlias(virtual, phi);
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()) {
531 EconomicMap<Integer, ProxyNode> proxies = EconomicMap.create(Equivalence.DEFAULT);
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
554 private static void processMaterializedAtLoopExit(LoopExitNode exitNode, GraphEffectList effects, EconomicMap<Integer, ProxyNode> proxies, int object, ObjectState exitObjState,
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()) {
568 exitNode.getDebug().log("materialized value changes within loop: %s vs. %s at %s", initialObjState.getMaterializedValue(), exitObjState.getMaterializedValue(), exitNode);
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
594 private EconomicMap<Object, ValuePhiNode> materializedPhis;
595 private EconomicMap<ValueNode, ValuePhiNode[]> valuePhis;
596 private EconomicMap<ValuePhiNode, VirtualObjectNode> valueObjectVirtuals;
597 private final boolean needsCaching;
598
599 public MergeProcessor(Block mergeBlock) {
600 super(mergeBlock);
601 // merge will only be called multiple times for loop headers
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) {
615 materializedPhis = EconomicMap.create(Equivalence.DEFAULT);
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) {
635 valuePhis = EconomicMap.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE);
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 {
650 VirtualObjectNode duplicate = virtual.duplicate();
651 duplicate.setNodeSourcePosition(virtual.getNodeSourcePosition());
652 return duplicate;
653 }
654 }
655
656 private VirtualObjectNode getValueObjectVirtualCached(ValuePhiNode phi, VirtualObjectNode virtual) {
657 if (valueObjectVirtuals == null) {
658 valueObjectVirtuals = EconomicMap.create(Equivalence.IDENTITY);
659 }
660 VirtualObjectNode result = valueObjectVirtuals.get(phi);
661 if (result == null) {
662 result = virtual.duplicate();
663 result.setNodeSourcePosition(virtual.getNodeSourcePosition());
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
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
717 boolean materialized;
718 do {
719 materialized = false;
720
721 if (!forceMaterialization && PartialEscapeBlockState.identicalObjectStates(states)) {
722 newState.adoptAddObjectStates(states[0]);
723 } else {
724
725 for (int object : virtualObjTemp) {
726 if (!forceMaterialization && PartialEscapeBlockState.identicalObjectStates(states, object)) {
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();
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 }
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) {
796 materialized |= processPhi((ValuePhiNode) phi, states);
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 }
812
813 int count = 0;
814 for (int objectIndex = 0; objectIndex < length; objectIndex++) {
815 if (intersectObjectState(states, objectIndex)) {
816 count++;
817 }
818 }
819
820 int index = 0;
821 int[] resultInts = new int[count];
822 for (int objectIndex = 0; objectIndex < length; objectIndex++) {
823 if (intersectObjectState(states, objectIndex)) {
824 resultInts[index++] = objectIndex;
825 }
826 }
827 assert index == count;
828 return resultInts;
829 }
830
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
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;
855 IntUnaryOperator getObject = index -> sourceObjects == null ? resultObject : sourceObjects[index];
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++) {
863 ObjectState objectState = states[i].getObjectState(getObject.applyAsInt(i));
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++) {
894 int object = getObject.applyAsInt(i);
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
902 debug.log("Rewriting entry %s to constant of larger size", valueIndex);
903 states[i].setEntry(object, valueIndex, ConstantNode.defaultForKind(twoSlotKinds[valueIndex], graph()));
904 states[i].setEntry(object, valueIndex + 1, ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccess(), graph()));
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
917 ValueNode[] values = states[0].getObjectState(getObject.applyAsInt(0)).getEntries().clone();
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) {
923 ValueNode field = states[i].getObjectState(getObject.applyAsInt(i)).getEntry(valueIndex);
924 if (values[valueIndex] != field) {
925 phis[valueIndex] = createValuePhi(values[valueIndex].stamp(NodeView.DEFAULT).unrestricted());
926 }
927 }
928 }
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());
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;
936 values[valueIndex] = ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccess(), graph());
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++) {
950 ObjectState state = states[i2].getObjectState(getObject.applyAsInt(i2));
951 if (!state.isVirtual()) {
952 break;
953 }
954 setPhiInput(phi, i2, state.getEntry(i));
955 }
956 }
957 values[i] = phi;
958 }
959 }
960 newState.addObject(resultObject, new ObjectState(values, states[0].getObjectState(getObject.applyAsInt(0)).getLocks(), ensureVirtual));
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);
967 if (!ensureVirtual && states[i].getObjectState(getObject.applyAsInt(i)).isVirtual()) {
968 // we can materialize if not all inputs are "ensureVirtualized"
969 states[i].getObjectState(getObject.applyAsInt(i)).setEnsureVirtualized(false);
970 }
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());
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 */
985 private boolean mergeObjectEntry(IntUnaryOperator objectIdFunc, PartialEscapeBlockState<?>[] states, PhiNode phi, int entryIndex) {
986 boolean materialized = false;
987 for (int i = 0; i < states.length; i++) {
988 int object = objectIdFunc.applyAsInt(i);
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 */
1018 private boolean processPhi(ValuePhiNode phi, PartialEscapeBlockState<?>[] states) {
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
1047 addVirtualAlias(virtualObjs[0], phi);
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];
1056
1057 if (!firstVirtual.type().equals(virtual.type()) || firstVirtual.entryCount() != virtual.entryCount()) {
1058 compatible = false;
1059 break;
1060 }
1061 if (!states[0].getObjectState(firstVirtual).locksEqual(states[i].getObjectState(virtual))) {
1062 compatible = false;
1063 break;
1064 }
1065 }
1066 if (compatible) {
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;
1075 break;
1076 }
1077 }
1078 }
1079 if (compatible) {
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);
1094 addVirtualAlias(virtual, virtual);
1095 addVirtualAlias(virtual, phi);
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 }
1124
1125 private boolean isSingleUsageAllocation(ValueNode value, VirtualObjectNode[] virtualObjs, PartialEscapeBlockState<?> state) {
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 */
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;
1153 }
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
1194 void addVirtualAlias(VirtualObjectNode virtual, ValueNode node) {
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 }