1 /*
   2  * Copyright (c) 2012, 2016, 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.java;
  24 
  25 import static org.graalvm.compiler.bytecode.Bytecodes.DUP;
  26 import static org.graalvm.compiler.bytecode.Bytecodes.DUP2;
  27 import static org.graalvm.compiler.bytecode.Bytecodes.DUP2_X1;
  28 import static org.graalvm.compiler.bytecode.Bytecodes.DUP2_X2;
  29 import static org.graalvm.compiler.bytecode.Bytecodes.DUP_X1;
  30 import static org.graalvm.compiler.bytecode.Bytecodes.DUP_X2;
  31 import static org.graalvm.compiler.bytecode.Bytecodes.POP;
  32 import static org.graalvm.compiler.bytecode.Bytecodes.POP2;
  33 import static org.graalvm.compiler.bytecode.Bytecodes.SWAP;
  34 import static org.graalvm.compiler.debug.GraalError.shouldNotReachHere;
  35 import static org.graalvm.compiler.java.BytecodeParserOptions.HideSubstitutionStates;
  36 import static org.graalvm.compiler.nodes.FrameState.TWO_SLOT_MARKER;
  37 
  38 import java.util.ArrayList;
  39 import java.util.Arrays;
  40 import java.util.List;
  41 import java.util.function.Function;
  42 
  43 import org.graalvm.compiler.bytecode.Bytecode;
  44 import org.graalvm.compiler.bytecode.ResolvedJavaMethodBytecode;
  45 import org.graalvm.compiler.core.common.GraalOptions;
  46 import org.graalvm.compiler.core.common.PermanentBailoutException;
  47 import org.graalvm.compiler.core.common.type.StampFactory;
  48 import org.graalvm.compiler.core.common.type.StampPair;
  49 import org.graalvm.compiler.debug.DebugContext;
  50 import org.graalvm.compiler.graph.NodeSourcePosition;
  51 import org.graalvm.compiler.java.BciBlockMapping.BciBlock;
  52 import org.graalvm.compiler.nodeinfo.Verbosity;
  53 import org.graalvm.compiler.nodes.AbstractMergeNode;
  54 import org.graalvm.compiler.nodes.ConstantNode;
  55 import org.graalvm.compiler.nodes.FrameState;
  56 import org.graalvm.compiler.nodes.LoopBeginNode;
  57 import org.graalvm.compiler.nodes.LoopExitNode;
  58 import org.graalvm.compiler.nodes.ParameterNode;
  59 import org.graalvm.compiler.nodes.PhiNode;
  60 import org.graalvm.compiler.nodes.ProxyNode;
  61 import org.graalvm.compiler.nodes.StateSplit;
  62 import org.graalvm.compiler.nodes.StructuredGraph;
  63 import org.graalvm.compiler.nodes.ValueNode;
  64 import org.graalvm.compiler.nodes.ValuePhiNode;
  65 import org.graalvm.compiler.nodes.calc.FloatingNode;
  66 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins;
  67 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderTool;
  68 import org.graalvm.compiler.nodes.graphbuilderconf.IntrinsicContext.SideEffectsState;
  69 import org.graalvm.compiler.nodes.graphbuilderconf.ParameterPlugin;
  70 import org.graalvm.compiler.nodes.java.MonitorIdNode;
  71 import org.graalvm.compiler.nodes.util.GraphUtil;
  72 
  73 import jdk.vm.ci.code.BytecodeFrame;
  74 import jdk.vm.ci.meta.Assumptions;
  75 import jdk.vm.ci.meta.JavaConstant;
  76 import jdk.vm.ci.meta.JavaKind;
  77 import jdk.vm.ci.meta.JavaType;
  78 import jdk.vm.ci.meta.ResolvedJavaMethod;
  79 import jdk.vm.ci.meta.ResolvedJavaType;
  80 import jdk.vm.ci.meta.Signature;
  81 
  82 public final class FrameStateBuilder implements SideEffectsState {
  83 
  84     private static final ValueNode[] EMPTY_ARRAY = new ValueNode[0];
  85     private static final MonitorIdNode[] EMPTY_MONITOR_ARRAY = new MonitorIdNode[0];
  86 
  87     private final BytecodeParser parser;
  88     private final GraphBuilderTool tool;
  89     private final Bytecode code;
  90     private int stackSize;
  91     protected final ValueNode[] locals;
  92     protected final ValueNode[] stack;
  93     private ValueNode[] lockedObjects;
  94     private boolean canVerifyKind;
  95 
  96     /**
  97      * @see BytecodeFrame#rethrowException
  98      */
  99     private boolean rethrowException;
 100 
 101     private MonitorIdNode[] monitorIds;
 102     private final StructuredGraph graph;
 103     private final boolean clearNonLiveLocals;
 104     private FrameState outerFrameState;
 105     private NodeSourcePosition outerSourcePosition;
 106 
 107     /**
 108      * The closest {@link StateSplit#hasSideEffect() side-effect} predecessors. There will be more
 109      * than one when the current block contains no side-effects but merging predecessor blocks do.
 110      */
 111     private List<StateSplit> sideEffects;
 112 
 113     private JavaConstant constantReceiver;
 114 
 115     /**
 116      * Creates a new frame state builder for the given method and the given target graph.
 117      *
 118      * @param method the method whose frame is simulated
 119      * @param graph the target graph of Graal nodes created by the builder
 120      */
 121     public FrameStateBuilder(GraphBuilderTool tool, ResolvedJavaMethod method, StructuredGraph graph) {
 122         this(tool, new ResolvedJavaMethodBytecode(method), graph);
 123     }
 124 
 125     /**
 126      * Creates a new frame state builder for the given code attribute, method and the given target
 127      * graph.
 128      *
 129      * @param code the bytecode in which the frame exists
 130      * @param graph the target graph of Graal nodes created by the builder
 131      */
 132     public FrameStateBuilder(GraphBuilderTool tool, Bytecode code, StructuredGraph graph) {
 133         this.tool = tool;
 134         if (tool instanceof BytecodeParser) {
 135             this.parser = (BytecodeParser) tool;
 136         } else {
 137             this.parser = null;
 138         }
 139         this.code = code;
 140         this.locals = allocateArray(code.getMaxLocals());
 141         this.stack = allocateArray(Math.max(1, code.getMaxStackSize()));
 142         this.lockedObjects = allocateArray(0);
 143 
 144         assert graph != null;
 145 
 146         this.monitorIds = EMPTY_MONITOR_ARRAY;
 147         this.graph = graph;
 148         this.clearNonLiveLocals = GraalOptions.OptClearNonLiveLocals.getValue(graph.getOptions());
 149         this.canVerifyKind = true;
 150     }
 151 
 152     public void disableKindVerification() {
 153         canVerifyKind = false;
 154     }
 155 
 156     public void initializeFromArgumentsArray(ValueNode[] arguments) {
 157 
 158         int javaIndex = 0;
 159         int index = 0;
 160         if (!getMethod().isStatic()) {
 161             // set the receiver
 162             locals[javaIndex] = arguments[index];
 163             javaIndex = 1;
 164             index = 1;
 165             constantReceiver = locals[0].asJavaConstant();
 166         }
 167         Signature sig = getMethod().getSignature();
 168         int max = sig.getParameterCount(false);
 169         for (int i = 0; i < max; i++) {
 170             JavaKind kind = sig.getParameterKind(i);
 171             locals[javaIndex] = arguments[index];
 172             javaIndex++;
 173             if (kind.needsTwoSlots()) {
 174                 locals[javaIndex] = TWO_SLOT_MARKER;
 175                 javaIndex++;
 176             }
 177             index++;
 178         }
 179     }
 180 
 181     public void initializeForMethodStart(Assumptions assumptions, boolean eagerResolve, Plugins plugins) {
 182 
 183         int javaIndex = 0;
 184         int index = 0;
 185         ResolvedJavaMethod method = getMethod();
 186         ResolvedJavaType originalType = method.getDeclaringClass();
 187         if (!method.isStatic()) {
 188             // add the receiver
 189             FloatingNode receiver = null;
 190             StampPair receiverStamp = null;
 191             if (plugins != null) {
 192                 receiverStamp = plugins.getOverridingStamp(tool, originalType, true);
 193             }
 194             if (receiverStamp == null) {
 195                 receiverStamp = StampFactory.forDeclaredType(assumptions, originalType, true);
 196             }
 197 
 198             if (plugins != null) {
 199                 for (ParameterPlugin plugin : plugins.getParameterPlugins()) {
 200                     receiver = plugin.interceptParameter(tool, index, receiverStamp);
 201                     if (receiver != null) {
 202                         break;
 203                     }
 204                 }
 205             }
 206             if (receiver == null) {
 207                 receiver = new ParameterNode(javaIndex, receiverStamp);
 208             }
 209 
 210             locals[javaIndex] = graph.addOrUnique(receiver);
 211             javaIndex = 1;
 212             index = 1;
 213         }
 214         Signature sig = method.getSignature();
 215         int max = sig.getParameterCount(false);
 216         ResolvedJavaType accessingClass = originalType;
 217         for (int i = 0; i < max; i++) {
 218             JavaType type = sig.getParameterType(i, accessingClass);
 219             if (eagerResolve) {
 220                 type = type.resolve(accessingClass);
 221             }
 222             JavaKind kind = type.getJavaKind();
 223             StampPair stamp = null;
 224             if (plugins != null) {
 225                 stamp = plugins.getOverridingStamp(tool, type, false);
 226             }
 227             if (stamp == null) {
 228                 stamp = StampFactory.forDeclaredType(assumptions, type, false);
 229             }
 230 
 231             FloatingNode param = null;
 232             if (plugins != null) {
 233                 for (ParameterPlugin plugin : plugins.getParameterPlugins()) {
 234                     param = plugin.interceptParameter(tool, index, stamp);
 235                     if (param != null) {
 236                         break;
 237                     }
 238                 }
 239             }
 240             if (param == null) {
 241                 param = new ParameterNode(index, stamp);
 242             }
 243 
 244             locals[javaIndex] = graph.addOrUnique(param);
 245             javaIndex++;
 246             if (kind.needsTwoSlots()) {
 247                 locals[javaIndex] = TWO_SLOT_MARKER;
 248                 javaIndex++;
 249             }
 250             index++;
 251         }
 252     }
 253 
 254     private FrameStateBuilder(FrameStateBuilder other) {
 255         this.parser = other.parser;
 256         this.tool = other.tool;
 257         this.code = other.code;
 258         this.stackSize = other.stackSize;
 259         this.locals = other.locals.clone();
 260         this.stack = other.stack.clone();
 261         this.lockedObjects = other.lockedObjects.length == 0 ? other.lockedObjects : other.lockedObjects.clone();
 262         this.rethrowException = other.rethrowException;
 263         this.canVerifyKind = other.canVerifyKind;
 264 
 265         assert locals.length == code.getMaxLocals();
 266         assert stack.length == Math.max(1, code.getMaxStackSize());
 267 
 268         assert other.graph != null;
 269         graph = other.graph;
 270         clearNonLiveLocals = other.clearNonLiveLocals;
 271         monitorIds = other.monitorIds.length == 0 ? other.monitorIds : other.monitorIds.clone();
 272 
 273         assert locals.length == code.getMaxLocals();
 274         assert stack.length == Math.max(1, code.getMaxStackSize());
 275         assert lockedObjects.length == monitorIds.length;
 276     }
 277 
 278     private static ValueNode[] allocateArray(int length) {
 279         return length == 0 ? EMPTY_ARRAY : new ValueNode[length];
 280     }
 281 
 282     public ResolvedJavaMethod getMethod() {
 283         return code.getMethod();
 284     }
 285 
 286     @Override
 287     public String toString() {
 288         StringBuilder sb = new StringBuilder();
 289         sb.append("[locals: [");
 290         for (int i = 0; i < locals.length; i++) {
 291             sb.append(i == 0 ? "" : ",").append(locals[i] == null ? "_" : locals[i] == TWO_SLOT_MARKER ? "#" : locals[i].toString(Verbosity.Id));
 292         }
 293         sb.append("] stack: [");
 294         for (int i = 0; i < stackSize; i++) {
 295             sb.append(i == 0 ? "" : ",").append(stack[i] == null ? "_" : stack[i] == TWO_SLOT_MARKER ? "#" : stack[i].toString(Verbosity.Id));
 296         }
 297         sb.append("] locks: [");
 298         for (int i = 0; i < lockedObjects.length; i++) {
 299             sb.append(i == 0 ? "" : ",").append(lockedObjects[i].toString(Verbosity.Id)).append(" / ").append(monitorIds[i].toString(Verbosity.Id));
 300         }
 301         sb.append("]");
 302         if (rethrowException) {
 303             sb.append(" rethrowException");
 304         }
 305         sb.append("]");
 306         return sb.toString();
 307     }
 308 
 309     public FrameState create(int bci, StateSplit forStateSplit) {
 310         if (parser != null && parser.parsingIntrinsic()) {
 311             NodeSourcePosition sourcePosition = createBytecodePosition(bci, false);
 312             return parser.intrinsicContext.createFrameState(parser.getGraph(), this, forStateSplit, sourcePosition);
 313         }
 314 
 315         // Skip intrinsic frames
 316         return create(bci, parser != null ? parser.getNonIntrinsicAncestor() : null, false, null, null);
 317     }
 318 
 319     /**
 320      * @param pushedValues if non-null, values to {@link #push(JavaKind, ValueNode)} to the stack
 321      *            before creating the {@link FrameState}
 322      */
 323     public FrameState create(int bci, BytecodeParser parent, boolean duringCall, JavaKind[] pushedSlotKinds, ValueNode[] pushedValues) {
 324         if (outerFrameState == null && parent != null) {
 325             assert !parent.parsingIntrinsic() : "must already have the next non-intrinsic ancestor";
 326             outerFrameState = parent.getFrameStateBuilder().create(parent.bci(), parent.getNonIntrinsicAncestor(), true, null, null);
 327         }
 328         if (bci == BytecodeFrame.AFTER_EXCEPTION_BCI && parent != null) {
 329             FrameState newFrameState = outerFrameState.duplicateModified(outerFrameState.bci, true, false, JavaKind.Void, new JavaKind[]{JavaKind.Object}, new ValueNode[]{stack[0]});
 330             return newFrameState;
 331         }
 332         if (bci == BytecodeFrame.INVALID_FRAMESTATE_BCI) {
 333             throw shouldNotReachHere();
 334         }
 335 
 336         if (pushedValues != null) {
 337             assert pushedSlotKinds.length == pushedValues.length;
 338             int stackSizeToRestore = stackSize;
 339             for (int i = 0; i < pushedValues.length; i++) {
 340                 push(pushedSlotKinds[i], pushedValues[i]);
 341             }
 342             FrameState res = graph.add(new FrameState(outerFrameState, code, bci, locals, stack, stackSize, lockedObjects, Arrays.asList(monitorIds), rethrowException, duringCall));
 343             stackSize = stackSizeToRestore;
 344             return res;
 345         } else {
 346             if (bci == BytecodeFrame.AFTER_EXCEPTION_BCI) {
 347                 assert outerFrameState == null;
 348                 clearLocals();
 349             }
 350             return graph.add(new FrameState(outerFrameState, code, bci, locals, stack, stackSize, lockedObjects, Arrays.asList(monitorIds), rethrowException, duringCall));
 351         }
 352     }
 353 
 354     public NodeSourcePosition createBytecodePosition(int bci) {
 355         return createBytecodePosition(bci, HideSubstitutionStates.getValue(parser.graph.getOptions()));
 356     }
 357 
 358     private NodeSourcePosition createBytecodePosition(int bci, boolean hideSubstitutionStates) {
 359         BytecodeParser parent = parser.getParent();
 360         if (hideSubstitutionStates) {
 361             if (parser.parsingIntrinsic()) {
 362                 // Attribute to the method being replaced
 363                 return new NodeSourcePosition(constantReceiver, parent.getFrameStateBuilder().createBytecodePosition(parent.bci()), parser.intrinsicContext.getOriginalMethod(), -1);
 364             }
 365             // Skip intrinsic frames
 366             parent = parser.getNonIntrinsicAncestor();
 367         }
 368         return create(constantReceiver, bci, parent, hideSubstitutionStates);
 369     }
 370 
 371     private NodeSourcePosition create(JavaConstant receiver, int bci, BytecodeParser parent, boolean hideSubstitutionStates) {
 372         if (outerSourcePosition == null && parent != null) {
 373             outerSourcePosition = parent.getFrameStateBuilder().createBytecodePosition(parent.bci(), hideSubstitutionStates);
 374         }
 375         if (bci == BytecodeFrame.AFTER_EXCEPTION_BCI && parent != null) {
 376             return FrameState.toSourcePosition(outerFrameState);
 377         }
 378         if (bci == BytecodeFrame.INVALID_FRAMESTATE_BCI) {
 379             throw shouldNotReachHere();
 380         }
 381         return new NodeSourcePosition(receiver, outerSourcePosition, code.getMethod(), bci);
 382     }
 383 
 384     public FrameStateBuilder copy() {
 385         return new FrameStateBuilder(this);
 386     }
 387 
 388     public boolean isCompatibleWith(FrameStateBuilder other) {
 389         assert code.equals(other.code) && graph == other.graph && localsSize() == other.localsSize() : "Can only compare frame states of the same method";
 390         assert lockedObjects.length == monitorIds.length && other.lockedObjects.length == other.monitorIds.length : "mismatch between lockedObjects and monitorIds";
 391 
 392         if (stackSize() != other.stackSize()) {
 393             return false;
 394         }
 395         for (int i = 0; i < stackSize(); i++) {
 396             ValueNode x = stack[i];
 397             ValueNode y = other.stack[i];
 398             assert x != null && y != null;
 399             if (x != y && (x == TWO_SLOT_MARKER || x.isDeleted() || y == TWO_SLOT_MARKER || y.isDeleted() || x.getStackKind() != y.getStackKind())) {
 400                 return false;
 401             }
 402         }
 403         if (lockedObjects.length != other.lockedObjects.length) {
 404             return false;
 405         }
 406         for (int i = 0; i < lockedObjects.length; i++) {
 407             if (GraphUtil.originalValue(lockedObjects[i]) != GraphUtil.originalValue(other.lockedObjects[i]) || monitorIds[i] != other.monitorIds[i]) {
 408                 throw new PermanentBailoutException("unbalanced monitors");
 409             }
 410         }
 411         return true;
 412     }
 413 
 414     public void merge(AbstractMergeNode block, FrameStateBuilder other) {
 415         assert isCompatibleWith(other);
 416 
 417         for (int i = 0; i < localsSize(); i++) {
 418             locals[i] = merge(locals[i], other.locals[i], block);
 419         }
 420         for (int i = 0; i < stackSize(); i++) {
 421             stack[i] = merge(stack[i], other.stack[i], block);
 422         }
 423         for (int i = 0; i < lockedObjects.length; i++) {
 424             lockedObjects[i] = merge(lockedObjects[i], other.lockedObjects[i], block);
 425             assert monitorIds[i] == other.monitorIds[i];
 426         }
 427 
 428         if (sideEffects == null) {
 429             sideEffects = other.sideEffects;
 430         } else {
 431             if (other.sideEffects != null) {
 432                 sideEffects.addAll(other.sideEffects);
 433             }
 434         }
 435     }
 436 
 437     private ValueNode merge(ValueNode currentValue, ValueNode otherValue, AbstractMergeNode block) {
 438         if (currentValue == null || currentValue.isDeleted()) {
 439             return null;
 440         } else if (block.isPhiAtMerge(currentValue)) {
 441             if (otherValue == null || otherValue == TWO_SLOT_MARKER || otherValue.isDeleted() || currentValue.getStackKind() != otherValue.getStackKind()) {
 442                 // This phi must be dead anyway, add input of correct stack kind to keep the graph
 443                 // invariants.
 444                 ((PhiNode) currentValue).addInput(ConstantNode.defaultForKind(currentValue.getStackKind(), graph));
 445             } else {
 446                 ((PhiNode) currentValue).addInput(otherValue);
 447             }
 448             return currentValue;
 449         } else if (currentValue != otherValue) {
 450             if (currentValue == TWO_SLOT_MARKER || otherValue == TWO_SLOT_MARKER) {
 451                 return null;
 452             } else if (otherValue == null || otherValue.isDeleted() || currentValue.getStackKind() != otherValue.getStackKind()) {
 453                 return null;
 454             }
 455             assert !(block instanceof LoopBeginNode) : String.format("Phi functions for loop headers are create eagerly for changed locals and all stack slots: %s != %s", currentValue, otherValue);
 456             return createValuePhi(currentValue, otherValue, block);
 457         } else {
 458             return currentValue;
 459         }
 460     }
 461 
 462     private ValuePhiNode createValuePhi(ValueNode currentValue, ValueNode otherValue, AbstractMergeNode block) {
 463         ValuePhiNode phi = graph.addWithoutUnique(new ValuePhiNode(currentValue.stamp().unrestricted(), block));
 464         for (int i = 0; i < block.phiPredecessorCount(); i++) {
 465             phi.addInput(currentValue);
 466         }
 467         phi.addInput(otherValue);
 468         assert phi.valueCount() == block.phiPredecessorCount() + 1;
 469         return phi;
 470     }
 471 
 472     public void inferPhiStamps(AbstractMergeNode block) {
 473         for (int i = 0; i < localsSize(); i++) {
 474             inferPhiStamp(block, locals[i]);
 475         }
 476         for (int i = 0; i < stackSize(); i++) {
 477             inferPhiStamp(block, stack[i]);
 478         }
 479         for (int i = 0; i < lockedObjects.length; i++) {
 480             inferPhiStamp(block, lockedObjects[i]);
 481         }
 482     }
 483 
 484     private static void inferPhiStamp(AbstractMergeNode block, ValueNode node) {
 485         if (block.isPhiAtMerge(node)) {
 486             node.inferStamp();
 487         }
 488     }
 489 
 490     public void insertLoopPhis(LocalLiveness liveness, int loopId, LoopBeginNode loopBegin, boolean forcePhis, boolean stampFromValueForForcedPhis) {
 491         for (int i = 0; i < localsSize(); i++) {
 492             boolean changedInLoop = liveness.localIsChangedInLoop(loopId, i);
 493             if (forcePhis || changedInLoop) {
 494                 locals[i] = createLoopPhi(loopBegin, locals[i], stampFromValueForForcedPhis && !changedInLoop);
 495             }
 496         }
 497         for (int i = 0; i < stackSize(); i++) {
 498             stack[i] = createLoopPhi(loopBegin, stack[i], false);
 499         }
 500         for (int i = 0; i < lockedObjects.length; i++) {
 501             lockedObjects[i] = createLoopPhi(loopBegin, lockedObjects[i], false);
 502         }
 503     }
 504 
 505     public void insertLoopProxies(LoopExitNode loopExit, FrameStateBuilder loopEntryState) {
 506         DebugContext debug = graph.getDebug();
 507         for (int i = 0; i < localsSize(); i++) {
 508             ValueNode value = locals[i];
 509             if (value != null && value != TWO_SLOT_MARKER && (!loopEntryState.contains(value) || loopExit.loopBegin().isPhiAtMerge(value))) {
 510                 debug.log(" inserting proxy for %s", value);
 511                 locals[i] = ProxyNode.forValue(value, loopExit, graph);
 512             }
 513         }
 514         for (int i = 0; i < stackSize(); i++) {
 515             ValueNode value = stack[i];
 516             if (value != null && value != TWO_SLOT_MARKER && (!loopEntryState.contains(value) || loopExit.loopBegin().isPhiAtMerge(value))) {
 517                 debug.log(" inserting proxy for %s", value);
 518                 stack[i] = ProxyNode.forValue(value, loopExit, graph);
 519             }
 520         }
 521         for (int i = 0; i < lockedObjects.length; i++) {
 522             ValueNode value = lockedObjects[i];
 523             if (value != null && (!loopEntryState.contains(value) || loopExit.loopBegin().isPhiAtMerge(value))) {
 524                 debug.log(" inserting proxy for %s", value);
 525                 lockedObjects[i] = ProxyNode.forValue(value, loopExit, graph);
 526             }
 527         }
 528     }
 529 
 530     public void insertProxies(Function<ValueNode, ValueNode> proxyFunction) {
 531         DebugContext debug = graph.getDebug();
 532         for (int i = 0; i < localsSize(); i++) {
 533             ValueNode value = locals[i];
 534             if (value != null && value != TWO_SLOT_MARKER) {
 535                 debug.log(" inserting proxy for %s", value);
 536                 locals[i] = proxyFunction.apply(value);
 537             }
 538         }
 539         for (int i = 0; i < stackSize(); i++) {
 540             ValueNode value = stack[i];
 541             if (value != null && value != TWO_SLOT_MARKER) {
 542                 debug.log(" inserting proxy for %s", value);
 543                 stack[i] = proxyFunction.apply(value);
 544             }
 545         }
 546         for (int i = 0; i < lockedObjects.length; i++) {
 547             ValueNode value = lockedObjects[i];
 548             if (value != null) {
 549                 debug.log(" inserting proxy for %s", value);
 550                 lockedObjects[i] = proxyFunction.apply(value);
 551             }
 552         }
 553     }
 554 
 555     private ValueNode createLoopPhi(AbstractMergeNode block, ValueNode value, boolean stampFromValue) {
 556         if (value == null || value == TWO_SLOT_MARKER) {
 557             return value;
 558         }
 559         assert !block.isPhiAtMerge(value) : "phi function for this block already created";
 560 
 561         ValuePhiNode phi = graph.addWithoutUnique(new ValuePhiNode(stampFromValue ? value.stamp() : value.stamp().unrestricted(), block));
 562         phi.addInput(value);
 563         return phi;
 564     }
 565 
 566     /**
 567      * Adds a locked monitor to this frame state.
 568      *
 569      * @param object the object whose monitor will be locked.
 570      */
 571     public void pushLock(ValueNode object, MonitorIdNode monitorId) {
 572         assert object.isAlive() && object.getStackKind() == JavaKind.Object : "unexpected value: " + object;
 573         lockedObjects = Arrays.copyOf(lockedObjects, lockedObjects.length + 1);
 574         monitorIds = Arrays.copyOf(monitorIds, monitorIds.length + 1);
 575         lockedObjects[lockedObjects.length - 1] = object;
 576         monitorIds[monitorIds.length - 1] = monitorId;
 577         assert lockedObjects.length == monitorIds.length;
 578     }
 579 
 580     /**
 581      * Removes a locked monitor from this frame state.
 582      *
 583      * @return the object whose monitor was removed from the locks list.
 584      */
 585     public ValueNode popLock() {
 586         try {
 587             return lockedObjects[lockedObjects.length - 1];
 588         } finally {
 589             lockedObjects = lockedObjects.length == 1 ? EMPTY_ARRAY : Arrays.copyOf(lockedObjects, lockedObjects.length - 1);
 590             monitorIds = monitorIds.length == 1 ? EMPTY_MONITOR_ARRAY : Arrays.copyOf(monitorIds, monitorIds.length - 1);
 591             assert lockedObjects.length == monitorIds.length;
 592         }
 593     }
 594 
 595     public MonitorIdNode peekMonitorId() {
 596         return monitorIds[monitorIds.length - 1];
 597     }
 598 
 599     /**
 600      * @return the current lock depth
 601      */
 602     public int lockDepth(boolean includeParents) {
 603         int depth = lockedObjects.length;
 604         assert depth == monitorIds.length;
 605         if (includeParents && parser.getParent() != null) {
 606             depth += parser.getParent().frameState.lockDepth(true);
 607         }
 608         return depth;
 609     }
 610 
 611     public boolean contains(ValueNode value) {
 612         for (int i = 0; i < localsSize(); i++) {
 613             if (locals[i] == value) {
 614                 return true;
 615             }
 616         }
 617         for (int i = 0; i < stackSize(); i++) {
 618             if (stack[i] == value) {
 619                 return true;
 620             }
 621         }
 622         assert lockedObjects.length == monitorIds.length;
 623         for (int i = 0; i < lockedObjects.length; i++) {
 624             if (lockedObjects[i] == value || monitorIds[i] == value) {
 625                 return true;
 626             }
 627         }
 628         return false;
 629     }
 630 
 631     public void clearNonLiveLocals(BciBlock block, LocalLiveness liveness, boolean liveIn) {
 632         /*
 633          * (lstadler) if somebody is tempted to remove/disable this clearing code: it's possible to
 634          * remove it for normal compilations, but not for OSR compilations - otherwise dead object
 635          * slots at the OSR entry aren't cleared. it is also not enough to rely on PiNodes with
 636          * Kind.Illegal, because the conflicting branch might not have been parsed.
 637          */
 638         if (!clearNonLiveLocals) {
 639             return;
 640         }
 641         if (liveIn) {
 642             for (int i = 0; i < locals.length; i++) {
 643                 if (!liveness.localIsLiveIn(block, i)) {
 644                     assert locals[i] != TWO_SLOT_MARKER || locals[i - 1] == null : "Clearing of second slot must have cleared the first slot too";
 645                     locals[i] = null;
 646                 }
 647             }
 648         } else {
 649             for (int i = 0; i < locals.length; i++) {
 650                 if (!liveness.localIsLiveOut(block, i)) {
 651                     assert locals[i] != TWO_SLOT_MARKER || locals[i - 1] == null : "Clearing of second slot must have cleared the first slot too";
 652                     locals[i] = null;
 653                 }
 654             }
 655         }
 656     }
 657 
 658     /**
 659      * Clears all local variables.
 660      */
 661     public void clearLocals() {
 662         for (int i = 0; i < locals.length; i++) {
 663             locals[i] = null;
 664         }
 665     }
 666 
 667     /**
 668      * @see BytecodeFrame#rethrowException
 669      */
 670     public boolean rethrowException() {
 671         return rethrowException;
 672     }
 673 
 674     /**
 675      * @see BytecodeFrame#rethrowException
 676      */
 677     public void setRethrowException(boolean b) {
 678         rethrowException = b;
 679     }
 680 
 681     /**
 682      * Returns the size of the local variables.
 683      *
 684      * @return the size of the local variables
 685      */
 686     public int localsSize() {
 687         return locals.length;
 688     }
 689 
 690     /**
 691      * Gets the current size (height) of the stack.
 692      */
 693     public int stackSize() {
 694         return stackSize;
 695     }
 696 
 697     private boolean verifyKind(JavaKind slotKind, ValueNode x) {
 698         assert x != null;
 699         assert x != TWO_SLOT_MARKER;
 700         assert slotKind.getSlotCount() > 0;
 701 
 702         if (canVerifyKind) {
 703             assert x.getStackKind() == slotKind.getStackKind();
 704         }
 705         return true;
 706     }
 707 
 708     /**
 709      * Loads the local variable at the specified index, checking that the returned value is non-null
 710      * and that two-stack values are properly handled.
 711      *
 712      * @param i the index of the local variable to load
 713      * @param slotKind the kind of the local variable from the point of view of the bytecodes
 714      * @return the instruction that produced the specified local
 715      */
 716     public ValueNode loadLocal(int i, JavaKind slotKind) {
 717         ValueNode x = locals[i];
 718         assert verifyKind(slotKind, x);
 719         assert slotKind.needsTwoSlots() ? locals[i + 1] == TWO_SLOT_MARKER : (i == locals.length - 1 || locals[i + 1] != TWO_SLOT_MARKER);
 720         return x;
 721     }
 722 
 723     /**
 724      * Stores a given local variable at the specified index. If the value occupies two slots, then
 725      * the next local variable index is also overwritten.
 726      *
 727      * @param i the index at which to store
 728      * @param slotKind the kind of the local variable from the point of view of the bytecodes
 729      * @param x the instruction which produces the value for the local
 730      */
 731     public void storeLocal(int i, JavaKind slotKind, ValueNode x) {
 732         assert verifyKind(slotKind, x);
 733 
 734         if (locals[i] == TWO_SLOT_MARKER) {
 735             /* Writing the second slot of a two-slot value invalidates the first slot. */
 736             locals[i - 1] = null;
 737         }
 738         locals[i] = x;
 739         if (slotKind.needsTwoSlots()) {
 740             /* Writing a two-slot value: mark the second slot. */
 741             locals[i + 1] = TWO_SLOT_MARKER;
 742         } else if (i < locals.length - 1 && locals[i + 1] == TWO_SLOT_MARKER) {
 743             /*
 744              * Writing a one-slot value to an index previously occupied by a two-slot value: clear
 745              * the old marker of the second slot.
 746              */
 747             locals[i + 1] = null;
 748         }
 749     }
 750 
 751     /**
 752      * Pushes an instruction onto the stack with the expected type.
 753      *
 754      * @param slotKind the kind of the stack element from the point of view of the bytecodes
 755      * @param x the instruction to push onto the stack
 756      */
 757     public void push(JavaKind slotKind, ValueNode x) {
 758         assert verifyKind(slotKind, x);
 759 
 760         xpush(x);
 761         if (slotKind.needsTwoSlots()) {
 762             xpush(TWO_SLOT_MARKER);
 763         }
 764     }
 765 
 766     public void pushReturn(JavaKind slotKind, ValueNode x) {
 767         if (slotKind != JavaKind.Void) {
 768             push(slotKind, x);
 769         }
 770     }
 771 
 772     /**
 773      * Pops an instruction off the stack with the expected type.
 774      *
 775      * @param slotKind the kind of the stack element from the point of view of the bytecodes
 776      * @return the instruction on the top of the stack
 777      */
 778     public ValueNode pop(JavaKind slotKind) {
 779         if (slotKind.needsTwoSlots()) {
 780             ValueNode s = xpop();
 781             assert s == TWO_SLOT_MARKER;
 782         }
 783         ValueNode x = xpop();
 784         assert verifyKind(slotKind, x);
 785         return x;
 786     }
 787 
 788     private void xpush(ValueNode x) {
 789         assert x != null;
 790         stack[stackSize++] = x;
 791     }
 792 
 793     private ValueNode xpop() {
 794         ValueNode result = stack[--stackSize];
 795         assert result != null;
 796         return result;
 797     }
 798 
 799     private ValueNode xpeek() {
 800         ValueNode result = stack[stackSize - 1];
 801         assert result != null;
 802         return result;
 803     }
 804 
 805     /**
 806      * Pop the specified number of slots off of this stack and return them as an array of
 807      * instructions.
 808      *
 809      * @return an array containing the arguments off of the stack
 810      */
 811     public ValueNode[] popArguments(int argSize) {
 812         ValueNode[] result = allocateArray(argSize);
 813         for (int i = argSize - 1; i >= 0; i--) {
 814             ValueNode x = xpop();
 815             if (x == TWO_SLOT_MARKER) {
 816                 /* Ignore second slot of two-slot value. */
 817                 x = xpop();
 818             }
 819             assert x != null && x != TWO_SLOT_MARKER;
 820             result[i] = x;
 821         }
 822         return result;
 823     }
 824 
 825     /**
 826      * Clears all values on this stack.
 827      */
 828     public void clearStack() {
 829         stackSize = 0;
 830     }
 831 
 832     /**
 833      * Performs a raw stack operation as defined in the Java bytecode specification.
 834      *
 835      * @param opcode The Java bytecode.
 836      */
 837     public void stackOp(int opcode) {
 838         switch (opcode) {
 839             case POP: {
 840                 ValueNode w1 = xpop();
 841                 assert w1 != TWO_SLOT_MARKER;
 842                 break;
 843             }
 844             case POP2: {
 845                 xpop();
 846                 ValueNode w2 = xpop();
 847                 assert w2 != TWO_SLOT_MARKER;
 848                 break;
 849             }
 850             case DUP: {
 851                 ValueNode w1 = xpeek();
 852                 assert w1 != TWO_SLOT_MARKER;
 853                 xpush(w1);
 854                 break;
 855             }
 856             case DUP_X1: {
 857                 ValueNode w1 = xpop();
 858                 ValueNode w2 = xpop();
 859                 assert w1 != TWO_SLOT_MARKER;
 860                 xpush(w1);
 861                 xpush(w2);
 862                 xpush(w1);
 863                 break;
 864             }
 865             case DUP_X2: {
 866                 ValueNode w1 = xpop();
 867                 ValueNode w2 = xpop();
 868                 ValueNode w3 = xpop();
 869                 assert w1 != TWO_SLOT_MARKER;
 870                 xpush(w1);
 871                 xpush(w3);
 872                 xpush(w2);
 873                 xpush(w1);
 874                 break;
 875             }
 876             case DUP2: {
 877                 ValueNode w1 = xpop();
 878                 ValueNode w2 = xpop();
 879                 xpush(w2);
 880                 xpush(w1);
 881                 xpush(w2);
 882                 xpush(w1);
 883                 break;
 884             }
 885             case DUP2_X1: {
 886                 ValueNode w1 = xpop();
 887                 ValueNode w2 = xpop();
 888                 ValueNode w3 = xpop();
 889                 xpush(w2);
 890                 xpush(w1);
 891                 xpush(w3);
 892                 xpush(w2);
 893                 xpush(w1);
 894                 break;
 895             }
 896             case DUP2_X2: {
 897                 ValueNode w1 = xpop();
 898                 ValueNode w2 = xpop();
 899                 ValueNode w3 = xpop();
 900                 ValueNode w4 = xpop();
 901                 xpush(w2);
 902                 xpush(w1);
 903                 xpush(w4);
 904                 xpush(w3);
 905                 xpush(w2);
 906                 xpush(w1);
 907                 break;
 908             }
 909             case SWAP: {
 910                 ValueNode w1 = xpop();
 911                 ValueNode w2 = xpop();
 912                 assert w1 != TWO_SLOT_MARKER;
 913                 assert w2 != TWO_SLOT_MARKER;
 914                 xpush(w1);
 915                 xpush(w2);
 916                 break;
 917             }
 918             default:
 919                 throw shouldNotReachHere();
 920         }
 921     }
 922 
 923     @Override
 924     public int hashCode() {
 925         int result = hashCode(locals, locals.length);
 926         result *= 13;
 927         result += hashCode(stack, this.stackSize);
 928         return result;
 929     }
 930 
 931     private static int hashCode(Object[] a, int length) {
 932         int result = 1;
 933         for (int i = 0; i < length; ++i) {
 934             Object element = a[i];
 935             result = 31 * result + (element == null ? 0 : System.identityHashCode(element));
 936         }
 937         return result;
 938     }
 939 
 940     private static boolean equals(ValueNode[] a, ValueNode[] b, int length) {
 941         for (int i = 0; i < length; ++i) {
 942             if (a[i] != b[i]) {
 943                 return false;
 944             }
 945         }
 946         return true;
 947     }
 948 
 949     @Override
 950     public boolean equals(Object otherObject) {
 951         if (otherObject instanceof FrameStateBuilder) {
 952             FrameStateBuilder other = (FrameStateBuilder) otherObject;
 953             if (!other.code.equals(code)) {
 954                 return false;
 955             }
 956             if (other.stackSize != stackSize) {
 957                 return false;
 958             }
 959             if (other.parser != parser) {
 960                 return false;
 961             }
 962             if (other.tool != tool) {
 963                 return false;
 964             }
 965             if (other.rethrowException != rethrowException) {
 966                 return false;
 967             }
 968             if (other.graph != graph) {
 969                 return false;
 970             }
 971             if (other.locals.length != locals.length) {
 972                 return false;
 973             }
 974             return equals(other.locals, locals, locals.length) && equals(other.stack, stack, stackSize) && equals(other.lockedObjects, lockedObjects, lockedObjects.length) &&
 975                             equals(other.monitorIds, monitorIds, monitorIds.length);
 976         }
 977         return false;
 978     }
 979 
 980     @Override
 981     public boolean isAfterSideEffect() {
 982         return sideEffects != null;
 983     }
 984 
 985     @Override
 986     public Iterable<StateSplit> sideEffects() {
 987         return sideEffects;
 988     }
 989 
 990     @Override
 991     public void addSideEffect(StateSplit sideEffect) {
 992         assert sideEffect != null;
 993         assert sideEffect.hasSideEffect();
 994         if (sideEffects == null) {
 995             sideEffects = new ArrayList<>(4);
 996         }
 997         sideEffects.add(sideEffect);
 998     }
 999 
1000     public void traceState() {
1001         DebugContext debug = graph.getDebug();
1002         debug.log("|   state [nr locals = %d, stack depth = %d, method = %s]", localsSize(), stackSize(), getMethod());
1003         for (int i = 0; i < localsSize(); ++i) {
1004             ValueNode value = locals[i];
1005             debug.log("|   local[%d] = %-8s : %s", i, value == null ? "bogus" : value == TWO_SLOT_MARKER ? "second" : value.getStackKind().getJavaName(), value);
1006         }
1007         for (int i = 0; i < stackSize(); ++i) {
1008             ValueNode value = stack[i];
1009             debug.log("|   stack[%d] = %-8s : %s", i, value == null ? "bogus" : value == TWO_SLOT_MARKER ? "second" : value.getStackKind().getJavaName(), value);
1010         }
1011     }
1012 }