8058610: must not let long operations overflow
authorattila
Tue, 21 Oct 2014 14:27:49 +0200
changeset 27208 e8a33eadb339
parent 27207 1f26a24d639a
child 27209 30d8609b9561
8058610: must not let long operations overflow Reviewed-by: hannesw, jlaskey, lagergren
nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/codegen/CodeGenerator.java
nashorn/test/script/basic/JDK-8058610.js
nashorn/test/script/basic/JDK-8058610.js.EXPECTED
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/codegen/CodeGenerator.java	Mon Oct 20 14:09:17 2014 +0200
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/codegen/CodeGenerator.java	Tue Oct 21 14:27:49 2014 +0200
@@ -552,10 +552,10 @@
     }
 
     MethodEmitter loadBinaryOperands(final BinaryNode binaryNode) {
-        return loadBinaryOperands(binaryNode.lhs(), binaryNode.rhs(), TypeBounds.UNBOUNDED.notWiderThan(binaryNode.getWidestOperandType()), false);
+        return loadBinaryOperands(binaryNode.lhs(), binaryNode.rhs(), TypeBounds.UNBOUNDED.notWiderThan(binaryNode.getWidestOperandType()), false, false);
     }
 
-    private MethodEmitter loadBinaryOperands(final Expression lhs, final Expression rhs, final TypeBounds explicitOperandBounds, final boolean baseAlreadyOnStack) {
+    private MethodEmitter loadBinaryOperands(final Expression lhs, final Expression rhs, final TypeBounds explicitOperandBounds, final boolean baseAlreadyOnStack, final boolean forceConversionSeparation) {
         // ECMAScript 5.1 specification (sections 11.5-11.11 and 11.13) prescribes that when evaluating a binary
         // expression "LEFT op RIGHT", the order of operations must be: LOAD LEFT, LOAD RIGHT, CONVERT LEFT, CONVERT
         // RIGHT, EXECUTE OP. Unfortunately, doing it in this order defeats potential optimizations that arise when we
@@ -572,15 +572,34 @@
         final Type narrowestOperandType = Type.narrowest(Type.widest(lhs.getType(), rhs.getType()), explicitOperandBounds.widest);
         final TypeBounds operandBounds = explicitOperandBounds.notNarrowerThan(narrowestOperandType);
         if (noToPrimitiveConversion(lhs.getType(), explicitOperandBounds.widest) || rhs.isLocal()) {
-            // Can reorder. Combine load and convert into single operations.
-            loadExpression(lhs, operandBounds, baseAlreadyOnStack);
-            loadExpression(rhs, operandBounds, false);
+            // Can reorder. We might still need to separate conversion, but at least we can do it with reordering
+            if (forceConversionSeparation) {
+                // Can reorder, but can't move conversion into the operand as the operation depends on operands
+                // exact types for its overflow guarantees. E.g. with {L}{%I}expr1 {L}* {L}{%I}expr2 we are not allowed
+                // to merge {L}{%I} into {%L}, as that can cause subsequent overflows; test for JDK-8058610 contains
+                // concrete cases where this could happen.
+                final TypeBounds safeConvertBounds = TypeBounds.UNBOUNDED.notNarrowerThan(narrowestOperandType);
+                loadExpression(lhs, safeConvertBounds, baseAlreadyOnStack);
+                method.convert(operandBounds.within(method.peekType()));
+                loadExpression(rhs, safeConvertBounds, false);
+                method.convert(operandBounds.within(method.peekType()));
+            } else {
+                // Can reorder and move conversion into the operand. Combine load and convert into single operations.
+                loadExpression(lhs, operandBounds, baseAlreadyOnStack);
+                loadExpression(rhs, operandBounds, false);
+            }
         } else {
             // Can't reorder. Load and convert separately.
             final TypeBounds safeConvertBounds = TypeBounds.UNBOUNDED.notNarrowerThan(narrowestOperandType);
             loadExpression(lhs, safeConvertBounds, baseAlreadyOnStack);
+            final Type lhsType = method.peekType();
             loadExpression(rhs, safeConvertBounds, false);
-            method.swap().convert(operandBounds.within(method.peekType())).swap().convert(operandBounds.within(method.peekType()));
+            final Type convertedLhsType = operandBounds.within(method.peekType());
+            if (convertedLhsType != lhsType) {
+                // Do it conditionally, so that if conversion is a no-op we don't introduce a SWAP, SWAP.
+                method.swap().convert(convertedLhsType).swap();
+            }
+            method.convert(operandBounds.within(method.peekType()));
         }
         assert Type.generic(method.peekType()) == operandBounds.narrowest;
         assert Type.generic(method.peekType(1)) == operandBounds.narrowest;
@@ -631,19 +650,11 @@
         }
 
         TypeBounds booleanToInt() {
-            return maybeNew(booleanToInt(narrowest), booleanToInt(widest));
+            return maybeNew(CodeGenerator.booleanToInt(narrowest), CodeGenerator.booleanToInt(widest));
         }
 
         TypeBounds objectToNumber() {
-            return maybeNew(objectToNumber(narrowest), objectToNumber(widest));
-        }
-
-        private static Type booleanToInt(final Type t) {
-            return t == Type.BOOLEAN ? Type.INT : t;
-        }
-
-        private static Type objectToNumber(final Type t) {
-            return t.isObject() ? Type.NUMBER : t;
+            return maybeNew(CodeGenerator.objectToNumber(narrowest), CodeGenerator.objectToNumber(widest));
         }
 
         Type within(final Type type) {
@@ -662,6 +673,14 @@
         }
     }
 
+    private static Type booleanToInt(final Type t) {
+        return t == Type.BOOLEAN ? Type.INT : t;
+    }
+
+    private static Type objectToNumber(final Type t) {
+        return t.isObject() ? Type.NUMBER : t;
+    }
+
     MethodEmitter loadExpressionAsType(final Expression expr, final Type type) {
         if(type == Type.BOOLEAN) {
             return loadExpressionAsBoolean(expr);
@@ -3543,13 +3562,15 @@
             void loadStack() {
                 final TypeBounds operandBounds;
                 final boolean isOptimistic = isValid(getProgramPoint());
+                boolean forceConversionSeparation = false;
                 if(isOptimistic) {
                     operandBounds = new TypeBounds(binaryNode.getType(), Type.OBJECT);
                 } else {
                     // Non-optimistic, non-FP +. Allow it to overflow.
                     operandBounds = new TypeBounds(binaryNode.getWidestOperandType(), Type.OBJECT);
+                    forceConversionSeparation = binaryNode.getWidestOperationType().narrowerThan(resultBounds.widest);
                 }
-                loadBinaryOperands(binaryNode.lhs(), binaryNode.rhs(), operandBounds, false);
+                loadBinaryOperands(binaryNode.lhs(), binaryNode.rhs(), operandBounds, false, forceConversionSeparation);
             }
 
             @Override
@@ -3660,12 +3681,21 @@
         @Override
         protected void evaluate() {
             final Expression lhs = assignNode.lhs();
-            final Type widest = assignNode.isTokenType(TokenType.ASSIGN_ADD) ? Type.OBJECT : assignNode.getWidestOperationType();
+            final Expression rhs = assignNode.rhs();
+            final Type widestOperationType = assignNode.getWidestOperationType();
+            final Type widest = assignNode.isTokenType(TokenType.ASSIGN_ADD) ? Type.OBJECT : widestOperationType;
             final TypeBounds bounds = new TypeBounds(assignNode.getType(), widest);
             new OptimisticOperation(assignNode, bounds) {
                 @Override
                 void loadStack() {
-                    loadBinaryOperands(lhs, assignNode.rhs(), bounds, true);
+                    final boolean forceConversionSeparation;
+                    if (isValid(getProgramPoint()) || widestOperationType == Type.NUMBER) {
+                        forceConversionSeparation = false;
+                    } else {
+                        final Type operandType = Type.widest(booleanToInt(objectToNumber(lhs.getType())), booleanToInt(objectToNumber(rhs.getType())));
+                        forceConversionSeparation = operandType.narrowerThan(widestOperationType);
+                    }
+                    loadBinaryOperands(lhs, rhs, bounds, true, forceConversionSeparation);
                 }
                 @Override
                 void consumeStack() {
@@ -3688,7 +3718,7 @@
 
         @Override
         protected void evaluate() {
-            loadBinaryOperands(assignNode.lhs(), assignNode.rhs(), TypeBounds.UNBOUNDED.notWiderThan(assignNode.getWidestOperandType()), true);
+            loadBinaryOperands(assignNode.lhs(), assignNode.rhs(), TypeBounds.UNBOUNDED.notWiderThan(assignNode.getWidestOperandType()), true, false);
             op();
         }
     }
@@ -3811,6 +3841,7 @@
                 @Override
                 void loadStack() {
                     final TypeBounds operandBounds;
+                    boolean forceConversionSeparation = false;
                     if(numericBounds.narrowest == Type.NUMBER) {
                         // Result should be double always. Propagate it into the operands so we don't have lots of I2D
                         // and L2D after operand evaluation.
@@ -3828,9 +3859,10 @@
                             // Non-optimistic, non-FP subtraction or multiplication. Allow them to overflow.
                             operandBounds = new TypeBounds(Type.narrowest(node.getWidestOperandType(),
                                     numericBounds.widest), Type.NUMBER);
+                            forceConversionSeparation = node.getWidestOperationType().narrowerThan(numericBounds.widest);
                         }
                     }
-                    loadBinaryOperands(node.lhs(), node.rhs(), operandBounds, false);
+                    loadBinaryOperands(node.lhs(), node.rhs(), operandBounds, false, forceConversionSeparation);
                 }
 
                 @Override
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/nashorn/test/script/basic/JDK-8058610.js	Tue Oct 21 14:27:49 2014 +0200
@@ -0,0 +1,77 @@
+/*
+ * Copyright (c) 2014 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.
+ */
+
+/**
+ * JDK-8058610: must not let long operations overflow
+ *
+ * @test
+ * @run
+ */
+
+function mul(x) { 
+    return x.foo * x.bar; 
+} 
+print("=== mul ===")
+print(mul({foo: 2147483647,  bar: 2147483647})); // 2^31
+print(mul({foo: 17179869184, bar: 2147483647})); // 2^34
+
+function self_mul(x) {
+    return x.foo *= x.bar; 
+}
+print("=== self_mul ===")
+print(self_mul({foo: 2147483647,  bar: 2147483647})); // 2^31
+print(self_mul({foo: 17179869184, bar: 2147483647})); // 2^34
+
+// We'll need to use this function to obtain long values larger in 
+// magnitude than those precisely representable in a double (2^53), 
+// as Nashorn's parser will reify such literals as a double. For 
+// overflow on add and sub we need (2^63)-1.
+var parseLong = Java.type("java.lang.Long").parseLong;
+
+function sub(x) {
+    return x.foo - x.bar;
+}
+print("=== sub ===")
+print(sub({foo: 2147483647,  bar: -2147483647})); // 2^31
+print(sub({foo: parseLong("9223372036854775807"), bar: parseLong("-9223372036854775807")})); // 2^63-1
+
+function self_sub(x) {
+    return x.foo -= x.bar;
+}
+print("=== self_sub ===")
+print(self_sub({foo: 2147483647,  bar: -2147483647})); // 2^31
+print(self_sub({foo: parseLong("9223372036854775807"), bar: parseLong("-9223372036854775807")})); // 2^63-1
+
+function add(x) {
+    return x.foo + x.bar;
+}
+print("=== add ===")
+print(add({foo: 2147483647,  bar: 2147483647})); // 2^31
+print(add({foo: parseLong("9223372036854775807"), bar: parseLong("9223372036854775807")})); // 2^63-1
+
+function self_add(x) {
+    return x.foo += x.bar;
+}
+print("=== self_add ===")
+print(self_add({foo: 2147483647,  bar: 2147483647})); // 2^31
+print(self_add({foo: parseLong("9223372036854775807"), bar: parseLong("9223372036854775807")})); // 2^63-1
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/nashorn/test/script/basic/JDK-8058610.js.EXPECTED	Tue Oct 21 14:27:49 2014 +0200
@@ -0,0 +1,18 @@
+=== mul ===
+4611686014132420600
+36893488130239234000
+=== self_mul ===
+4611686014132420600
+36893488130239234000
+=== sub ===
+4294967294
+18446744073709552000
+=== self_sub ===
+4294967294
+18446744073709552000
+=== add ===
+4294967294
+18446744073709552000
+=== self_add ===
+4294967294
+18446744073709552000