1 /*
   2  * Copyright (c) 2011, 2014, 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.graph;
  24 
  25 import java.util.ArrayDeque;
  26 import java.util.Deque;
  27 
  28 import org.graalvm.compiler.graph.Node;
  29 import org.graalvm.compiler.graph.NodeBitMap;
  30 import org.graalvm.compiler.nodes.AbstractBeginNode;
  31 import org.graalvm.compiler.nodes.AbstractMergeNode;
  32 import org.graalvm.compiler.nodes.ControlSinkNode;
  33 import org.graalvm.compiler.nodes.ControlSplitNode;
  34 import org.graalvm.compiler.nodes.EndNode;
  35 import org.graalvm.compiler.nodes.FixedNode;
  36 import org.graalvm.compiler.nodes.FixedWithNextNode;
  37 import org.graalvm.compiler.nodes.LoopBeginNode;
  38 import org.graalvm.compiler.nodes.LoopEndNode;
  39 
  40 /**
  41  * This iterator implements a reverse post order iteration over the fixed nodes in the graph,
  42  * starting at the given fixed node.
  43  *
  44  * No changes to the fixed nodes are expected during the iteration, they cause undefined behavior.
  45  */
  46 public abstract class StatelessPostOrderNodeIterator {
  47 
  48     private final NodeBitMap visitedEnds;
  49     private final Deque<AbstractBeginNode> nodeQueue;
  50     private final FixedNode start;
  51 
  52     public StatelessPostOrderNodeIterator(FixedNode start) {
  53         visitedEnds = start.graph().createNodeBitMap();
  54         nodeQueue = new ArrayDeque<>();
  55         this.start = start;
  56     }
  57 
  58     public void apply() {
  59         FixedNode current = start;
  60 
  61         do {
  62             if (current instanceof LoopBeginNode) {
  63                 loopBegin((LoopBeginNode) current);
  64                 current = ((LoopBeginNode) current).next();
  65                 assert current != null;
  66             } else if (current instanceof LoopEndNode) {
  67                 loopEnd((LoopEndNode) current);
  68                 assert !visitedEnds.isMarked(current);
  69                 visitedEnds.mark(current);
  70                 current = nodeQueue.pollFirst();
  71             } else if (current instanceof AbstractMergeNode) {
  72                 merge((AbstractMergeNode) current);
  73                 current = ((AbstractMergeNode) current).next();
  74                 assert current != null;
  75             } else if (current instanceof FixedWithNextNode) {
  76                 node(current);
  77                 current = ((FixedWithNextNode) current).next();
  78             } else if (current instanceof EndNode) {
  79                 end((EndNode) current);
  80                 queueMerge((EndNode) current);
  81                 current = nodeQueue.pollFirst();
  82             } else if (current instanceof ControlSinkNode) {
  83                 node(current);
  84                 current = nodeQueue.pollFirst();
  85             } else if (current instanceof ControlSplitNode) {
  86                 controlSplit((ControlSplitNode) current);
  87                 for (Node node : current.successors()) {
  88                     nodeQueue.addFirst((AbstractBeginNode) node);
  89                 }
  90                 current = nodeQueue.pollFirst();
  91             } else {
  92                 assert false : current;
  93             }
  94         } while (current != null);
  95         finished();
  96     }
  97 
  98     private void queueMerge(EndNode end) {
  99         assert !visitedEnds.isMarked(end);
 100         visitedEnds.mark(end);
 101         AbstractMergeNode merge = end.merge();
 102         boolean endsVisited = true;
 103         for (int i = 0; i < merge.forwardEndCount(); i++) {
 104             if (!visitedEnds.isMarked(merge.forwardEndAt(i))) {
 105                 endsVisited = false;
 106                 break;
 107             }
 108         }
 109         if (endsVisited) {
 110             nodeQueue.add(merge);
 111         }
 112     }
 113 
 114     protected void node(@SuppressWarnings("unused") FixedNode node) {
 115         // empty default implementation
 116     }
 117 
 118     protected void end(EndNode endNode) {
 119         node(endNode);
 120     }
 121 
 122     protected void merge(AbstractMergeNode merge) {
 123         node(merge);
 124     }
 125 
 126     protected void loopBegin(LoopBeginNode loopBegin) {
 127         node(loopBegin);
 128     }
 129 
 130     protected void loopEnd(LoopEndNode loopEnd) {
 131         node(loopEnd);
 132     }
 133 
 134     protected void controlSplit(ControlSplitNode controlSplit) {
 135         node(controlSplit);
 136     }
 137 
 138     protected void finished() {
 139         // nothing to do
 140     }
 141 }