1 /*
2 * Copyright (c) 2016, 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.nodes.ConstantNode.getConstantNodes;
26
27 import java.util.ArrayList;
28 import java.util.HashMap;
29 import java.util.Map.Entry;
30
31 import jdk.vm.ci.hotspot.HotSpotMetaspaceConstant;
32 import jdk.vm.ci.meta.JavaConstant;
33
34 import org.graalvm.compiler.graph.Node;
35 import org.graalvm.compiler.graph.iterators.NodeIterable;
36 import org.graalvm.compiler.hotspot.nodes.aot.InitializeKlassNode;
37 import org.graalvm.compiler.nodes.ConstantNode;
38 import org.graalvm.compiler.nodes.FixedWithNextNode;
39 import org.graalvm.compiler.nodes.Invoke;
40 import org.graalvm.compiler.nodes.StructuredGraph;
41 import org.graalvm.compiler.nodes.cfg.Block;
42 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
43 import org.graalvm.compiler.phases.BasePhase;
44 import org.graalvm.compiler.phases.tiers.PhaseContext;
45
46 public class EliminateRedundantInitializationPhase extends BasePhase<PhaseContext> {
47 /**
48 * Find blocks with class initializing nodes for the class identified the by the constant node.
49 * Return the map of a block to a list of initializing nodes in that block.
50 *
51 * @param cfg an instance of the {@link ControlFlowGraph}.
52 * @param constant common input to the instances of {@link InitializeKlassNode}.
53 * @return map of blocks to lists of initializing nodes.
54 */
55 private static HashMap<Block, ArrayList<Node>> findBlocksWithInitializers(ControlFlowGraph cfg, ConstantNode constant) {
56 // node is ConstantNode representing a metaspace constant (a klass reference).
57 // InitializeKlassNodes for the same class would share the same ConstantNode input.
58 NodeIterable<?> initializers = constant.usages().filter(InitializeKlassNode.class);
59 // Map the found nodes to blocks
60 HashMap<Block, ArrayList<Node>> blockToInits = new HashMap<>();
61 for (Node i : initializers) {
62 Block b = cfg.blockFor(i);
63 ArrayList<Node> initsInBlock = blockToInits.get(b);
64 if (initsInBlock == null) {
65 initsInBlock = new ArrayList<>();
66 }
67 initsInBlock.add(i);
68 blockToInits.put(b, initsInBlock);
69 }
70 return blockToInits;
71 }
72
73 /**
74 * Process the block-to-initializers map and produce a list of blocks that contain more than one
75 * instance of {@link InitializeKlassNode}.
76 *
77 * @param blockToInits a map of blocks to lists of {@link InitializeKlassNode} instances.
78 * @return list of blocks that contain multiple instances of {@link InitializeKlassNode}.
79 */
80 private static ArrayList<Block> findBlocksWithMultipleInitializers(HashMap<Block, ArrayList<Node>> blockToInits) {
81 ArrayList<Block> result = new ArrayList<>();
82 // Select the blocks from the blocksToInits map that have more than one InitializeKlassNode
83 for (Entry<Block, ArrayList<Node>> e : blockToInits.entrySet()) {
84 if (e.getValue().size() > 1) {
85 result.add(e.getKey());
86 }
87 }
88 return result;
89 }
90
91 /**
92 * Iterate through blocks with multiple instances of {@link InitializeKlassNode} and identify
93 * redundant instances. Remove redundant instances from the block-to-list-of-initializer map.
94 *
95 * @param blockToInits a map of blocks to lists of {@link InitializeKlassNode} instances.
96 * @param blocksWithMultipleInits a list of blocks that contain multiple instances of
97 * {@link InitializeKlassNode}.
98 * @param constant common input to the instances of {@link InitializeKlassNode}.
99 * @return list of {@link InitializeKlassNode} instances that can be removed.
100 */
101 private static ArrayList<Node> findRedundantLocalInitializers(HashMap<Block, ArrayList<Node>> blockToInits, ArrayList<Block> blocksWithMultipleInits, ConstantNode constant) {
102 ArrayList<Node> result = new ArrayList<>();
103 for (Block b : blocksWithMultipleInits) {
104 // First initializer for our constant in the block
105 InitializeKlassNode first = null;
106 for (Node n : b.getNodes()) {
107 if (n instanceof InitializeKlassNode) {
108 InitializeKlassNode i = (InitializeKlassNode) n;
109 if (i.value() == constant) {
110 if (first == null) {
111 // First instance of {@link InitializeKlassNode} stays.
112 first = i;
113 } else {
114 // All the following instances of {@link InitializeKlassNode} can be
115 // removed.
116 result.add(i);
117 }
118 }
119 }
120 }
121 assert first != null;
122
123 // Replace the entry in the initsInBlock map to contain just a single initializer
124 ArrayList<Node> initsInBlock = new ArrayList<>();
125 initsInBlock.add(first);
126 blockToInits.put(b, initsInBlock);
127 }
128 return result;
129 }
130
131 /**
132 * Find cases when one {@link InitializeKlassNode} instance dominates another. The dominated
133 * instance can be removed.
134 *
135 * @param blockToInits a map of blocks to lists of {@link InitializeKlassNode} instances.
136 * @return list of {@link InitializeKlassNode} instances that can be removed.
137 */
138 private static ArrayList<Node> findRedundantGlobalInitializers(HashMap<Block, ArrayList<Node>> blockToInits) {
139 ArrayList<Node> result = new ArrayList<>();
140 for (Entry<Block, ArrayList<Node>> e : blockToInits.entrySet()) {
141 Block currentBlock = e.getKey();
142 ArrayList<Node> nodesInCurrent = e.getValue();
143 if (nodesInCurrent != null) { // if the list is null, the initializer has already been
144 // eliminated.
145 for (Block d : currentBlock.getDominated()) {
146 ArrayList<Node> nodesInDominated = blockToInits.get(d);
147 if (nodesInDominated != null) { // if the list is null, the initializer has
148 // already been eliminated.
149 assert nodesInDominated.size() == 1;
150 Node n = nodesInDominated.iterator().next();
151 result.add(n);
152 blockToInits.put(d, null);
153 }
154 }
155 }
156 }
157 return result;
158 }
159
160 /**
161 * Compute the list of redundant {@link InitializeKlassNode} instances that have the common
162 * {@link ConstantNode}.
163 *
164 * @param cfg an instance of the {@link ControlFlowGraph}.
165 * @param constant common input to the instances of {@link InitializeKlassNode}.
166 * @return list of {@link InitializeKlassNode} instances that can be removed.
167 */
168 private static ArrayList<Node> processConstantNode(ControlFlowGraph cfg, ConstantNode constant) {
169 HashMap<Block, ArrayList<Node>> blockToInits = findBlocksWithInitializers(cfg, constant);
170 ArrayList<Block> blocksWithMultipleInits = findBlocksWithMultipleInitializers(blockToInits);
171 ArrayList<Node> redundantInits = findRedundantLocalInitializers(blockToInits, blocksWithMultipleInits, constant);
172 // At this point each block has at most one initializer for this constant
173 if (blockToInits.size() > 1) {
174 redundantInits.addAll(findRedundantGlobalInitializers(blockToInits));
175 }
176 return redundantInits;
177 }
178
179 /**
180 * Find each {@link Invoke} that has a corresponding {@link InitializeKlassNode}. These
181 * {@link InitializeKlassNode} are redundant and are removed.
182 *
183 */
184 private static void removeInitsAtStaticCalls(StructuredGraph graph) {
185 for (Invoke invoke : graph.getInvokes()) {
186 if (invoke.classInit() != null) {
187 Node classInit = invoke.classInit();
188 classInit.replaceAtUsages(null);
189 graph.removeFixed((FixedWithNextNode) classInit);
190 }
191 }
192 }
193
194 /**
195 * Find {@link InitializeKlassNode} instances that can be removed because there is an existing
196 * dominating initialization.
197 *
198 * @param graph the program graph.
199 */
200 private static void removeRedundantInits(StructuredGraph graph) {
201 // Create cfg, we need blocks and dominators.
202 ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, false, true, false);
203 ArrayList<Node> redundantInits = new ArrayList<>();
204 for (ConstantNode node : getConstantNodes(graph)) {
205 JavaConstant constant = node.asJavaConstant();
206 if (constant instanceof HotSpotMetaspaceConstant) {
207 redundantInits.addAll(processConstantNode(cfg, node));
208 }
209 }
210 // Remove redundant instances of {@link InitializeKlassNode} from the graph.
211 for (Node n : redundantInits) {
212 graph.removeFixed((FixedWithNextNode) n);
213 }
214 }
215
216 @Override
217 protected void run(StructuredGraph graph, PhaseContext context) {
218 removeInitsAtStaticCalls(graph);
219 removeRedundantInits(graph);
220 }
221 }