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 }