# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1429545927 -7200
# Node ID f226f63af996eae1e0e190eaddc3646be2ec8b24
# Parent  da2b2d3edeeb9ac4ab787d2d9b35203cace77a0e
Add SSAVerifier.

diff -r da2b2d3edeeb -r f226f63af996 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java	Mon Apr 20 17:30:30 2015 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java	Mon Apr 20 18:05:27 2015 +0200
@@ -22,6 +22,8 @@
  */
 package com.oracle.graal.compiler;
 
+import static com.oracle.graal.compiler.common.GraalOptions.*;
+
 import java.util.*;
 
 import com.oracle.graal.api.code.*;
@@ -29,6 +31,7 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.lir.phases.*;
+import com.oracle.graal.lir.ssa.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.cfg.*;
 import com.oracle.graal.nodes.spi.*;
@@ -60,6 +63,7 @@
             emitBlock(nodeLirBuilder, lirGenRes, (Block) b, graph, schedule.getBlockToNodesMap());
         }
         context.lirGen.beforeRegisterAllocation();
+        assert !SSA_LIR.getValue() || SSAUtils.verifySSAForm(lirGenRes.getLIR());
     }
 
     private static void emitBlock(NodeLIRBuilderTool nodeLirGen, LIRGenerationResult lirGenRes, Block b, StructuredGraph graph, BlockMap<List<Node>> blockMap) {
diff -r da2b2d3edeeb -r f226f63af996 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAUtils.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAUtils.java	Mon Apr 20 17:30:30 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAUtils.java	Mon Apr 20 18:05:27 2015 +0200
@@ -53,14 +53,14 @@
  *   v0|i = ...
  *   JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1
  * ________________________________________________
- * 
+ *
  * B2 -> B1
  *   ...
  *   v1|i = ...
  *   v2|i = ...
  *   JUMP ~[v1|i, v2|i] destination: B2 -> B1
  * ________________________________________________
- * 
+ *
  * B1 <- B0,B2
  *   [v3|i, v4|i] = LABEL
  *   ...
@@ -99,4 +99,8 @@
         }
     }
 
+    public static boolean verifySSAForm(LIR lir) {
+        return new SSAVerifier(lir).verify();
+    }
+
 }
diff -r da2b2d3edeeb -r f226f63af996 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAVerifier.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAVerifier.java	Mon Apr 20 18:05:27 2015 +0200
@@ -0,0 +1,137 @@
+/*
+ * Copyright (c) 2015, 2015, 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.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package com.oracle.graal.lir.ssa;
+
+import static com.oracle.graal.api.code.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.debug.Debug.Scope;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.OperandFlag;
+import com.oracle.graal.lir.LIRInstruction.OperandMode;
+
+final class SSAVerifier {
+    private static class Entry {
+        private final LIRInstruction inst;
+        private final AbstractBlockBase<?> block;
+
+        Entry(LIRInstruction inst, AbstractBlockBase<?> block) {
+            this.inst = inst;
+            this.block = block;
+        }
+    }
+
+    private final LIR lir;
+    private final BitSet visited;
+    private final HashMap<Value, Entry> defined;
+    private AbstractBlockBase<?> currentBlock;
+
+    SSAVerifier(LIR lir) {
+        this.lir = lir;
+        this.visited = new BitSet(lir.getControlFlowGraph().getBlocks().size());
+        this.defined = new HashMap<>();
+    }
+
+    public boolean verify() {
+        // init();
+        try (Scope s = Debug.scope("SSAVerifier", lir)) {
+            for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
+                doBlock(block);
+            }
+        } catch (Throwable e) {
+            throw Debug.handle(e);
+        }
+        return true;
+    }
+
+    private void doBlock(AbstractBlockBase<?> b) {
+        if (visited.get(b.getId())) {
+            return;
+        }
+        for (AbstractBlockBase<?> pred : b.getPredecessors()) {
+            if (!b.isLoopHeader() || !pred.isLoopEnd()) {
+                doBlock(pred);
+            }
+        }
+        try (Indent indent = Debug.logAndIndent("handle block %s", b)) {
+            assert verifyBlock(b);
+        }
+    }
+
+    private boolean verifyBlock(AbstractBlockBase<?> block) {
+        currentBlock = block;
+        assert !visited.get(block.getId()) : "Block already visited: " + block;
+        visited.set(block.getId());
+        for (LIRInstruction op : lir.getLIRforBlock(block)) {
+            op.visitEachAlive(this::useConsumer);
+            /*
+             * TODO(je) we are currently skipping LIRFrameStates because there are problems with
+             * eliminated StackLockValue. (The slot is not defined but we can't tell that the lock
+             * is eliminated.)
+             */
+            // op.visitEachState(this::useConsumer);
+            op.visitEachInput(this::useConsumer);
+
+            op.visitEachTemp(this::defConsumer);
+            op.visitEachOutput(this::defConsumer);
+
+        }
+        currentBlock = null;
+        return true;
+    }
+
+    /**
+     * @see InstructionValueConsumer
+     * @param mode
+     * @param flags
+     */
+    private void useConsumer(LIRInstruction inst, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
+        if (shouldProcess(value)) {
+            assert defined.keySet().contains(value) || flags.contains(OperandFlag.UNINITIALIZED) : String.format("Value %s used at instruction %s in block %s but never defined", value, inst,
+                            currentBlock);
+        }
+    }
+
+    /**
+     * @see InstructionValueConsumer
+     * @param mode
+     * @param flags
+     */
+    private void defConsumer(LIRInstruction inst, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
+        if (shouldProcess(value)) {
+            assert !defined.keySet().contains(value) : String.format("Value %s redefined at %s but never defined (previous definition %s in block %s)", value, inst, defined.get(value).inst,
+                            defined.get(value).block);
+            defined.put(value, new Entry(inst, currentBlock));
+        }
+    }
+
+    private static boolean shouldProcess(Value value) {
+        return !value.equals(Value.ILLEGAL) && !isConstant(value) && !isRegister(value);
+    }
+
+}