Source code

001/*
002 * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.virtual.phases.ea;
024
025import java.util.*;
026import java.util.function.*;
027
028import com.oracle.graal.debug.*;
029import jdk.internal.jvmci.meta.*;
030
031import com.oracle.graal.compiler.common.*;
032import com.oracle.graal.compiler.common.cfg.*;
033import com.oracle.graal.compiler.common.type.*;
034import com.oracle.graal.compiler.common.util.*;
035import com.oracle.graal.graph.*;
036import com.oracle.graal.graph.spi.*;
037import com.oracle.graal.nodes.*;
038import com.oracle.graal.nodes.VirtualState.NodeClosure;
039import com.oracle.graal.nodes.cfg.*;
040import com.oracle.graal.nodes.spi.*;
041import com.oracle.graal.nodes.virtual.*;
042import com.oracle.graal.phases.schedule.*;
043
044public abstract class PartialEscapeClosure<BlockT extends PartialEscapeBlockState<BlockT>> extends EffectsClosure<BlockT> {
045
046    public static final DebugMetric METRIC_MATERIALIZATIONS = Debug.metric("Materializations");
047    public static final DebugMetric METRIC_MATERIALIZATIONS_PHI = Debug.metric("MaterializationsPhi");
048    public static final DebugMetric METRIC_MATERIALIZATIONS_MERGE = Debug.metric("MaterializationsMerge");
049    public static final DebugMetric METRIC_MATERIALIZATIONS_UNHANDLED = Debug.metric("MaterializationsUnhandled");
050    public static final DebugMetric METRIC_MATERIALIZATIONS_LOOP_REITERATION = Debug.metric("MaterializationsLoopReiteration");
051    public static final DebugMetric METRIC_MATERIALIZATIONS_LOOP_END = Debug.metric("MaterializationsLoopEnd");
052    public static final DebugMetric METRIC_ALLOCATION_REMOVED = Debug.metric("AllocationsRemoved");
053
054    public static final DebugMetric METRIC_MEMORYCHECKPOINT = Debug.metric("MemoryCheckpoint");
055
056    private final NodeBitMap hasVirtualInputs;
057    private final VirtualizerToolImpl tool;
058
059    public final ArrayList<VirtualObjectNode> virtualObjects = new ArrayList<>();
060
061    private final class CollectVirtualObjectsClosure extends NodeClosure<ValueNode> {
062        private final Set<VirtualObjectNode> virtual;
063        private final GraphEffectList effects;
064        private final BlockT state;
065
066        private CollectVirtualObjectsClosure(Set<VirtualObjectNode> virtual, GraphEffectList effects, BlockT state) {
067            this.virtual = virtual;
068            this.effects = effects;
069            this.state = state;
070        }
071
072        @Override
073        public void apply(Node usage, ValueNode value) {
074            if (value instanceof VirtualObjectNode) {
075                VirtualObjectNode object = (VirtualObjectNode) value;
076                if (object.getObjectId() != -1 && state.getObjectStateOptional(object) != null) {
077                    virtual.add(object);
078                }
079            } else {
080                ValueNode alias = getAlias(value);
081                if (alias instanceof VirtualObjectNode) {
082                    VirtualObjectNode object = (VirtualObjectNode) alias;
083                    virtual.add(object);
084                    effects.replaceFirstInput(usage, value, object);
085                }
086            }
087        }
088    }
089
090    /**
091     * Final subclass of PartialEscapeClosure, for performance and to make everything behave nicely
092     * with generics.
093     */
094    public static final class Final extends PartialEscapeClosure<PartialEscapeBlockState.Final> {
095
096        public Final(SchedulePhase schedule, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection) {
097            super(schedule, metaAccess, constantReflection);
098        }
099
100        @Override
101        protected PartialEscapeBlockState.Final getInitialState() {
102            return new PartialEscapeBlockState.Final();
103        }
104
105        @Override
106        protected PartialEscapeBlockState.Final cloneState(PartialEscapeBlockState.Final oldState) {
107            return new PartialEscapeBlockState.Final(oldState);
108        }
109    }
110
111    public PartialEscapeClosure(SchedulePhase schedule, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection) {
112        super(schedule, schedule.getCFG());
113        this.hasVirtualInputs = schedule.getCFG().graph.createNodeBitMap();
114        this.tool = new VirtualizerToolImpl(metaAccess, constantReflection, this);
115    }
116
117    /**
118     * @return true if the node was deleted, false otherwise
119     */
120    @Override
121    protected boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
122        /*
123         * These checks make up for the fact that an earliest schedule moves CallTargetNodes upwards
124         * and thus materializes virtual objects needlessly. Also, FrameStates and ConstantNodes are
125         * scheduled, but can safely be ignored.
126         */
127        if (node instanceof CallTargetNode || node instanceof FrameState || node instanceof ConstantNode) {
128            return false;
129        } else if (node instanceof Invoke) {
130            processNodeInternal(((Invoke) node).callTarget(), state, effects, lastFixedNode);
131        }
132        return processNodeInternal(node, state, effects, lastFixedNode);
133    }
134
135    private boolean processNodeInternal(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
136        FixedNode nextFixedNode = lastFixedNode == null ? null : lastFixedNode.next();
137        VirtualUtil.trace("%s", node);
138
139        if (requiresProcessing(node)) {
140            if (processVirtualizable((ValueNode) node, nextFixedNode, state, effects) == false) {
141                return false;
142            }
143            if (tool.isDeleted()) {
144                VirtualUtil.trace("deleted virtualizable allocation %s", node);
145                return true;
146            }
147        }
148        if (hasVirtualInputs.isMarked(node) && node instanceof ValueNode) {
149            if (node instanceof Virtualizable) {
150                if (processVirtualizable((ValueNode) node, nextFixedNode, state, effects) == false) {
151                    return false;
152                }
153                if (tool.isDeleted()) {
154                    VirtualUtil.trace("deleted virtualizable node %s", node);
155                    return true;
156                }
157            }
158            processNodeInputs((ValueNode) node, nextFixedNode, state, effects);
159        }
160
161        if (hasScalarReplacedInputs(node) && node instanceof ValueNode) {
162            if (processNodeWithScalarReplacedInputs((ValueNode) node, nextFixedNode, state, effects)) {
163                return true;
164            }
165        }
166        return false;
167    }
168
169    protected boolean requiresProcessing(Node node) {
170        return node instanceof VirtualizableAllocation;
171    }
172
173    private boolean processNodeWithScalarReplacedInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
174        ValueNode canonicalizedValue = node;
175        if (node instanceof Canonicalizable.Unary<?>) {
176            @SuppressWarnings("unchecked")
177            Canonicalizable.Unary<ValueNode> canonicalizable = (Canonicalizable.Unary<ValueNode>) node;
178            ObjectState valueObj = getObjectState(state, canonicalizable.getValue());
179            ValueNode valueAlias = valueObj != null ? valueObj.getMaterializedValue() : getScalarAlias(canonicalizable.getValue());
180            if (valueAlias != canonicalizable.getValue()) {
181                canonicalizedValue = (ValueNode) canonicalizable.canonical(tool, valueAlias);
182            }
183        } else if (node instanceof Canonicalizable.Binary<?>) {
184            @SuppressWarnings("unchecked")
185            Canonicalizable.Binary<ValueNode> canonicalizable = (Canonicalizable.Binary<ValueNode>) node;
186            ObjectState xObj = getObjectState(state, canonicalizable.getX());
187            ValueNode xAlias = xObj != null ? xObj.getMaterializedValue() : getScalarAlias(canonicalizable.getX());
188            ObjectState yObj = getObjectState(state, canonicalizable.getY());
189            ValueNode yAlias = yObj != null ? yObj.getMaterializedValue() : getScalarAlias(canonicalizable.getY());
190            if (xAlias != canonicalizable.getX() || yAlias != canonicalizable.getY()) {
191                canonicalizedValue = (ValueNode) canonicalizable.canonical(tool, xAlias, yAlias);
192            }
193        } else {
194            return false;
195        }
196        if (canonicalizedValue != node && canonicalizedValue != null) {
197            if (canonicalizedValue.isAlive()) {
198                ValueNode alias = getAliasAndResolve(state, canonicalizedValue);
199                if (alias instanceof VirtualObjectNode) {
200                    addAndMarkAlias((VirtualObjectNode) alias, node);
201                    effects.deleteNode(node);
202                } else {
203                    effects.replaceAtUsages(node, alias);
204                    addScalarAlias(node, alias);
205                }
206            } else {
207                if (!prepareCanonicalNode(canonicalizedValue, state, effects)) {
208                    VirtualUtil.trace("replacement via canonicalization too complex: %s -> %s", node, canonicalizedValue);
209                    return false;
210                }
211                effects.ensureAdded(canonicalizedValue, insertBefore);
212                if (canonicalizedValue instanceof ControlSinkNode) {
213                    effects.replaceWithSink((FixedWithNextNode) node, (ControlSinkNode) canonicalizedValue);
214                    state.markAsDead();
215                } else {
216                    effects.replaceAtUsages(node, canonicalizedValue);
217                    addScalarAlias(node, canonicalizedValue);
218                }
219            }
220            VirtualUtil.trace("replaced via canonicalization: %s -> %s", node, canonicalizedValue);
221            return true;
222        }
223        return false;
224    }
225
226    private boolean prepareCanonicalNode(ValueNode node, BlockT state, GraphEffectList effects) {
227        assert !node.isAlive();
228        NodePosIterator iter = node.inputs().iterator();
229        while (iter.hasNext()) {
230            Position pos = iter.nextPosition();
231            Node input = pos.get(node);
232            if (input instanceof ValueNode) {
233                if (input.isAlive()) {
234                    ObjectState obj = getObjectState(state, (ValueNode) input);
235                    if (obj != null) {
236                        if (obj.isVirtual()) {
237                            return false;
238                        } else {
239                            pos.initialize(node, obj.getMaterializedValue());
240                        }
241                    } else {
242                        pos.initialize(node, getScalarAlias((ValueNode) input));
243                    }
244                } else {
245                    if (!prepareCanonicalNode((ValueNode) input, state, effects)) {
246                        return false;
247                    }
248                }
249            }
250        }
251        return true;
252    }
253
254    private void processNodeInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
255        VirtualUtil.trace("processing nodewithstate: %s", node);
256        for (Node input : node.inputs()) {
257            if (input instanceof ValueNode) {
258                ValueNode alias = getAlias((ValueNode) input);
259                if (alias instanceof VirtualObjectNode) {
260                    int id = ((VirtualObjectNode) alias).getObjectId();
261                    ensureMaterialized(state, id, insertBefore, effects, METRIC_MATERIALIZATIONS_UNHANDLED);
262                    effects.replaceFirstInput(node, input, state.getObjectState(id).getMaterializedValue());
263                    VirtualUtil.trace("replacing input %s at %s", input, node);
264                }
265            }
266        }
267        if (node instanceof NodeWithState) {
268            processNodeWithState((NodeWithState) node, state, effects);
269        }
270    }
271
272    private boolean processVirtualizable(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) {
273        tool.reset(state, node, insertBefore, effects);
274        return virtualize(node, tool);
275    }
276
277    protected boolean virtualize(ValueNode node, VirtualizerTool vt) {
278        ((Virtualizable) node).virtualize(vt);
279        return true; // request further processing
280    }
281
282    private void processNodeWithState(NodeWithState nodeWithState, BlockT state, GraphEffectList effects) {
283        for (FrameState fs : nodeWithState.states()) {
284            FrameState frameState = getUniqueFramestate(nodeWithState, fs);
285            Set<VirtualObjectNode> virtual = new ArraySet<>();
286            frameState.applyToNonVirtual(new CollectVirtualObjectsClosure(virtual, effects, state));
287            collectLockedVirtualObjects(state, virtual);
288            collectReferencedVirtualObjects(state, virtual);
289            addVirtualMappings(frameState, virtual, state, effects);
290        }
291    }
292
293    private static FrameState getUniqueFramestate(NodeWithState nodeWithState, FrameState frameState) {
294        if (frameState.getUsageCount() > 1) {
295            // Can happen for example from inlined snippets with multiple state split nodes.
296            FrameState copy = (FrameState) frameState.copyWithInputs();
297            nodeWithState.asNode().replaceFirstInput(frameState, copy);
298            return copy;
299        }
300        return frameState;
301    }
302
303    private void addVirtualMappings(FrameState frameState, Set<VirtualObjectNode> virtual, BlockT state, GraphEffectList effects) {
304        for (VirtualObjectNode obj : virtual) {
305            effects.addVirtualMapping(frameState, state.getObjectState(obj).createEscapeObjectState(obj));
306        }
307    }
308
309    private void collectReferencedVirtualObjects(BlockT state, Set<VirtualObjectNode> virtual) {
310        ArrayDeque<VirtualObjectNode> queue = new ArrayDeque<>(virtual);
311        while (!queue.isEmpty()) {
312            VirtualObjectNode object = queue.removeLast();
313            int id = object.getObjectId();
314            if (id != -1) {
315                ObjectState objState = state.getObjectStateOptional(id);
316                if (objState != null && objState.isVirtual()) {
317                    for (ValueNode entry : objState.getEntries()) {
318                        if (entry instanceof VirtualObjectNode) {
319                            VirtualObjectNode entryVirtual = (VirtualObjectNode) entry;
320                            if (!virtual.contains(entryVirtual)) {
321                                virtual.add(entryVirtual);
322                                queue.addLast(entryVirtual);
323                            }
324                        }
325                    }
326                }
327            }
328        }
329    }
330
331    private void collectLockedVirtualObjects(BlockT state, Set<VirtualObjectNode> virtual) {
332        for (int i = 0; i < state.getStateCount(); i++) {
333            ObjectState objState = state.getObjectStateOptional(i);
334            if (objState != null && objState.isVirtual() && objState.hasLocks()) {
335                virtual.add(virtualObjects.get(i));
336            }
337        }
338    }
339
340    /**
341     * @return true if materialization happened, false if not.
342     */
343    private boolean ensureMaterialized(PartialEscapeBlockState<?> state, int object, FixedNode materializeBefore, GraphEffectList effects, DebugMetric metric) {
344        if (state.getObjectState(object).isVirtual()) {
345            metric.increment();
346            VirtualObjectNode virtual = virtualObjects.get(object);
347            state.materializeBefore(materializeBefore, virtual, effects);
348            updateStatesForMaterialized(state, virtual, state.getObjectState(object).getMaterializedValue());
349            return true;
350        } else {
351            return false;
352        }
353    }
354
355    public static void updateStatesForMaterialized(PartialEscapeBlockState<?> state, VirtualObjectNode virtual, ValueNode materializedValue) {
356        // update all existing states with the newly materialized object
357        for (int i = 0; i < state.getStateCount(); i++) {
358            ObjectState objState = state.getObjectStateOptional(i);
359            if (objState != null && objState.isVirtual()) {
360                ValueNode[] entries = objState.getEntries();
361                for (int i2 = 0; i2 < entries.length; i2++) {
362                    if (entries[i2] == virtual) {
363                        state.setEntry(i, i2, materializedValue);
364                    }
365                }
366            }
367        }
368    }
369
370    @Override
371    protected void processInitialLoopState(Loop<Block> loop, BlockT initialState) {
372        for (PhiNode phi : ((LoopBeginNode) loop.getHeader().getBeginNode()).phis()) {
373            if (phi.valueAt(0) != null) {
374                ValueNode alias = getAliasAndResolve(initialState, phi.valueAt(0));
375                if (alias instanceof VirtualObjectNode) {
376                    VirtualObjectNode virtual = (VirtualObjectNode) alias;
377                    addAndMarkAlias(virtual, phi);
378                }
379            }
380        }
381    }
382
383    @Override
384    protected void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects) {
385        if (exitNode.graph().hasValueProxies()) {
386            Map<Integer, ProxyNode> proxies = new IdentityHashMap<>();
387            for (ProxyNode proxy : exitNode.proxies()) {
388                ValueNode alias = getAlias(proxy.value());
389                if (alias instanceof VirtualObjectNode) {
390                    VirtualObjectNode virtual = (VirtualObjectNode) alias;
391                    proxies.put(virtual.getObjectId(), proxy);
392                }
393            }
394            for (int i = 0; i < exitState.getStateCount(); i++) {
395                ObjectState exitObjState = exitState.getObjectStateOptional(i);
396                if (exitObjState != null) {
397                    ObjectState initialObjState = initialState.getObjectStateOptional(i);
398
399                    if (exitObjState.isVirtual()) {
400                        processVirtualAtLoopExit(exitNode, effects, i, exitObjState, initialObjState, exitState);
401                    } else {
402                        processMaterializedAtLoopExit(exitNode, effects, proxies, i, exitObjState, initialObjState, exitState);
403                    }
404                }
405            }
406        }
407    }
408
409    private static void processMaterializedAtLoopExit(LoopExitNode exitNode, GraphEffectList effects, Map<Integer, ProxyNode> proxies, int object, ObjectState exitObjState,
410                    ObjectState initialObjState, PartialEscapeBlockState<?> exitState) {
411        if (initialObjState == null || initialObjState.isVirtual()) {
412            ProxyNode proxy = proxies.get(object);
413            if (proxy == null) {
414                proxy = new ValueProxyNode(exitObjState.getMaterializedValue(), exitNode);
415                effects.addFloatingNode(proxy, "proxy");
416            } else {
417                effects.replaceFirstInput(proxy, proxy.value(), exitObjState.getMaterializedValue());
418                // nothing to do - will be handled in processNode
419            }
420            exitState.updateMaterializedValue(object, proxy);
421        } else {
422            if (initialObjState.getMaterializedValue() != exitObjState.getMaterializedValue()) {
423                Debug.log("materialized value changes within loop: %s vs. %s at %s", initialObjState.getMaterializedValue(), exitObjState.getMaterializedValue(), exitNode);
424            }
425        }
426    }
427
428    private static void processVirtualAtLoopExit(LoopExitNode exitNode, GraphEffectList effects, int object, ObjectState exitObjState, ObjectState initialObjState, PartialEscapeBlockState<?> exitState) {
429        for (int i = 0; i < exitObjState.getEntries().length; i++) {
430            ValueNode value = exitState.getObjectState(object).getEntry(i);
431            if (!(value instanceof VirtualObjectNode || value.isConstant())) {
432                if (exitNode.loopBegin().isPhiAtMerge(value) || initialObjState == null || !initialObjState.isVirtual() || initialObjState.getEntry(i) != value) {
433                    ProxyNode proxy = new ValueProxyNode(value, exitNode);
434                    exitState.setEntry(object, i, proxy);
435                    effects.addFloatingNode(proxy, "virtualProxy");
436                }
437            }
438        }
439    }
440
441    @Override
442    protected MergeProcessor createMergeProcessor(Block merge) {
443        return new MergeProcessor(merge);
444    }
445
446    protected class MergeProcessor extends EffectsClosure<BlockT>.MergeProcessor {
447
448        private HashMap<Object, ValuePhiNode> materializedPhis;
449        private Map<ValueNode, ValuePhiNode[]> valuePhis;
450        private Map<ValuePhiNode, VirtualObjectNode> valueObjectVirtuals;
451        private final boolean needsCaching;
452
453        public MergeProcessor(Block mergeBlock) {
454            super(mergeBlock);
455            needsCaching = mergeBlock.isLoopHeader();
456        }
457
458        protected <T> PhiNode getPhi(T virtual, Stamp stamp) {
459            if (needsCaching) {
460                return getPhiCached(virtual, stamp);
461            } else {
462                return createValuePhi(stamp);
463            }
464        }
465
466        private <T> PhiNode getPhiCached(T virtual, Stamp stamp) {
467            if (materializedPhis == null) {
468                materializedPhis = CollectionsFactory.newMap();
469            }
470            ValuePhiNode result = materializedPhis.get(virtual);
471            if (result == null) {
472                result = createValuePhi(stamp);
473                materializedPhis.put(virtual, result);
474            }
475            return result;
476        }
477
478        private PhiNode[] getValuePhis(ValueNode key, int entryCount) {
479            if (needsCaching) {
480                return getValuePhisCached(key, entryCount);
481            } else {
482                return new ValuePhiNode[entryCount];
483            }
484        }
485
486        private PhiNode[] getValuePhisCached(ValueNode key, int entryCount) {
487            if (valuePhis == null) {
488                valuePhis = Node.newIdentityMap();
489            }
490            ValuePhiNode[] result = valuePhis.get(key);
491            if (result == null) {
492                result = new ValuePhiNode[entryCount];
493                valuePhis.put(key, result);
494            }
495            assert result.length == entryCount;
496            return result;
497        }
498
499        private VirtualObjectNode getValueObjectVirtual(ValuePhiNode phi, VirtualObjectNode virtual) {
500            if (needsCaching) {
501                return getValueObjectVirtualCached(phi, virtual);
502            } else {
503                return virtual.duplicate();
504            }
505        }
506
507        private VirtualObjectNode getValueObjectVirtualCached(ValuePhiNode phi, VirtualObjectNode virtual) {
508            if (valueObjectVirtuals == null) {
509                valueObjectVirtuals = Node.newIdentityMap();
510            }
511            VirtualObjectNode result = valueObjectVirtuals.get(phi);
512            if (result == null) {
513                result = virtual.duplicate();
514                valueObjectVirtuals.put(phi, result);
515            }
516            return result;
517        }
518
519        /**
520         * Merge all predecessor block states into one block state. This is an iterative process,
521         * because merging states can lead to materializations which make previous parts of the
522         * merging operation invalid. The merging process is executed until a stable state has been
523         * reached. This method needs to be careful to place the effects of the merging operation
524         * into the correct blocks.
525         *
526         * @param statesList the predecessor block states of the merge
527         */
528        @Override
529        protected void merge(List<BlockT> statesList) {
530            super.merge(statesList);
531
532            PartialEscapeBlockState<?>[] states = new PartialEscapeBlockState<?>[statesList.size()];
533            for (int i = 0; i < statesList.size(); i++) {
534                states[i] = statesList.get(i);
535            }
536
537            // calculate the set of virtual objects that exist in all predecessors
538            int[] virtualObjTemp = intersectVirtualObjects(states);
539
540            boolean materialized;
541            do {
542                materialized = false;
543
544                if (PartialEscapeBlockState.identicalObjectStates(states)) {
545                    newState.adoptAddObjectStates(states[0]);
546                } else {
547
548                    for (int object : virtualObjTemp) {
549
550                        if (PartialEscapeBlockState.identicalObjectStates(states, object)) {
551                            newState.addObject(object, states[0].getObjectState(object).share());
552                            continue;
553                        }
554
555                        // determine if all inputs are virtual or the same materialized value
556                        int virtualCount = 0;
557                        ObjectState startObj = states[0].getObjectState(object);
558                        boolean locksMatch = true;
559                        boolean ensureVirtual = true;
560                        ValueNode uniqueMaterializedValue = startObj.isVirtual() ? null : startObj.getMaterializedValue();
561                        for (int i = 0; i < states.length; i++) {
562                            ObjectState obj = states[i].getObjectState(object);
563                            ensureVirtual &= obj.getEnsureVirtualized();
564                            if (obj.isVirtual()) {
565                                virtualCount++;
566                                uniqueMaterializedValue = null;
567                                locksMatch &= obj.locksEqual(startObj);
568                            } else if (obj.getMaterializedValue() != uniqueMaterializedValue) {
569                                uniqueMaterializedValue = null;
570                            }
571                        }
572
573                        if (virtualCount == states.length && locksMatch) {
574                            materialized |= mergeObjectStates(object, null, states);
575                        } else {
576                            if (uniqueMaterializedValue != null) {
577                                newState.addObject(object, new ObjectState(uniqueMaterializedValue, null, ensureVirtual));
578                            } else {
579                                PhiNode materializedValuePhi = getPhi(object, StampFactory.forKind(Kind.Object));
580                                mergeEffects.addFloatingNode(materializedValuePhi, "materializedPhi");
581                                for (int i = 0; i < states.length; i++) {
582                                    ObjectState obj = states[i].getObjectState(object);
583                                    if (obj.isVirtual()) {
584                                        Block predecessor = getPredecessor(i);
585                                        materialized |= ensureMaterialized(states[i], object, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE);
586                                        obj = states[i].getObjectState(object);
587                                    }
588                                    setPhiInput(materializedValuePhi, i, obj.getMaterializedValue());
589                                }
590                                newState.addObject(object, new ObjectState(materializedValuePhi, null, false));
591                            }
592                        }
593                    }
594                }
595
596                for (PhiNode phi : getPhis()) {
597                    if (hasVirtualInputs.isMarked(phi) && phi instanceof ValuePhiNode) {
598                        materialized |= processPhi((ValuePhiNode) phi, states, virtualObjTemp);
599                    }
600                }
601                if (materialized) {
602                    newState.resetObjectStates(virtualObjects.size());
603                    mergeEffects.clear();
604                    afterMergeEffects.clear();
605                }
606            } while (materialized);
607        }
608
609        private int[] intersectVirtualObjects(PartialEscapeBlockState<?>[] states) {
610            int length = states[0].getStateCount();
611            for (int i = 1; i < states.length; i++) {
612                length = Math.min(length, states[i].getStateCount());
613            }
614            boolean[] result = new boolean[length];
615            Arrays.fill(result, true);
616            int count = length;
617            for (int i = 0; i < states.length; i++) {
618                PartialEscapeBlockState<?> state = states[i];
619                for (int i2 = 0; i2 < length; i2++) {
620                    if (result[i2]) {
621                        if (state.getObjectStateOptional(i2) == null) {
622                            result[i2] = false;
623                            count--;
624                        }
625                    }
626                }
627            }
628            int[] resultInts = new int[count];
629            int index = 0;
630            for (int i = 0; i < length; i++) {
631                if (result[i]) {
632                    resultInts[index++] = i;
633                }
634            }
635            assert index == count;
636            return resultInts;
637        }
638
639        /**
640         * Try to merge multiple virtual object states into a single object state. If the incoming
641         * object states are compatible, then this method will create PhiNodes for the object's
642         * entries where needed. If they are incompatible, then all incoming virtual objects will be
643         * materialized, and a PhiNode for the materialized values will be created. Object states
644         * can be incompatible if they contain {@code long} or {@code double} values occupying two
645         * {@code int} slots in such a way that that their values cannot be merged using PhiNodes.
646         *
647         * @param states the predecessor block states of the merge
648         * @return true if materialization happened during the merge, false otherwise
649         */
650        private boolean mergeObjectStates(int resultObject, int[] sourceObjects, PartialEscapeBlockState<?>[] states) {
651            boolean compatible = true;
652            boolean ensureVirtual = true;
653            IntFunction<Integer> getObject = index -> sourceObjects == null ? resultObject : sourceObjects[index];
654
655            VirtualObjectNode virtual = virtualObjects.get(resultObject);
656            int entryCount = virtual.entryCount();
657
658            // determine all entries that have a two-slot value
659            Kind[] twoSlotKinds = null;
660            outer: for (int i = 0; i < states.length; i++) {
661                ObjectState objectState = states[i].getObjectState(getObject.apply(i));
662                ValueNode[] entries = objectState.getEntries();
663                int valueIndex = 0;
664                ensureVirtual &= objectState.getEnsureVirtualized();
665                while (valueIndex < entryCount) {
666                    Kind otherKind = entries[valueIndex].getKind();
667                    Kind entryKind = virtual.entryKind(valueIndex);
668                    if (entryKind == Kind.Int && otherKind.needsTwoSlots()) {
669                        if (twoSlotKinds == null) {
670                            twoSlotKinds = new Kind[entryCount];
671                        }
672                        if (twoSlotKinds[valueIndex] != null && twoSlotKinds[valueIndex] != otherKind) {
673                            compatible = false;
674                            break outer;
675                        }
676                        twoSlotKinds[valueIndex] = otherKind;
677                        // skip the next entry
678                        valueIndex++;
679                    } else {
680                        assert entryKind.getStackKind() == otherKind.getStackKind() || (entryKind == Kind.Int && otherKind == Kind.Illegal) || entryKind.getBitCount() >= otherKind.getBitCount() : entryKind +
681                                        " vs " + otherKind;
682                    }
683                    valueIndex++;
684                }
685            }
686            if (compatible && twoSlotKinds != null) {
687                // if there are two-slot values then make sure the incoming states can be merged
688                outer: for (int valueIndex = 0; valueIndex < entryCount; valueIndex++) {
689                    if (twoSlotKinds[valueIndex] != null) {
690                        assert valueIndex < virtual.entryCount() - 1 && virtual.entryKind(valueIndex) == Kind.Int && virtual.entryKind(valueIndex + 1) == Kind.Int;
691                        for (int i = 0; i < states.length; i++) {
692                            int object = getObject.apply(i);
693                            ObjectState objectState = states[i].getObjectState(object);
694                            ValueNode value = objectState.getEntry(valueIndex);
695                            Kind valueKind = value.getKind();
696                            if (valueKind != twoSlotKinds[valueIndex]) {
697                                ValueNode nextValue = objectState.getEntry(valueIndex + 1);
698                                if (value.isConstant() && value.asConstant().equals(JavaConstant.INT_0) && nextValue.isConstant() && nextValue.asConstant().equals(JavaConstant.INT_0)) {
699                                    // rewrite to a zero constant of the larger kind
700                                    states[i].setEntry(object, valueIndex, ConstantNode.defaultForKind(twoSlotKinds[valueIndex], graph()));
701                                    states[i].setEntry(object, valueIndex + 1, ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), graph()));
702                                } else {
703                                    compatible = false;
704                                    break outer;
705                                }
706                            }
707                        }
708                    }
709                }
710            }
711
712            if (compatible) {
713                // virtual objects are compatible: create phis for all entries that need them
714                ValueNode[] values = states[0].getObjectState(getObject.apply(0)).getEntries().clone();
715                PhiNode[] phis = getValuePhis(virtual, virtual.entryCount());
716                int valueIndex = 0;
717                while (valueIndex < values.length) {
718                    for (int i = 1; i < states.length; i++) {
719                        if (phis[valueIndex] == null) {
720                            ValueNode field = states[i].getObjectState(getObject.apply(i)).getEntry(valueIndex);
721                            if (values[valueIndex] != field) {
722                                phis[valueIndex] = createValuePhi(values[valueIndex].stamp().unrestricted());
723                            }
724                        }
725                    }
726                    if (phis[valueIndex] != null && !phis[valueIndex].stamp().isCompatible(values[valueIndex].stamp())) {
727                        phis[valueIndex] = createValuePhi(values[valueIndex].stamp().unrestricted());
728                    }
729                    if (twoSlotKinds != null && twoSlotKinds[valueIndex] != null) {
730                        // skip an entry after a long/double value that occupies two int slots
731                        valueIndex++;
732                        phis[valueIndex] = null;
733                        values[valueIndex] = ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), graph());
734                    }
735                    valueIndex++;
736                }
737
738                boolean materialized = false;
739                for (int i = 0; i < values.length; i++) {
740                    PhiNode phi = phis[i];
741                    if (phi != null) {
742                        mergeEffects.addFloatingNode(phi, "virtualMergePhi");
743                        if (virtual.entryKind(i) == Kind.Object) {
744                            materialized |= mergeObjectEntry(getObject, states, phi, i);
745                        } else {
746                            for (int i2 = 0; i2 < states.length; i2++) {
747                                ObjectState state = states[i2].getObjectState(getObject.apply(i2));
748                                if (!state.isVirtual()) {
749                                    break;
750                                }
751                                setPhiInput(phi, i2, state.getEntry(i));
752                            }
753                        }
754                        values[i] = phi;
755                    }
756                }
757                newState.addObject(resultObject, new ObjectState(values, states[0].getObjectState(getObject.apply(0)).getLocks(), ensureVirtual));
758                return materialized;
759            } else {
760                // not compatible: materialize in all predecessors
761                PhiNode materializedValuePhi = getPhi(resultObject, StampFactory.forKind(Kind.Object));
762                for (int i = 0; i < states.length; i++) {
763                    Block predecessor = getPredecessor(i);
764                    ensureMaterialized(states[i], getObject.apply(i), predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE);
765                    setPhiInput(materializedValuePhi, i, states[i].getObjectState(getObject.apply(i)).getMaterializedValue());
766                }
767                newState.addObject(resultObject, new ObjectState(materializedValuePhi, null, ensureVirtual));
768                return true;
769            }
770        }
771
772        /**
773         * Fill the inputs of the PhiNode corresponding to one {@link Kind#Object} entry in the
774         * virtual object.
775         *
776         * @return true if materialization happened during the merge, false otherwise
777         */
778        private boolean mergeObjectEntry(IntFunction<Integer> objectIdFunc, PartialEscapeBlockState<?>[] states, PhiNode phi, int entryIndex) {
779            boolean materialized = false;
780            for (int i = 0; i < states.length; i++) {
781                int object = objectIdFunc.apply(i);
782                ObjectState objectState = states[i].getObjectState(object);
783                if (!objectState.isVirtual()) {
784                    break;
785                }
786                ValueNode entry = objectState.getEntry(entryIndex);
787                if (entry instanceof VirtualObjectNode) {
788                    VirtualObjectNode entryVirtual = (VirtualObjectNode) entry;
789                    Block predecessor = getPredecessor(i);
790                    materialized |= ensureMaterialized(states[i], entryVirtual.getObjectId(), predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE);
791                    objectState = states[i].getObjectState(object);
792                    if (objectState.isVirtual()) {
793                        states[i].setEntry(object, entryIndex, entry = states[i].getObjectState(entryVirtual.getObjectId()).getMaterializedValue());
794                    }
795                }
796                setPhiInput(phi, i, entry);
797            }
798            return materialized;
799        }
800
801        /**
802         * Examine a PhiNode and try to replace it with merging of virtual objects if all its inputs
803         * refer to virtual object states. In order for the merging to happen, all incoming object
804         * states need to be compatible and without object identity (meaning that their object
805         * identity if not used later on).
806         *
807         * @param phi the PhiNode that should be processed
808         * @param states the predecessor block states of the merge
809         * @param mergedVirtualObjects the set of virtual objects that exist in all incoming states,
810         *            and therefore also exist in the merged state
811         * @return true if materialization happened during the merge, false otherwise
812         */
813        private boolean processPhi(ValuePhiNode phi, PartialEscapeBlockState<?>[] states, int[] mergedVirtualObjects) {
814            aliases.set(phi, null);
815
816            // determine how many inputs are virtual and if they're all the same virtual object
817            int virtualInputs = 0;
818            boolean uniqueVirtualObject = true;
819            VirtualObjectNode[] virtualObjs = new VirtualObjectNode[states.length];
820            for (int i = 0; i < states.length; i++) {
821                ValueNode alias = getAlias(getPhiValueAt(phi, i));
822                if (alias instanceof VirtualObjectNode) {
823                    VirtualObjectNode virtual = (VirtualObjectNode) alias;
824                    virtualObjs[i] = virtual;
825                    if (states[i].getObjectState(virtual).isVirtual()) {
826                        if (virtualObjs[0] != alias) {
827                            uniqueVirtualObject = false;
828                        }
829                        virtualInputs++;
830                    }
831                }
832            }
833            if (virtualInputs == states.length) {
834                if (uniqueVirtualObject) {
835                    // all inputs refer to the same object: just make the phi node an alias
836                    addAndMarkAlias(virtualObjs[0], phi);
837                    mergeEffects.deleteNode(phi);
838                    return false;
839                } else {
840                    // all inputs are virtual: check if they're compatible and without identity
841                    boolean compatible = true;
842                    boolean hasIdentity = false;
843                    VirtualObjectNode firstVirtual = virtualObjs[0];
844                    for (int i = 0; i < states.length; i++) {
845                        VirtualObjectNode virtual = virtualObjs[i];
846                        hasIdentity |= virtual.hasIdentity();
847                        boolean identitySurvives = virtual.hasIdentity() && Arrays.asList(mergedVirtualObjects).contains(virtual.getObjectId());
848                        if (identitySurvives || !firstVirtual.type().equals(virtual.type()) || firstVirtual.entryCount() != virtual.entryCount()) {
849                            compatible = false;
850                            break;
851                        }
852                        if (!states[0].getObjectState(firstVirtual).locksEqual(states[i].getObjectState(virtual))) {
853                            compatible = false;
854                            break;
855                        }
856                    }
857                    if (compatible && hasIdentity) {
858                        // we still need to check whether this value is referenced by any other phi
859                        outer: for (PhiNode otherPhi : getPhis().filter(otherPhi -> otherPhi != phi)) {
860                            for (int i = 0; i < states.length; i++) {
861                                ValueNode alias = getAliasAndResolve(states[i], getPhiValueAt(otherPhi, i));
862                                if (alias instanceof VirtualObjectNode) {
863                                    VirtualObjectNode phiValueVirtual = (VirtualObjectNode) alias;
864                                    if (Arrays.asList(virtualObjs).contains(phiValueVirtual)) {
865                                        compatible = false;
866                                        break outer;
867                                    }
868                                }
869                            }
870                        }
871                    }
872
873                    if (compatible) {
874                        VirtualObjectNode virtual = getValueObjectVirtual(phi, virtualObjs[0]);
875                        mergeEffects.addFloatingNode(virtual, "valueObjectNode");
876                        mergeEffects.deleteNode(phi);
877                        if (virtual.getObjectId() == -1) {
878                            int id = virtualObjects.size();
879                            virtualObjects.add(virtual);
880                            virtual.setObjectId(id);
881                        }
882
883                        int[] virtualObjectIds = new int[states.length];
884                        for (int i = 0; i < states.length; i++) {
885                            virtualObjectIds[i] = virtualObjs[i].getObjectId();
886                        }
887                        boolean materialized = mergeObjectStates(virtual.getObjectId(), virtualObjectIds, states);
888                        addAndMarkAlias(virtual, virtual);
889                        addAndMarkAlias(virtual, phi);
890                        return materialized;
891                    }
892                }
893            }
894
895            // otherwise: materialize all phi inputs
896            boolean materialized = false;
897            for (int i = 0; i < states.length; i++) {
898                VirtualObjectNode virtual = virtualObjs[i];
899                if (virtual != null) {
900                    Block predecessor = getPredecessor(i);
901                    materialized |= ensureMaterialized(states[i], virtual.getObjectId(), predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_PHI);
902                    setPhiInput(phi, i, getAliasAndResolve(states[i], virtual));
903                }
904            }
905            return materialized;
906        }
907    }
908
909    public ObjectState getObjectState(PartialEscapeBlockState<?> state, ValueNode value) {
910        if (value == null) {
911            return null;
912        }
913        if (value.isAlive() && !aliases.isNew(value)) {
914            ValueNode object = aliases.get(value);
915            return object instanceof VirtualObjectNode ? state.getObjectStateOptional((VirtualObjectNode) object) : null;
916        } else {
917            if (value instanceof VirtualObjectNode) {
918                return state.getObjectStateOptional((VirtualObjectNode) value);
919            }
920            return null;
921        }
922    }
923
924    public ValueNode getAlias(ValueNode value) {
925        if (value != null && !(value instanceof VirtualObjectNode)) {
926            if (value.isAlive() && !aliases.isNew(value)) {
927                ValueNode result = aliases.get(value);
928                if (result != null) {
929                    return result;
930                }
931            }
932        }
933        return value;
934    }
935
936    public ValueNode getAliasAndResolve(PartialEscapeBlockState<?> state, ValueNode value) {
937        ValueNode result = getAlias(value);
938        if (result instanceof VirtualObjectNode) {
939            int id = ((VirtualObjectNode) result).getObjectId();
940            if (id != -1 && !state.getObjectState(id).isVirtual()) {
941                result = state.getObjectState(id).getMaterializedValue();
942            }
943        }
944        return result;
945    }
946
947    void addAndMarkAlias(VirtualObjectNode virtual, ValueNode node) {
948        if (node.isAlive()) {
949            aliases.set(node, virtual);
950            for (Node usage : node.usages()) {
951                markVirtualUsages(usage);
952            }
953        }
954    }
955
956    private void markVirtualUsages(Node node) {
957        if (!hasVirtualInputs.isNew(node) && !hasVirtualInputs.isMarked(node)) {
958            hasVirtualInputs.mark(node);
959            if (node instanceof VirtualState) {
960                for (Node usage : node.usages()) {
961                    markVirtualUsages(usage);
962                }
963            }
964        }
965    }
966}