1 /*
2 * Copyright (c) 2011, 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.core.test.ea;
26
27 import java.util.List;
28
29 import org.graalvm.compiler.graph.Node;
30 import org.graalvm.compiler.graph.iterators.NodeIterable;
31 import org.graalvm.compiler.loop.DefaultLoopPolicies;
32 import org.graalvm.compiler.loop.phases.LoopFullUnrollPhase;
33 import org.graalvm.compiler.loop.phases.LoopPeelingPhase;
34 import org.graalvm.compiler.nodes.ConstantNode;
35 import org.graalvm.compiler.nodes.ReturnNode;
36 import org.graalvm.compiler.nodes.extended.BoxNode;
37 import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
38 import org.graalvm.compiler.nodes.java.LoadFieldNode;
39 import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode;
40 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
41 import org.graalvm.compiler.phases.common.CanonicalizerPhase;
42 import org.graalvm.compiler.phases.schedule.SchedulePhase;
43 import org.graalvm.compiler.virtual.phases.ea.PartialEscapePhase;
44 import org.junit.Assert;
45 import org.junit.Assume;
46 import org.junit.Test;
47
48 import jdk.vm.ci.meta.JavaConstant;
49
50 /**
51 * The PartialEscapeAnalysisPhase is expected to remove all allocations and return the correct
52 * values.
53 */
54 public class EscapeAnalysisTest extends EATestBase {
55
56 @Test
57 public void test1() {
58 testEscapeAnalysis("test1Snippet", JavaConstant.forInt(101), false);
59 }
60
61 @SuppressWarnings("deprecation")
62 public static int test1Snippet() {
63 Integer x = new Integer(101);
64 return x.intValue();
65 }
66
67 @Test
68 public void test2() {
69 testEscapeAnalysis("test2Snippet", JavaConstant.forInt(0), false);
70 }
71
72 public static int test2Snippet() {
73 Integer[] x = new Integer[0];
74 return x.length;
75 }
76
77 @Test
78 public void test3() {
79 testEscapeAnalysis("test3Snippet", JavaConstant.NULL_POINTER, false);
80 }
81
82 public static Object test3Snippet() {
83 Integer[] x = new Integer[1];
84 return x[0];
85 }
86
87 @Test
88 public void testMonitor() {
89 testEscapeAnalysis("testMonitorSnippet", JavaConstant.forInt(0), false);
90 }
91
92 @SuppressWarnings("deprecation")
93 public static int testMonitorSnippet() {
94 Integer x = new Integer(0);
95 Double y = new Double(0);
96 Object z = new Object();
97 synchronized (x) {
98 synchronized (y) {
99 synchronized (z) {
100 notInlineable();
101 }
102 }
103 }
104 return x.intValue();
105 }
106
107 @Test
108 public void testMonitor2() {
109 testEscapeAnalysis("testMonitor2Snippet", JavaConstant.forInt(0), false);
110 }
111
112 /**
113 * This test case differs from the last one in that it requires inlining within a synchronized
114 * region.
115 */
116 @SuppressWarnings("deprecation")
117 public static int testMonitor2Snippet() {
118 Integer x = new Integer(0);
119 Double y = new Double(0);
120 Object z = new Object();
121 synchronized (x) {
122 synchronized (y) {
123 synchronized (z) {
124 notInlineable();
125 return x.intValue();
126 }
127 }
128 }
129 }
130
131 @Test
132 public void testMerge() {
133 testEscapeAnalysis("testMerge1Snippet", JavaConstant.forInt(0), true);
134 }
135
136 public static int testMerge1Snippet(int a) {
137 TestClassInt obj = new TestClassInt(1, 0);
138 if (a < 0) {
139 obj.x = obj.x + 1;
140 } else {
141 obj.x = obj.x + 2;
142 obj.y = 0;
143 }
144 if (obj.x > 1000) {
145 return 1;
146 }
147 return obj.y;
148 }
149
150 @Test
151 public void testSimpleLoop() {
152 testEscapeAnalysis("testSimpleLoopSnippet", JavaConstant.forInt(1), false);
153 }
154
155 public int testSimpleLoopSnippet(int a) {
156 TestClassInt obj = new TestClassInt(1, 2);
157 for (int i = 0; i < a; i++) {
158 notInlineable();
159 }
160 return obj.x;
161 }
162
163 @Test
164 public void testModifyingLoop() {
165 testEscapeAnalysis("testModifyingLoopSnippet", JavaConstant.forInt(1), false);
166 }
167
168 public int testModifyingLoopSnippet(int a) {
169 TestClassInt obj = new TestClassInt(1, 2);
170 for (int i = 0; i < a; i++) {
171 obj.x = 3;
172 notInlineable();
173 }
174 return obj.x <= 3 ? 1 : 0;
175 }
176
177 @Test
178 public void testMergeAllocationsInt() {
179 testEscapeAnalysis("testMergeAllocationsIntSnippet", JavaConstant.forInt(1), false);
180 }
181
182 public int testMergeAllocationsIntSnippet(int a) {
183 TestClassInt obj;
184 if (a < 0) {
185 obj = new TestClassInt(1, 2);
186 notInlineable();
187 } else {
188 obj = new TestClassInt(1, 2);
189 notInlineable();
190 }
191 return obj.x <= 3 ? 1 : 0;
192 }
193
194 @Test
195 public void testMergeAllocationsInt2() {
196 testEscapeAnalysis("testMergeAllocationsInt2Snippet", JavaConstant.forInt(1), true);
197 }
198
199 public int testMergeAllocationsInt2Snippet(int a) {
200 /*
201 * The initial object in obj exists until the end of the function, but it can still be
202 * merged with the one allocated in the else block because noone can observe the identity.
203 */
204 TestClassInt obj = new TestClassInt(1, 2);
205 if (a < 0) {
206 notInlineable();
207 } else {
208 obj = new TestClassInt(1, 2);
209 notInlineable();
210 }
211 return obj.x <= 3 ? 1 : 0;
212 }
213
214 @Test
215 public void testMergeAllocationsInt3() {
216 // ensure that the result is not constant:
217 assertTrue(testMergeAllocationsInt3Snippet(true));
218 assertFalse(testMergeAllocationsInt3Snippet(false));
219
220 prepareGraph("testMergeAllocationsInt3Snippet", true);
221 assertFalse(graph.getNodes().filter(ReturnNode.class).first().result().isConstant());
222 }
223
224 public boolean testMergeAllocationsInt3Snippet(boolean a) {
225 TestClassInt phi1;
226 TestClassInt phi2;
227 if (a) {
228 field = new TestClassObject();
229 field = new TestClassObject();
230 phi1 = phi2 = new TestClassInt(1, 2);
231 } else {
232 phi1 = new TestClassInt(2, 3);
233 phi2 = new TestClassInt(3, 4);
234 }
235 return phi1 == phi2;
236 }
237
238 @Test
239 public void testMergeAllocationsObj() {
240 testEscapeAnalysis("testMergeAllocationsObjSnippet", JavaConstant.forInt(1), false);
241 }
242
243 public int testMergeAllocationsObjSnippet(int a) {
244 TestClassObject obj;
245 Integer one = 1;
246 Integer two = 2;
247 Integer three = 3;
248 if (a < 0) {
249 obj = new TestClassObject(one, two);
250 notInlineable();
251 } else {
252 obj = new TestClassObject(one, three);
253 notInlineable();
254 }
255 return ((Integer) obj.x).intValue() <= 3 ? 1 : 0;
256 }
257
258 @Test
259 public void testMergeAllocationsObjCirc() {
260 testEscapeAnalysis("testMergeAllocationsObjCircSnippet", JavaConstant.forInt(1), false);
261 }
262
263 public int testMergeAllocationsObjCircSnippet(int a) {
264 TestClassObject obj;
265 Integer one = 1;
266 Integer two = 2;
267 Integer three = 3;
268 if (a < 0) {
269 obj = new TestClassObject(one);
270 obj.y = obj;
271 obj.y = two;
272 notInlineable();
273 } else {
274 obj = new TestClassObject(one);
275 obj.y = obj;
276 obj.y = three;
277 notInlineable();
278 }
279 return ((Integer) obj.x).intValue() <= 3 ? 1 : 0;
280 }
281
282 static class MyException extends RuntimeException {
283
284 private static final long serialVersionUID = 0L;
285
286 protected Integer value;
287
288 MyException(Integer value) {
289 super((Throwable) null);
290 this.value = value;
291 }
292
293 @SuppressWarnings("sync-override")
294 @Override
295 public final Throwable fillInStackTrace() {
296 return this;
297 }
298 }
299
300 @Test
301 public void testMergeAllocationsException() {
302 testEscapeAnalysis("testMergeAllocationsExceptionSnippet", JavaConstant.forInt(1), false);
303 }
304
305 public int testMergeAllocationsExceptionSnippet(int a) {
306 MyException obj;
307 Integer one = 1;
308 if (a < 0) {
309 obj = new MyException(one);
310 notInlineable();
311 } else {
312 obj = new MyException(one);
313 notInlineable();
314 }
315 return obj.value <= 3 ? 1 : 0;
316 }
317
318 /**
319 * Tests that a graph with allocations that does not make progress during PEA will not be
320 * changed.
321 */
322 @Test
323 public void testChangeHandling() {
324 prepareGraph("testChangeHandlingSnippet", false);
325 Assert.assertEquals(2, graph.getNodes().filter(CommitAllocationNode.class).count());
326 Assert.assertEquals(1, graph.getNodes().filter(BoxNode.class).count());
327 List<Node> nodes = graph.getNodes().snapshot();
328 // verify that an additional run doesn't add or remove nodes
329 new PartialEscapePhase(false, false, new CanonicalizerPhase(), null, graph.getOptions()).apply(graph, context);
330 Assert.assertEquals(nodes.size(), graph.getNodeCount());
331 for (Node node : nodes) {
332 Assert.assertTrue(node.isAlive());
333 }
334 }
335
336 public volatile Object field;
337
338 @SuppressWarnings("deprecation")
339 public int testChangeHandlingSnippet(int a) {
340 Object obj;
341 Integer one = 1;
342 obj = new MyException(one);
343 if (a < 0) {
344 notInlineable();
345 } else {
346 obj = new Integer(1);
347 notInlineable();
348 }
349 field = obj;
350 return 1;
351 }
352
353 /**
354 * Test the case where allocations before and during a loop that have no usages other than their
355 * phi need to be recognized as an important change. This needs a loop so that the allocation is
356 * not trivially removed by dead code elimination.
357 */
358 @Test
359 public void testRemovalSpecialCase() {
360 prepareGraph("testRemovalSpecialCaseSnippet", false);
361 Assert.assertEquals(2, graph.getNodes().filter(CommitAllocationNode.class).count());
362 // create the situation by removing the if
363 graph.replaceFixedWithFloating(graph.getNodes().filter(LoadFieldNode.class).first(), graph.unique(ConstantNode.forInt(0)));
364 new CanonicalizerPhase().apply(graph, context);
365 // verify that an additional run removes all allocations
366 new PartialEscapePhase(false, false, new CanonicalizerPhase(), null, graph.getOptions()).apply(graph, context);
367 Assert.assertEquals(0, graph.getNodes().filter(CommitAllocationNode.class).count());
368 }
369
370 public volatile int field2;
371
372 public int testRemovalSpecialCaseSnippet(int a) {
373 Object phi = new Object();
374 for (int i = 0; i < a; i++) {
375 field = null;
376 if (field2 == 1) {
377 phi = new Object();
378 }
379 }
380 return phi == null ? 1 : 0;
381 }
382
383 @Test
384 public void testCheckCast() {
385 testEscapeAnalysis("testCheckCastSnippet", getSnippetReflection().forObject(TestClassObject.class), true);
386 }
387
388 public Object testCheckCastSnippet() {
389 TestClassObject obj = new TestClassObject(TestClassObject.class);
390 TestClassObject obj2 = new TestClassObject(obj);
391 return ((TestClassObject) obj2.x).x;
392 }
393
394 @Test
395 public void testInstanceOf() {
396 testEscapeAnalysis("testInstanceOfSnippet", JavaConstant.forInt(1), false);
397 }
398
399 public boolean testInstanceOfSnippet() {
400 TestClassObject obj = new TestClassObject(TestClassObject.class);
401 TestClassObject obj2 = new TestClassObject(obj);
402 return obj2.x instanceof TestClassObject;
403 }
404
405 @SuppressWarnings("unused")
406 public static void testNewNodeSnippet() {
407 new ValueAnchorNode(null);
408 }
409
410 /**
411 * This test makes sure that the allocation of a {@link Node} can be removed. It therefore also
412 * tests the intrinsification of {@link Object#getClass()}.
413 */
414 @Test
415 public void testNewNode() {
416 // Trackking of creation interferes with escape analysis
417 Assume.assumeFalse(Node.TRACK_CREATION_POSITION);
418 testEscapeAnalysis("testNewNodeSnippet", null, false);
419 }
420
421 private static final TestClassObject staticObj = new TestClassObject();
422
423 public static Object testFullyUnrolledLoopSnippet() {
424 /*
425 * This tests a case that can appear if PEA is performed both before and after loop
426 * unrolling/peeling: If the VirtualInstanceNode is not duplicated correctly with the loop,
427 * the resulting object will reference itself, and not a second (different) object.
428 */
429 TestClassObject obj = staticObj;
430 for (int i = 0; i < 2; i++) {
431 obj = new TestClassObject(obj);
432 }
433 return obj.x;
434 }
435
436 @Test
437 public void testFullyUnrolledLoop() {
438 prepareGraph("testFullyUnrolledLoopSnippet", false);
439 new LoopFullUnrollPhase(new CanonicalizerPhase(), new DefaultLoopPolicies()).apply(graph, context);
440 new PartialEscapePhase(false, new CanonicalizerPhase(), graph.getOptions()).apply(graph, context);
441 Assert.assertEquals(1, returnNodes.size());
442 Assert.assertTrue(returnNodes.get(0).result() instanceof AllocatedObjectNode);
443 CommitAllocationNode commit = ((AllocatedObjectNode) returnNodes.get(0).result()).getCommit();
444 Assert.assertEquals(2, commit.getValues().size());
445 Assert.assertEquals(1, commit.getVirtualObjects().size());
446 Assert.assertTrue("non-cyclic data structure expected", commit.getVirtualObjects().get(0) != commit.getValues().get(0));
447 }
448
449 @SuppressWarnings("unused") private static Object staticField;
450
451 private static TestClassObject inlinedPart(TestClassObject obj) {
452 TestClassObject ret = new TestClassObject(obj);
453 staticField = null;
454 return ret;
455 }
456
457 public static Object testPeeledLoopSnippet() {
458 TestClassObject obj = staticObj;
459 int i = 0;
460 do {
461 obj = inlinedPart(obj);
462 } while (i++ < 10);
463 staticField = obj;
464 return obj.x;
465 }
466
467 @Test
468 public void testPeeledLoop() {
469 prepareGraph("testPeeledLoopSnippet", false);
470 new LoopPeelingPhase(new DefaultLoopPolicies()).apply(graph, getDefaultHighTierContext());
471 new SchedulePhase(graph.getOptions()).apply(graph);
472 }
473
474 public static void testDeoptMonitorSnippetInner(Object o2, Object t, int i) {
475 staticField = null;
476 if (i == 0) {
477 staticField = o2;
478 Number n = (Number) t;
479 n.toString();
480 }
481 }
482
483 public static void testDeoptMonitorSnippet(Object t, int i) {
484 TestClassObject o = new TestClassObject();
485 TestClassObject o2 = new TestClassObject(o);
486
487 synchronized (o) {
488 testDeoptMonitorSnippetInner(o2, t, i);
489 }
490 }
491
492 @Test
493 public void testDeoptMonitor() {
494 test("testDeoptMonitorSnippet", new Object(), 0);
495 }
496
497 @Test
498 public void testInterfaceArrayAssignment() {
499 prepareGraph("testInterfaceArrayAssignmentSnippet", false);
500 NodeIterable<ReturnNode> returns = graph.getNodes().filter(ReturnNode.class);
501 assertTrue(returns.count() == 1);
502 assertFalse(returns.first().result().isConstant());
503 }
504
505 private interface TestInterface {
506 }
507
508 public static boolean testInterfaceArrayAssignmentSnippet() {
509 Object[] array = new TestInterface[1];
510 array[0] = new Object();
511 return array[0] == null;
512 }
513
514 static final class Complex {
515 private final double real;
516 private final double imag;
517
518 Complex(double real, double imag) {
519 this.real = real;
520 this.imag = imag;
521 }
522
523 public Complex mul(Complex other) {
524 return new Complex(real * other.real - imag * other.imag, imag * other.real + real * other.imag);
525 }
526
527 public Complex add(Complex other) {
528 return new Complex(real + other.real, imag + other.imag);
529 }
530
531 // equals is needed for result comparison
532
533 @Override
534 public boolean equals(Object obj) {
535 if (obj == null || getClass() != obj.getClass()) {
536 return false;
537 }
538 Complex other = (Complex) obj;
539 return this == other || Double.doubleToLongBits(imag) == Double.doubleToLongBits(other.imag) && Double.doubleToLongBits(real) == Double.doubleToLongBits(other.real);
540 }
541
542 @Override
543 public int hashCode() {
544 return Double.hashCode(real) ^ Double.hashCode(imag);
545 }
546 }
547
548 private static final Complex[][] inputValue = new Complex[100][100];
549 static {
550 for (int i = 0; i < 100; i++) {
551 for (int j = 0; j < 100; j++) {
552 inputValue[i][j] = new Complex(i, j);
553 }
554 }
555 }
556
557 public static Complex[][] testComplexMultiplySnippet1(Complex[][] input) {
558 int size = input.length;
559 Complex[][] result = new Complex[size][size];
560 for (int i = 0; i < size; i++) {
561 for (int j = 0; j < size; j++) {
562 Complex s = new Complex(0, 0);
563 for (int k = 0; k < size; k++) {
564 s = s.add(input[i][k].mul(input[k][j]));
565 }
566 result[i][j] = s;
567 }
568 }
569 return result;
570 }
571
572 @Test
573 public void testComplexMultiply1() {
574 test("testComplexMultiplySnippet1", (Object) inputValue);
575
576 // EA test: only one allocation remains (not counting the NewMultiArray), using iterative EA
577 testEscapeAnalysis("testComplexMultiplySnippet1", null, true, 1);
578 }
579
580 public static Complex[][] testComplexMultiplySnippet2(Complex[][] input) {
581 int size = input.length;
582 Complex[][] result = new Complex[size][size];
583 for (int i = 0; i < size; i++) {
584 for (int j = 0; j < size; j++) {
585 Complex s = input[i][0].mul(input[0][j]);
586 for (int k = 1; k < size; k++) {
587 s = s.add(input[i][k].mul(input[k][j]));
588 }
589 result[i][j] = s;
590 }
591 }
592 return result;
593 }
594
595 @Test
596 public void testComplexMultiply2() {
597 test("testComplexMultiplySnippet2", (Object) inputValue);
598
599 // EA test: only one allocation remains (not counting the NewMultiArray), using iterative EA
600 testEscapeAnalysis("testComplexMultiplySnippet2", null, true, 1);
601 }
602
603 public static Complex testComplexAddSnippet(Complex[][] input) {
604 int size = input.length;
605 Complex s = new Complex(0, 0);
606 for (int i = 0; i < size; i++) {
607 Complex s2 = new Complex(0, 0);
608 for (int j = 0; j < size; j++) {
609 s2 = s2.add(input[i][j]);
610 }
611 s.add(s2);
612 }
613 return s;
614 }
615
616 @Test
617 public void testComplexAdd() {
618 test("testComplexAddSnippet", (Object) inputValue);
619
620 // EA test: only one allocation remains (not counting the NewMultiArray), using iterative EA
621 testEscapeAnalysis("testComplexAddSnippet", null, true, 1);
622 }
623
624 public static Complex[] testComplexRowSumSnippet(Complex[][] input) {
625 int size = input.length;
626 Complex[] result = new Complex[size];
627 for (int i = 0; i < size; i++) {
628 Complex s = new Complex(0, 0);
629 for (int j = 0; j < size; j++) {
630 s = s.add(input[i][j]);
631 }
632 result[i] = s;
633 }
634 return result;
635 }
636
637 @Test
638 public void testComplexRowSum() {
639 test("testComplexRowSumSnippet", (Object) inputValue);
640
641 // EA test: only two allocations (new array and new instance) remain
642 testEscapeAnalysis("testComplexRowSumSnippet", null, true, 2);
643 }
644 }