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