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.phases.common; 26 27 import org.graalvm.compiler.debug.CounterKey; 28 import org.graalvm.compiler.debug.DebugContext; 29 import org.graalvm.compiler.graph.Node; 30 import org.graalvm.compiler.graph.NodeFlood; 31 import org.graalvm.compiler.nodes.AbstractEndNode; 32 import org.graalvm.compiler.nodes.GuardNode; 33 import org.graalvm.compiler.nodes.StructuredGraph; 34 import org.graalvm.compiler.options.Option; 35 import org.graalvm.compiler.options.OptionKey; 36 import org.graalvm.compiler.options.OptionType; 37 import org.graalvm.compiler.phases.Phase; 38 39 public class DeadCodeEliminationPhase extends Phase { 40 41 public static class Options { 42 43 // @formatter:off 44 @Option(help = "Disable optional dead code eliminations", type = OptionType.Debug) 45 public static final OptionKey<Boolean> ReduceDCE = new OptionKey<>(true); 46 // @formatter:on 47 } 48 49 private static final CounterKey counterNodesRemoved = DebugContext.counter("NodesRemoved"); 50 51 public enum Optionality { 52 Optional, 53 Required; 54 } 55 56 /** 57 * Creates a dead code elimination phase that will be run irrespective of 58 * {@link Options#ReduceDCE}. 59 */ DeadCodeEliminationPhase()60 public DeadCodeEliminationPhase() { 61 this(Optionality.Required); 62 } 63 64 /** 65 * Creates a dead code elimination phase that will be run only if it is 66 * {@linkplain Optionality#Required non-optional} or {@link Options#ReduceDCE} is false. 67 */ DeadCodeEliminationPhase(Optionality optionality)68 public DeadCodeEliminationPhase(Optionality optionality) { 69 this.optional = optionality == Optionality.Optional; 70 } 71 72 private final boolean optional; 73 74 @Override run(StructuredGraph graph)75 public void run(StructuredGraph graph) { 76 if (optional && Options.ReduceDCE.getValue(graph.getOptions())) { 77 return; 78 } 79 80 NodeFlood flood = graph.createNodeFlood(); 81 int totalNodeCount = graph.getNodeCount(); 82 flood.add(graph.start()); 83 iterateSuccessorsAndInputs(flood); 84 boolean changed = false; 85 for (GuardNode guard : graph.getNodes(GuardNode.TYPE)) { 86 if (flood.isMarked(guard.getAnchor().asNode())) { 87 flood.add(guard); 88 changed = true; 89 } 90 } 91 if (changed) { 92 iterateSuccessorsAndInputs(flood); 93 } 94 int totalMarkedCount = flood.getTotalMarkedCount(); 95 if (totalNodeCount == totalMarkedCount) { 96 // All nodes are live => nothing more to do. 97 return; 98 } else { 99 // Some nodes are not marked alive and therefore dead => proceed. 100 assert totalNodeCount > totalMarkedCount; 101 } 102 103 deleteNodes(flood, graph); 104 } 105 iterateSuccessorsAndInputs(NodeFlood flood)106 private static void iterateSuccessorsAndInputs(NodeFlood flood) { 107 Node.EdgeVisitor consumer = new Node.EdgeVisitor() { 108 @Override 109 public Node apply(Node n, Node succOrInput) { 110 assert succOrInput.isAlive() : "dead successor or input " + succOrInput + " in " + n; 111 flood.add(succOrInput); 112 return succOrInput; 113 } 114 }; 115 116 for (Node current : flood) { 117 if (current instanceof AbstractEndNode) { 118 AbstractEndNode end = (AbstractEndNode) current; 119 flood.add(end.merge()); 120 } else { 121 current.applySuccessors(consumer); 122 current.applyInputs(consumer); 123 } 124 } 125 } 126 deleteNodes(NodeFlood flood, StructuredGraph graph)127 private static void deleteNodes(NodeFlood flood, StructuredGraph graph) { 128 Node.EdgeVisitor consumer = new Node.EdgeVisitor() { 129 @Override 130 public Node apply(Node n, Node input) { 131 if (input.isAlive() && flood.isMarked(input)) { 132 input.removeUsage(n); 133 } 134 return input; 135 } 136 }; 137 138 DebugContext debug = graph.getDebug(); 139 for (Node node : graph.getNodes()) { 140 if (!flood.isMarked(node)) { 141 node.markDeleted(); 142 node.applyInputs(consumer); 143 counterNodesRemoved.increment(debug); 144 } 145 } 146 } 147 } 148