# HG changeset patch
# User Bernhard Urban <bernhard.urban@jku.at>
# Date 1368453341 -7200
# Node ID 822adbb2ee7b38a95078a067172bc49c6a247820
# Parent  eade47d311a33a76a332e28db15ca262faa5cfc3
CFGVerifier: verify post-dominator calculation

verified against changeset 902a974d55c8, where post-dominator
calculation was bogus.

diff -r eade47d311a3 -r 822adbb2ee7b graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SimpleCFGTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SimpleCFGTest.java	Mon May 13 14:17:35 2013 +0200
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SimpleCFGTest.java	Mon May 13 15:55:41 2013 +0200
@@ -22,14 +22,23 @@
  */
 package com.oracle.graal.compiler.test;
 
-import static org.junit.Assert.*;
-
 import org.junit.*;
 
+import com.oracle.graal.debug.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.cfg.*;
 
-public class SimpleCFGTest {
+public class SimpleCFGTest extends GraalCompilerTest {
+
+    private static void dumpGraph(final StructuredGraph graph) {
+        Debug.scope("SimpleCFGTest", new Runnable() {
+
+            @Override
+            public void run() {
+                Debug.dump(graph, "Graph");
+            }
+        });
+    }
 
     @Test
     public void testImplies() {
@@ -52,6 +61,8 @@
         ReturnNode returnNode = graph.add(new ReturnNode(null));
         merge.setNext(returnNode);
 
+        dumpGraph(graph);
+
         ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true);
 
         Block[] blocks = cfg.getBlocks();
@@ -88,15 +99,15 @@
     }
 
     public static void assertDominator(Block block, Block expectedDominator) {
-        assertEquals("dominator of " + block, expectedDominator, block.getDominator());
+        Assert.assertEquals("dominator of " + block, expectedDominator, block.getDominator());
     }
 
     public static void assertDominatedSize(Block block, int size) {
-        assertEquals("number of dominated blocks of " + block, size, block.getDominated().size());
+        Assert.assertEquals("number of dominated blocks of " + block, size, block.getDominated().size());
     }
 
     public static void assertPostdominator(Block block, Block expectedPostdominator) {
-        assertEquals("postdominator of " + block, expectedPostdominator, block.getPostdominator());
+        Assert.assertEquals("postdominator of " + block, expectedPostdominator, block.getPostdominator());
     }
 
 }
diff -r eade47d311a3 -r 822adbb2ee7b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/CFGVerifier.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/CFGVerifier.java	Mon May 13 14:17:35 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/CFGVerifier.java	Mon May 13 15:55:41 2013 +0200
@@ -22,6 +22,8 @@
  */
 package com.oracle.graal.nodes.cfg;
 
+import java.util.*;
+
 public class CFGVerifier {
 
     public static boolean verify(ControlFlowGraph cfg) {
@@ -48,6 +50,36 @@
                 assert dominated.getDominator() == block;
             }
 
+            Block postDominatorBlock = block.getPostdominator();
+            if (postDominatorBlock != null) {
+                assert block.getSuccessorCount() > 0 : "block has post-dominator block, but no successors";
+
+                BlockMap<Boolean> visitedBlocks = new BlockMap<>(cfg);
+                visitedBlocks.put(block, true);
+
+                Deque<Block> stack = new ArrayDeque<>();
+                for (Block sux : block.getSuccessors()) {
+                    visitedBlocks.put(sux, true);
+                    stack.push(sux);
+                }
+
+                while (stack.size() > 0) {
+                    Block tos = stack.pop();
+                    assert tos.getId() <= postDominatorBlock.getId();
+                    if (tos == postDominatorBlock) {
+                        continue; // found a valid path
+                    }
+                    assert tos.getSuccessorCount() > 0 : "no path found";
+
+                    for (Block sux : tos.getSuccessors()) {
+                        if (visitedBlocks.get(sux) == null) {
+                            visitedBlocks.put(sux, true);
+                            stack.push(sux);
+                        }
+                    }
+                }
+            }
+
             assert cfg.getLoops() == null || !block.isLoopHeader() || block.getLoop().header == block : block.beginNode;
         }