src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.nodes/src/org/graalvm/compiler/nodes/cfg/ControlFlowGraph.java

*** 1,7 ****
  /*
!  * Copyright (c) 2011, 2016, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.
--- 1,7 ----
  /*
!  * Copyright (c) 2011, 2017, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.
*** 22,32 ****
   */
  package org.graalvm.compiler.nodes.cfg;
  
  import java.util.ArrayList;
  import java.util.Arrays;
! import java.util.Collections;
  import java.util.List;
  
  import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
  import org.graalvm.compiler.core.common.cfg.CFGVerifier;
  import org.graalvm.compiler.core.common.cfg.Loop;
--- 22,32 ----
   */
  package org.graalvm.compiler.nodes.cfg;
  
  import java.util.ArrayList;
  import java.util.Arrays;
! import java.util.BitSet;
  import java.util.List;
  
  import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
  import org.graalvm.compiler.core.common.cfg.CFGVerifier;
  import org.graalvm.compiler.core.common.cfg.Loop;
*** 34,43 ****
--- 34,44 ----
  import org.graalvm.compiler.debug.GraalError;
  import org.graalvm.compiler.graph.Node;
  import org.graalvm.compiler.graph.NodeMap;
  import org.graalvm.compiler.nodes.AbstractBeginNode;
  import org.graalvm.compiler.nodes.AbstractEndNode;
+ import org.graalvm.compiler.nodes.ControlSinkNode;
  import org.graalvm.compiler.nodes.ControlSplitNode;
  import org.graalvm.compiler.nodes.EndNode;
  import org.graalvm.compiler.nodes.FixedNode;
  import org.graalvm.compiler.nodes.FixedWithNextNode;
  import org.graalvm.compiler.nodes.IfNode;
*** 62,71 ****
--- 63,79 ----
      public final StructuredGraph graph;
  
      private NodeMap<Block> nodeToBlock;
      private Block[] reversePostOrder;
      private List<Loop<Block>> loops;
+     private int maxDominatorDepth;
+ 
+     public interface RecursiveVisitor<V> {
+         V enter(Block b);
+ 
+         void exit(Block b, V value);
+     }
  
      public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) {
          ControlFlowGraph cfg = new ControlFlowGraph(graph);
          cfg.identifyBlocks();
          cfg.computeProbabilities();
*** 77,115 ****
              cfg.computeDominators();
          }
          if (computePostdominators) {
              cfg.computePostdominators();
          }
          // there's not much to verify when connectBlocks == false
          assert !(connectBlocks || computeLoops || computeDominators || computePostdominators) || CFGVerifier.verify(cfg);
          return cfg;
      }
  
      private ControlFlowGraph(StructuredGraph graph) {
          this.graph = graph;
          this.nodeToBlock = graph.createNodeMap();
      }
  
      private void computeDominators() {
          assert reversePostOrder[0].getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator";
          Block[] blocks = reversePostOrder;
          for (int i = 1; i < blocks.length; i++) {
              Block block = blocks[i];
              assert block.getPredecessorCount() > 0;
              Block dominator = null;
              for (Block pred : block.getPredecessors()) {
                  if (!pred.isLoopEnd()) {
                      dominator = ((dominator == null) ? pred : commonDominatorRaw(dominator, pred));
                  }
              }
!             // set dominator
              block.setDominator(dominator);
!             if (dominator.getDominated().equals(Collections.emptyList())) {
!                 dominator.setDominated(new ArrayList<>());
              }
!             dominator.getDominated().add(block);
          }
          calcDominatorRanges(getStartBlock(), reversePostOrder.length);
      }
  
      private static void calcDominatorRanges(Block block, int size) {
          Block[] stack = new Block[size];
--- 85,333 ----
              cfg.computeDominators();
          }
          if (computePostdominators) {
              cfg.computePostdominators();
          }
+ 
          // there's not much to verify when connectBlocks == false
          assert !(connectBlocks || computeLoops || computeDominators || computePostdominators) || CFGVerifier.verify(cfg);
          return cfg;
      }
  
+     public String dominatorTreeString() {
+         return dominatorTreeString(getStartBlock());
+     }
+ 
+     private static String dominatorTreeString(Block b) {
+         StringBuilder sb = new StringBuilder();
+         sb.append(b);
+         sb.append("(");
+         Block firstDominated = b.getFirstDominated();
+         while (firstDominated != null) {
+             if (firstDominated.getDominator().getPostdominator() == firstDominated) {
+                 sb.append("!");
+             }
+             sb.append(dominatorTreeString(firstDominated));
+             firstDominated = firstDominated.getDominatedSibling();
+         }
+         sb.append(") ");
+         return sb.toString();
+     }
+ 
+     @SuppressWarnings("unchecked")
+     public <V> void visitDominatorTreeDefault(RecursiveVisitor<V> visitor) {
+ 
+         Block[] stack = new Block[maxDominatorDepth + 1];
+         Block current = getStartBlock();
+         int tos = 0;
+         Object[] values = null;
+         int valuesTOS = 0;
+ 
+         while (tos >= 0) {
+             Block state = stack[tos];
+             if (state == null || state.getDominator() == null || state.getDominator().getPostdominator() != state) {
+                 if (state == null) {
+                     // We enter this block for the first time.
+                     V value = visitor.enter(current);
+                     if (value != null || values != null) {
+                         if (values == null) {
+                             values = new Object[maxDominatorDepth + 1];
+                         }
+                         values[valuesTOS++] = value;
+                     }
+ 
+                     Block dominated = skipPostDom(current.getFirstDominated());
+                     if (dominated != null) {
+                         // Descend into dominated.
+                         stack[tos] = dominated;
+                         current = dominated;
+                         stack[++tos] = null;
+                         continue;
+                     }
+                 } else {
+                     Block next = skipPostDom(state.getDominatedSibling());
+                     if (next != null) {
+                         // Descend into dominated.
+                         stack[tos] = next;
+                         current = next;
+                         stack[++tos] = null;
+                         continue;
+                     }
+                 }
+ 
+                 // Finished processing all normal dominators.
+                 Block postDom = current.getPostdominator();
+                 if (postDom != null && postDom.getDominator() == current) {
+                     // Descend into post dominator.
+                     stack[tos] = postDom;
+                     current = postDom;
+                     stack[++tos] = null;
+                     continue;
+                 }
+             }
+ 
+             // Finished processing this node, exit and pop from stack.
+             V value = null;
+             if (values != null && valuesTOS > 0) {
+                 value = (V) values[--valuesTOS];
+             }
+             visitor.exit(current, value);
+             current = current.getDominator();
+             --tos;
+         }
+     }
+ 
+     private static Block skipPostDom(Block block) {
+         if (block != null && block.getDominator().getPostdominator() == block) {
+             // This is an always reached block.
+             return block.getDominatedSibling();
+         }
+         return block;
+     }
+ 
+     private static final class DeferredExit {
+ 
+         private DeferredExit(Block block, DeferredExit next) {
+             this.block = block;
+             this.next = next;
+         }
+ 
+         private final Block block;
+         private final DeferredExit next;
+     }
+ 
+     private static void addDeferredExit(DeferredExit[] deferredExits, Block b) {
+         Loop<Block> outermostExited = b.getDominator().getLoop();
+         Loop<Block> exitBlockLoop = b.getLoop();
+         assert outermostExited != null;
+         while (outermostExited.getParent() != null && outermostExited.getParent() != exitBlockLoop) {
+             outermostExited = outermostExited.getParent();
+         }
+         int loopIndex = outermostExited.getIndex();
+         deferredExits[loopIndex] = new DeferredExit(b, deferredExits[loopIndex]);
+     }
+ 
+     @SuppressWarnings({"unchecked"})
+     public <V> void visitDominatorTreeDeferLoopExits(RecursiveVisitor<V> visitor) {
+         Block[] stack = new Block[getBlocks().length];
+         int tos = 0;
+         BitSet visited = new BitSet(getBlocks().length);
+         int loopCount = getLoops().size();
+         DeferredExit[] deferredExits = new DeferredExit[loopCount];
+         Object[] values = null;
+         int valuesTOS = 0;
+         stack[0] = getStartBlock();
+ 
+         while (tos >= 0) {
+             Block cur = stack[tos];
+             int curId = cur.getId();
+             if (visited.get(curId)) {
+                 V value = null;
+                 if (values != null && valuesTOS > 0) {
+                     value = (V) values[--valuesTOS];
+                 }
+                 visitor.exit(cur, value);
+                 --tos;
+                 if (cur.isLoopHeader()) {
+                     int loopIndex = cur.getLoop().getIndex();
+                     DeferredExit deferredExit = deferredExits[loopIndex];
+                     if (deferredExit != null) {
+                         while (deferredExit != null) {
+                             stack[++tos] = deferredExit.block;
+                             deferredExit = deferredExit.next;
+                         }
+                         deferredExits[loopIndex] = null;
+                     }
+                 }
+             } else {
+                 visited.set(curId);
+                 V value = visitor.enter(cur);
+                 if (value != null || values != null) {
+                     if (values == null) {
+                         values = new Object[maxDominatorDepth + 1];
+                     }
+                     values[valuesTOS++] = value;
+                 }
+ 
+                 Block alwaysReached = cur.getPostdominator();
+                 if (alwaysReached != null) {
+                     if (alwaysReached.getDominator() != cur) {
+                         alwaysReached = null;
+                     } else if (isDominatorTreeLoopExit(alwaysReached)) {
+                         addDeferredExit(deferredExits, alwaysReached);
+                     } else {
+                         stack[++tos] = alwaysReached;
+                     }
+                 }
+ 
+                 Block b = cur.getFirstDominated();
+                 while (b != null) {
+                     if (b != alwaysReached) {
+                         if (isDominatorTreeLoopExit(b)) {
+                             addDeferredExit(deferredExits, b);
+                         } else {
+                             stack[++tos] = b;
+                         }
+                     }
+                     b = b.getDominatedSibling();
+                 }
+             }
+         }
+     }
+ 
+     public <V> void visitDominatorTree(RecursiveVisitor<V> visitor, boolean deferLoopExits) {
+         if (deferLoopExits && this.getLoops().size() > 0) {
+             visitDominatorTreeDeferLoopExits(visitor);
+         } else {
+             visitDominatorTreeDefault(visitor);
+         }
+     }
+ 
+     private static boolean isDominatorTreeLoopExit(Block b) {
+         Block dominator = b.getDominator();
+         return dominator != null && b.getLoop() != dominator.getLoop() && (!b.isLoopHeader() || dominator.getLoopDepth() >= b.getLoopDepth());
+     }
+ 
      private ControlFlowGraph(StructuredGraph graph) {
          this.graph = graph;
          this.nodeToBlock = graph.createNodeMap();
      }
  
      private void computeDominators() {
          assert reversePostOrder[0].getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator";
          Block[] blocks = reversePostOrder;
+         int curMaxDominatorDepth = 0;
          for (int i = 1; i < blocks.length; i++) {
              Block block = blocks[i];
              assert block.getPredecessorCount() > 0;
              Block dominator = null;
              for (Block pred : block.getPredecessors()) {
                  if (!pred.isLoopEnd()) {
                      dominator = ((dominator == null) ? pred : commonDominatorRaw(dominator, pred));
                  }
              }
! 
!             // Set dominator.
              block.setDominator(dominator);
! 
!             // Keep dominated linked list sorted by block ID such that predecessor blocks are always
!             // before successor blocks.
!             Block currentDominated = dominator.getFirstDominated();
!             if (currentDominated != null && currentDominated.getId() < block.getId()) {
!                 while (currentDominated.getDominatedSibling() != null && currentDominated.getDominatedSibling().getId() < block.getId()) {
!                     currentDominated = currentDominated.getDominatedSibling();
                  }
!                 block.setDominatedSibling(currentDominated.getDominatedSibling());
!                 currentDominated.setDominatedSibling(block);
!             } else {
!                 block.setDominatedSibling(dominator.getFirstDominated());
!                 dominator.setFirstDominated(block);
!             }
! 
!             curMaxDominatorDepth = Math.max(curMaxDominatorDepth, block.getDominatorDepth());
          }
+         this.maxDominatorDepth = curMaxDominatorDepth;
          calcDominatorRanges(getStartBlock(), reversePostOrder.length);
      }
  
      private static void calcDominatorRanges(Block block, int size) {
          Block[] stack = new Block[size];
*** 117,142 ****
          int tos = 0;
          int myNumber = 0;
  
          do {
              Block cur = stack[tos];
!             List<Block> dominated = cur.getDominated();
  
              if (cur.getDominatorNumber() == -1) {
                  cur.setDominatorNumber(myNumber);
!                 if (dominated.size() > 0) {
                      // Push children onto stack.
!                     for (Block b : dominated) {
!                         stack[++tos] = b;
!                     }
                  } else {
                      cur.setMaxChildDomNumber(myNumber);
                      --tos;
                  }
                  ++myNumber;
              } else {
!                 cur.setMaxChildDomNumber(dominated.get(0).getMaxChildDominatorNumber());
                  --tos;
              }
          } while (tos >= 0);
      }
  
--- 335,361 ----
          int tos = 0;
          int myNumber = 0;
  
          do {
              Block cur = stack[tos];
!             Block dominated = cur.getFirstDominated();
  
              if (cur.getDominatorNumber() == -1) {
                  cur.setDominatorNumber(myNumber);
!                 if (dominated != null) {
                      // Push children onto stack.
!                     do {
!                         stack[++tos] = dominated;
!                         dominated = dominated.getDominatedSibling();
!                     } while (dominated != null);
                  } else {
                      cur.setMaxChildDomNumber(myNumber);
                      --tos;
                  }
                  ++myNumber;
              } else {
!                 cur.setMaxChildDomNumber(dominated.getMaxChildDominatorNumber());
                  --tos;
              }
          } while (tos >= 0);
      }
  
*** 253,262 ****
--- 472,483 ----
                      falseSucc.setPredecessors(ifPred);
                  } else if (last instanceof LoopEndNode) {
                      LoopEndNode loopEndNode = (LoopEndNode) last;
                      block.setSuccessors(new Block[]{nodeMap.get(loopEndNode.loopBegin())});
                      // Nothing to do push onto the stack.
+                 } else if (last instanceof ControlSinkNode) {
+                     block.setSuccessors(Block.EMPTY_ARRAY);
                  } else {
                      assert !(last instanceof AbstractEndNode) : "Algorithm only supports EndNode and LoopEndNode.";
                      int startTos = tos;
                      Block[] ifPred = new Block[]{block};
                      for (Node suxNode : last.successors()) {
*** 340,355 ****
                      LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
                      probability *= loopBegin.loopFrequency();
                  }
              }
              if (probability < MIN_PROBABILITY) {
!                 block.setProbability(MIN_PROBABILITY);
              } else if (probability > MAX_PROBABILITY) {
!                 block.setProbability(MAX_PROBABILITY);
!             } else {
!                 block.setProbability(probability);
              }
          }
  
      }
  
      private void computeLoopInformation() {
--- 561,575 ----
                      LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
                      probability *= loopBegin.loopFrequency();
                  }
              }
              if (probability < MIN_PROBABILITY) {
!                 probability = MIN_PROBABILITY;
              } else if (probability > MAX_PROBABILITY) {
!                 probability = MAX_PROBABILITY;
              }
+             block.setProbability(probability);
          }
  
      }
  
      private void computeLoopInformation() {
*** 469,479 ****
      }
  
      public void computePostdominators() {
  
          Block[] reversePostOrderTmp = this.reversePostOrder;
- 
          outer: for (int j = reversePostOrderTmp.length - 1; j >= 0; --j) {
              Block block = reversePostOrderTmp[j];
              if (block.isLoopEnd()) {
                  // We do not want the loop header registered as the postdominator of the loop end.
                  continue;
--- 689,698 ----
*** 494,504 ****
                      // There is a dead end => no postdominator available.
                      continue outer;
                  }
              }
              assert !Arrays.asList(block.getSuccessors()).contains(postdominator) : "Block " + block + " has a wrong post dominator: " + postdominator;
!             block.postdominator = postdominator;
          }
      }
  
      private static Block commonPostdominator(Block a, Block b) {
          Block iterA = a;
--- 713,723 ----
                      // There is a dead end => no postdominator available.
                      continue outer;
                  }
              }
              assert !Arrays.asList(block.getSuccessors()).contains(postdominator) : "Block " + block + " has a wrong post dominator: " + postdominator;
!             block.setPostDominator(postdominator);
          }
      }
  
      private static Block commonPostdominator(Block a, Block b) {
          Block iterA = a;