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