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