--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/type/IntegerStamp.java	Wed Jun 10 16:07:59 2015 +0200
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/type/IntegerStamp.java	Wed Jun 10 16:18:22 2015 +0200
@@ -353,7 +353,7 @@
         return null;
     }
 
-    private static boolean addOverflowsPositively(long x, long y, int bits) {
+    public static boolean addOverflowsPositively(long x, long y, int bits) {
         long result = x + y;
         if (bits == 64) {
             return (~x & ~y & result) < 0;
@@ -362,7 +362,7 @@
         }
     }
 
-    private static boolean addOverflowsNegatively(long x, long y, int bits) {
+    public static boolean addOverflowsNegatively(long x, long y, int bits) {
         long result = x + y;
         if (bits == 64) {
             return (x & y & ~result) < 0;
@@ -371,7 +371,7 @@
         }
     }
 
-    private static long carryBits(long x, long y) {
+    public static long carryBits(long x, long y) {
         return (x + y) ^ x ^ y;
     }
 

--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/nodes/arithmetic/IntegerAddExactNode.java	Wed Jun 10 16:07:59 2015 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/nodes/arithmetic/IntegerAddExactNode.java	Wed Jun 10 16:18:22 2015 +0200
@@ -29,8 +29,11 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.jvmci.code.*;
 import com.oracle.jvmci.meta.*;
 
+import static com.oracle.graal.compiler.common.type.IntegerStamp.*;
+
 /**
  * Node representing an exact integer addition that will throw an {@link ArithmeticException} in
  * case the addition would overflow the 32 bit range.
@@ -41,14 +44,59 @@
 
     public IntegerAddExactNode(ValueNode x, ValueNode y) {
         super(TYPE, x, y);
-        setStamp(x.stamp().unrestricted());
+        setStamp(foldStamp(x.stamp(), y.stamp()));
         assert x.stamp().isCompatible(y.stamp()) && x.stamp() instanceof IntegerStamp;
     }
 
     @Override
     public boolean inferStamp() {
-        // TODO Should probably use a specialized version which understands that it can't overflow
-        return false;
+        return updateStamp(foldStamp(x.stamp(), y.stamp()));
+    }
+
+    private static Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
+        IntegerStamp a = (IntegerStamp) stamp1;
+        IntegerStamp b = (IntegerStamp) stamp2;
+
+        int bits = a.getBits();
+        assert bits == b.getBits();
+
+        long defaultMask = CodeUtil.mask(bits);
+        long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask());
+        long variableBitsWithCarry = variableBits | (carryBits(a.downMask(), b.downMask()) ^ carryBits(a.upMask(), b.upMask()));
+        long newDownMask = (a.downMask() + b.downMask()) & ~variableBitsWithCarry;
+        long newUpMask = (a.downMask() + b.downMask()) | variableBitsWithCarry;
+
+        newDownMask &= defaultMask;
+        newUpMask &= defaultMask;
+
+        long newLowerBound;
+        long newUpperBound;
+        boolean lowerOverflowsPositively = addOverflowsPositively(a.lowerBound(), b.lowerBound(), bits);
+        boolean upperOverflowsPositively = addOverflowsPositively(a.upperBound(), b.upperBound(), bits);
+        boolean lowerOverflowsNegatively = addOverflowsNegatively(a.lowerBound(), b.lowerBound(), bits);
+        boolean upperOverflowsNegatively = addOverflowsNegatively(a.upperBound(), b.upperBound(), bits);
+        if (lowerOverflowsPositively) {
+            newLowerBound = CodeUtil.maxValue(bits);
+        } else if (lowerOverflowsNegatively) {
+            newLowerBound = CodeUtil.minValue(bits);
+        } else {
+            newLowerBound = CodeUtil.signExtend((a.lowerBound() + b.lowerBound()) & defaultMask, bits);
+        }
+
+        if (upperOverflowsPositively) {
+            newUpperBound = CodeUtil.maxValue(bits);
+        } else if (upperOverflowsNegatively) {
+            newUpperBound = CodeUtil.minValue(bits);
+        } else {
+            newUpperBound = CodeUtil.signExtend((a.upperBound() + b.upperBound()) & defaultMask, bits);
+        }
+
+        IntegerStamp limit = StampFactory.forInteger(bits, newLowerBound, newUpperBound);
+        newUpMask &= limit.upMask();
+        newUpperBound = CodeUtil.signExtend(newUpperBound & newUpMask, bits);
+        newDownMask |= limit.downMask();
+        newLowerBound |= newDownMask;
+        return new IntegerStamp(bits, newLowerBound, newUpperBound, newDownMask, newUpMask);
     }
 
     @Override