1 /*
   2  * Copyright (c) 2016, 2017, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.graalvm.compiler.hotspot.phases.aot;
  24 
  25 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.strictlyDominates;
  26 import static org.graalvm.compiler.hotspot.nodes.aot.LoadMethodCountersNode.getLoadMethodCountersNodes;
  27 import static org.graalvm.compiler.nodes.ConstantNode.getConstantNodes;
  28 
  29 import java.util.HashSet;
  30 import java.util.List;
  31 
  32 import org.graalvm.compiler.core.common.cfg.BlockMap;
  33 import org.graalvm.compiler.core.common.type.ObjectStamp;
  34 import org.graalvm.compiler.core.common.type.Stamp;
  35 import org.graalvm.compiler.core.common.type.StampFactory;
  36 import org.graalvm.compiler.debug.GraalError;
  37 import org.graalvm.compiler.graph.Node;
  38 import org.graalvm.compiler.graph.NodeMap;
  39 import org.graalvm.compiler.hotspot.meta.HotSpotConstantLoadAction;
  40 import org.graalvm.compiler.hotspot.nodes.aot.InitializeKlassNode;
  41 import org.graalvm.compiler.hotspot.nodes.aot.LoadConstantIndirectlyFixedNode;
  42 import org.graalvm.compiler.hotspot.nodes.aot.LoadConstantIndirectlyNode;
  43 import org.graalvm.compiler.hotspot.nodes.aot.LoadMethodCountersNode;
  44 import org.graalvm.compiler.hotspot.nodes.aot.ResolveConstantNode;
  45 import org.graalvm.compiler.hotspot.nodes.aot.ResolveDynamicConstantNode;
  46 import org.graalvm.compiler.hotspot.nodes.aot.ResolveMethodAndLoadCountersNode;
  47 import org.graalvm.compiler.nodes.AbstractBeginNode;
  48 import org.graalvm.compiler.nodes.AbstractMergeNode;
  49 import org.graalvm.compiler.nodes.ConstantNode;
  50 import org.graalvm.compiler.nodes.FixedNode;
  51 import org.graalvm.compiler.nodes.FixedWithNextNode;
  52 import org.graalvm.compiler.nodes.FrameState;
  53 import org.graalvm.compiler.nodes.LoopBeginNode;
  54 import org.graalvm.compiler.nodes.LoopExitNode;
  55 import org.graalvm.compiler.nodes.StateSplit;
  56 import org.graalvm.compiler.nodes.StructuredGraph;
  57 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
  58 import org.graalvm.compiler.nodes.ValueNode;
  59 import org.graalvm.compiler.nodes.calc.FloatingNode;
  60 import org.graalvm.compiler.nodes.cfg.Block;
  61 import org.graalvm.compiler.phases.BasePhase;
  62 import org.graalvm.compiler.phases.graph.ReentrantNodeIterator;
  63 import org.graalvm.compiler.phases.graph.ReentrantNodeIterator.NodeIteratorClosure;
  64 import org.graalvm.compiler.phases.schedule.SchedulePhase;
  65 import org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy;
  66 import org.graalvm.compiler.phases.tiers.PhaseContext;
  67 import org.graalvm.util.EconomicMap;
  68 
  69 import jdk.vm.ci.code.BytecodeFrame;
  70 import jdk.vm.ci.hotspot.HotSpotMetaspaceConstant;
  71 import jdk.vm.ci.hotspot.HotSpotObjectConstant;
  72 import jdk.vm.ci.hotspot.HotSpotResolvedJavaType;
  73 import jdk.vm.ci.hotspot.HotSpotResolvedObjectType;
  74 import jdk.vm.ci.meta.Constant;
  75 import jdk.vm.ci.meta.ConstantReflectionProvider;
  76 import jdk.vm.ci.meta.ResolvedJavaType;
  77 
  78 public class ReplaceConstantNodesPhase extends BasePhase<PhaseContext> {
  79 
  80     private static final HashSet<Class<?>> builtIns = new HashSet<>();
  81     private final boolean verifyFingerprints;
  82 
  83     static {
  84         builtIns.add(Boolean.class);
  85 
  86         Class<?> characterCacheClass = Character.class.getDeclaredClasses()[0];
  87         assert "java.lang.Character$CharacterCache".equals(characterCacheClass.getName());
  88         builtIns.add(characterCacheClass);
  89 
  90         Class<?> byteCacheClass = Byte.class.getDeclaredClasses()[0];
  91         assert "java.lang.Byte$ByteCache".equals(byteCacheClass.getName());
  92         builtIns.add(byteCacheClass);
  93 
  94         Class<?> shortCacheClass = Short.class.getDeclaredClasses()[0];
  95         assert "java.lang.Short$ShortCache".equals(shortCacheClass.getName());
  96         builtIns.add(shortCacheClass);
  97 
  98         Class<?> integerCacheClass = Integer.class.getDeclaredClasses()[0];
  99         assert "java.lang.Integer$IntegerCache".equals(integerCacheClass.getName());
 100         builtIns.add(integerCacheClass);
 101 
 102         Class<?> longCacheClass = Long.class.getDeclaredClasses()[0];
 103         assert "java.lang.Long$LongCache".equals(longCacheClass.getName());
 104         builtIns.add(longCacheClass);
 105     }
 106 
 107     private static boolean isReplacementNode(Node n) {
 108         // @formatter:off
 109         return n instanceof LoadConstantIndirectlyNode      ||
 110                n instanceof LoadConstantIndirectlyFixedNode ||
 111                n instanceof ResolveDynamicConstantNode      ||
 112                n instanceof ResolveConstantNode             ||
 113                n instanceof InitializeKlassNode;
 114         // @formatter:on
 115     }
 116 
 117     private static boolean anyUsagesNeedReplacement(ConstantNode node) {
 118         return node.usages().filter(n -> !isReplacementNode(n)).isNotEmpty();
 119     }
 120 
 121     private static boolean anyUsagesNeedReplacement(LoadMethodCountersNode node) {
 122         return node.usages().filter(n -> !(n instanceof ResolveMethodAndLoadCountersNode)).isNotEmpty();
 123     }
 124 
 125     private static boolean checkForBadFingerprint(HotSpotResolvedJavaType type) {
 126         if (type.isArray()) {
 127             if (type.getElementalType().isPrimitive()) {
 128                 return false;
 129             }
 130             return ((HotSpotResolvedObjectType) (type.getElementalType())).getFingerprint() == 0;
 131         }
 132         return ((HotSpotResolvedObjectType) type).getFingerprint() == 0;
 133     }
 134 
 135     /**
 136      * Insert the replacement node into the graph. We may need to insert it into a place different
 137      * than the original {@link FloatingNode} since we need to make sure that replacement will have
 138      * a valid state assigned.
 139      *
 140      * @param graph
 141      * @param stateMapper
 142      * @param node
 143      * @param replacement
 144      */
 145     private static void insertReplacement(StructuredGraph graph, FrameStateMapperClosure stateMapper, FloatingNode node, FixedWithNextNode replacement) {
 146         FixedWithNextNode insertionPoint = findInsertionPoint(graph, stateMapper, node);
 147         graph.addAfterFixed(insertionPoint, replacement);
 148         stateMapper.addState(replacement, stateMapper.getState(insertionPoint));
 149     }
 150 
 151     /**
 152      * Find a good place to insert a stateful fixed node that is above the given node. A good
 153      * insertion point should have a valid FrameState reaching it.
 154      *
 155      * @param graph
 156      * @param stateMapper
 157      * @param node start search from this node up
 158      * @return an insertion point
 159      */
 160     private static FixedWithNextNode findInsertionPoint(StructuredGraph graph, FrameStateMapperClosure stateMapper, FloatingNode node) {
 161         FixedWithNextNode fixed = findFixedBeforeFloating(graph, node);
 162         FixedWithNextNode result = findFixedWithValidState(graph, stateMapper, fixed);
 163         return result;
 164     }
 165 
 166     /**
 167      * Find the first {@link FixedWithNextNode} that is currently scheduled before the given
 168      * floating node.
 169      *
 170      * @param graph
 171      * @param node start search from this node up
 172      * @return the first {@link FixedWithNextNode}
 173      */
 174     private static FixedWithNextNode findFixedBeforeFloating(StructuredGraph graph, FloatingNode node) {
 175         ScheduleResult schedule = graph.getLastSchedule();
 176         NodeMap<Block> nodeToBlock = schedule.getNodeToBlockMap();
 177         Block block = nodeToBlock.get(node);
 178         BlockMap<List<Node>> blockToNodes = schedule.getBlockToNodesMap();
 179         FixedWithNextNode result = null;
 180         for (Node n : blockToNodes.get(block)) {
 181             if (n.equals(node)) {
 182                 break;
 183             }
 184             if (n instanceof FixedWithNextNode) {
 185                 result = (FixedWithNextNode) n;
 186             }
 187         }
 188         assert result != null;
 189         return result;
 190     }
 191 
 192     /**
 193      * Find first dominating {@link FixedWithNextNode} that has a valid state reaching it starting
 194      * from the given node.
 195      *
 196      * @param graph
 197      * @param stateMapper
 198      * @param node
 199      * @return {@link FixedWithNextNode} that we can use as an insertion point
 200      */
 201     private static FixedWithNextNode findFixedWithValidState(StructuredGraph graph, FrameStateMapperClosure stateMapper, FixedWithNextNode node) {
 202         ScheduleResult schedule = graph.getLastSchedule();
 203         NodeMap<Block> nodeToBlock = schedule.getNodeToBlockMap();
 204         Block block = nodeToBlock.get(node);
 205 
 206         Node n = node;
 207         do {
 208             if (isFixedWithValidState(stateMapper, n)) {
 209                 return (FixedWithNextNode) n;
 210             }
 211             while (n != block.getBeginNode()) {
 212                 n = n.predecessor();
 213                 if (isFixedWithValidState(stateMapper, n)) {
 214                     return (FixedWithNextNode) n;
 215                 }
 216             }
 217             block = block.getDominator();
 218             if (block != null) {
 219                 n = block.getEndNode();
 220             }
 221         } while (block != null);
 222 
 223         return graph.start();
 224     }
 225 
 226     private static boolean isFixedWithValidState(FrameStateMapperClosure stateMapper, Node n) {
 227         if (n instanceof FixedWithNextNode) {
 228             FixedWithNextNode fixed = (FixedWithNextNode) n;
 229             assert stateMapper.getState(fixed) != null;
 230             if (!BytecodeFrame.isPlaceholderBci(stateMapper.getState(fixed).bci)) {
 231                 return true;
 232             }
 233         }
 234         return false;
 235     }
 236 
 237     /**
 238      * Compute frame states for all fixed nodes in the graph.
 239      */
 240     private static class FrameStateMapperClosure extends NodeIteratorClosure<FrameState> {
 241         private NodeMap<FrameState> reachingStates;
 242 
 243         @Override
 244         protected FrameState processNode(FixedNode node, FrameState previousState) {
 245             FrameState currentState = previousState;
 246             if (node instanceof StateSplit) {
 247                 StateSplit stateSplit = (StateSplit) node;
 248                 FrameState stateAfter = stateSplit.stateAfter();
 249                 if (stateAfter != null) {
 250                     currentState = stateAfter;
 251                 }
 252             }
 253             reachingStates.put(node, currentState);
 254             return currentState;
 255         }
 256 
 257         @Override
 258         protected FrameState merge(AbstractMergeNode merge, List<FrameState> states) {
 259             FrameState singleFrameState = singleFrameState(states);
 260             FrameState currentState = singleFrameState == null ? merge.stateAfter() : singleFrameState;
 261             reachingStates.put(merge, currentState);
 262             return currentState;
 263         }
 264 
 265         @Override
 266         protected FrameState afterSplit(AbstractBeginNode node, FrameState oldState) {
 267             return oldState;
 268         }
 269 
 270         @Override
 271         protected EconomicMap<LoopExitNode, FrameState> processLoop(LoopBeginNode loop, FrameState initialState) {
 272             return ReentrantNodeIterator.processLoop(this, loop, initialState).exitStates;
 273         }
 274 
 275         private static FrameState singleFrameState(List<FrameState> states) {
 276             FrameState singleState = states.get(0);
 277             for (int i = 1; i < states.size(); ++i) {
 278                 if (states.get(i) != singleState) {
 279                     return null;
 280                 }
 281             }
 282             return singleState;
 283         }
 284 
 285         FrameStateMapperClosure(StructuredGraph graph) {
 286             reachingStates = new NodeMap<>(graph);
 287         }
 288 
 289         public FrameState getState(Node n) {
 290             return reachingStates.get(n);
 291         }
 292 
 293         public void addState(Node n, FrameState s) {
 294             reachingStates.setAndGrow(n, s);
 295         }
 296     }
 297 
 298     /**
 299      * Try to find dominating node doing the resolution that can be reused.
 300      *
 301      * @param graph
 302      * @param node {@link ConstantNode} containing a {@link HotSpotResolvedJavaType} that needs
 303      *            resolution.
 304      */
 305     private static void tryToReplaceWithExisting(StructuredGraph graph, ConstantNode node) {
 306         ScheduleResult schedule = graph.getLastSchedule();
 307         NodeMap<Block> nodeToBlock = schedule.getNodeToBlockMap();
 308         BlockMap<List<Node>> blockToNodes = schedule.getBlockToNodesMap();
 309 
 310         EconomicMap<Block, Node> blockToExisting = EconomicMap.create();
 311         for (Node n : node.usages().filter(n -> isReplacementNode(n))) {
 312             blockToExisting.put(nodeToBlock.get(n), n);
 313         }
 314         for (Node use : node.usages().filter(n -> !isReplacementNode(n)).snapshot()) {
 315             boolean replaced = false;
 316             Block b = nodeToBlock.get(use);
 317             Node e = blockToExisting.get(b);
 318             if (e != null) {
 319                 // There is an initialization or resolution in the same block as the use, look if
 320                 // the use is scheduled after it.
 321                 for (Node n : blockToNodes.get(b)) {
 322                     if (n.equals(use)) {
 323                         // Usage is before initialization, can't use it
 324                         break;
 325                     }
 326                     if (n.equals(e)) {
 327                         use.replaceFirstInput(node, e);
 328                         replaced = true;
 329                         break;
 330                     }
 331                 }
 332             }
 333             if (!replaced) {
 334                 // Look for dominating blocks that have existing nodes
 335                 for (Block d : blockToExisting.getKeys()) {
 336                     if (strictlyDominates(d, b)) {
 337                         use.replaceFirstInput(node, blockToExisting.get(d));
 338                         break;
 339                     }
 340                 }
 341             }
 342         }
 343     }
 344 
 345     /**
 346      * Replace the uses of a constant with either {@link LoadConstantIndirectlyNode} or
 347      * {@link ResolveConstantNode}.
 348      *
 349      * @param graph
 350      * @param stateMapper
 351      * @param node {@link ConstantNode} containing a {@link HotSpotResolvedJavaType} that needs
 352      *            resolution.
 353      */
 354     private static void replaceWithResolution(StructuredGraph graph, FrameStateMapperClosure stateMapper, ConstantNode node) {
 355         HotSpotMetaspaceConstant metaspaceConstant = (HotSpotMetaspaceConstant) node.asConstant();
 356         HotSpotResolvedJavaType type = (HotSpotResolvedJavaType) metaspaceConstant.asResolvedJavaType();
 357         ResolvedJavaType topMethodHolder = graph.method().getDeclaringClass();
 358         ValueNode replacement;
 359 
 360         if (type.isArray() && type.getComponentType().isPrimitive()) {
 361             // Special case for primitive arrays. The AOT runtime pre-resolves them, so we may
 362             // omit the resolution call.
 363             replacement = graph.addOrUnique(new LoadConstantIndirectlyNode(node));
 364         } else if (type.equals(topMethodHolder) || (type.isAssignableFrom(topMethodHolder) && !type.isInterface())) {
 365             // If it's a supertype of or the same class that declares the top method, we are
 366             // guaranteed to have it resolved already. If it's an interface, we just test for
 367             // equality.
 368             replacement = graph.addOrUnique(new LoadConstantIndirectlyNode(node));
 369         } else {
 370             FixedWithNextNode fixedReplacement;
 371             if (builtIns.contains(type.mirror())) {
 372                 // Special case of klass constants that come from {@link BoxingSnippets}.
 373                 fixedReplacement = graph.add(new ResolveConstantNode(node, HotSpotConstantLoadAction.INITIALIZE));
 374             } else {
 375                 fixedReplacement = graph.add(new ResolveConstantNode(node));
 376             }
 377             insertReplacement(graph, stateMapper, node, fixedReplacement);
 378             replacement = fixedReplacement;
 379         }
 380         node.replaceAtUsages(replacement, n -> !isReplacementNode(n));
 381     }
 382 
 383     /**
 384      * Replace {@link ConstantNode} containing a {@link HotSpotResolvedJavaType} with indirection.
 385      *
 386      * @param graph
 387      * @param stateMapper
 388      * @param node {@link ConstantNode} containing a {@link HotSpotResolvedJavaType} that needs
 389      *            resolution.
 390      */
 391     private void handleHotSpotMetaspaceConstant(StructuredGraph graph, FrameStateMapperClosure stateMapper, ConstantNode node) {
 392         HotSpotMetaspaceConstant metaspaceConstant = (HotSpotMetaspaceConstant) node.asConstant();
 393         HotSpotResolvedJavaType type = (HotSpotResolvedJavaType) metaspaceConstant.asResolvedJavaType();
 394 
 395         if (type != null) {
 396             if (verifyFingerprints && checkForBadFingerprint(type)) {
 397                 throw new GraalError("Type with bad fingerprint: " + type);
 398             }
 399             assert !metaspaceConstant.isCompressed() : "No support for replacing compressed metaspace constants";
 400             tryToReplaceWithExisting(graph, node);
 401             if (anyUsagesNeedReplacement(node)) {
 402                 replaceWithResolution(graph, stateMapper, node);
 403             }
 404         } else {
 405             throw new GraalError("Unsupported metaspace constant type: " + type);
 406         }
 407     }
 408 
 409     /**
 410      * Replace an object constant with an indirect load {@link ResolveConstantNode}. Currently we
 411      * support only strings.
 412      *
 413      * @param graph
 414      * @param stateMapper
 415      * @param node {@link ConstantNode} containing a {@link HotSpotObjectConstant} that needs
 416      *            resolution.
 417      */
 418     private static void handleHotSpotObjectConstant(StructuredGraph graph, FrameStateMapperClosure stateMapper, ConstantNode node) {
 419         HotSpotObjectConstant constant = (HotSpotObjectConstant) node.asJavaConstant();
 420         HotSpotResolvedJavaType type = (HotSpotResolvedJavaType) constant.getType();
 421         if (type.mirror().equals(String.class)) {
 422             assert !constant.isCompressed() : "No support for replacing compressed oop constants";
 423             FixedWithNextNode replacement = graph.add(new ResolveConstantNode(node));
 424             insertReplacement(graph, stateMapper, node, replacement);
 425             node.replaceAtUsages(replacement, n -> !(n instanceof ResolveConstantNode));
 426         } else {
 427             throw new GraalError("Unsupported object constant type: " + type);
 428         }
 429     }
 430 
 431     /**
 432      * Replace {@link LoadMethodCountersNode} with indirect load
 433      * {@link ResolveMethodAndLoadCountersNode}, expose a klass constant of the holder.
 434      *
 435      * @param graph
 436      * @param stateMapper
 437      * @param node
 438      * @param context
 439      */
 440     private static void handleLoadMethodCounters(StructuredGraph graph, FrameStateMapperClosure stateMapper, LoadMethodCountersNode node, PhaseContext context) {
 441         ResolvedJavaType type = node.getMethod().getDeclaringClass();
 442         Stamp hubStamp = context.getStampProvider().createHubStamp((ObjectStamp) StampFactory.objectNonNull());
 443         ConstantReflectionProvider constantReflection = context.getConstantReflection();
 444         ConstantNode klassHint = ConstantNode.forConstant(hubStamp, constantReflection.asObjectHub(type), context.getMetaAccess(), graph);
 445         FixedWithNextNode replacement = graph.add(new ResolveMethodAndLoadCountersNode(node.getMethod(), klassHint));
 446         insertReplacement(graph, stateMapper, node, replacement);
 447         node.replaceAtUsages(replacement, n -> !(n instanceof ResolveMethodAndLoadCountersNode));
 448     }
 449 
 450     /**
 451      * Replace {@link LoadMethodCountersNode} with {@link ResolveMethodAndLoadCountersNode}, expose
 452      * klass constants.
 453      *
 454      * @param graph
 455      * @param stateMapper
 456      * @param context
 457      */
 458     private static void replaceLoadMethodCounters(StructuredGraph graph, FrameStateMapperClosure stateMapper, PhaseContext context) {
 459         new SchedulePhase(SchedulingStrategy.LATEST_OUT_OF_LOOPS, true).apply(graph, false);
 460 
 461         for (LoadMethodCountersNode node : getLoadMethodCountersNodes(graph)) {
 462             if (anyUsagesNeedReplacement(node)) {
 463                 handleLoadMethodCounters(graph, stateMapper, node, context);
 464             }
 465         }
 466     }
 467 
 468     /**
 469      * Replace object and klass constants with resolution nodes or reuse preceding initializations.
 470      *
 471      * @param graph
 472      * @param stateMapper
 473      */
 474     private void replaceKlassesAndObjects(StructuredGraph graph, FrameStateMapperClosure stateMapper) {
 475         new SchedulePhase(SchedulingStrategy.LATEST_OUT_OF_LOOPS, true).apply(graph, false);
 476 
 477         for (ConstantNode node : getConstantNodes(graph)) {
 478             Constant constant = node.asConstant();
 479             if (constant instanceof HotSpotMetaspaceConstant && anyUsagesNeedReplacement(node)) {
 480                 handleHotSpotMetaspaceConstant(graph, stateMapper, node);
 481             } else if (constant instanceof HotSpotObjectConstant && anyUsagesNeedReplacement(node)) {
 482                 handleHotSpotObjectConstant(graph, stateMapper, node);
 483             }
 484         }
 485     }
 486 
 487     @Override
 488     protected void run(StructuredGraph graph, PhaseContext context) {
 489         FrameStateMapperClosure stateMapper = new FrameStateMapperClosure(graph);
 490         ReentrantNodeIterator.apply(stateMapper, graph.start(), null);
 491 
 492         // Replace LoadMethodCountersNode with ResolveMethodAndLoadCountersNode, expose klass
 493         // constants.
 494         replaceLoadMethodCounters(graph, stateMapper, context);
 495 
 496         // Replace object and klass constants (including the ones added in the previous pass) with
 497         // resolution nodes.
 498         replaceKlassesAndObjects(graph, stateMapper);
 499     }
 500 
 501     @Override
 502     public boolean checkContract() {
 503         return false;
 504     }
 505 
 506     public ReplaceConstantNodesPhase() {
 507         this(true);
 508     }
 509 
 510     public ReplaceConstantNodesPhase(boolean verifyFingerprints) {
 511         this.verifyFingerprints = verifyFingerprints;
 512     }
 513 }