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