1 /*
   2  * Copyright (c) 2011, 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.hotspot.phases;
  24 
  25 import static jdk.vm.ci.meta.SpeculationLog.SpeculationReason;
  26 import static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Required;
  27 
  28 import jdk.vm.ci.meta.DeoptimizationAction;
  29 import jdk.vm.ci.meta.DeoptimizationReason;
  30 import jdk.vm.ci.meta.JavaConstant;
  31 import jdk.vm.ci.meta.JavaKind;
  32 import org.graalvm.compiler.core.common.PermanentBailoutException;
  33 import org.graalvm.compiler.core.common.cfg.Loop;
  34 import org.graalvm.compiler.core.common.type.ObjectStamp;
  35 import org.graalvm.compiler.core.common.type.Stamp;
  36 import org.graalvm.compiler.debug.CounterKey;
  37 import org.graalvm.compiler.debug.DebugContext;
  38 import org.graalvm.compiler.debug.GraalError;
  39 import org.graalvm.compiler.graph.Node;
  40 import org.graalvm.compiler.graph.iterators.NodeIterable;
  41 import org.graalvm.compiler.loop.LoopsData;
  42 import org.graalvm.compiler.loop.phases.LoopTransformations;
  43 import org.graalvm.compiler.nodeinfo.InputType;
  44 import org.graalvm.compiler.nodeinfo.Verbosity;
  45 import org.graalvm.compiler.nodes.AbstractBeginNode;

  46 import org.graalvm.compiler.nodes.EntryMarkerNode;
  47 import org.graalvm.compiler.nodes.EntryProxyNode;
  48 import org.graalvm.compiler.nodes.FixedGuardNode;
  49 import org.graalvm.compiler.nodes.FixedNode;
  50 import org.graalvm.compiler.nodes.FrameState;
  51 import org.graalvm.compiler.nodes.LogicNode;
  52 import org.graalvm.compiler.nodes.LoopBeginNode;
  53 import org.graalvm.compiler.nodes.ParameterNode;
  54 import org.graalvm.compiler.nodes.PiNode;
  55 import org.graalvm.compiler.nodes.StartNode;
  56 import org.graalvm.compiler.nodes.StructuredGraph;
  57 import org.graalvm.compiler.nodes.ValueNode;
  58 import org.graalvm.compiler.nodes.cfg.Block;
  59 import org.graalvm.compiler.nodes.extended.OSRLocalNode;
  60 import org.graalvm.compiler.nodes.extended.OSRLockNode;
  61 import org.graalvm.compiler.nodes.extended.OSRMonitorEnterNode;
  62 import org.graalvm.compiler.nodes.extended.OSRStartNode;
  63 import org.graalvm.compiler.nodes.java.AccessMonitorNode;
  64 import org.graalvm.compiler.nodes.java.InstanceOfNode;
  65 import org.graalvm.compiler.nodes.java.MonitorEnterNode;
  66 import org.graalvm.compiler.nodes.java.MonitorExitNode;
  67 import org.graalvm.compiler.nodes.java.MonitorIdNode;
  68 import org.graalvm.compiler.nodes.util.GraphUtil;
  69 import org.graalvm.compiler.options.Option;
  70 import org.graalvm.compiler.options.OptionKey;
  71 import org.graalvm.compiler.options.OptionType;
  72 import org.graalvm.compiler.options.OptionValues;
  73 import org.graalvm.compiler.phases.Phase;
  74 import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase;
  75 
  76 import jdk.vm.ci.runtime.JVMCICompiler;
  77 
  78 public class OnStackReplacementPhase extends Phase {
  79 
  80     public static class Options {
  81         // @formatter:off
  82         @Option(help = "Deoptimize OSR compiled code when the OSR entry loop is finished " +
  83                        "if there is no mature profile available for the rest of the method.", type = OptionType.Debug)
  84         public static final OptionKey<Boolean> DeoptAfterOSR = new OptionKey<>(true);
  85         @Option(help = "Support OSR compilations with locks. If DeoptAfterOSR is true we can per definition not have " +
  86                        "unbalaced enter/extis mappings. If DeoptAfterOSR is false insert artificial monitor enters after " +
  87                        "the OSRStart to have balanced enter/exits in the graph.", type = OptionType.Debug)
  88         public static final OptionKey<Boolean> SupportOSRWithLocks = new OptionKey<>(true);
  89         // @formatter:on
  90     }
  91 
  92     private static final CounterKey OsrWithLocksCount = DebugContext.counter("OSRWithLocks");
  93 
  94     private static boolean supportOSRWithLocks(OptionValues options) {
  95         return Options.SupportOSRWithLocks.getValue(options);
  96     }
  97 
  98     @Override
  99     protected void run(StructuredGraph graph) {
 100         DebugContext debug = graph.getDebug();
 101         if (graph.getEntryBCI() == JVMCICompiler.INVOCATION_ENTRY_BCI) {
 102             // This happens during inlining in a OSR method, because the same phase plan will be
 103             // used.
 104             assert graph.getNodes(EntryMarkerNode.TYPE).isEmpty();
 105             return;
 106         }
 107         debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement initial at bci %d", graph.getEntryBCI());
 108 
 109         EntryMarkerNode osr;
 110         int maxIterations = -1;
 111         int iterations = 0;
 112 
 113         final EntryMarkerNode originalOSRNode = getEntryMarker(graph);
 114         final LoopBeginNode originalOSRLoop = osrLoop(originalOSRNode);
 115         final boolean currentOSRWithLocks = osrWithLocks(originalOSRNode);
 116 
 117         if (originalOSRLoop == null) {
 118             /*
 119              * OSR with Locks: We do not have an OSR loop for the original OSR bci. Therefore we
 120              * cannot decide where to deopt and which framestate will be used. In the worst case the
 121              * framestate of the OSR entry would be used.
 122              */
 123             throw new PermanentBailoutException("OSR compilation without OSR entry loop.");
 124         }
 125 
 126         if (!supportOSRWithLocks(graph.getOptions()) && currentOSRWithLocks) {
 127             throw new PermanentBailoutException("OSR with locks disabled.");
 128         }
 129 
 130         do {
 131             osr = getEntryMarker(graph);
 132             LoopsData loops = new LoopsData(graph);
 133             // Find the loop that contains the EntryMarker
 134             Loop<Block> l = loops.getCFG().getNodeToBlock().get(osr).getLoop();
 135             if (l == null) {
 136                 break;
 137             }
 138 
 139             iterations++;
 140             if (maxIterations == -1) {
 141                 maxIterations = l.getDepth();
 142             } else if (iterations > maxIterations) {
 143                 throw GraalError.shouldNotReachHere();
 144             }
 145             // Peel the outermost loop first
 146             while (l.getParent() != null) {
 147                 l = l.getParent();
 148             }
 149 
 150             LoopTransformations.peel(loops.loop(l));
 151             osr.replaceAtUsages(InputType.Guard, AbstractBeginNode.prevBegin((FixedNode) osr.predecessor()));
 152             for (Node usage : osr.usages().snapshot()) {
 153                 EntryProxyNode proxy = (EntryProxyNode) usage;
 154                 proxy.replaceAndDelete(proxy.value());
 155             }
 156             GraphUtil.removeFixedWithUnusedInputs(osr);
 157             debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement loop peeling result");
 158         } while (true);
 159 
 160         FrameState osrState = osr.stateAfter();
 161         osr.setStateAfter(null);
 162         OSRStartNode osrStart = graph.add(new OSRStartNode());
 163         StartNode start = graph.start();
 164         FixedNode next = osr.next();
 165         osr.setNext(null);
 166         osrStart.setNext(next);
 167         graph.setStart(osrStart);
 168         osrStart.setStateAfter(osrState);
 169 
 170         debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement after setting OSR start");
 171         final int localsSize = osrState.localsSize();
 172         final int locksSize = osrState.locksSize();
 173 
 174         for (int i = 0; i < localsSize + locksSize; i++) {
 175             ValueNode value = null;
 176             if (i >= localsSize) {
 177                 value = osrState.lockAt(i - localsSize);
 178             } else {
 179                 value = osrState.localAt(i);
 180             }
 181             if (value instanceof EntryProxyNode) {
 182                 EntryProxyNode proxy = (EntryProxyNode) value;
 183                 /*
 184                  * We need to drop the stamp since the types we see during OSR may be too precise
 185                  * (if a branch was not parsed for example). In cases when this is possible, we
 186                  * insert a guard and narrow the OSRLocal stamp at its usages.
 187                  */
 188                 Stamp narrowedStamp = proxy.value().stamp();
 189                 Stamp unrestrictedStamp = proxy.stamp().unrestricted();
 190                 ValueNode osrLocal;
 191                 if (i >= localsSize) {
 192                     osrLocal = graph.addOrUnique(new OSRLockNode(i - localsSize, unrestrictedStamp));
 193                 } else {
 194                     osrLocal = graph.addOrUnique(new OSRLocalNode(i, unrestrictedStamp));
 195                 }
 196                 // Speculate on the OSRLocal stamps that could be more precise.
 197                 OSRLocalSpeculationReason reason = new OSRLocalSpeculationReason(osrState.bci, narrowedStamp, i);
 198                 if (graph.getSpeculationLog().maySpeculate(reason) && osrLocal instanceof OSRLocalNode && value.getStackKind().equals(JavaKind.Object) && !narrowedStamp.isUnrestricted()) {
 199                     // Add guard.
 200                     LogicNode check = graph.addOrUniqueWithInputs(InstanceOfNode.createHelper((ObjectStamp) narrowedStamp, osrLocal, null, null));
 201                     JavaConstant constant = graph.getSpeculationLog().speculate(reason);
 202                     FixedGuardNode guard = graph.add(new FixedGuardNode(check, DeoptimizationReason.OptimizedTypeCheckViolated, DeoptimizationAction.InvalidateRecompile, constant, false));
 203                     graph.addAfterFixed(osrStart, guard);
 204 
 205                     // Replace with a more specific type at usages.
 206                     // We know that we are at the root,
 207                     // so we need to replace the proxy in the state.
 208                     proxy.replaceAtMatchingUsages(osrLocal, n -> n == osrState);
 209                     osrLocal = graph.addOrUnique(new PiNode(osrLocal, narrowedStamp, guard));
 210                 }
 211                 proxy.replaceAndDelete(osrLocal);
 212             } else {
 213                 assert value == null || value instanceof OSRLocalNode;
 214             }
 215         }
 216 
 217         osr.replaceAtUsages(InputType.Guard, osrStart);
 218         debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement after replacing entry proxies");
 219         GraphUtil.killCFG(start);
 220         debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement result");
 221         new DeadCodeEliminationPhase(Required).apply(graph);
 222 
 223         if (currentOSRWithLocks) {
 224             OsrWithLocksCount.increment(debug);
 225             for (int i = osrState.monitorIdCount() - 1; i >= 0; --i) {
 226                 MonitorIdNode id = osrState.monitorIdAt(i);
 227                 ValueNode lockedObject = osrState.lockAt(i);
 228                 OSRMonitorEnterNode osrMonitorEnter = graph.add(new OSRMonitorEnterNode(lockedObject, id));
 229                 for (Node usage : id.usages()) {
 230                     if (usage instanceof AccessMonitorNode) {
 231                         AccessMonitorNode access = (AccessMonitorNode) usage;
 232                         access.setObject(lockedObject);
 233                     }
 234                 }
 235                 FixedNode oldNext = osrStart.next();
 236                 oldNext.replaceAtPredecessor(null);
 237                 osrMonitorEnter.setNext(oldNext);
 238                 osrStart.setNext(osrMonitorEnter);
 239             }
 240             debug.dump(DebugContext.DETAILED_LEVEL, graph, "After inserting OSR monitor enters");
 241             /*
 242              * Ensure balanced monitorenter - monitorexit
 243              *
 244              * Ensure that there is no monitor exit without a monitor enter in the graph. If there
 245              * is one this can only be done by bytecode as we have the monitor enter before the OSR
 246              * loop but the exit in a path of the loop that must be under a condition, else it will
 247              * throw an IllegalStateException anyway in the 2.iteration
 248              */
 249             for (MonitorExitNode exit : graph.getNodes(MonitorExitNode.TYPE)) {
 250                 MonitorIdNode id = exit.getMonitorId();
 251                 if (id.usages().filter(MonitorEnterNode.class).count() != 1) {
 252                     throw new PermanentBailoutException("Unbalanced monitor enter-exit in OSR compilation with locks. Object is locked before the loop but released inside the loop.");
 253                 }
 254             }
 255         }
 256         debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement result");
 257         new DeadCodeEliminationPhase(Required).apply(graph);
 258         /*
 259          * There must not be any parameter nodes left after OSR compilation.
 260          */
 261         assert graph.getNodes(ParameterNode.TYPE).count() == 0 : "OSR Compilation contains references to parameters.";
 262     }
 263 
 264     private static EntryMarkerNode getEntryMarker(StructuredGraph graph) {
 265         NodeIterable<EntryMarkerNode> osrNodes = graph.getNodes(EntryMarkerNode.TYPE);
 266         EntryMarkerNode osr = osrNodes.first();
 267         if (osr == null) {
 268             throw new PermanentBailoutException("No OnStackReplacementNode generated");
 269         }
 270         if (osrNodes.count() > 1) {
 271             throw new GraalError("Multiple OnStackReplacementNodes generated");
 272         }
 273         if (osr.stateAfter().stackSize() != 0) {
 274             throw new PermanentBailoutException("OSR with stack entries not supported: %s", osr.stateAfter().toString(Verbosity.Debugger));
 275         }
 276         return osr;
 277     }
 278 
 279     private static LoopBeginNode osrLoop(EntryMarkerNode osr) {
 280         // Check that there is an OSR loop for the OSR begin
 281         LoopsData loops = new LoopsData(osr.graph());
 282         Loop<Block> l = loops.getCFG().getNodeToBlock().get(osr).getLoop();
 283         if (l == null) {
 284             return null;
 285         }
 286         return (LoopBeginNode) l.getHeader().getBeginNode();
 287     }
 288 
 289     private static boolean osrWithLocks(EntryMarkerNode osr) {
 290         return osr.stateAfter().locksSize() != 0;
 291     }
 292 
 293     @Override
 294     public float codeSizeIncrease() {
 295         return 5.0f;
 296     }
 297 
 298     private static class OSRLocalSpeculationReason implements SpeculationReason {
 299         private int bci;
 300         private Stamp speculatedStamp;
 301         private int localIndex;
 302 
 303         OSRLocalSpeculationReason(int bci, Stamp speculatedStamp, int localIndex) {
 304             this.bci = bci;
 305             this.speculatedStamp = speculatedStamp;
 306             this.localIndex = localIndex;
 307         }
 308 
 309         @Override
 310         public boolean equals(Object obj) {
 311             if (obj instanceof OSRLocalSpeculationReason) {
 312                 OSRLocalSpeculationReason that = (OSRLocalSpeculationReason) obj;
 313                 return this.bci == that.bci && this.speculatedStamp.equals(that.speculatedStamp) && this.localIndex == that.localIndex;
 314             }
 315             return false;
 316         }
 317 
 318         @Override
 319         public int hashCode() {
 320             return (bci << 16) ^ speculatedStamp.hashCode() ^ localIndex;
 321         }
 322     }
 323 }
--- EOF ---