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