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 }