1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
/*
* Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*
*/
/*
* @test
* @bug 8327110 8327111
* @requires vm.compiler2.enabled
* @summary Test that DFS algorithm for cloning Template Assertion Predicate Expression does not endlessly process paths.
* @run main/othervm/timeout=30 -Xcomp -XX:LoopMaxUnroll=0
* -XX:CompileCommand=compileonly,*TestCloningWithManyDiamondsInExpression::test*
* -XX:CompileCommand=inline,*TestCloningWithManyDiamondsInExpression::create*
* compiler.predicates.TestCloningWithManyDiamondsInExpression
* @run main/othervm/timeout=30 -Xbatch -XX:LoopMaxUnroll=0
* -XX:CompileCommand=compileonly,*TestCloningWithManyDiamondsInExpression::test*
* -XX:CompileCommand=inline,*TestCloningWithManyDiamondsInExpression::create*
* compiler.predicates.TestCloningWithManyDiamondsInExpression
* @run main/timeout=30 compiler.predicates.TestCloningWithManyDiamondsInExpression
*/
/*
* @test
* @bug 8327111
* @summary Test that DFS algorithm for cloning Template Assertion Predicate Expression does not endlessly process paths.
* @run main/othervm/timeout=30 -Xcomp
* -XX:CompileCommand=compileonly,*TestCloningWithManyDiamondsInExpression::test*
* -XX:CompileCommand=inline,*TestCloningWithManyDiamondsInExpression::create*
* compiler.predicates.TestCloningWithManyDiamondsInExpression
* @run main/othervm/timeout=30 -Xbatch
* -XX:CompileCommand=compileonly,*TestCloningWithManyDiamondsInExpression::test*
* -XX:CompileCommand=inline,*TestCloningWithManyDiamondsInExpression::create*
* compiler.predicates.TestCloningWithManyDiamondsInExpression
*/
package compiler.predicates;
public class TestCloningWithManyDiamondsInExpression {
static int limit = 100;
static int iFld;
static boolean flag;
static int[] iArr;
public static void main(String[] strArr) {
Math.min(10, 13); // Load class for Xcomp mode.
for (int i = 0; i < 10_000; i++) {
testSplitIf(i % 2);
testLoopUnswitching(i % 2);
testLoopUnrolling(i % 2);
testLoopPeeling(i % 2);
}
}
static void testLoopUnswitching(int x) {
// We create an array with a positive size whose type range is known by the C2 compiler to be positive.
// Loop Predication will then be able to hoist the array check out of the loop by creating a Hoisted
// Check Predicate accompanied by a Template Assertion Predicate. The Template Assertion Predicate
// Expression gets the size as an input. When splitting the loop further (i.e. when doing Loop Unswitching),
// the predicate needs to be updated. We need to clone all nodes of the Tempalte Assertion Predicate
// Expression. We first need to find them by doing a DFS walk.
//
// createExpressionWithManyDiamonds() creates an expression with many diamonds. The current implementation
// (found in create_bool_from_template_assertion_predicate()) to clone the Template Assertion Predicate
// does not use a visited set. Therefore, the DFS implementation visits nodes twice to discover more paths.
// The more diamonds we add, the more possible paths we get to visit. This leads to an exponential explosion
// of paths and time required to visit them all. This example here will get "stuck" during DFS while trying
// to walk all the possible paths.
//
int[] a = new int[createExpressionWithManyDiamonds(x) + 1000];
for (int i = 0; i < limit; i++) {
a[i] = i; // Loop Predication hoists this check and creates a Template Assertion Predicate.
// Triggers Loop Unswitching -> we need to clone the Template Assertion Predicates
// to both the true- and false-path loop. Will take forever (see explanation above).
if (x == 0) {
iFld = 34;
}
}
}
// Same as for Loop Unswitching but triggered in Split If when the Tempalte Assertion Predicate Expression
// needs to be cloned. This time it's not the size of the array that contains many diamonds but the array
// index for the first and last value Template Assertion Predicate Expression.
static void testSplitIf(int x) {
int e = createExpressionWithManyDiamonds(x);
iArr = new int[1000];
int a;
if (flag) {
a = 4;
} else {
a = 3;
}
for (int i = a; i < 100; i++) {
iArr[i+e] = 34;
}
}
static void testLoopUnrolling(int x) {
int[] a = new int[createExpressionWithManyDiamonds(x) + 1000];
for (int i = 0; i < limit; i++) {
a[i] = i; // Loop Predication hoists this check and creates a Template Assertion Predicate.
}
}
static void testLoopPeeling(int x) {
int[] a = new int[createExpressionWithManyDiamonds(x) + 1000];
for (int i = 0; i < limit; i++) {
a[i] = i; // Loop Predication hoists this check and creates a Template Assertion Predicate.
if (x == 0) { // Reason to peel with LoopMaxUnroll=0
return;
}
}
}
// Creates in int expression with many diamonds. This method is forced-inlined.
static int createExpressionWithManyDiamonds(int x) {
int e = Math.min(10, Math.max(1, x));
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2) - 823542;
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2) - 823542;
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2);
e = e + (e << 1) + (e << 2) - 823542;
return e;
}
}
|
