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