--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompiler.java	Mon Feb 20 14:28:39 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompiler.java	Mon Feb 20 14:29:51 2012 +0100
@@ -36,6 +36,7 @@
 import com.oracle.max.graal.compiler.phases.PhasePlan.PhasePosition;
 import com.oracle.max.graal.compiler.schedule.*;
 import com.oracle.max.graal.compiler.target.*;
+import com.oracle.max.graal.compiler.types.*;
 import com.oracle.max.graal.cri.*;
 import com.oracle.max.graal.debug.*;
 import com.oracle.max.graal.lir.*;
@@ -144,6 +145,14 @@
             new IntrinsificationPhase(runtime).apply(graph);
         }
 
+        if (GraalOptions.PropagateTypes) {
+            if (GraalOptions.OptCanonicalizer) {
+                new CanonicalizerPhase(target, runtime, assumptions).apply(graph);
+            }
+
+            new PropagateTypesPhase(target, runtime, assumptions).apply(graph);
+        }
+
         if (GraalOptions.Inline && !plan.isPhaseDisabled(InliningPhase.class)) {
             new InliningPhase(target, runtime, null, assumptions, plan).apply(graph);
             new DeadCodeEliminationPhase().apply(graph);
@@ -154,6 +163,10 @@
             new CanonicalizerPhase(target, runtime, assumptions).apply(graph);
         }
 
+        if (GraalOptions.PropagateTypes) {
+            new PropagateTypesPhase(target, runtime, assumptions).apply(graph);
+        }
+
         plan.runPhases(PhasePosition.HIGH_LEVEL, graph);
 
         if (GraalOptions.OptLoops) {

--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Mon Feb 20 14:28:39 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Mon Feb 20 14:29:51 2012 +0100
@@ -141,6 +141,7 @@
     public static boolean AssumeVerifiedBytecode             = true;
 
     // Code generator settings
+    public static boolean PropagateTypes                     = true;
     public static boolean UseBranchPrediction                = true;
     public static boolean UseExceptionProbability            = true;
     public static boolean AllowExplicitExceptionChecks       = true;

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/types/PostOrderBlockIterator.java	Mon Feb 20 14:29:51 2012 +0100
@@ -0,0 +1,68 @@
+/*
+ * Copyright (c) 2011, 2012, 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.max.graal.compiler.types;
+
+import java.util.*;
+
+import com.oracle.max.graal.graph.*;
+import com.oracle.max.graal.lir.cfg.*;
+
+public abstract class PostOrderBlockIterator {
+
+    private final BitMap visitedEndBlocks;
+    private final Deque<Block> blockQueue;
+
+    public PostOrderBlockIterator(Block start, int blockCount) {
+        visitedEndBlocks = new BitMap(blockCount);
+        blockQueue = new ArrayDeque<>();
+        blockQueue.add(start);
+    }
+
+    public void apply() {
+        while (!blockQueue.isEmpty()) {
+            Block current = blockQueue.removeLast();
+            block(current);
+
+            for (int i = 0; i < current.getSuccessors().size(); i++) {
+                Block successor = current.getSuccessors().get(i);
+                if (successor.getPredecessors().size() > 1) {
+                    queueMerge(current, successor);
+                } else {
+                    blockQueue.addLast(successor);
+                }
+            }
+        }
+    }
+
+    protected abstract void block(Block block);
+
+    private void queueMerge(Block end, Block merge) {
+        visitedEndBlocks.set(end.getId());
+        for (Block pred : merge.getPredecessors()) {
+            if (!visitedEndBlocks.get(pred.getId())) {
+                return;
+            }
+        }
+        blockQueue.addFirst(merge);
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/types/PropagateTypesPhase.java	Mon Feb 20 14:29:51 2012 +0100
@@ -0,0 +1,264 @@
+/*
+ * Copyright (c) 2011, 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.max.graal.compiler.types;
+
+import java.util.*;
+import java.util.Map.Entry;
+
+import com.oracle.max.cri.ci.*;
+import com.oracle.max.cri.ri.*;
+import com.oracle.max.graal.compiler.graph.*;
+import com.oracle.max.graal.compiler.phases.*;
+import com.oracle.max.graal.compiler.schedule.*;
+import com.oracle.max.graal.debug.*;
+import com.oracle.max.graal.graph.*;
+import com.oracle.max.graal.graph.NodeClass.NodeClassIterator;
+import com.oracle.max.graal.graph.NodeClass.Position;
+import com.oracle.max.graal.nodes.*;
+import com.oracle.max.graal.nodes.calc.*;
+import com.oracle.max.graal.nodes.java.*;
+import com.oracle.max.graal.nodes.spi.*;
+import com.oracle.max.graal.nodes.type.*;
+
+public class PropagateTypesPhase extends Phase {
+
+    private final CiTarget target;
+    private final RiRuntime runtime;
+    private final CiAssumptions assumptions;
+
+    private NodeWorkList changedNodes;
+
+    public PropagateTypesPhase(CiTarget target, RiRuntime runtime, CiAssumptions assumptions) {
+        this.target = target;
+        this.runtime = runtime;
+        this.assumptions = assumptions;
+    }
+
+    @Override
+    protected void run(StructuredGraph graph) {
+
+        new DeadCodeEliminationPhase().apply(graph);
+
+        changedNodes = graph.createNodeWorkList(false, 10);
+
+        SchedulePhase schedule = new SchedulePhase();
+        schedule.apply(graph);
+
+        schedule.scheduleGraph();
+        Debug.dump(graph, "scheduled");
+
+        new PropagateTypes(graph.start()).apply();
+        Debug.dump(graph, "after propagation");
+
+        new UnscheduleNodes(graph.start()).apply();
+
+        CanonicalizerPhase.canonicalize(graph, changedNodes, runtime, target, assumptions);
+    }
+
+    private class PiNodeList {
+
+        public final PiNodeList last;
+        public final ValueNode replacement;
+        public final int depth;
+
+        public PiNodeList(ValueNode replacement, PiNodeList last) {
+            this.last = last;
+            this.replacement = replacement;
+            this.depth = last != null ? last.depth + 1 : 1;
+        }
+
+        public PiNodeList merge(PiNodeList other) {
+            PiNodeList thisList = this;
+            PiNodeList otherList = other;
+            while (thisList.depth > otherList.depth) {
+                thisList = thisList.last;
+            }
+            while (otherList.depth > thisList.depth) {
+                otherList = otherList.last;
+            }
+            while (thisList != otherList) {
+                thisList = thisList.last;
+                otherList = otherList.last;
+            }
+            return thisList;
+        }
+    }
+
+    private class TypeInfo implements MergeableState<TypeInfo> {
+
+        private HashMap<ValueNode, PiNodeList> piNodes = new HashMap<>();
+
+        public TypeInfo(HashMap<ValueNode, PiNodeList> piNodes) {
+            this.piNodes.putAll(piNodes);
+        }
+
+        @Override
+        public TypeInfo clone() {
+            return new TypeInfo(piNodes);
+        }
+
+        @Override
+        public boolean merge(MergeNode merge, Collection<TypeInfo> withStates) {
+            if (merge.forwardEndCount() > 1) {
+                HashMap<ValueNode, PiNodeList> newPiNodes = new HashMap<>();
+                for (Entry<ValueNode, PiNodeList> entry : piNodes.entrySet()) {
+                    PiNodeList list = entry.getValue();
+                    for (TypeInfo info : withStates) {
+                        PiNodeList other = info.piNodes.get(entry.getKey());
+                        if (other == null) {
+                            list = null;
+                        } else {
+                            list = list.merge(other);
+                        }
+                        if (list == null) {
+                            break;
+                        }
+                    }
+                    if (list != null) {
+                        newPiNodes.put(entry.getKey(), list);
+                    }
+                }
+                piNodes = newPiNodes;
+            }
+            return true;
+        }
+
+        @Override
+        public void loopBegin(LoopBeginNode loop) {
+        }
+
+        @Override
+        public void loopEnds(LoopBeginNode loop, Collection<TypeInfo> loopEndStates) {
+        }
+
+        @Override
+        public void afterSplit(FixedNode node) {
+            assert node.predecessor() != null;
+            assert node.predecessor() instanceof ControlSplitNode;
+//            TTY.println("after split: %s", node);
+            if (node.predecessor() instanceof IfNode) {
+                IfNode ifNode = (IfNode) node.predecessor();
+                if (ifNode.compare() instanceof InstanceOfNode) {
+                    InstanceOfNode instanceOf = (InstanceOfNode) ifNode.compare();
+                    assert node == ifNode.trueSuccessor() || node == ifNode.falseSuccessor();
+                    if ((node == ifNode.trueSuccessor() && !instanceOf.negated()) || (node == ifNode.falseSuccessor() && instanceOf.negated())) {
+                        ValueNode value = instanceOf.object();
+                        if (value.declaredType() != instanceOf.targetClass() || !value.stamp().nonNull()) {
+                            PiNode piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.declaredNonNull(instanceOf.targetClass())));
+                            PiNodeList list = piNodes.get(value);
+                            piNodes.put(value, new PiNodeList(piNode, list));
+                        }
+                    }
+                } else if (ifNode.compare() instanceof CompareNode) {
+                    CompareNode compare = (CompareNode) ifNode.compare();
+                    assert node == ifNode.trueSuccessor() || node == ifNode.falseSuccessor();
+                    if ((node == ifNode.trueSuccessor() && compare.condition() == Condition.EQ) || (node == ifNode.falseSuccessor() && compare.condition() == Condition.NE)) {
+                        if (compare.y().isConstant()) {
+                            ValueNode value = compare.x();
+                            PiNodeList list = piNodes.get(value);
+                            piNodes.put(value, new PiNodeList(compare.y(), list));
+                        }
+                    } else if ((node == ifNode.trueSuccessor() && compare.condition() == Condition.NE) || (node == ifNode.falseSuccessor() && compare.condition() == Condition.EQ)) {
+                        if (!compare.x().isConstant() && compare.y().isNullConstant() && !compare.x().stamp().nonNull()) {
+                            ValueNode value = compare.x();
+                            PiNode piNode;
+                            if (value.exactType() != null) {
+                                piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.declaredNonNull(value.exactType())));
+                            } else if (value.declaredType() != null) {
+                                piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.declaredNonNull(value.declaredType())));
+                            } else {
+                                piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.objectNonNull()));
+                            }
+                            PiNodeList list = piNodes.get(value);
+                            piNodes.put(value, new PiNodeList(piNode, list));
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    private class Tool implements CanonicalizerTool {
+        @Override
+        public CiTarget target() {
+            return target;
+        }
+
+        @Override
+        public CiAssumptions assumptions() {
+            return assumptions;
+        }
+
+        @Override
+        public RiRuntime runtime() {
+            return runtime;
+        }
+    }
+
+    private final Tool tool = new Tool();
+
+    private class PropagateTypes extends ScheduledNodeIterator<TypeInfo> {
+
+        public PropagateTypes(FixedNode start) {
+            super(start, new TypeInfo(new HashMap<ValueNode, PiNodeList>()));
+        }
+
+        @Override
+        protected void node(ScheduledNode node) {
+            if (node instanceof Canonicalizable || node instanceof Invoke) {
+                NodeClassIterator iter = node.inputs().iterator();
+                ArrayList<Node> changedInputs = new ArrayList<>();
+                while (iter.hasNext()) {
+                    Position pos = iter.nextPosition();
+                    Node value = pos.get(node);
+                    PiNodeList list = state.piNodes.get(value);
+                    if (list != null) {
+                        changedInputs.add(list.replacement instanceof PiNode ? value : null);
+                        pos.set(node, list.replacement);
+                    } else {
+                        changedInputs.add(null);
+                    }
+                }
+
+                ValueNode canonical = null;
+                if (node instanceof Canonicalizable) {
+                    canonical = ((Canonicalizable) node).canonical(tool);
+                }
+
+                if (canonical == node) {
+                    iter = node.inputs().iterator();
+                    int i = 0;
+                    while (iter.hasNext()) {
+                        Position pos = iter.nextPosition();
+                        if (changedInputs.get(i) != null) {
+                            pos.set(node, changedInputs.get(i));
+                        }
+                        i++;
+                    }
+                } else {
+                    changedNodes.add(node);
+                }
+            }
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/PiNode.java	Mon Feb 20 14:29:51 2012 +0100
@@ -0,0 +1,53 @@
+/*
+ * Copyright (c) 2012, 2012, 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.max.graal.nodes;
+
+import com.oracle.max.graal.nodes.calc.*;
+import com.oracle.max.graal.nodes.spi.*;
+import com.oracle.max.graal.nodes.type.*;
+
+
+public class PiNode extends FloatingNode implements LIRLowerable {
+
+    @Input private ValueNode value;
+    @Input private BeginNode anchor;
+
+    public ValueNode value() {
+        return value;
+    }
+
+    public BeginNode anchor() {
+        return anchor;
+    }
+
+    public PiNode(ValueNode value, BeginNode anchor, Stamp stamp) {
+        super(stamp);
+        this.value = value;
+        this.anchor = anchor;
+    }
+
+    @Override
+    public void generate(LIRGeneratorTool generator) {
+        generator.setResult(this, generator.operand(value));
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.tests/src/com/oracle/max/graal/compiler/tests/TypeSystemTest.java	Mon Feb 20 14:29:51 2012 +0100
@@ -0,0 +1,71 @@
+/*
+ * Copyright (c) 2011, 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.max.graal.compiler.tests;
+
+import org.junit.*;
+
+import com.oracle.max.graal.compiler.phases.*;
+import com.oracle.max.graal.compiler.types.*;
+import com.oracle.max.graal.debug.*;
+import com.oracle.max.graal.graph.*;
+import com.oracle.max.graal.nodes.*;
+import com.oracle.max.graal.nodes.java.*;
+
+/**
+ * In the following tests, the scalar type system of the compiler should be complete enough to see the relation between the different conditions.
+ */
+public class TypeSystemTest extends GraphTest {
+
+    @Test
+    public void test1() {
+        test("test1Snippet", CheckCastNode.class);
+    }
+
+    public static int test1Snippet(Object a) {
+        if (a instanceof Boolean) {
+            return ((Boolean) a).booleanValue() ? 0 : 1;
+        }
+        return 1;
+    }
+
+    @Test
+    public void test2() {
+        test("test2Snippet", CheckCastNode.class);
+    }
+
+    public static int test2Snippet(Object a) {
+        if (a instanceof Integer) {
+            return ((Number) a).intValue();
+        }
+        return 1;
+    }
+
+    private <T extends Node & Node.IterableNodeType> void test(String snippet, Class<T> clazz) {
+        StructuredGraph graph = parse(snippet);
+        Debug.dump(graph, "Graph");
+        new CanonicalizerPhase(null, runtime(), null).apply(graph);
+        new PropagateTypesPhase(null, null, null).apply(graph);
+        Debug.dump(graph, "Graph");
+        Assert.assertFalse("shouldn't have nodes of type " + clazz, graph.getNodes(clazz).iterator().hasNext());
+    }
+}