1 /*
2 * Copyright (c) 2016, 2019, 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.util.CollectionsUtil.anyMatch;
28
29 import java.util.ArrayList;
30 import java.util.Iterator;
31 import java.util.List;
32
33 import jdk.internal.vm.compiler.collections.EconomicSet;
34 import org.graalvm.compiler.graph.Node;
35 import org.graalvm.compiler.hotspot.nodes.aot.InitializeKlassNode;
36 import org.graalvm.compiler.hotspot.nodes.aot.ResolveConstantNode;
37 import org.graalvm.compiler.nodes.AbstractMergeNode;
38 import org.graalvm.compiler.nodes.FixedNode;
39 import org.graalvm.compiler.nodes.FixedWithNextNode;
40 import org.graalvm.compiler.nodes.Invoke;
41 import org.graalvm.compiler.nodes.StructuredGraph;
42 import org.graalvm.compiler.nodes.spi.CoreProviders;
43 import org.graalvm.compiler.phases.BasePhase;
44 import org.graalvm.compiler.phases.graph.MergeableState;
45 import org.graalvm.compiler.phases.graph.PostOrderNodeIterator;
46
47 import jdk.vm.ci.hotspot.HotSpotMetaspaceConstant;
48 import jdk.vm.ci.meta.Constant;
49 import jdk.vm.ci.meta.ResolvedJavaType;
50
51 public class EliminateRedundantInitializationPhase extends BasePhase<CoreProviders> {
52 /**
53 * Find each {@link Invoke} that has a corresponding {@link InitializeKlassNode}. These
54 * {@link InitializeKlassNode} are redundant and are removed.
55 */
56 private static void removeInitsAtStaticCalls(StructuredGraph graph) {
57 for (Invoke invoke : graph.getInvokes()) {
58 Node classInit = invoke.classInit();
59 if (classInit != null) {
60 classInit.replaceAtUsages(null);
61 graph.removeFixed((FixedWithNextNode) classInit);
62 }
63 }
64 }
65
66 /**
67 * Remove redundant {@link InitializeKlassNode} or {@link ResolveConstantNode} instances from
68 * the graph.
69 *
70 * @param graph the program graph
71 */
72 private static void removeRedundantInits(StructuredGraph graph) {
73 // Find and remove redundant nodes from the graph.
74 List<FixedWithNextNode> redundantNodes = findRedundantInits(graph);
75 for (FixedWithNextNode n : redundantNodes) {
76 graph.removeFixed(n);
77 }
78 }
79
80 /**
81 * Find {@link InitializeKlassNode} and {@link ResolveConstantNode} instances that can be
82 * removed because there is an existing dominating node.
83 *
84 * @param graph the program graph
85 */
86 private static List<FixedWithNextNode> findRedundantInits(StructuredGraph graph) {
87 EliminateRedundantInitializationIterator i = new EliminateRedundantInitializationIterator(graph.start(), new InitializedTypes());
88 i.apply();
89 return i.getRedundantNodes();
90 }
91
92 /**
93 * State for {@link EliminateRedundantInitializationIterator}.
94 */
95 private static class InitializedTypes extends MergeableState<InitializedTypes> implements Cloneable {
96 private EconomicSet<ResolvedJavaType> types;
97
98 InitializedTypes() {
99 types = EconomicSet.create();
100 }
101
102 private InitializedTypes(EconomicSet<ResolvedJavaType> types) {
103 this.types = types;
104 }
105
106 @Override
107 public InitializedTypes clone() {
108 return new InitializedTypes(EconomicSet.create(types));
109 }
110
111 public boolean contains(ResolvedJavaType type) {
112 if (type.isInterface() || type.isArray()) {
113 // Check for exact match for interfaces
114 return types.contains(type);
115 }
116 // For other types see if there is the same type or a subtype
117 return anyMatch(types, t -> type.isAssignableFrom(t));
118 }
119
120 public void add(ResolvedJavaType type) {
121 types.add(type);
122 }
123
124 /**
125 * Merge two given types. Interfaces and arrays have to be the same to merge successfully.
126 * For other types the answer is the LCA.
127 *
128 * @param a initialized type
129 * @param b initialized type
130 * @return lowest common type that is initialized if either a or b are initialized, null if
131 * no such type exists.
132 */
133 private static ResolvedJavaType merge(ResolvedJavaType a, ResolvedJavaType b) {
134 // We want exact match for interfaces or arrays
135 if (a.isInterface() || b.isInterface() || a.isArray() || b.isArray()) {
136 if (a.equals(b)) {
137 return a;
138 } else {
139 return null;
140 }
141 } else {
142 // And LCA for other types
143 ResolvedJavaType c = a.findLeastCommonAncestor(b);
144 if (c.isJavaLangObject()) {
145 // Not a very useful type, always initialized, don't pollute the sets.
146 return null;
147 }
148 return c;
149 }
150 }
151
152 /**
153 * Merge two sets of types. Essentially a computation of the LCA for each element of the
154 * cartesian product of the input sets. Interfaces have to match exactly.
155 *
156 * @param a set of initialized types
157 * @param b set of initialized types
158 * @return set of common types that would be initialized if types in either a or b are
159 * initialized
160 */
161 private static EconomicSet<ResolvedJavaType> merge(EconomicSet<ResolvedJavaType> a, EconomicSet<ResolvedJavaType> b) {
162 EconomicSet<ResolvedJavaType> c = EconomicSet.create();
163 for (ResolvedJavaType ta : a) {
164 for (ResolvedJavaType tb : b) {
165 ResolvedJavaType tc = merge(ta, tb);
166 if (tc != null) {
167 c.add(tc);
168 if (tc.isInterface() || tc.isArray()) {
169 // Interfaces and arrays are not going merge with anything else, so bail
170 // out early.
171 break;
172 }
173 }
174 }
175 }
176 return c;
177 }
178
179 @Override
180 public boolean merge(AbstractMergeNode merge, List<InitializedTypes> withStates) {
181 for (InitializedTypes ts : withStates) {
182 types = merge(types, ts.types);
183 }
184 return true;
185 }
186
187 protected static String toString(EconomicSet<ResolvedJavaType> types) {
188 StringBuilder b = new StringBuilder();
189 b.append("[");
190 Iterator<ResolvedJavaType> i = types.iterator();
191 while (i.hasNext()) {
192 ResolvedJavaType t = i.next();
193 b.append(t.toString());
194 if (i.hasNext()) {
195 b.append(",");
196 }
197 }
198 b.append("]");
199 return b.toString();
200 }
201
202 @Override
203 public String toString() {
204 return toString(types);
205 }
206 }
207
208 /**
209 * Do data flow analysis of class initializations and array resolutions. Collect redundant
210 * nodes.
211 */
212 private static class EliminateRedundantInitializationIterator extends PostOrderNodeIterator<InitializedTypes> {
213 private List<FixedWithNextNode> redundantNodes = new ArrayList<>();
214
215 public List<FixedWithNextNode> getRedundantNodes() {
216 return redundantNodes;
217 }
218
219 EliminateRedundantInitializationIterator(FixedNode start, InitializedTypes initialState) {
220 super(start, initialState);
221 }
222
223 private void processType(FixedWithNextNode node, Constant c) {
224 HotSpotMetaspaceConstant klass = (HotSpotMetaspaceConstant) c;
225 ResolvedJavaType t = klass.asResolvedJavaType();
226 if (t != null) {
227 if (state.contains(t)) {
228 redundantNodes.add(node);
229 } else {
230 state.add(t);
231 }
232 }
233 }
234
235 @Override
236 protected void node(FixedNode node) {
237 if (node instanceof InitializeKlassNode) {
238 InitializeKlassNode i = (InitializeKlassNode) node;
239 if (i.value().isConstant()) {
240 processType(i, i.value().asConstant());
241 }
242 } else if (node instanceof ResolveConstantNode) {
243 ResolveConstantNode r = (ResolveConstantNode) node;
244 if (r.hasNoUsages()) {
245 if (r.value().isConstant()) {
246 processType(r, r.value().asConstant());
247 }
248 }
249 }
250 }
251
252 }
253
254 @Override
255 protected void run(StructuredGraph graph, CoreProviders context) {
256 removeInitsAtStaticCalls(graph);
257 removeRedundantInits(graph);
258 }
259 }