Mercurial > hg > truffle

changeset 11361:07625ef93345

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge.
author Doug Simon <doug.simon@oracle.com>
date Mon, 19 Aug 2013 14:11:10 +0200
parents 9b64c7982932 (current diff) a88f1ddbbad1 (diff)
children eefa7d842e7f
files
diffstat 24 files changed, 532 insertions(+), 164 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.asm.amd64/src/com/oracle/graal/asm/amd64/AMD64Assembler.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.asm.amd64/src/com/oracle/graal/asm/amd64/AMD64Assembler.java	Mon Aug 19 14:11:10 2013 +0200
@@ -1189,6 +1189,12 @@
         emitByte(0xD8 | encode);
     }
 
+    public final void notl(Register dst) {
+        int encode = prefixAndEncode(dst.encoding);
+        emitByte(0xF7);
+        emitByte(0xD0 | encode);
+    }
+
     public final void ensureUniquePC() {
         nop();
     }
@@ -2212,6 +2218,12 @@
         emitByte(0xD8 | encode);
     }
 
+    public final void notq(Register dst) {
+        int encode = prefixqAndEncode(dst.encoding);
+        emitByte(0xF7);
+        emitByte(0xD0 | encode);
+    }
+
     public final void orq(Register dst, int imm32) {
         prefixqAndEncode(dst.encoding);
         emitArith(0x81, 0xC8, dst, imm32);
--- a/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java	Mon Aug 19 14:11:10 2013 +0200
@@ -359,6 +359,23 @@
         return result;
     }
 
+    @Override
+    public Variable emitNot(Value inputVal) {
+        AllocatableValue input = asAllocatable(inputVal);
+        Variable result = newVariable(input.getKind());
+        switch (input.getKind()) {
+            case Int:
+                append(new Unary1Op(INOT, result, input));
+                break;
+            case Long:
+                append(new Unary1Op(LNOT, result, input));
+                break;
+            default:
+                throw GraalInternalError.shouldNotReachHere();
+        }
+        return result;
+    }
+
     private Variable emitBinary(AMD64Arithmetic op, boolean commutative, Value a, Value b) {
         if (isConstant(b)) {
             return emitBinaryConst(op, commutative, asAllocatable(a), asConstant(b));
--- a/graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILLIRGenerator.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILLIRGenerator.java	Mon Aug 19 14:11:10 2013 +0200
@@ -300,6 +300,20 @@
 
     }
 
+    @Override
+    public Variable emitNot(Value input) {
+        Variable result = newVariable(input.getKind());
+        switch (input.getKind()) {
+            case Int:
+                append(new Op1Stack(INOT, result, input));
+                break;
+            default:
+                throw GraalInternalError.shouldNotReachHere();
+        }
+        return result;
+
+    }
+
     public Variable emitTestAddressAdd(Value a, Value b) {
         Variable result = newVariable(a.getKind());
         switch (a.getKind()) {
--- a/graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXLIRGenerator.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXLIRGenerator.java	Mon Aug 19 14:11:10 2013 +0200
@@ -315,6 +315,22 @@
     }
 
     @Override
+    public Variable emitNot(Value input) {
+        Variable result = newVariable(input.getKind());
+        switch (input.getKind()) {
+            case Int:
+                append(new Op1Stack(INOT, result, input));
+                break;
+            case Long:
+                append(new Op1Stack(LNOT, result, input));
+                break;
+            default:
+                throw GraalInternalError.shouldNotReachHere();
+        }
+        return result;
+    }
+
+    @Override
     public Variable emitAdd(Value a, Value b) {
         Variable result = newVariable(a.getKind());
         switch (a.getKind()) {
--- a/graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCLIRGenerator.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCLIRGenerator.java	Mon Aug 19 14:11:10 2013 +0200
@@ -468,6 +468,22 @@
         return result;
     }
 
+    @Override
+    public Value emitNot(Value input) {
+        Variable result = newVariable(input.getKind());
+        switch (input.getKind().getStackKind()) {
+            case Int:
+                append(new Op1Stack(INOT, result, input));
+                break;
+            case Long:
+                append(new Op1Stack(LNOT, result, input));
+                break;
+            default:
+                throw GraalInternalError.shouldNotReachHere();
+        }
+        return result;
+    }
+
     private Variable emitBinary(SPARCArithmetic op, boolean commutative, Value a, Value b) {
         if (isConstant(b)) {
             return emitBinaryConst(op, commutative, asAllocatable(a), asConstant(b));
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/IntegerStampTest.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/IntegerStampTest.java	Mon Aug 19 14:11:10 2013 +0200
@@ -22,6 +22,8 @@
  */
 package com.oracle.graal.compiler.test;
 
+import static org.junit.Assert.*;
+
 import org.junit.*;
 
 import com.oracle.graal.api.meta.*;
@@ -31,7 +33,7 @@
 /**
  * This class tests that integer stamps are created correctly for constants.
  */
-public class IntegerStampTest extends GraalCompilerTest {
+public class IntegerStampTest {
 
     private StructuredGraph graph;
 
@@ -42,51 +44,140 @@
 
     @Test
     public void testBooleanConstant() {
-        assertEquals(new IntegerStamp(Kind.Int, 1, 1, 0x1), ConstantNode.forBoolean(true, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, 0, 0, 0x0), ConstantNode.forBoolean(false, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 1, 1, 0x1, 0x1), ConstantNode.forBoolean(true, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 0, 0, 0x0, 0x0), ConstantNode.forBoolean(false, graph).stamp());
     }
 
     @Test
     public void testByteConstant() {
-        assertEquals(new IntegerStamp(Kind.Int, 0, 0, 0x0), ConstantNode.forByte((byte) 0, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, 16, 16, 0x10), ConstantNode.forByte((byte) 16, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, -16, -16, 0xf0), ConstantNode.forByte((byte) -16, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, 127, 127, 0x7f), ConstantNode.forByte((byte) 127, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, -128, -128, 0x80), ConstantNode.forByte((byte) -128, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 0, 0, 0x0, 0x0), ConstantNode.forByte((byte) 0, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 16, 16, 0x10, 0x10), ConstantNode.forByte((byte) 16, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, -16, -16, 0xf0, 0xf0), ConstantNode.forByte((byte) -16, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 127, 127, 0x7f, 0x7f), ConstantNode.forByte((byte) 127, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, -128, -128, 0x80, 0x80), ConstantNode.forByte((byte) -128, graph).stamp());
     }
 
     @Test
     public void testShortConstant() {
-        assertEquals(new IntegerStamp(Kind.Int, 0, 0, 0x0), ConstantNode.forShort((short) 0, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, 128, 128, 0x80), ConstantNode.forShort((short) 128, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, -128, -128, 0xff80), ConstantNode.forShort((short) -128, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, 32767, 32767, 0x7fff), ConstantNode.forShort((short) 32767, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, -32768, -32768, 0x8000), ConstantNode.forShort((short) -32768, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 0, 0, 0x0, 0x0), ConstantNode.forShort((short) 0, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 128, 128, 0x80, 0x80), ConstantNode.forShort((short) 128, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, -128, -128, 0xff80, 0xff80), ConstantNode.forShort((short) -128, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 32767, 32767, 0x7fff, 0x7fff), ConstantNode.forShort((short) 32767, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, -32768, -32768, 0x8000, 0x8000), ConstantNode.forShort((short) -32768, graph).stamp());
     }
 
     @Test
     public void testCharConstant() {
-        assertEquals(new IntegerStamp(Kind.Int, 0, 0, 0x0), ConstantNode.forChar((char) 0, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, 'A', 'A', 'A'), ConstantNode.forChar('A', graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, 128, 128, 0x80), ConstantNode.forChar((char) 128, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, 65535, 65535, 0xffff), ConstantNode.forChar((char) 65535, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 0, 0, 0x0, 0x0), ConstantNode.forChar((char) 0, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 'A', 'A', 'A', 'A'), ConstantNode.forChar('A', graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 128, 128, 0x80, 0x80), ConstantNode.forChar((char) 128, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 65535, 65535, 0xffff, 0xffff), ConstantNode.forChar((char) 65535, graph).stamp());
     }
 
     @Test
     public void testIntConstant() {
-        assertEquals(new IntegerStamp(Kind.Int, 0, 0, 0x0), ConstantNode.forInt(0, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, 128, 128, 0x80), ConstantNode.forInt(128, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, -128, -128, 0xffffff80L), ConstantNode.forInt(-128, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, Integer.MAX_VALUE, Integer.MAX_VALUE, 0x7fffffff), ConstantNode.forInt(Integer.MAX_VALUE, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Int, Integer.MIN_VALUE, Integer.MIN_VALUE, 0x80000000L), ConstantNode.forInt(Integer.MIN_VALUE, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 0, 0, 0x0, 0x0), ConstantNode.forInt(0, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, 128, 128, 0x80, 0x80), ConstantNode.forInt(128, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, -128, -128, 0xffffff80L, 0xffffff80L), ConstantNode.forInt(-128, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, Integer.MAX_VALUE, Integer.MAX_VALUE, 0x7fffffff, 0x7fffffff), ConstantNode.forInt(Integer.MAX_VALUE, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Int, Integer.MIN_VALUE, Integer.MIN_VALUE, 0x80000000L, 0x80000000L), ConstantNode.forInt(Integer.MIN_VALUE, graph).stamp());
     }
 
     @Test
     public void testLongConstant() {
-        assertEquals(new IntegerStamp(Kind.Long, 0, 0, 0x0), ConstantNode.forLong(0, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Long, 128, 128, 0x80), ConstantNode.forLong(128, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Long, -128, -128, 0xffffffffffffff80L), ConstantNode.forLong(-128, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Long, Long.MAX_VALUE, Long.MAX_VALUE, 0x7fffffffffffffffL), ConstantNode.forLong(Long.MAX_VALUE, graph).stamp());
-        assertEquals(new IntegerStamp(Kind.Long, Long.MIN_VALUE, Long.MIN_VALUE, 0x8000000000000000L), ConstantNode.forLong(Long.MIN_VALUE, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Long, 0, 0, 0x0, 0x0), ConstantNode.forLong(0, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Long, 128, 128, 0x80, 0x80), ConstantNode.forLong(128, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Long, -128, -128, 0xffffffffffffff80L, 0xffffffffffffff80L), ConstantNode.forLong(-128, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Long, Long.MAX_VALUE, Long.MAX_VALUE, 0x7fffffffffffffffL, 0x7fffffffffffffffL), ConstantNode.forLong(Long.MAX_VALUE, graph).stamp());
+        assertEquals(new IntegerStamp(Kind.Long, Long.MIN_VALUE, Long.MIN_VALUE, 0x8000000000000000L, 0x8000000000000000L), ConstantNode.forLong(Long.MIN_VALUE, graph).stamp());
+    }
+
+    @Test
+    public void testPositiveRanges() {
+        assertEquals(new IntegerStamp(Kind.Int, 0, 0, 0, 0), StampFactory.forInteger(Kind.Int, 0, 0));
+        assertEquals(new IntegerStamp(Kind.Int, 0, 1, 0, 1), StampFactory.forInteger(Kind.Int, 0, 1));
+        assertEquals(new IntegerStamp(Kind.Int, 0, 0x123, 0, 0x1ff), StampFactory.forInteger(Kind.Int, 0, 0x123));
+        assertEquals(new IntegerStamp(Kind.Int, 0x120, 0x123, 0x120, 0x123), StampFactory.forInteger(Kind.Int, 0x120, 0x123));
+        assertEquals(new IntegerStamp(Kind.Int, 10000, 15000, 0x2000, 0x3fff), StampFactory.forInteger(Kind.Int, 10000, 15000));
+        assertEquals(new IntegerStamp(Kind.Long, 0, 1, 0, 1), StampFactory.forInteger(Kind.Long, 0, 1));
+        assertEquals(new IntegerStamp(Kind.Long, 10000, 15000, 0x2000, 0x3fff), StampFactory.forInteger(Kind.Long, 10000, 15000));
+        assertEquals(new IntegerStamp(Kind.Long, 140000000000L, 150000000000L, 0x2000000000L, 0x23ffffffffL), StampFactory.forInteger(Kind.Long, 140000000000L, 150000000000L));
+    }
+
+    @Test
+    public void testNegativeRanges() {
+        assertEquals(new IntegerStamp(Kind.Int, -2, -1, 0xfffffffeL, 0xffffffffL), StampFactory.forInteger(Kind.Int, -2, -1));
+        assertEquals(new IntegerStamp(Kind.Int, -20, -10, 0xffffffe0L, 0xffffffffL), StampFactory.forInteger(Kind.Int, -20, -10));
+        assertEquals(new IntegerStamp(Kind.Int, -10000, 0, 0, 0xffffffffL), StampFactory.forInteger(Kind.Int, -10000, 0));
+        assertEquals(new IntegerStamp(Kind.Int, -10000, -1, 0xffffc000L, 0xffffffffL), StampFactory.forInteger(Kind.Int, -10000, -1));
+        assertEquals(new IntegerStamp(Kind.Int, -10010, -10000, 0xffffd8e0L, 0xffffd8ffL), StampFactory.forInteger(Kind.Int, -10010, -10000));
+        assertEquals(new IntegerStamp(Kind.Long, -2, -1, 0xfffffffffffffffeL, 0xffffffffffffffffL), StampFactory.forInteger(Kind.Long, -2, -1));
+        assertEquals(new IntegerStamp(Kind.Long, -10010, -10000, 0xffffffffffffd8e0L, 0xffffffffffffd8ffL), StampFactory.forInteger(Kind.Long, -10010, -10000));
+        assertEquals(new IntegerStamp(Kind.Long, -150000000000L, -140000000000L, 0xffffffdc00000000L, 0xffffffdfffffffffL), StampFactory.forInteger(Kind.Long, -150000000000L, -140000000000L));
+    }
+
+    @Test
+    public void testMixedRanges() {
+        assertEquals(new IntegerStamp(Kind.Int, -1, 0, 0, 0xffffffffL), StampFactory.forInteger(Kind.Int, -1, 0));
+        assertEquals(new IntegerStamp(Kind.Int, -10000, 1000, 0, 0xffffffffL), StampFactory.forInteger(Kind.Int, -10000, 1000));
+        assertEquals(new IntegerStamp(Kind.Long, -10000, 1000, 0, 0xffffffffffffffffL), StampFactory.forInteger(Kind.Long, -10000, 1000));
+    }
+
+    @Test
+    public void testNarrowingConversions() {
+        // byte cases
+        assertEquals(StampFactory.forInteger(Kind.Int, 0, 0), StampTool.intToByte(StampFactory.forInteger(Kind.Int, 0, 0)));
+        assertEquals(StampFactory.forInteger(Kind.Int, 0, 10), StampTool.intToByte(StampFactory.forInteger(Kind.Int, 0, 10)));
+        assertEquals(StampFactory.forInteger(Kind.Int, 10, 20), StampTool.intToByte(StampFactory.forInteger(Kind.Int, 10, 20)));
+        assertEquals(StampFactory.forInteger(Kind.Int, -10, 0), StampTool.intToByte(StampFactory.forInteger(Kind.Int, -10, 0)));
+        assertEquals(StampFactory.forInteger(Kind.Int, -20, -10), StampTool.intToByte(StampFactory.forInteger(Kind.Int, -20, -10)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Byte.MIN_VALUE, Byte.MAX_VALUE), StampTool.intToByte(StampFactory.forInteger(Kind.Int, 100, 200)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Byte.MIN_VALUE, Byte.MAX_VALUE), StampTool.intToByte(StampFactory.forInteger(Kind.Int, -100, 200)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Byte.MIN_VALUE, Byte.MAX_VALUE), StampTool.intToByte(StampFactory.forInteger(Kind.Int, -200, -100)));
+        // char cases
+        assertEquals(StampFactory.forInteger(Kind.Int, 0, 10), StampTool.intToChar(StampFactory.forInteger(Kind.Int, 0, 10)));
+        assertEquals(StampFactory.forInteger(Kind.Int, 10, 20), StampTool.intToChar(StampFactory.forInteger(Kind.Int, 10, 20)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Character.MIN_VALUE, Character.MAX_VALUE), StampTool.intToChar(StampFactory.forInteger(Kind.Int, 20000, 80000)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Character.MIN_VALUE, Character.MAX_VALUE), StampTool.intToChar(StampFactory.forInteger(Kind.Int, -10000, 40000)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Character.MIN_VALUE, Character.MAX_VALUE), StampTool.intToChar(StampFactory.forInteger(Kind.Int, -40000, -10000)));
+        // short cases
+        assertEquals(StampFactory.forInteger(Kind.Int, 0, 10), StampTool.intToShort(StampFactory.forInteger(Kind.Int, 0, 10)));
+        assertEquals(StampFactory.forInteger(Kind.Int, 10, 20), StampTool.intToShort(StampFactory.forInteger(Kind.Int, 10, 20)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Short.MIN_VALUE, Short.MAX_VALUE), StampTool.intToShort(StampFactory.forInteger(Kind.Int, 20000, 40000)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Short.MIN_VALUE, Short.MAX_VALUE), StampTool.intToShort(StampFactory.forInteger(Kind.Int, -10000, 40000)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Short.MIN_VALUE, Short.MAX_VALUE), StampTool.intToShort(StampFactory.forInteger(Kind.Int, -40000, -10000)));
+        // int cases
+        assertEquals(StampFactory.forInteger(Kind.Int, 0, 10), StampTool.longToInt(StampFactory.forInteger(Kind.Long, 0, 10)));
+        assertEquals(StampFactory.forInteger(Kind.Int, 10, 20), StampTool.longToInt(StampFactory.forInteger(Kind.Long, 10, 20)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Integer.MIN_VALUE, Integer.MAX_VALUE), StampTool.longToInt(StampFactory.forInteger(Kind.Long, 20000000000L, 40000000000L)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Integer.MIN_VALUE, Integer.MAX_VALUE), StampTool.longToInt(StampFactory.forInteger(Kind.Long, -10000000000L, 40000000000L)));
+        assertEquals(StampFactory.forInteger(Kind.Int, Integer.MIN_VALUE, Integer.MAX_VALUE), StampTool.longToInt(StampFactory.forInteger(Kind.Long, -40000000000L, -10000000000L)));
+    }
+
+    @Test
+    public void testXor() {
+        assertEquals(new IntegerStamp(Kind.Int, 0, 0xff, 0, 0xff), StampTool.xor(new IntegerStamp(Kind.Int, 0, 0, 0, 0), new IntegerStamp(Kind.Int, 0, 0xff, 0, 0xff)));
+        assertEquals(new IntegerStamp(Kind.Int, 0x10, 0x1f, 0x10, 0x1f), StampTool.xor(new IntegerStamp(Kind.Int, 0, 0, 0, 0), new IntegerStamp(Kind.Int, 0x10, 0x1f, 0x10, 0x1f)));
+        assertEquals(new IntegerStamp(Kind.Int, 0x0, 0xf, 0x0, 0xf), StampTool.xor(new IntegerStamp(Kind.Int, 0x10, 0x10, 0x10, 0x10), new IntegerStamp(Kind.Int, 0x10, 0x1f, 0x10, 0x1f)));
+        assertEquals(new IntegerStamp(Kind.Int, 0x10, 0x1f, 0x10, 0x1f), StampTool.xor(new IntegerStamp(Kind.Int, 0x10, 0x10, 0x10, 0x10), new IntegerStamp(Kind.Int, 0x0, 0xf, 0x0, 0xf)));
+    }
+
+    @Test
+    public void testNot() {
+        assertEquals(new IntegerStamp(Kind.Int, -11, -1, 0xfffffff0L, 0xffffffffL), StampTool.not(new IntegerStamp(Kind.Int, 0, 10, 0, 0xf)));
+    }
+
+    @Test
+    public void testAdd() {
+        assertEquals(StampFactory.forInteger(Kind.Int, 0, 30), StampTool.add(StampFactory.forInteger(Kind.Int, 0, 10), StampFactory.forInteger(Kind.Int, 0, 20)));
+        assertEquals(StampFactory.forKind(Kind.Long),
+                        StampTool.add(StampFactory.forInteger(Kind.Long, Long.MIN_VALUE, Long.MIN_VALUE + 1), StampFactory.forInteger(Kind.Long, Integer.MIN_VALUE, Integer.MAX_VALUE)));
+        assertEquals(StampFactory.forInteger(Kind.Int, -2147483647, 31 - 2147483647),
+                        StampTool.add(StampFactory.forInteger(Kind.Int, 0, 31), StampFactory.forInteger(Kind.Int, -2147483647, -2147483647)));
+    }
+
+    @Test
+    public void testAnd() {
+        assertEquals(new IntegerStamp(Kind.Int, Integer.MIN_VALUE, 0x40000000L, 0, 0xc0000000L), StampTool.and(StampFactory.forKind(Kind.Int), StampFactory.forConstant(Constant.forInt(0xc0000000))));
     }
 }
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/StampCanonicalizerTest.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/StampCanonicalizerTest.java	Mon Aug 19 14:11:10 2013 +0200
@@ -31,7 +31,7 @@
 
 /**
  * This class tests some specific patterns the stamp system should be able to canonicalize away
- * using {@link IntegerStamp#mask()}.
+ * using {@link IntegerStamp#upMask()}.
  */
 public class StampCanonicalizerTest extends GraalCompilerTest {
 
--- a/graal/com.oracle.graal.hotspot.sparc/src/com/oracle/graal/hotspot/sparc/SPARCHotSpotLIRGenerator.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.hotspot.sparc/src/com/oracle/graal/hotspot/sparc/SPARCHotSpotLIRGenerator.java	Mon Aug 19 14:11:10 2013 +0200
@@ -276,4 +276,10 @@
             append(new StoreOp(kind, storeAddress, input, state));
         }
     }
+
+    @Override
+    public Value emitNot(Value input) {
+        GraalInternalError.shouldNotReachHere("binary negation not implemented");
+        return null;
+    }
 }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/SystemSubstitutions.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/SystemSubstitutions.java	Mon Aug 19 14:11:10 2013 +0200
@@ -24,6 +24,7 @@
 
 import static com.oracle.graal.hotspot.replacements.HotSpotReplacementsUtil.*;
 import static com.oracle.graal.nodes.extended.BranchProbabilityNode.*;
+import static com.oracle.graal.phases.GraalOptions.*;
 
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.api.replacements.*;
@@ -64,7 +65,7 @@
 
         @Override
         protected Constant evaluate(Constant param, MetaAccessProvider metaAccess) {
-            return param.isNull() ? null : Constant.forInt(System.identityHashCode(param.asObject()));
+            return AOTCompilation.getValue() || param.isNull() ? null : Constant.forInt(System.identityHashCode(param.asObject()));
         }
     }
 
--- a/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64Arithmetic.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64Arithmetic.java	Mon Aug 19 14:11:10 2013 +0200
@@ -42,7 +42,7 @@
     LADD, LSUB, LMUL, LDIV, LDIVREM, LREM, LUDIV, LUREM, LAND, LOR, LXOR, LSHL, LSHR, LUSHR,
     FADD, FSUB, FMUL, FDIV, FREM, FAND, FOR, FXOR,
     DADD, DSUB, DMUL, DDIV, DREM, DAND, DOR, DXOR,
-    INEG, LNEG,
+    INEG, LNEG, INOT, LNOT,
     SQRT,
     I2L, L2I, I2B, I2C, I2S,
     F2D, D2F,
@@ -364,6 +364,12 @@
             case LNEG:
                 masm.negq(asLongReg(result));
                 break;
+            case INOT:
+                masm.notl(asIntReg(result));
+                break;
+            case LNOT:
+                masm.notq(asLongReg(result));
+                break;
             case L2I:
                 masm.andl(asIntReg(result), 0xFFFFFFFF);
                 break;
--- a/graal/com.oracle.graal.lir.hsail/src/com/oracle/graal/lir/hsail/HSAILArithmetic.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.lir.hsail/src/com/oracle/graal/lir/hsail/HSAILArithmetic.java	Mon Aug 19 14:11:10 2013 +0200
@@ -44,7 +44,7 @@
     IMIN, LMIN, IUMIN, LUMIN, IREM,
     LREM, FREM, DREM, IUREM, LUREM,
     ICARRY, LCARRY, IUCARRY, LUCARRY,
-    IAND, LAND, INEG, I2B, I2S, I2L,
+    IAND, LAND, INEG, INOT, I2B, I2S, I2L,
     F2D, F2I, F2L, D2F, I2F, I2D, D2I,
     L2F, D2L, MOV_F2I, MOV_D2L, L2D, MOV_I2F,
     MOV_L2D, ISHL, LSHL, ISHR, LSHR, IUSHR, LUSHR,
@@ -233,6 +233,7 @@
                 case SQRT: masm.emitArg1("sqrt", dst, src); break;
                 case UNDEF: masm.undefined("undefined node"); break;
                 case CALL: masm.undefined("undefined node CALL"); break;
+                case INOT: masm.emitArg1("not", dst, src); break;
                 default:
                     throw GraalInternalError.shouldNotReachHere();
             }
--- a/graal/com.oracle.graal.lir.ptx/src/com/oracle/graal/lir/ptx/PTXArithmetic.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.lir.ptx/src/com/oracle/graal/lir/ptx/PTXArithmetic.java	Mon Aug 19 14:11:10 2013 +0200
@@ -37,7 +37,7 @@
     LADD, LSUB, LMUL, LDIV, LDIVREM, LREM, LUDIV, LUREM, LAND, LOR, LXOR, LSHL, LSHR, LUSHR,
     FADD, FSUB, FMUL, FDIV, FREM, FAND, FOR, FXOR,
     DADD, DSUB, DMUL, DDIV, DREM, DAND, DOR, DXOR,
-    INEG, LNEG, FNEG, DNEG,
+    INEG, LNEG, FNEG, DNEG, INOT, LNOT,
     I2L, L2I, I2B, I2C, I2S,
     F2D, D2F,
     I2F, I2D, F2I, D2I,
@@ -270,6 +270,12 @@
                 case INEG:
                     masm.neg_s32(asIntReg(dst), asIntReg(src));
                     break;
+                case INOT:
+                    masm.not_s32(asIntReg(dst), asIntReg(src));
+                    break;
+                case LNOT:
+                    masm.not_s64(asLongReg(dst), asLongReg(src));
+                    break;
                 case I2L:
                     masm.cvt_s64_s32(asLongReg(dst), asIntReg(src));
                     break;
--- a/graal/com.oracle.graal.lir.sparc/src/com/oracle/graal/lir/sparc/SPARCArithmetic.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.lir.sparc/src/com/oracle/graal/lir/sparc/SPARCArithmetic.java	Mon Aug 19 14:11:10 2013 +0200
@@ -39,7 +39,7 @@
     LADD, LSUB, LMUL, LDIV, LREM, LUDIV, LUREM, LAND, LOR, LXOR, LSHL, LSHR, LUSHR,
     FADD, FSUB, FMUL, FDIV, FREM, FAND, FOR, FXOR,
     DADD, DSUB, DMUL, DDIV, DREM, DAND, DOR, DXOR,
-    INEG, LNEG, FNEG, DNEG,
+    INEG, LNEG, FNEG, DNEG, INOT, LNOT,
     I2L, L2I, I2B, I2C, I2S,
     F2D, D2F,
     I2F, I2D, F2I, D2I,
@@ -525,6 +525,12 @@
                 case INEG:
                     new Neg(asIntReg(src), asIntReg(dst)).emit(masm);
                     break;
+                case INOT:
+                    new Not(asIntReg(src), asIntReg(dst)).emit(masm);
+                    break;
+                case LNOT:
+                    new Not(asLongReg(src), asLongReg(dst)).emit(masm);
+                    break;
                 case I2L:
                     new Signx(asIntReg(src), asLongReg(dst)).emit(masm);
                     break;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ConditionalNode.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ConditionalNode.java	Mon Aug 19 14:11:10 2013 +0200
@@ -72,7 +72,7 @@
             IntegerEqualsNode equals = (IntegerEqualsNode) condition;
             if (equals.y().isConstant() && equals.y().asConstant().equals(Constant.INT_0) && equals.x().stamp() instanceof IntegerStamp) {
                 IntegerStamp equalsXStamp = (IntegerStamp) equals.x().stamp();
-                if (equalsXStamp.mask() == 1) {
+                if (equalsXStamp.upMask() == 1) {
                     if (x().asConstant().equals(Constant.INT_0) && y().asConstant().equals(Constant.INT_1)) {
                         return equals.x();
                     }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerDivNode.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerDivNode.java	Mon Aug 19 14:11:10 2013 +0200
@@ -68,7 +68,7 @@
                 IntegerStamp stampX = (IntegerStamp) x().stamp();
                 int log2 = CodeUtil.log2(abs);
                 // no rounding if dividend is positive or if its low bits are always 0
-                if (stampX.canBeNegative() || (stampX.mask() & (abs - 1)) != 0) {
+                if (stampX.canBeNegative() || (stampX.upMask() & (abs - 1)) != 0) {
                     int bits;
                     if (kind().getStackKind() == Kind.Int) {
                         bits = 32;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerTestNode.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerTestNode.java	Mon Aug 19 14:11:10 2013 +0200
@@ -68,7 +68,7 @@
         if (x().stamp() instanceof IntegerStamp && y().stamp() instanceof IntegerStamp) {
             IntegerStamp xStamp = (IntegerStamp) x().stamp();
             IntegerStamp yStamp = (IntegerStamp) y().stamp();
-            if ((xStamp.mask() & yStamp.mask()) == 0) {
+            if ((xStamp.upMask() & yStamp.upMask()) == 0) {
                 return LogicConstantNode.tautology(graph());
             }
         }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NotNode.java	Mon Aug 19 14:11:10 2013 +0200
@@ -0,0 +1,77 @@
+/*
+ * Copyright (c) 2009, 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.graal.nodes.calc;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.type.*;
+
+/**
+ * Binary negation of long or integer values.
+ */
+public final class NotNode extends FloatingNode implements Canonicalizable, ArithmeticLIRLowerable {
+
+    @Input private ValueNode x;
+
+    public ValueNode x() {
+        return x;
+    }
+
+    @Override
+    public boolean inferStamp() {
+        return updateStamp(StampTool.not(x().stamp()));
+    }
+
+    /**
+     * Creates new NegateNode instance.
+     * 
+     * @param x the instruction producing the value that is input to this instruction
+     */
+    public NotNode(ValueNode x) {
+        super(StampTool.not(x.stamp()));
+        assert x.kind() == Kind.Int || x.kind() == Kind.Long;
+        this.x = x;
+    }
+
+    @Override
+    public ValueNode canonical(CanonicalizerTool tool) {
+        if (x().isConstant()) {
+            switch (x().kind()) {
+                case Int:
+                    return ConstantNode.forInt(~x().asConstant().asInt(), graph());
+                case Long:
+                    return ConstantNode.forLong(~x().asConstant().asLong(), graph());
+            }
+        }
+        if (x() instanceof NotNode) {
+            return ((NotNode) x()).x();
+        }
+        return this;
+    }
+
+    @Override
+    public void generate(ArithmeticLIRGenerator gen) {
+        gen.setResult(this, gen.emitNot(gen.operand(x())));
+    }
+}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java	Mon Aug 19 14:11:10 2013 +0200
@@ -60,12 +60,16 @@
                 int c = y().asConstant().asInt();
                 if (c == 0) {
                     return x();
+                } else if (c == -1) {
+                    return graph().unique(new NotNode(x()));
                 }
             } else {
                 assert kind() == Kind.Long;
                 long c = y().asConstant().asLong();
                 if (c == 0) {
                     return x();
+                } else if (c == -1) {
+                    return graph().unique(new NotNode(x()));
                 }
             }
             return BinaryNode.reassociate(this, ValueNode.isConstantPredicate());
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/ArithmeticLIRGenerator.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/ArithmeticLIRGenerator.java	Mon Aug 19 14:11:10 2013 +0200
@@ -52,6 +52,8 @@
 
     Value emitURem(Value a, Value b, DeoptimizingNode deopting);
 
+    Value emitNot(Value input);
+
     Value emitAnd(Value a, Value b);
 
     Value emitOr(Value a, Value b);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/ValueProxy.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/ValueProxy.java	Mon Aug 19 14:11:10 2013 +0200
@@ -24,6 +24,12 @@
 
 import com.oracle.graal.nodes.*;
 
+/**
+ * This interface marks nodes whose result is the same as one of their inputs. Such nodes are used
+ * to add type information, to introduce scheduling restrictions, etc.
+ * 
+ * For some algorithms it is necessary or advantageous to see through these proxies.
+ */
 public interface ValueProxy {
 
     ValueNode getOriginalValue();
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/FloatStamp.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/FloatStamp.java	Mon Aug 19 14:11:10 2013 +0200
@@ -62,6 +62,10 @@
         return upperBound;
     }
 
+    public boolean isNonNaN() {
+        return nonNaN;
+    }
+
     public boolean isUnrestricted() {
         return lowerBound == Double.NEGATIVE_INFINITY && upperBound == Double.POSITIVE_INFINITY && !nonNaN;
     }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/IntegerStamp.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/IntegerStamp.java	Mon Aug 19 14:11:10 2013 +0200
@@ -29,27 +29,33 @@
 /**
  * Describes the possible values of a {@link ValueNode} that produces an int or long result.
  * 
- * The description consists of (inclusive) lower and upper bounds and a bit-mask.
+ * The description consists of (inclusive, signed) lower and upper bounds and up (may be set) and
+ * down (always set) bit-masks.
  */
 public class IntegerStamp extends Stamp {
 
     private final long lowerBound;
     private final long upperBound;
-    private final long mask;
+    private final long downMask;
+    private final long upMask;
 
     public IntegerStamp(Kind kind) {
-        this(kind.getStackKind(), kind.getMinValue(), kind.getMaxValue(), defaultMask(kind));
+        this(kind.getStackKind(), kind.getMinValue(), kind.getMaxValue(), 0, defaultMask(kind == Kind.Char ? kind : kind.getStackKind()));
     }
 
-    public IntegerStamp(Kind kind, long lowerBound, long upperBound, long mask) {
+    public IntegerStamp(Kind kind, long lowerBound, long upperBound, long downMask, long upMask) {
         super(kind);
-        assert lowerBound <= upperBound;
-        assert lowerBound >= kind.getMinValue();
-        assert upperBound <= kind.getMaxValue();
-        assert (mask & defaultMask(kind)) == mask;
         this.lowerBound = lowerBound;
         this.upperBound = upperBound;
-        this.mask = mask;
+        this.downMask = downMask;
+        this.upMask = upMask;
+        assert lowerBound <= upperBound : this;
+        assert lowerBound >= kind.getMinValue() : this;
+        assert upperBound <= kind.getMaxValue() : this;
+        assert (downMask & defaultMask(kind)) == downMask : this;
+        assert (upMask & defaultMask(kind)) == upMask : this;
+        assert (lowerBound & downMask) == downMask : this;
+        assert (upperBound & downMask) == downMask : this;
     }
 
     @Override
@@ -72,19 +78,25 @@
     }
 
     /**
-     * This bit-mask describes the bits that can be set in the value described by this stamp. It is
-     * primarily used to represent values that are multiples of a known power of two.
+     * This bit-mask describes the bits that are always set in the value described by this stamp.
      */
-    public long mask() {
-        return mask;
+    public long downMask() {
+        return downMask;
+    }
+
+    /**
+     * This bit-mask describes the bits that can be set in the value described by this stamp.
+     */
+    public long upMask() {
+        return upMask;
     }
 
     public boolean isUnrestricted() {
-        return lowerBound == kind().getMinValue() && upperBound == kind().getMaxValue() && mask == defaultMask(kind());
+        return lowerBound == kind().getMinValue() && upperBound == kind().getMaxValue() && downMask == 0 && upMask == defaultMask(kind());
     }
 
     public boolean contains(long value) {
-        return value >= lowerBound && value <= upperBound && (value & mask) == (value & defaultMask(kind()));
+        return value >= lowerBound && value <= upperBound && (value & downMask) == downMask && (value & upMask) == (value & defaultMask(kind()));
     }
 
     public boolean isPositive() {
@@ -120,8 +132,11 @@
         } else if (lowerBound != kind().getMinValue() || upperBound != kind().getMaxValue()) {
             str.append(" [").append(lowerBound).append(" - ").append(upperBound).append(']');
         }
-        if (mask != defaultMask(kind())) {
-            str.append(" #").append(Long.toHexString(mask));
+        if (downMask != 0) {
+            str.append(" \u21ca").append(Long.toHexString(downMask));
+        }
+        if (upMask != defaultMask(kind())) {
+            str.append(" \u21c8").append(Long.toHexString(upMask));
         }
         return str.toString();
     }
@@ -131,7 +146,7 @@
         IntegerStamp other = (IntegerStamp) otherStamp;
         if (lowerBound > other.upperBound || upperBound < other.lowerBound) {
             return true;
-        } else if ((mask & other.mask) == 0 && (lowerBound > 0 || upperBound < 0 || other.lowerBound > 0 || other.upperBound < 0)) {
+        } else if ((upMask & other.upMask) == 0 && (lowerBound > 0 || upperBound < 0 || other.lowerBound > 0 || other.upperBound < 0)) {
             /*
              * Zero is the only common value if the masks don't overlap. If one of the two values is
              * less than or greater than zero, they are always distinct.
@@ -141,6 +156,19 @@
         return false;
     }
 
+    private Stamp createStamp(IntegerStamp other, long newUpperBound, long newLowerBound, long newDownMask, long newUpMask) {
+        assert kind() == other.kind();
+        if (newLowerBound > newUpperBound || (newDownMask & (~newUpMask)) != 0) {
+            return StampFactory.illegal();
+        } else if (newLowerBound == lowerBound && newUpperBound == upperBound && newDownMask == downMask && newUpMask == upMask) {
+            return this;
+        } else if (newLowerBound == other.lowerBound && newUpperBound == other.upperBound && newDownMask == other.downMask && newUpMask == other.upMask) {
+            return other;
+        } else {
+            return new IntegerStamp(kind(), newLowerBound, newUpperBound, newDownMask, newUpMask);
+        }
+    }
+
     @Override
     public Stamp meet(Stamp otherStamp) {
         if (otherStamp == this) {
@@ -153,17 +181,7 @@
             return StampFactory.illegal();
         }
         IntegerStamp other = (IntegerStamp) otherStamp;
-        assert kind() == other.kind();
-        long meetUpperBound = Math.max(upperBound, other.upperBound);
-        long meetLowerBound = Math.min(lowerBound, other.lowerBound);
-        long meetMask = mask | other.mask;
-        if (meetLowerBound == lowerBound && meetUpperBound == upperBound && meetMask == mask) {
-            return this;
-        } else if (meetLowerBound == other.lowerBound && meetUpperBound == other.upperBound && meetMask == other.mask) {
-            return other;
-        } else {
-            return new IntegerStamp(kind(), meetLowerBound, meetUpperBound, meetMask);
-        }
+        return createStamp(other, Math.max(upperBound, other.upperBound), Math.min(lowerBound, other.lowerBound), downMask & other.downMask, upMask | other.upMask);
     }
 
     @Override
@@ -178,19 +196,7 @@
             return StampFactory.illegal();
         }
         IntegerStamp other = (IntegerStamp) otherStamp;
-        assert kind() == other.kind();
-        long joinUpperBound = Math.min(upperBound, other.upperBound);
-        long joinLowerBound = Math.max(lowerBound, other.lowerBound);
-        long joinMask = mask & other.mask;
-        if (joinLowerBound == lowerBound && joinUpperBound == upperBound && joinMask == mask) {
-            return this;
-        } else if (joinLowerBound == other.lowerBound && joinUpperBound == other.upperBound && joinMask == other.mask) {
-            return other;
-        } else if (joinLowerBound > joinUpperBound) {
-            return StampFactory.illegal();
-        } else {
-            return new IntegerStamp(kind(), joinLowerBound, joinUpperBound, joinMask);
-        }
+        return createStamp(other, Math.min(upperBound, other.upperBound), Math.max(lowerBound, other.lowerBound), downMask | other.downMask, upMask & other.upMask);
     }
 
     @Override
@@ -199,7 +205,8 @@
         int result = 1;
         result = prime * result + (int) (lowerBound ^ (lowerBound >>> 32));
         result = prime * result + (int) (upperBound ^ (upperBound >>> 32));
-        result = prime * result + (int) (mask ^ (mask >>> 32));
+        result = prime * result + (int) (downMask ^ (downMask >>> 32));
+        result = prime * result + (int) (upMask ^ (upMask >>> 32));
         return result;
     }
 
@@ -212,7 +219,7 @@
             return false;
         }
         IntegerStamp other = (IntegerStamp) obj;
-        if (lowerBound != other.lowerBound || upperBound != other.upperBound || mask != other.mask) {
+        if (lowerBound != other.lowerBound || upperBound != other.upperBound || downMask != other.downMask || upMask != other.upMask) {
             return false;
         }
         return true;
@@ -237,7 +244,7 @@
         }
     }
 
-    public static long maskFor(Kind kind, long lowerBound, long upperBound) {
+    public static long upMaskFor(Kind kind, long lowerBound, long upperBound) {
         long mask = lowerBound | upperBound;
         if (mask == 0) {
             return 0;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java	Mon Aug 19 14:11:10 2013 +0200
@@ -43,7 +43,7 @@
     private static final Stamp voidStamp = new GenericStamp(GenericStampType.Void);
     private static final Stamp nodeIntrinsicStamp = new ObjectStamp(null, false, false, false);
     private static final Stamp wordStamp = new ObjectStamp(null, false, false, false);
-    private static final Stamp positiveInt = forInteger(Kind.Int, 0, Integer.MAX_VALUE, Integer.MAX_VALUE);
+    private static final Stamp positiveInt = forInteger(Kind.Int, 0, Integer.MAX_VALUE, 0, Integer.MAX_VALUE);
 
     private static void setCache(Kind kind, Stamp stamp) {
         stampCache[kind.ordinal()] = stamp;
@@ -117,21 +117,41 @@
         return IllegalStamp.ILLEGAL;
     }
 
-    public static Stamp forInteger(Kind kind, long lowerBound, long upperBound, long mask) {
-        return new IntegerStamp(kind, lowerBound, upperBound, mask);
+    public static IntegerStamp forInteger(Kind kind, long lowerBound, long upperBound, long downMask, long upMask) {
+        return new IntegerStamp(kind, lowerBound, upperBound, downMask, upMask);
     }
 
-    public static Stamp forInteger(Kind kind, long lowerBound, long upperBound) {
-        long mask;
-        if (lowerBound < 0) {
-            mask = IntegerStamp.defaultMask(kind);
+    public static IntegerStamp forInteger(Kind kind, long lowerBound, long upperBound) {
+        long defaultMask = IntegerStamp.defaultMask(kind);
+        if (lowerBound == upperBound) {
+            return new IntegerStamp(kind, lowerBound, lowerBound, lowerBound & defaultMask, lowerBound & defaultMask);
+        }
+        final long downMask;
+        final long upMask;
+        if (lowerBound >= 0) {
+            int upperBoundLeadingZeros = Long.numberOfLeadingZeros(upperBound);
+            long differentBits = lowerBound ^ upperBound;
+            int sameBitCount = Long.numberOfLeadingZeros(differentBits << upperBoundLeadingZeros);
+
+            upMask = upperBound | -1L >>> (upperBoundLeadingZeros + sameBitCount);
+            downMask = upperBound & ~(-1L >>> (upperBoundLeadingZeros + sameBitCount));
         } else {
-            mask = -1 >>> Long.numberOfLeadingZeros(upperBound);
+            if (upperBound >= 0) {
+                upMask = defaultMask;
+                downMask = 0;
+            } else {
+                int lowerBoundLeadingOnes = Long.numberOfLeadingZeros(~lowerBound);
+                long differentBits = lowerBound ^ upperBound;
+                int sameBitCount = Long.numberOfLeadingZeros(differentBits << lowerBoundLeadingOnes);
+
+                upMask = lowerBound | -1L >>> (lowerBoundLeadingOnes + sameBitCount) | ~(-1L >>> lowerBoundLeadingOnes);
+                downMask = lowerBound & ~(-1L >>> (lowerBoundLeadingOnes + sameBitCount)) | ~(-1L >>> lowerBoundLeadingOnes);
+            }
         }
-        return forInteger(kind, lowerBound, upperBound, mask);
+        return forInteger(kind, lowerBound, upperBound, downMask & defaultMask, upMask & defaultMask);
     }
 
-    public static Stamp forFloat(Kind kind, double lowerBound, double upperBound, boolean nonNaN) {
+    public static FloatStamp forFloat(Kind kind, double lowerBound, double upperBound, boolean nonNaN) {
         return new FloatStamp(kind, lowerBound, upperBound, nonNaN);
     }
 
@@ -144,7 +164,8 @@
             case Short:
             case Int:
             case Long:
-                return forInteger(kind.getStackKind(), value.asLong(), value.asLong(), value.asLong() & IntegerStamp.defaultMask(kind));
+                long mask = value.asLong() & IntegerStamp.defaultMask(kind);
+                return forInteger(kind.getStackKind(), value.asLong(), value.asLong(), mask, mask);
             case Float:
                 return forFloat(kind, value.asFloat(), value.asFloat(), !Float.isNaN(value.asFloat()));
             case Double:
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampTool.java	Mon Aug 19 14:05:55 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampTool.java	Mon Aug 19 14:11:10 2013 +0200
@@ -29,7 +29,6 @@
 /**
  * Helper class that is used to keep all stamp-related operations in one place.
  */
-// TODO(ls) maybe move the contents into IntegerStamp
 public class StampTool {
 
     public static Stamp negate(Stamp stamp) {
@@ -38,12 +37,26 @@
             IntegerStamp integerStamp = (IntegerStamp) stamp;
             if (integerStamp.lowerBound() != kind.getMinValue()) {
                 // TODO(ls) check if the mask calculation is correct...
-                return new IntegerStamp(kind, -integerStamp.upperBound(), -integerStamp.lowerBound(), IntegerStamp.defaultMask(kind) & (integerStamp.mask() | -integerStamp.mask()));
+                return StampFactory.forInteger(kind, -integerStamp.upperBound(), -integerStamp.lowerBound());
             }
+        } else if (stamp instanceof FloatStamp) {
+            FloatStamp floatStamp = (FloatStamp) stamp;
+            return new FloatStamp(kind, -floatStamp.upperBound(), -floatStamp.lowerBound(), floatStamp.isNonNaN());
         }
+
         return StampFactory.forKind(kind);
     }
 
+    public static Stamp not(Stamp stamp) {
+        if (stamp instanceof IntegerStamp) {
+            IntegerStamp integerStamp = (IntegerStamp) stamp;
+            assert stamp.kind() == Kind.Int || stamp.kind() == Kind.Long;
+            long defaultMask = IntegerStamp.defaultMask(stamp.kind());
+            return new IntegerStamp(stamp.kind(), ~integerStamp.upperBound(), ~integerStamp.lowerBound(), (~integerStamp.upMask()) & defaultMask, (~integerStamp.downMask()) & defaultMask);
+        }
+        return StampFactory.forKind(stamp.kind());
+    }
+
     public static Stamp meet(Collection<? extends StampProvider> values) {
         Iterator<? extends StampProvider> iterator = values.iterator();
         if (iterator.hasNext()) {
@@ -64,20 +77,8 @@
         return StampFactory.illegal();
     }
 
-    public static Stamp add(IntegerStamp stamp1, IntegerStamp stamp2) {
-        Kind kind = stamp1.kind();
-        assert kind == stamp2.kind();
-        if (addOverflow(stamp1.lowerBound(), stamp2.lowerBound(), kind)) {
-            return StampFactory.forKind(kind);
-        }
-        if (addOverflow(stamp1.upperBound(), stamp2.upperBound(), kind)) {
-            return StampFactory.forKind(kind);
-        }
-        long lowerBound = stamp1.lowerBound() + stamp2.lowerBound();
-        long upperBound = stamp1.upperBound() + stamp2.upperBound();
-        long mask = IntegerStamp.maskFor(kind, lowerBound, upperBound);
-
-        return StampFactory.forInteger(kind, lowerBound, upperBound, mask);
+    private static long carryBits(long x, long y) {
+        return (x + y) ^ x ^ y;
     }
 
     public static Stamp sub(Stamp stamp1, Stamp stamp2) {
@@ -92,16 +93,17 @@
     }
 
     public static Stamp div(IntegerStamp stamp1, IntegerStamp stamp2) {
+        assert stamp1.kind() == stamp2.kind();
         Kind kind = stamp1.kind();
         if (stamp2.isStrictlyPositive()) {
             long lowerBound = stamp1.lowerBound() / stamp2.lowerBound();
             long upperBound = stamp1.upperBound() / stamp2.lowerBound();
-            return StampFactory.forInteger(kind, lowerBound, upperBound, IntegerStamp.maskFor(kind, lowerBound, upperBound));
+            return StampFactory.forInteger(kind, lowerBound, upperBound);
         }
         return StampFactory.forKind(kind);
     }
 
-    private static boolean addOverflow(long x, long y, Kind kind) {
+    private static boolean addOverflows(long x, long y, Kind kind) {
         long result = x + y;
         if (kind == Kind.Long) {
             return ((x ^ result) & (y ^ result)) < 0;
@@ -111,29 +113,64 @@
         }
     }
 
-    private static final long INTEGER_SIGN_BIT = 0x80000000L;
-    private static final long LONG_SIGN_BIT = 0x8000000000000000L;
+    public static IntegerStamp add(IntegerStamp stamp1, IntegerStamp stamp2) {
+        try {
+            if (stamp1.isUnrestricted() || stamp2.isUnrestricted()) {
+                return (IntegerStamp) StampFactory.forKind(stamp1.kind());
+            }
+            Kind kind = stamp1.kind();
+            assert stamp1.kind() == stamp2.kind();
+            long defaultMask = IntegerStamp.defaultMask(kind);
+            long variableBits = (stamp1.downMask() ^ stamp1.upMask()) | (stamp2.downMask() ^ stamp2.upMask());
+            long variableBitsWithCarry = variableBits | (carryBits(stamp1.downMask(), stamp2.downMask()) ^ carryBits(stamp1.upMask(), stamp2.upMask()));
+            long newDownMask = (stamp1.downMask() + stamp2.downMask()) & ~variableBitsWithCarry;
+            long newUpMask = (stamp1.downMask() + stamp2.downMask()) | variableBitsWithCarry;
+
+            newDownMask &= defaultMask;
+            newUpMask &= defaultMask;
 
-    private static Stamp stampForMask(Kind kind, long mask) {
-        return stampForMask(kind, mask, 0);
+            long lowerBound;
+            long upperBound;
+            if (addOverflows(stamp1.lowerBound(), stamp2.lowerBound(), kind) || addOverflows(stamp1.upperBound(), stamp2.upperBound(), kind)) {
+                lowerBound = kind.getMinValue();
+                upperBound = kind.getMaxValue();
+            } else {
+                lowerBound = stamp1.lowerBound() + stamp2.lowerBound();
+                upperBound = stamp1.upperBound() + stamp2.upperBound();
+            }
+            IntegerStamp limit = StampFactory.forInteger(kind, lowerBound, upperBound);
+            newUpMask &= limit.upMask();
+            return new IntegerStamp(kind, lowerBound | newDownMask, signExtend(upperBound & newUpMask, kind), newDownMask, newUpMask);
+        } catch (Throwable e) {
+            throw new RuntimeException(stamp1 + " + " + stamp2, e);
+        }
     }
 
-    private static Stamp stampForMask(Kind kind, long mask, long alwaysSetBits) {
+    public static Stamp sub(IntegerStamp stamp1, IntegerStamp stamp2) {
+        if (stamp1.isUnrestricted() || stamp2.isUnrestricted()) {
+            return StampFactory.forKind(stamp1.kind());
+        }
+        return add(stamp1, (IntegerStamp) StampTool.negate(stamp2));
+    }
+
+    private static Stamp stampForMask(Kind kind, long downMask, long upMask) {
         long lowerBound;
         long upperBound;
-        if (kind == Kind.Int && (mask & INTEGER_SIGN_BIT) != 0) {
-            // the mask is negative
-            lowerBound = Integer.MIN_VALUE;
-            upperBound = mask ^ INTEGER_SIGN_BIT;
-        } else if (kind == Kind.Long && (mask & LONG_SIGN_BIT) != 0) {
-            // the mask is negative
-            lowerBound = Long.MIN_VALUE;
-            upperBound = mask ^ LONG_SIGN_BIT;
+        if (((upMask >>> (kind.getBitCount() - 1)) & 1) == 0) {
+            lowerBound = downMask;
+            upperBound = upMask;
+        } else if (((downMask >>> (kind.getBitCount() - 1)) & 1) == 1) {
+            lowerBound = downMask;
+            upperBound = upMask;
         } else {
-            lowerBound = alwaysSetBits;
-            upperBound = mask;
+            lowerBound = downMask | (-1L << (kind.getBitCount() - 1));
+            upperBound = kind.getMaxValue() & upMask;
         }
-        return StampFactory.forInteger(kind, lowerBound, upperBound, mask);
+        if (kind == Kind.Int) {
+            return StampFactory.forInteger(kind, (int) lowerBound, (int) upperBound, downMask, upMask);
+        } else {
+            return StampFactory.forInteger(kind, lowerBound, upperBound, downMask, upMask);
+        }
     }
 
     public static Stamp and(Stamp stamp1, Stamp stamp2) {
@@ -144,9 +181,8 @@
     }
 
     public static Stamp and(IntegerStamp stamp1, IntegerStamp stamp2) {
-        Kind kind = stamp1.kind();
-        long mask = stamp1.mask() & stamp2.mask();
-        return stampForMask(kind, mask);
+        assert stamp1.kind() == stamp2.kind();
+        return stampForMask(stamp1.kind(), stamp1.downMask() & stamp2.downMask(), stamp1.upMask() & stamp2.upMask());
     }
 
     public static Stamp or(Stamp stamp1, Stamp stamp2) {
@@ -157,13 +193,8 @@
     }
 
     public static Stamp or(IntegerStamp stamp1, IntegerStamp stamp2) {
-        Kind kind = stamp1.kind();
-        long mask = stamp1.mask() | stamp2.mask();
-        if (stamp1.lowerBound() >= 0 && stamp2.lowerBound() >= 0) {
-            return stampForMask(kind, mask, stamp1.lowerBound() | stamp2.lowerBound());
-        } else {
-            return stampForMask(kind, mask);
-        }
+        assert stamp1.kind() == stamp2.kind();
+        return stampForMask(stamp1.kind(), stamp1.downMask() | stamp2.downMask(), stamp1.upMask() | stamp2.upMask());
     }
 
     public static Stamp xor(Stamp stamp1, Stamp stamp2) {
@@ -174,9 +205,11 @@
     }
 
     public static Stamp xor(IntegerStamp stamp1, IntegerStamp stamp2) {
-        Kind kind = stamp1.kind();
-        long mask = stamp1.mask() | stamp2.mask();
-        return stampForMask(kind, mask);
+        assert stamp1.kind() == stamp2.kind();
+        long variableBits = (stamp1.downMask() ^ stamp1.upMask()) | (stamp2.downMask() ^ stamp2.upMask());
+        long newDownMask = (stamp1.downMask() ^ stamp2.downMask()) & ~variableBits;
+        long newUpMask = (stamp1.downMask() ^ stamp2.downMask()) | variableBits;
+        return stampForMask(stamp1.kind(), newDownMask, newUpMask);
     }
 
     public static Stamp unsignedRightShift(Stamp value, Stamp shift) {
@@ -201,12 +234,11 @@
                     lowerBound = value.lowerBound() >>> shiftCount;
                     upperBound = value.upperBound() >>> shiftCount;
                 }
-                long mask = value.mask() >>> shiftCount;
-                return StampFactory.forInteger(kind, lowerBound, upperBound, mask);
+                return new IntegerStamp(kind, lowerBound, upperBound, value.downMask() >>> shiftCount, value.upMask() >>> shiftCount);
             }
         }
-        long mask = IntegerStamp.maskFor(kind, value.lowerBound(), value.upperBound());
-        return stampForMask(kind, mask);
+        long mask = IntegerStamp.upMaskFor(kind, value.lowerBound(), value.upperBound());
+        return stampForMask(kind, 0, mask);
     }
 
     public static Stamp leftShift(Stamp value, Stamp shift) {
@@ -218,55 +250,78 @@
 
     public static Stamp leftShift(IntegerStamp value, IntegerStamp shift) {
         Kind kind = value.kind();
+        long defaultMask = IntegerStamp.defaultMask(kind);
+        if (value.upMask() == 0) {
+            return value;
+        }
         int shiftBits = kind == Kind.Int ? 5 : 6;
         long shiftMask = kind == Kind.Int ? 0x1FL : 0x3FL;
         if ((shift.lowerBound() >>> shiftBits) == (shift.upperBound() >>> shiftBits)) {
-            long mask = 0;
-            for (long i = shift.lowerBound() & shiftMask; i <= (shift.upperBound() & shiftMask); i++) {
-                mask |= value.mask() << i;
+            long downMask = defaultMask;
+            long upMask = 0;
+            for (long i = shift.lowerBound(); i <= shift.upperBound(); i++) {
+                if (shift.contains(i)) {
+                    downMask &= value.downMask() << (i & shiftMask);
+                    upMask |= value.upMask() << (i & shiftMask);
+                }
             }
-            mask &= IntegerStamp.defaultMask(kind);
-            return stampForMask(kind, mask);
+            Stamp result = stampForMask(kind, downMask, upMask & IntegerStamp.defaultMask(kind));
+            return result;
         }
         return StampFactory.forKind(kind);
     }
 
     public static Stamp intToLong(IntegerStamp intStamp) {
-        long mask;
-        if (intStamp.isPositive()) {
-            mask = intStamp.mask();
-        } else {
-            mask = 0xffffffff00000000L | intStamp.mask();
-        }
-        return StampFactory.forInteger(Kind.Long, intStamp.lowerBound(), intStamp.upperBound(), mask);
+        return StampFactory.forInteger(Kind.Long, intStamp.lowerBound(), intStamp.upperBound(), signExtend(intStamp.downMask(), Kind.Int), signExtend(intStamp.upMask(), Kind.Int));
     }
 
-    private static Stamp narrowingKindConvertion(IntegerStamp fromStamp, Kind toKind) {
-        long mask = fromStamp.mask() & IntegerStamp.defaultMask(toKind);
-        long lowerBound = saturate(fromStamp.lowerBound(), toKind);
-        long upperBound = saturate(fromStamp.upperBound(), toKind);
+    private static IntegerStamp narrowingKindConvertion(IntegerStamp fromStamp, Kind toKind) {
+        assert toKind == Kind.Byte || toKind == Kind.Char || toKind == Kind.Short || toKind == Kind.Int;
+        final long upperBound;
         if (fromStamp.lowerBound() < toKind.getMinValue()) {
             upperBound = toKind.getMaxValue();
+        } else {
+            upperBound = saturate(fromStamp.upperBound(), toKind);
         }
+        final long lowerBound;
         if (fromStamp.upperBound() > toKind.getMaxValue()) {
             lowerBound = toKind.getMinValue();
+        } else {
+            lowerBound = saturate(fromStamp.lowerBound(), toKind);
         }
-        return StampFactory.forInteger(toKind.getStackKind(), lowerBound, upperBound, mask);
+
+        long defaultMask = IntegerStamp.defaultMask(toKind);
+        long intMask = IntegerStamp.defaultMask(Kind.Int);
+        long newUpMask = signExtend(fromStamp.upMask() & defaultMask, toKind) & intMask;
+        long newDownMask = signExtend(fromStamp.downMask() & defaultMask, toKind) & intMask;
+        return new IntegerStamp(toKind.getStackKind(), (int) ((lowerBound | newDownMask) & newUpMask), (int) ((upperBound | newDownMask) & newUpMask), newDownMask, newUpMask);
     }
 
-    public static Stamp intToByte(IntegerStamp intStamp) {
+    private static long signExtend(long value, Kind valueKind) {
+        if (valueKind != Kind.Char && (value >>> (valueKind.getBitCount() - 1) & 1) == 1) {
+            return value | (-1L << valueKind.getBitCount());
+        } else {
+            return value;
+        }
+    }
+
+    public static IntegerStamp intToByte(IntegerStamp intStamp) {
+        assert intStamp.kind() == Kind.Int;
         return narrowingKindConvertion(intStamp, Kind.Byte);
     }
 
-    public static Stamp intToShort(IntegerStamp intStamp) {
+    public static IntegerStamp intToShort(IntegerStamp intStamp) {
+        assert intStamp.kind() == Kind.Int;
         return narrowingKindConvertion(intStamp, Kind.Short);
     }
 
-    public static Stamp intToChar(IntegerStamp intStamp) {
+    public static IntegerStamp intToChar(IntegerStamp intStamp) {
+        assert intStamp.kind() == Kind.Int;
         return narrowingKindConvertion(intStamp, Kind.Char);
     }
 
-    public static Stamp longToInt(IntegerStamp longStamp) {
+    public static IntegerStamp longToInt(IntegerStamp longStamp) {
+        assert longStamp.kind() == Kind.Long;
         return narrowingKindConvertion(longStamp, Kind.Int);
     }