1 /*
   2  * Copyright (c) 2011, 2017, 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 package org.graalvm.compiler.virtual.phases.ea;
  24 
  25 import java.util.ArrayList;
  26 import java.util.BitSet;
  27 import java.util.Iterator;
  28 import java.util.List;
  29 import java.util.function.IntUnaryOperator;
  30 
  31 import org.graalvm.compiler.core.common.GraalOptions;
  32 import org.graalvm.compiler.core.common.cfg.Loop;
  33 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
  34 import org.graalvm.compiler.core.common.type.Stamp;
  35 import org.graalvm.compiler.core.common.type.StampFactory;
  36 import org.graalvm.compiler.debug.Debug;
  37 import org.graalvm.compiler.debug.DebugCounter;
  38 import org.graalvm.compiler.graph.Node;
  39 import org.graalvm.compiler.graph.NodeBitMap;
  40 import org.graalvm.compiler.graph.Position;
  41 import org.graalvm.compiler.graph.spi.Canonicalizable;
  42 import org.graalvm.compiler.nodes.AbstractEndNode;
  43 import org.graalvm.compiler.nodes.CallTargetNode;
  44 import org.graalvm.compiler.nodes.ConstantNode;
  45 import org.graalvm.compiler.nodes.ControlSinkNode;
  46 import org.graalvm.compiler.nodes.FixedNode;
  47 import org.graalvm.compiler.nodes.FixedWithNextNode;
  48 import org.graalvm.compiler.nodes.FrameState;
  49 import org.graalvm.compiler.nodes.Invoke;
  50 import org.graalvm.compiler.nodes.LoopBeginNode;
  51 import org.graalvm.compiler.nodes.LoopExitNode;
  52 import org.graalvm.compiler.nodes.PhiNode;
  53 import org.graalvm.compiler.nodes.ProxyNode;
  54 import org.graalvm.compiler.nodes.StructuredGraph;
  55 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
  56 import org.graalvm.compiler.nodes.ValueNode;
  57 import org.graalvm.compiler.nodes.ValuePhiNode;
  58 import org.graalvm.compiler.nodes.ValueProxyNode;
  59 import org.graalvm.compiler.nodes.VirtualState;
  60 import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
  61 import org.graalvm.compiler.nodes.cfg.Block;
  62 import org.graalvm.compiler.nodes.spi.LoweringProvider;
  63 import org.graalvm.compiler.nodes.spi.NodeWithState;
  64 import org.graalvm.compiler.nodes.spi.Virtualizable;
  65 import org.graalvm.compiler.nodes.spi.VirtualizableAllocation;
  66 import org.graalvm.compiler.nodes.spi.VirtualizerTool;
  67 import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode;
  68 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
  69 import org.graalvm.compiler.virtual.nodes.VirtualObjectState;
  70 import org.graalvm.util.EconomicMap;
  71 import org.graalvm.util.EconomicSet;
  72 import org.graalvm.util.Equivalence;
  73 
  74 import jdk.vm.ci.meta.ConstantReflectionProvider;
  75 import jdk.vm.ci.meta.JavaConstant;
  76 import jdk.vm.ci.meta.JavaKind;
  77 import jdk.vm.ci.meta.MetaAccessProvider;
  78 
  79 public abstract class PartialEscapeClosure<BlockT extends PartialEscapeBlockState<BlockT>> extends EffectsClosure<BlockT> {
  80 
  81     public static final DebugCounter COUNTER_MATERIALIZATIONS = Debug.counter("Materializations");
  82     public static final DebugCounter COUNTER_MATERIALIZATIONS_PHI = Debug.counter("MaterializationsPhi");
  83     public static final DebugCounter COUNTER_MATERIALIZATIONS_MERGE = Debug.counter("MaterializationsMerge");
  84     public static final DebugCounter COUNTER_MATERIALIZATIONS_UNHANDLED = Debug.counter("MaterializationsUnhandled");
  85     public static final DebugCounter COUNTER_MATERIALIZATIONS_LOOP_REITERATION = Debug.counter("MaterializationsLoopReiteration");
  86     public static final DebugCounter COUNTER_MATERIALIZATIONS_LOOP_END = Debug.counter("MaterializationsLoopEnd");
  87     public static final DebugCounter COUNTER_ALLOCATION_REMOVED = Debug.counter("AllocationsRemoved");
  88     public static final DebugCounter COUNTER_MEMORYCHECKPOINT = Debug.counter("MemoryCheckpoint");
  89 
  90     /**
  91      * Nodes with inputs that were modified during analysis are marked in this bitset - this way
  92      * nodes that are not influenced at all by analysis can be rejected quickly.
  93      */
  94     private final NodeBitMap hasVirtualInputs;
  95 
  96     /**
  97      * This is handed out to implementers of {@link Virtualizable}.
  98      */
  99     protected final VirtualizerToolImpl tool;
 100 
 101     /**
 102      * The indexes into this array correspond to {@link VirtualObjectNode#getObjectId()}.
 103      */
 104     public final ArrayList<VirtualObjectNode> virtualObjects = new ArrayList<>();
 105 
 106     @Override
 107     public boolean needsApplyEffects() {
 108         if (hasChanged()) {
 109             return true;
 110         }
 111         /*
 112          * If there is a mismatch between the number of materializations and the number of
 113          * virtualizations, we need to apply effects, even if there were no other significant
 114          * changes to the graph.
 115          */
 116         int delta = 0;
 117         for (Block block : cfg.getBlocks()) {
 118             GraphEffectList effects = blockEffects.get(block);
 119             if (effects != null) {
 120                 delta += effects.getVirtualizationDelta();
 121             }
 122         }
 123         for (Loop<Block> loop : cfg.getLoops()) {
 124             GraphEffectList effects = loopMergeEffects.get(loop);
 125             if (effects != null) {
 126                 delta += effects.getVirtualizationDelta();
 127             }
 128         }
 129         return delta != 0;
 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());
 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(), 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(), "%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(), "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(), "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     private boolean processNodeWithScalarReplacedInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
 265         ValueNode canonicalizedValue = node;
 266         if (node instanceof Canonicalizable.Unary<?>) {
 267             @SuppressWarnings("unchecked")
 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             @SuppressWarnings("unchecked")
 276             Canonicalizable.Binary<ValueNode> canonicalizable = (Canonicalizable.Binary<ValueNode>) node;
 277             ObjectState xObj = getObjectState(state, canonicalizable.getX());
 278             ValueNode xAlias = xObj != null ? xObj.getMaterializedValue() : getScalarAlias(canonicalizable.getX());
 279             ObjectState yObj = getObjectState(state, canonicalizable.getY());
 280             ValueNode yAlias = yObj != null ? yObj.getMaterializedValue() : getScalarAlias(canonicalizable.getY());
 281             if (xAlias != canonicalizable.getX() || yAlias != canonicalizable.getY()) {
 282                 canonicalizedValue = (ValueNode) canonicalizable.canonical(tool, xAlias, yAlias);
 283             }
 284         } else {
 285             return false;
 286         }
 287         if (canonicalizedValue != node && canonicalizedValue != null) {
 288             if (canonicalizedValue.isAlive()) {
 289                 ValueNode alias = getAliasAndResolve(state, canonicalizedValue);
 290                 if (alias instanceof VirtualObjectNode) {
 291                     addVirtualAlias((VirtualObjectNode) alias, node);
 292                     effects.deleteNode(node);
 293                 } else {
 294                     effects.replaceAtUsages(node, alias, insertBefore);
 295                     addScalarAlias(node, alias);
 296                 }
 297             } else {
 298                 if (!prepareCanonicalNode(canonicalizedValue, state, effects)) {
 299                     VirtualUtil.trace(node.getOptions(), "replacement via canonicalization too complex: %s -> %s", node, canonicalizedValue);
 300                     return false;
 301                 }
 302                 if (canonicalizedValue instanceof ControlSinkNode) {
 303                     effects.replaceWithSink((FixedWithNextNode) node, (ControlSinkNode) canonicalizedValue);
 304                     state.markAsDead();
 305                 } else {
 306                     effects.replaceAtUsages(node, canonicalizedValue, insertBefore);
 307                     addScalarAlias(node, canonicalizedValue);
 308                 }
 309             }
 310             VirtualUtil.trace(node.getOptions(), "replaced via canonicalization: %s -> %s", node, canonicalizedValue);
 311             return true;
 312         }
 313         return false;
 314     }
 315 
 316     /**
 317      * Nodes created during canonicalizations need to be scanned for values that were replaced.
 318      */
 319     private boolean prepareCanonicalNode(ValueNode node, BlockT state, GraphEffectList effects) {
 320         assert !node.isAlive();
 321         for (Position pos : node.inputPositions()) {
 322             Node input = pos.get(node);
 323             if (input instanceof ValueNode) {
 324                 if (input.isAlive()) {
 325                     if (!(input instanceof VirtualObjectNode)) {
 326                         ObjectState obj = getObjectState(state, (ValueNode) input);
 327                         if (obj != null) {
 328                             if (obj.isVirtual()) {
 329                                 return false;
 330                             } else {
 331                                 pos.initialize(node, obj.getMaterializedValue());
 332                             }
 333                         } else {
 334                             pos.initialize(node, getScalarAlias((ValueNode) input));
 335                         }
 336                     }
 337                 } else {
 338                     if (!prepareCanonicalNode((ValueNode) input, state, effects)) {
 339                         return false;
 340                     }
 341                 }
 342             }
 343         }
 344         return true;
 345     }
 346 
 347     /**
 348      * This replaces all inputs that point to virtual or materialized values with the actual value,
 349      * materializing if necessary. Also takes care of frame states, adding the necessary
 350      * {@link VirtualObjectState}.
 351      */
 352     private void processNodeInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
 353         VirtualUtil.trace(node.getOptions(), "processing nodewithstate: %s", node);
 354         for (Node input : node.inputs()) {
 355             if (input instanceof ValueNode) {
 356                 ValueNode alias = getAlias((ValueNode) input);
 357                 if (alias instanceof VirtualObjectNode) {
 358                     int id = ((VirtualObjectNode) alias).getObjectId();
 359                     ensureMaterialized(state, id, insertBefore, effects, COUNTER_MATERIALIZATIONS_UNHANDLED);
 360                     effects.replaceFirstInput(node, input, state.getObjectState(id).getMaterializedValue());
 361                     VirtualUtil.trace(node.getOptions(), "replacing input %s at %s", input, node);
 362                 }
 363             }
 364         }
 365         if (node instanceof NodeWithState) {
 366             processNodeWithState((NodeWithState) node, state, effects);
 367         }
 368     }
 369 
 370     private void processNodeWithState(NodeWithState nodeWithState, BlockT state, GraphEffectList effects) {
 371         for (FrameState fs : nodeWithState.states()) {
 372             FrameState frameState = getUniqueFramestate(nodeWithState, fs);
 373             EconomicSet<VirtualObjectNode> virtual = EconomicSet.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE);
 374             frameState.applyToNonVirtual(new CollectVirtualObjectsClosure(virtual, effects, state));
 375             collectLockedVirtualObjects(state, virtual);
 376             collectReferencedVirtualObjects(state, virtual);
 377             addVirtualMappings(frameState, virtual, state, effects);
 378         }
 379     }
 380 
 381     private static FrameState getUniqueFramestate(NodeWithState nodeWithState, FrameState frameState) {
 382         if (frameState.hasMoreThanOneUsage()) {
 383             // Can happen for example from inlined snippets with multiple state split nodes.
 384             FrameState copy = (FrameState) frameState.copyWithInputs();
 385             nodeWithState.asNode().replaceFirstInput(frameState, copy);
 386             return copy;
 387         }
 388         return frameState;
 389     }
 390 
 391     private void addVirtualMappings(FrameState frameState, EconomicSet<VirtualObjectNode> virtual, BlockT state, GraphEffectList effects) {
 392         for (VirtualObjectNode obj : virtual) {
 393             effects.addVirtualMapping(frameState, state.getObjectState(obj).createEscapeObjectState(obj));
 394         }
 395     }
 396 
 397     private void collectReferencedVirtualObjects(BlockT state, EconomicSet<VirtualObjectNode> virtual) {
 398         Iterator<VirtualObjectNode> iterator = virtual.iterator();
 399         while (iterator.hasNext()) {
 400             VirtualObjectNode object = iterator.next();
 401             int id = object.getObjectId();
 402             if (id != -1) {
 403                 ObjectState objState = state.getObjectStateOptional(id);
 404                 if (objState != null && objState.isVirtual()) {
 405                     for (ValueNode entry : objState.getEntries()) {
 406                         if (entry instanceof VirtualObjectNode) {
 407                             VirtualObjectNode entryVirtual = (VirtualObjectNode) entry;
 408                             if (!virtual.contains(entryVirtual)) {
 409                                 virtual.add(entryVirtual);
 410                             }
 411                         }
 412                     }
 413                 }
 414             }
 415         }
 416     }
 417 
 418     private void collectLockedVirtualObjects(BlockT state, EconomicSet<VirtualObjectNode> virtual) {
 419         for (int i = 0; i < state.getStateCount(); i++) {
 420             ObjectState objState = state.getObjectStateOptional(i);
 421             if (objState != null && objState.isVirtual() && objState.hasLocks()) {
 422                 virtual.add(virtualObjects.get(i));
 423             }
 424         }
 425     }
 426 
 427     /**
 428      * @return true if materialization happened, false if not.
 429      */
 430     protected boolean ensureMaterialized(PartialEscapeBlockState<?> state, int object, FixedNode materializeBefore, GraphEffectList effects, DebugCounter counter) {
 431         if (state.getObjectState(object).isVirtual()) {
 432             counter.increment();
 433             VirtualObjectNode virtual = virtualObjects.get(object);
 434             state.materializeBefore(materializeBefore, virtual, effects);
 435             assert !updateStatesForMaterialized(state, virtual, state.getObjectState(object).getMaterializedValue()) : "method must already have been called before";
 436             return true;
 437         } else {
 438             return false;
 439         }
 440     }
 441 
 442     public static boolean updateStatesForMaterialized(PartialEscapeBlockState<?> state, VirtualObjectNode virtual, ValueNode materializedValue) {
 443         // update all existing states with the newly materialized object
 444         boolean change = false;
 445         for (int i = 0; i < state.getStateCount(); i++) {
 446             ObjectState objState = state.getObjectStateOptional(i);
 447             if (objState != null && objState.isVirtual()) {
 448                 ValueNode[] entries = objState.getEntries();
 449                 for (int i2 = 0; i2 < entries.length; i2++) {
 450                     if (entries[i2] == virtual) {
 451                         state.setEntry(i, i2, materializedValue);
 452                         change = true;
 453                     }
 454                 }
 455             }
 456         }
 457         return change;
 458     }
 459 
 460     @Override
 461     protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT originalInitialState) {
 462         BlockT initialState = super.stripKilledLoopLocations(loop, originalInitialState);
 463         if (loop.getDepth() > GraalOptions.EscapeAnalysisLoopCutoff.getValue(cfg.graph.getOptions())) {
 464             /*
 465              * After we've reached the maximum loop nesting, we'll simply materialize everything we
 466              * can to make sure that the loops only need to be iterated one time. Care is taken here
 467              * to not materialize virtual objects that have the "ensureVirtualized" flag set.
 468              */
 469             LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode();
 470             AbstractEndNode end = loopBegin.forwardEnd();
 471             Block loopPredecessor = loop.getHeader().getFirstPredecessor();
 472             assert loopPredecessor.getEndNode() == end;
 473             int length = initialState.getStateCount();
 474 
 475             boolean change;
 476             BitSet ensureVirtualized = new BitSet(length);
 477             for (int i = 0; i < length; i++) {
 478                 ObjectState state = initialState.getObjectStateOptional(i);
 479                 if (state != null && state.isVirtual() && state.getEnsureVirtualized()) {
 480                     ensureVirtualized.set(i);
 481                 }
 482             }
 483             do {
 484                 // propagate "ensureVirtualized" flag
 485                 change = false;
 486                 for (int i = 0; i < length; i++) {
 487                     if (!ensureVirtualized.get(i)) {
 488                         ObjectState state = initialState.getObjectStateOptional(i);
 489                         if (state != null && state.isVirtual()) {
 490                             for (ValueNode entry : state.getEntries()) {
 491                                 if (entry instanceof VirtualObjectNode) {
 492                                     if (ensureVirtualized.get(((VirtualObjectNode) entry).getObjectId())) {
 493                                         change = true;
 494                                         ensureVirtualized.set(i);
 495                                         break;
 496                                     }
 497                                 }
 498                             }
 499                         }
 500                     }
 501                 }
 502             } while (change);
 503 
 504             for (int i = 0; i < length; i++) {
 505                 ObjectState state = initialState.getObjectStateOptional(i);
 506                 if (state != null && state.isVirtual() && !ensureVirtualized.get(i)) {
 507                     initialState.materializeBefore(end, virtualObjects.get(i), blockEffects.get(loopPredecessor));
 508                 }
 509             }
 510         }
 511         return initialState;
 512     }
 513 
 514     @Override
 515     protected void processInitialLoopState(Loop<Block> loop, BlockT initialState) {
 516         for (PhiNode phi : ((LoopBeginNode) loop.getHeader().getBeginNode()).phis()) {
 517             if (phi.valueAt(0) != null) {
 518                 ValueNode alias = getAliasAndResolve(initialState, phi.valueAt(0));
 519                 if (alias instanceof VirtualObjectNode) {
 520                     VirtualObjectNode virtual = (VirtualObjectNode) alias;
 521                     addVirtualAlias(virtual, phi);
 522                 } else {
 523                     aliases.set(phi, null);
 524                 }
 525             }
 526         }
 527     }
 528 
 529     @Override
 530     protected void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects) {
 531         if (exitNode.graph().hasValueProxies()) {
 532             EconomicMap<Integer, ProxyNode> proxies = EconomicMap.create(Equivalence.DEFAULT);
 533             for (ProxyNode proxy : exitNode.proxies()) {
 534                 ValueNode alias = getAlias(proxy.value());
 535                 if (alias instanceof VirtualObjectNode) {
 536                     VirtualObjectNode virtual = (VirtualObjectNode) alias;
 537                     proxies.put(virtual.getObjectId(), proxy);
 538                 }
 539             }
 540             for (int i = 0; i < exitState.getStateCount(); i++) {
 541                 ObjectState exitObjState = exitState.getObjectStateOptional(i);
 542                 if (exitObjState != null) {
 543                     ObjectState initialObjState = initialState.getObjectStateOptional(i);
 544 
 545                     if (exitObjState.isVirtual()) {
 546                         processVirtualAtLoopExit(exitNode, effects, i, exitObjState, initialObjState, exitState);
 547                     } else {
 548                         processMaterializedAtLoopExit(exitNode, effects, proxies, i, exitObjState, initialObjState, exitState);
 549                     }
 550                 }
 551             }
 552         }
 553     }
 554 
 555     private static void processMaterializedAtLoopExit(LoopExitNode exitNode, GraphEffectList effects, EconomicMap<Integer, ProxyNode> proxies, int object, ObjectState exitObjState,
 556                     ObjectState initialObjState, PartialEscapeBlockState<?> exitState) {
 557         if (initialObjState == null || initialObjState.isVirtual()) {
 558             ProxyNode proxy = proxies.get(object);
 559             if (proxy == null) {
 560                 proxy = new ValueProxyNode(exitObjState.getMaterializedValue(), exitNode);
 561                 effects.addFloatingNode(proxy, "proxy");
 562             } else {
 563                 effects.replaceFirstInput(proxy, proxy.value(), exitObjState.getMaterializedValue());
 564                 // nothing to do - will be handled in processNode
 565             }
 566             exitState.updateMaterializedValue(object, proxy);
 567         } else {
 568             if (initialObjState.getMaterializedValue() != exitObjState.getMaterializedValue()) {
 569                 Debug.log("materialized value changes within loop: %s vs. %s at %s", initialObjState.getMaterializedValue(), exitObjState.getMaterializedValue(), exitNode);
 570             }
 571         }
 572     }
 573 
 574     private static void processVirtualAtLoopExit(LoopExitNode exitNode, GraphEffectList effects, int object, ObjectState exitObjState, ObjectState initialObjState,
 575                     PartialEscapeBlockState<?> exitState) {
 576         for (int i = 0; i < exitObjState.getEntries().length; i++) {
 577             ValueNode value = exitState.getObjectState(object).getEntry(i);
 578             if (!(value instanceof VirtualObjectNode || value.isConstant())) {
 579                 if (exitNode.loopBegin().isPhiAtMerge(value) || initialObjState == null || !initialObjState.isVirtual() || initialObjState.getEntry(i) != value) {
 580                     ProxyNode proxy = new ValueProxyNode(value, exitNode);
 581                     exitState.setEntry(object, i, proxy);
 582                     effects.addFloatingNode(proxy, "virtualProxy");
 583                 }
 584             }
 585         }
 586     }
 587 
 588     @Override
 589     protected MergeProcessor createMergeProcessor(Block merge) {
 590         return new MergeProcessor(merge);
 591     }
 592 
 593     protected class MergeProcessor extends EffectsClosure<BlockT>.MergeProcessor {
 594 
 595         private EconomicMap<Object, ValuePhiNode> materializedPhis;
 596         private EconomicMap<ValueNode, ValuePhiNode[]> valuePhis;
 597         private EconomicMap<ValuePhiNode, VirtualObjectNode> valueObjectVirtuals;
 598         private final boolean needsCaching;
 599 
 600         public MergeProcessor(Block mergeBlock) {
 601             super(mergeBlock);
 602             // merge will only be called multiple times for loop headers
 603             needsCaching = mergeBlock.isLoopHeader();
 604         }
 605 
 606         protected <T> PhiNode getPhi(T virtual, Stamp stamp) {
 607             if (needsCaching) {
 608                 return getPhiCached(virtual, stamp);
 609             } else {
 610                 return createValuePhi(stamp);
 611             }
 612         }
 613 
 614         private <T> PhiNode getPhiCached(T virtual, Stamp stamp) {
 615             if (materializedPhis == null) {
 616                 materializedPhis = EconomicMap.create(Equivalence.DEFAULT);
 617             }
 618             ValuePhiNode result = materializedPhis.get(virtual);
 619             if (result == null) {
 620                 result = createValuePhi(stamp);
 621                 materializedPhis.put(virtual, result);
 622             }
 623             return result;
 624         }
 625 
 626         private PhiNode[] getValuePhis(ValueNode key, int entryCount) {
 627             if (needsCaching) {
 628                 return getValuePhisCached(key, entryCount);
 629             } else {
 630                 return new ValuePhiNode[entryCount];
 631             }
 632         }
 633 
 634         private PhiNode[] getValuePhisCached(ValueNode key, int entryCount) {
 635             if (valuePhis == null) {
 636                 valuePhis = EconomicMap.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE);
 637             }
 638             ValuePhiNode[] result = valuePhis.get(key);
 639             if (result == null) {
 640                 result = new ValuePhiNode[entryCount];
 641                 valuePhis.put(key, result);
 642             }
 643             assert result.length == entryCount;
 644             return result;
 645         }
 646 
 647         private VirtualObjectNode getValueObjectVirtual(ValuePhiNode phi, VirtualObjectNode virtual) {
 648             if (needsCaching) {
 649                 return getValueObjectVirtualCached(phi, virtual);
 650             } else {
 651                 return virtual.duplicate();
 652             }
 653         }
 654 
 655         private VirtualObjectNode getValueObjectVirtualCached(ValuePhiNode phi, VirtualObjectNode virtual) {
 656             if (valueObjectVirtuals == null) {
 657                 valueObjectVirtuals = EconomicMap.create(Equivalence.IDENTITY);
 658             }
 659             VirtualObjectNode result = valueObjectVirtuals.get(phi);
 660             if (result == null) {
 661                 result = virtual.duplicate();
 662                 valueObjectVirtuals.put(phi, result);
 663             }
 664             return result;
 665         }
 666 
 667         /**
 668          * Merge all predecessor block states into one block state. This is an iterative process,
 669          * because merging states can lead to materializations which make previous parts of the
 670          * merging operation invalid. The merging process is executed until a stable state has been
 671          * reached. This method needs to be careful to place the effects of the merging operation
 672          * into the correct blocks.
 673          *
 674          * @param statesList the predecessor block states of the merge
 675          */
 676         @Override
 677         protected void merge(List<BlockT> statesList) {
 678 
 679             PartialEscapeBlockState<?>[] states = new PartialEscapeBlockState<?>[statesList.size()];
 680             for (int i = 0; i < statesList.size(); i++) {
 681                 states[i] = statesList.get(i);
 682             }
 683 
 684             // calculate the set of virtual objects that exist in all predecessors
 685             int[] virtualObjTemp = intersectVirtualObjects(states);
 686 
 687             boolean materialized;
 688             do {
 689                 materialized = false;
 690 
 691                 if (PartialEscapeBlockState.identicalObjectStates(states)) {
 692                     newState.adoptAddObjectStates(states[0]);
 693                 } else {
 694 
 695                     for (int object : virtualObjTemp) {
 696                         if (PartialEscapeBlockState.identicalObjectStates(states, object)) {
 697                             newState.addObject(object, states[0].getObjectState(object).share());
 698                             continue;
 699                         }
 700 
 701                         // determine if all inputs are virtual or the same materialized value
 702                         int virtualCount = 0;
 703                         ObjectState startObj = states[0].getObjectState(object);
 704                         boolean locksMatch = true;
 705                         boolean ensureVirtual = true;
 706                         ValueNode uniqueMaterializedValue = startObj.isVirtual() ? null : startObj.getMaterializedValue();
 707                         for (int i = 0; i < states.length; i++) {
 708                             ObjectState obj = states[i].getObjectState(object);
 709                             ensureVirtual &= obj.getEnsureVirtualized();
 710                             if (obj.isVirtual()) {
 711                                 virtualCount++;
 712                                 uniqueMaterializedValue = null;
 713                                 locksMatch &= obj.locksEqual(startObj);
 714                             } else if (obj.getMaterializedValue() != uniqueMaterializedValue) {
 715                                 uniqueMaterializedValue = null;
 716                             }
 717                         }
 718 
 719                         if (virtualCount == states.length && locksMatch) {
 720                             materialized |= mergeObjectStates(object, null, states);
 721                         } else {
 722                             if (uniqueMaterializedValue != null) {
 723                                 newState.addObject(object, new ObjectState(uniqueMaterializedValue, null, ensureVirtual));
 724                             } else {
 725                                 PhiNode materializedValuePhi = getPhi(object, StampFactory.forKind(JavaKind.Object));
 726                                 mergeEffects.addFloatingNode(materializedValuePhi, "materializedPhi");
 727                                 for (int i = 0; i < states.length; i++) {
 728                                     ObjectState obj = states[i].getObjectState(object);
 729                                     if (obj.isVirtual()) {
 730                                         Block predecessor = getPredecessor(i);
 731                                         if (!ensureVirtual && obj.isVirtual()) {
 732                                             // we can materialize if not all inputs are
 733                                             // "ensureVirtualized"
 734                                             obj.setEnsureVirtualized(false);
 735                                         }
 736                                         materialized |= ensureMaterialized(states[i], object, predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_MERGE);
 737                                         obj = states[i].getObjectState(object);
 738                                     }
 739                                     setPhiInput(materializedValuePhi, i, obj.getMaterializedValue());
 740                                 }
 741                                 newState.addObject(object, new ObjectState(materializedValuePhi, null, false));
 742                             }
 743                         }
 744                     }
 745                 }
 746 
 747                 for (PhiNode phi : getPhis()) {
 748                     aliases.set(phi, null);
 749                     if (hasVirtualInputs.isMarked(phi) && phi instanceof ValuePhiNode) {
 750                         materialized |= processPhi((ValuePhiNode) phi, states);
 751                     }
 752                 }
 753                 if (materialized) {
 754                     newState.resetObjectStates(virtualObjects.size());
 755                     mergeEffects.clear();
 756                     afterMergeEffects.clear();
 757                 }
 758             } while (materialized);
 759         }
 760 
 761         private int[] intersectVirtualObjects(PartialEscapeBlockState<?>[] states) {
 762             int length = states[0].getStateCount();
 763             for (int i = 1; i < states.length; i++) {
 764                 length = Math.min(length, states[i].getStateCount());
 765             }
 766 
 767             int count = 0;
 768             for (int objectIndex = 0; objectIndex < length; objectIndex++) {
 769                 if (intersectObjectState(states, objectIndex)) {
 770                     count++;
 771                 }
 772             }
 773 
 774             int index = 0;
 775             int[] resultInts = new int[count];
 776             for (int objectIndex = 0; objectIndex < length; objectIndex++) {
 777                 if (intersectObjectState(states, objectIndex)) {
 778                     resultInts[index++] = objectIndex;
 779                 }
 780             }
 781             assert index == count;
 782             return resultInts;
 783         }
 784 
 785         private boolean intersectObjectState(PartialEscapeBlockState<?>[] states, int objectIndex) {
 786             for (int i = 0; i < states.length; i++) {
 787                 PartialEscapeBlockState<?> state = states[i];
 788                 if (state.getObjectStateOptional(objectIndex) == null) {
 789                     return false;
 790                 }
 791             }
 792             return true;
 793         }
 794 
 795         /**
 796          * Try to merge multiple virtual object states into a single object state. If the incoming
 797          * object states are compatible, then this method will create PhiNodes for the object's
 798          * entries where needed. If they are incompatible, then all incoming virtual objects will be
 799          * materialized, and a PhiNode for the materialized values will be created. Object states
 800          * can be incompatible if they contain {@code long} or {@code double} values occupying two
 801          * {@code int} slots in such a way that that their values cannot be merged using PhiNodes.
 802          *
 803          * @param states the predecessor block states of the merge
 804          * @return true if materialization happened during the merge, false otherwise
 805          */
 806         private boolean mergeObjectStates(int resultObject, int[] sourceObjects, PartialEscapeBlockState<?>[] states) {
 807             boolean compatible = true;
 808             boolean ensureVirtual = true;
 809             IntUnaryOperator getObject = index -> sourceObjects == null ? resultObject : sourceObjects[index];
 810 
 811             VirtualObjectNode virtual = virtualObjects.get(resultObject);
 812             int entryCount = virtual.entryCount();
 813 
 814             // determine all entries that have a two-slot value
 815             JavaKind[] twoSlotKinds = null;
 816             outer: for (int i = 0; i < states.length; i++) {
 817                 ObjectState objectState = states[i].getObjectState(getObject.applyAsInt(i));
 818                 ValueNode[] entries = objectState.getEntries();
 819                 int valueIndex = 0;
 820                 ensureVirtual &= objectState.getEnsureVirtualized();
 821                 while (valueIndex < entryCount) {
 822                     JavaKind otherKind = entries[valueIndex].getStackKind();
 823                     JavaKind entryKind = virtual.entryKind(valueIndex);
 824                     if (entryKind == JavaKind.Int && otherKind.needsTwoSlots()) {
 825                         if (twoSlotKinds == null) {
 826                             twoSlotKinds = new JavaKind[entryCount];
 827                         }
 828                         if (twoSlotKinds[valueIndex] != null && twoSlotKinds[valueIndex] != otherKind) {
 829                             compatible = false;
 830                             break outer;
 831                         }
 832                         twoSlotKinds[valueIndex] = otherKind;
 833                         // skip the next entry
 834                         valueIndex++;
 835                     } else {
 836                         assert entryKind.getStackKind() == otherKind.getStackKind() || (entryKind == JavaKind.Int && otherKind == JavaKind.Illegal) ||
 837                                         entryKind.getBitCount() >= otherKind.getBitCount() : entryKind + " vs " + otherKind;
 838                     }
 839                     valueIndex++;
 840                 }
 841             }
 842             if (compatible && twoSlotKinds != null) {
 843                 // if there are two-slot values then make sure the incoming states can be merged
 844                 outer: for (int valueIndex = 0; valueIndex < entryCount; valueIndex++) {
 845                     if (twoSlotKinds[valueIndex] != null) {
 846                         assert valueIndex < virtual.entryCount() - 1 && virtual.entryKind(valueIndex) == JavaKind.Int && virtual.entryKind(valueIndex + 1) == JavaKind.Int;
 847                         for (int i = 0; i < states.length; i++) {
 848                             int object = getObject.applyAsInt(i);
 849                             ObjectState objectState = states[i].getObjectState(object);
 850                             ValueNode value = objectState.getEntry(valueIndex);
 851                             JavaKind valueKind = value.getStackKind();
 852                             if (valueKind != twoSlotKinds[valueIndex]) {
 853                                 ValueNode nextValue = objectState.getEntry(valueIndex + 1);
 854                                 if (value.isConstant() && value.asConstant().equals(JavaConstant.INT_0) && nextValue.isConstant() && nextValue.asConstant().equals(JavaConstant.INT_0)) {
 855                                     // rewrite to a zero constant of the larger kind
 856                                     states[i].setEntry(object, valueIndex, ConstantNode.defaultForKind(twoSlotKinds[valueIndex], graph()));
 857                                     states[i].setEntry(object, valueIndex + 1, ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), graph()));
 858                                 } else {
 859                                     compatible = false;
 860                                     break outer;
 861                                 }
 862                             }
 863                         }
 864                     }
 865                 }
 866             }
 867 
 868             if (compatible) {
 869                 // virtual objects are compatible: create phis for all entries that need them
 870                 ValueNode[] values = states[0].getObjectState(getObject.applyAsInt(0)).getEntries().clone();
 871                 PhiNode[] phis = getValuePhis(virtual, virtual.entryCount());
 872                 int valueIndex = 0;
 873                 while (valueIndex < values.length) {
 874                     for (int i = 1; i < states.length; i++) {
 875                         if (phis[valueIndex] == null) {
 876                             ValueNode field = states[i].getObjectState(getObject.applyAsInt(i)).getEntry(valueIndex);
 877                             if (values[valueIndex] != field) {
 878                                 phis[valueIndex] = createValuePhi(values[valueIndex].stamp().unrestricted());
 879                             }
 880                         }
 881                     }
 882                     if (phis[valueIndex] != null && !phis[valueIndex].stamp().isCompatible(values[valueIndex].stamp())) {
 883                         phis[valueIndex] = createValuePhi(values[valueIndex].stamp().unrestricted());
 884                     }
 885                     if (twoSlotKinds != null && twoSlotKinds[valueIndex] != null) {
 886                         // skip an entry after a long/double value that occupies two int slots
 887                         valueIndex++;
 888                         phis[valueIndex] = null;
 889                         values[valueIndex] = ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), graph());
 890                     }
 891                     valueIndex++;
 892                 }
 893 
 894                 boolean materialized = false;
 895                 for (int i = 0; i < values.length; i++) {
 896                     PhiNode phi = phis[i];
 897                     if (phi != null) {
 898                         mergeEffects.addFloatingNode(phi, "virtualMergePhi");
 899                         if (virtual.entryKind(i) == JavaKind.Object) {
 900                             materialized |= mergeObjectEntry(getObject, states, phi, i);
 901                         } else {
 902                             for (int i2 = 0; i2 < states.length; i2++) {
 903                                 ObjectState state = states[i2].getObjectState(getObject.applyAsInt(i2));
 904                                 if (!state.isVirtual()) {
 905                                     break;
 906                                 }
 907                                 setPhiInput(phi, i2, state.getEntry(i));
 908                             }
 909                         }
 910                         values[i] = phi;
 911                     }
 912                 }
 913                 newState.addObject(resultObject, new ObjectState(values, states[0].getObjectState(getObject.applyAsInt(0)).getLocks(), ensureVirtual));
 914                 return materialized;
 915             } else {
 916                 // not compatible: materialize in all predecessors
 917                 PhiNode materializedValuePhi = getPhi(resultObject, StampFactory.forKind(JavaKind.Object));
 918                 for (int i = 0; i < states.length; i++) {
 919                     Block predecessor = getPredecessor(i);
 920                     if (!ensureVirtual && states[i].getObjectState(getObject.applyAsInt(i)).isVirtual()) {
 921                         // we can materialize if not all inputs are "ensureVirtualized"
 922                         states[i].getObjectState(getObject.applyAsInt(i)).setEnsureVirtualized(false);
 923                     }
 924                     ensureMaterialized(states[i], getObject.applyAsInt(i), predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_MERGE);
 925                     setPhiInput(materializedValuePhi, i, states[i].getObjectState(getObject.applyAsInt(i)).getMaterializedValue());
 926                 }
 927                 newState.addObject(resultObject, new ObjectState(materializedValuePhi, null, ensureVirtual));
 928                 return true;
 929             }
 930         }
 931 
 932         /**
 933          * Fill the inputs of the PhiNode corresponding to one {@link JavaKind#Object} entry in the
 934          * virtual object.
 935          *
 936          * @return true if materialization happened during the merge, false otherwise
 937          */
 938         private boolean mergeObjectEntry(IntUnaryOperator objectIdFunc, PartialEscapeBlockState<?>[] states, PhiNode phi, int entryIndex) {
 939             boolean materialized = false;
 940             for (int i = 0; i < states.length; i++) {
 941                 int object = objectIdFunc.applyAsInt(i);
 942                 ObjectState objectState = states[i].getObjectState(object);
 943                 if (!objectState.isVirtual()) {
 944                     break;
 945                 }
 946                 ValueNode entry = objectState.getEntry(entryIndex);
 947                 if (entry instanceof VirtualObjectNode) {
 948                     VirtualObjectNode entryVirtual = (VirtualObjectNode) entry;
 949                     Block predecessor = getPredecessor(i);
 950                     materialized |= ensureMaterialized(states[i], entryVirtual.getObjectId(), predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_MERGE);
 951                     objectState = states[i].getObjectState(object);
 952                     if (objectState.isVirtual()) {
 953                         states[i].setEntry(object, entryIndex, entry = states[i].getObjectState(entryVirtual.getObjectId()).getMaterializedValue());
 954                     }
 955                 }
 956                 setPhiInput(phi, i, entry);
 957             }
 958             return materialized;
 959         }
 960 
 961         /**
 962          * Examine a PhiNode and try to replace it with merging of virtual objects if all its inputs
 963          * refer to virtual object states. In order for the merging to happen, all incoming object
 964          * states need to be compatible and without object identity (meaning that their object
 965          * identity if not used later on).
 966          *
 967          * @param phi the PhiNode that should be processed
 968          * @param states the predecessor block states of the merge
 969          * @return true if materialization happened during the merge, false otherwise
 970          */
 971         private boolean processPhi(ValuePhiNode phi, PartialEscapeBlockState<?>[] states) {
 972 
 973             // determine how many inputs are virtual and if they're all the same virtual object
 974             int virtualInputs = 0;
 975             boolean uniqueVirtualObject = true;
 976             boolean ensureVirtual = true;
 977             VirtualObjectNode[] virtualObjs = new VirtualObjectNode[states.length];
 978             for (int i = 0; i < states.length; i++) {
 979                 ValueNode alias = getAlias(getPhiValueAt(phi, i));
 980                 if (alias instanceof VirtualObjectNode) {
 981                     VirtualObjectNode virtual = (VirtualObjectNode) alias;
 982                     virtualObjs[i] = virtual;
 983                     ObjectState objectState = states[i].getObjectStateOptional(virtual);
 984                     if (objectState == null) {
 985                         assert getPhiValueAt(phi, i) instanceof PhiNode : "this should only happen for phi nodes";
 986                         return false;
 987                     }
 988                     if (objectState.isVirtual()) {
 989                         if (virtualObjs[0] != alias) {
 990                             uniqueVirtualObject = false;
 991                         }
 992                         ensureVirtual &= objectState.getEnsureVirtualized();
 993                         virtualInputs++;
 994                     }
 995                 }
 996             }
 997             if (virtualInputs == states.length) {
 998                 if (uniqueVirtualObject) {
 999                     // all inputs refer to the same object: just make the phi node an alias
1000                     addVirtualAlias(virtualObjs[0], phi);
1001                     mergeEffects.deleteNode(phi);
1002                     return false;
1003                 } else {
1004                     // all inputs are virtual: check if they're compatible and without identity
1005                     boolean compatible = true;
1006                     VirtualObjectNode firstVirtual = virtualObjs[0];
1007                     for (int i = 0; i < states.length; i++) {
1008                         VirtualObjectNode virtual = virtualObjs[i];
1009 
1010                         boolean identitySurvives = virtual.hasIdentity() &&
1011                                         // check whether we trivially see that this is the only
1012                                         // reference to this allocation
1013                                         !isSingleUsageAllocation(getPhiValueAt(phi, i));
1014 
1015                         if (identitySurvives || !firstVirtual.type().equals(virtual.type()) || firstVirtual.entryCount() != virtual.entryCount()) {
1016                             compatible = false;
1017                             break;
1018                         }
1019                         if (!states[0].getObjectState(firstVirtual).locksEqual(states[i].getObjectState(virtual))) {
1020                             compatible = false;
1021                             break;
1022                         }
1023                     }
1024                     if (compatible) {
1025                         VirtualObjectNode virtual = getValueObjectVirtual(phi, virtualObjs[0]);
1026                         mergeEffects.addFloatingNode(virtual, "valueObjectNode");
1027                         mergeEffects.deleteNode(phi);
1028                         if (virtual.getObjectId() == -1) {
1029                             int id = virtualObjects.size();
1030                             virtualObjects.add(virtual);
1031                             virtual.setObjectId(id);
1032                         }
1033 
1034                         int[] virtualObjectIds = new int[states.length];
1035                         for (int i = 0; i < states.length; i++) {
1036                             virtualObjectIds[i] = virtualObjs[i].getObjectId();
1037                         }
1038                         boolean materialized = mergeObjectStates(virtual.getObjectId(), virtualObjectIds, states);
1039                         addVirtualAlias(virtual, virtual);
1040                         addVirtualAlias(virtual, phi);
1041                         return materialized;
1042                     }
1043                 }
1044             }
1045 
1046             // otherwise: materialize all phi inputs
1047             boolean materialized = false;
1048             if (virtualInputs > 0) {
1049                 for (int i = 0; i < states.length; i++) {
1050                     VirtualObjectNode virtual = virtualObjs[i];
1051                     if (virtual != null) {
1052                         Block predecessor = getPredecessor(i);
1053                         if (!ensureVirtual && states[i].getObjectState(virtual).isVirtual()) {
1054                             // we can materialize if not all inputs are "ensureVirtualized"
1055                             states[i].getObjectState(virtual).setEnsureVirtualized(false);
1056                         }
1057                         materialized |= ensureMaterialized(states[i], virtual.getObjectId(), predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_PHI);
1058                     }
1059                 }
1060             }
1061             for (int i = 0; i < states.length; i++) {
1062                 VirtualObjectNode virtual = virtualObjs[i];
1063                 if (virtual != null) {
1064                     setPhiInput(phi, i, getAliasAndResolve(states[i], virtual));
1065                 }
1066             }
1067             return materialized;
1068         }
1069 
1070         private boolean isSingleUsageAllocation(ValueNode value) {
1071             /*
1072              * If the phi input is an allocation, we know that it is a "fresh" value, i.e., that
1073              * this is a value that will only appear through this source, and cannot appear anywhere
1074              * else. If the phi is also the only usage of this input, we know that no other place
1075              * can check object identity against it, so it is safe to lose the object identity here.
1076              */
1077             return value instanceof AllocatedObjectNode && value.hasExactlyOneUsage();
1078         }
1079     }
1080 
1081     public ObjectState getObjectState(PartialEscapeBlockState<?> state, ValueNode value) {
1082         if (value == null) {
1083             return null;
1084         }
1085         if (value.isAlive() && !aliases.isNew(value)) {
1086             ValueNode object = aliases.get(value);
1087             return object instanceof VirtualObjectNode ? state.getObjectStateOptional((VirtualObjectNode) object) : null;
1088         } else {
1089             if (value instanceof VirtualObjectNode) {
1090                 return state.getObjectStateOptional((VirtualObjectNode) value);
1091             }
1092             return null;
1093         }
1094     }
1095 
1096     public ValueNode getAlias(ValueNode value) {
1097         if (value != null && !(value instanceof VirtualObjectNode)) {
1098             if (value.isAlive() && !aliases.isNew(value)) {
1099                 ValueNode result = aliases.get(value);
1100                 if (result != null) {
1101                     return result;
1102                 }
1103             }
1104         }
1105         return value;
1106     }
1107 
1108     public ValueNode getAliasAndResolve(PartialEscapeBlockState<?> state, ValueNode value) {
1109         ValueNode result = getAlias(value);
1110         if (result instanceof VirtualObjectNode) {
1111             int id = ((VirtualObjectNode) result).getObjectId();
1112             if (id != -1 && !state.getObjectState(id).isVirtual()) {
1113                 result = state.getObjectState(id).getMaterializedValue();
1114             }
1115         }
1116         return result;
1117     }
1118 
1119     void addVirtualAlias(VirtualObjectNode virtual, ValueNode node) {
1120         if (node.isAlive()) {
1121             aliases.set(node, virtual);
1122             for (Node usage : node.usages()) {
1123                 markVirtualUsages(usage);
1124             }
1125         }
1126     }
1127 
1128     private void markVirtualUsages(Node node) {
1129         if (!hasVirtualInputs.isNew(node) && !hasVirtualInputs.isMarked(node)) {
1130             hasVirtualInputs.mark(node);
1131             if (node instanceof VirtualState) {
1132                 for (Node usage : node.usages()) {
1133                     markVirtualUsages(usage);
1134                 }
1135             }
1136         }
1137     }
1138 }