Bug 1183400 - Fold binary arithmetic operations by kind, not arity. r=efaust
authorJeff Walden <jwalden@mit.edu>
Wed, 08 Jul 2015 13:54:14 -0700
changeset 287218 d8e044ff83721b62f5bf408840cc7e14edf7cfeb
parent 287217 c80e97aaf3b79b7c6329d3c2767436a60cfe60a1
child 287219 43ae47ffe011363092fd4a5d64c14d8a7c9ce69e
push id5067
push userraliiev@mozilla.com
push dateMon, 21 Sep 2015 14:04:52 +0000
treeherdermozilla-beta@14221ffe5b2f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersefaust
bugs1183400
milestone42.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1183400 - Fold binary arithmetic operations by kind, not arity. r=efaust
js/src/frontend/FoldConstants.cpp
--- a/js/src/frontend/FoldConstants.cpp
+++ b/js/src/frontend/FoldConstants.cpp
@@ -1159,16 +1159,128 @@ FoldFunction(ExclusiveContext* cx, Parse
         {
             return false;
         }
     }
 
     return true;
 }
 
+static bool
+FoldBinaryArithmetic(ExclusiveContext* cx, ParseNode* node, Parser<FullParseHandler>& parser,
+                     bool inGenexpLambda)
+{
+    MOZ_ASSERT(node->isKind(PNK_SUB) ||
+               node->isKind(PNK_STAR) ||
+               node->isKind(PNK_LSH) ||
+               node->isKind(PNK_RSH) ||
+               node->isKind(PNK_URSH) ||
+               node->isKind(PNK_DIV) ||
+               node->isKind(PNK_MOD));
+    MOZ_ASSERT(node->isArity(PN_LIST));
+    MOZ_ASSERT(node->pn_count >= 2);
+
+    // Fold each operand, ideally into a number.
+    ParseNode** listp = &node->pn_head;
+    for (; *listp; listp = &(*listp)->pn_next) {
+        if (!Fold(cx, listp, parser, inGenexpLambda, SyntacticContext::Other))
+            return false;
+
+        if (!FoldType(cx, *listp, PNK_NUMBER))
+            return false;
+    }
+
+    // Repoint the list's tail pointer.
+    node->pn_tail = listp;
+
+    // Now fold all leading numeric terms together into a single number.
+    // (Trailing terms for the non-shift operations can't be folded together
+    // due to floating point imprecision.  For example, if |x === -2**53|,
+    // |x - 1 - 1 === -2**53| but |x - 2 === -2**53 - 2|.  Shifts could be
+    // folded, but it doesn't seem worth the effort.)
+    JSOp op = node->getOp();
+    ParseNode* elem = node->pn_head;
+    ParseNode* next = elem->pn_next;
+    if (elem->isKind(PNK_NUMBER)) {
+        while (true) {
+            if (!next || !next->isKind(PNK_NUMBER))
+                break;
+
+            ParseNode* afterNext = next->pn_next;
+            if (!FoldBinaryNumeric(cx, op, elem, next, elem))
+                return false;
+
+            parser.freeTree(next);
+            next = afterNext;
+            elem->pn_next = next;
+
+            node->pn_count--;
+        }
+
+        if (node->pn_count == 1) {
+            MOZ_ASSERT(node->pn_head == elem);
+            MOZ_ASSERT(elem->isKind(PNK_NUMBER));
+
+            double d = elem->pn_dval;
+            node->setKind(PNK_NUMBER);
+            node->setArity(PN_NULLARY);
+            node->setOp(JSOP_DOUBLE);
+            node->pn_dval = d;
+
+            parser.freeTree(elem);
+        }
+    }
+
+    return true;
+}
+
+static bool
+FoldExponentiation(ExclusiveContext* cx, ParseNode* node, Parser<FullParseHandler>& parser,
+                   bool inGenexpLambda)
+{
+    MOZ_ASSERT(node->isKind(PNK_POW));
+    MOZ_ASSERT(node->isArity(PN_LIST));
+    MOZ_ASSERT(node->pn_count >= 2);
+
+    // Fold each operand, ideally into a number.
+    ParseNode** listp = &node->pn_head;
+    for (; *listp; listp = &(*listp)->pn_next) {
+        if (!Fold(cx, listp, parser, inGenexpLambda, SyntacticContext::Other))
+            return false;
+
+        if (!FoldType(cx, *listp, PNK_NUMBER))
+            return false;
+    }
+
+    // Repoint the list's tail pointer.
+    node->pn_tail = listp;
+
+    // Unlike all other binary arithmetic operators, ** is right-associative:
+    // 2**3**5 is 2**(3**5), not (2**3)**5.  As list nodes singly-link their
+    // children, full constant-folding requires either linear space or dodgy
+    // in-place linked list reversal.  So we only fold one exponentiation: it's
+    // easy and addresses common cases like |2**32|.
+    if (node->pn_count > 2)
+        return true;
+
+    ParseNode* base = node->pn_head;
+    ParseNode* exponent = base->pn_next;
+    if (!base->isKind(PNK_NUMBER) || !exponent->isKind(PNK_NUMBER))
+        return true;
+
+    double d1 = base->pn_dval, d2 = exponent->pn_dval;
+
+    parser.prepareNodeForMutation(node);
+    node->setKind(PNK_NUMBER);
+    node->setArity(PN_NULLARY);
+    node->setOp(JSOP_DOUBLE);
+    node->pn_dval = ecmaPow(d1, d2);
+    return true;
+}
+
 bool
 Fold(ExclusiveContext* cx, ParseNode** pnp, Parser<FullParseHandler>& parser, bool inGenexpLambda,
      SyntacticContext sc)
 {
     JS_CHECK_RECURSION(cx, return false);
 
     ParseNode* pn = *pnp;
     ParseNode* pn1 = nullptr;
@@ -1264,16 +1376,28 @@ Fold(ExclusiveContext* cx, ParseNode** p
 
       case PNK_AND:
       case PNK_OR:
         return FoldAndOr(cx, pnp, parser, inGenexpLambda, sc);
 
       case PNK_FUNCTION:
         return FoldFunction(cx, pn, parser, inGenexpLambda);
 
+      case PNK_SUB:
+      case PNK_STAR:
+      case PNK_LSH:
+      case PNK_RSH:
+      case PNK_URSH:
+      case PNK_DIV:
+      case PNK_MOD:
+        return FoldBinaryArithmetic(cx, pn, parser, inGenexpLambda);
+
+      case PNK_POW:
+        return FoldExponentiation(cx, pn, parser, inGenexpLambda);
+
       case PNK_EXPORT:
       case PNK_ASSIGN:
       case PNK_ADDASSIGN:
       case PNK_SUBASSIGN:
       case PNK_BITORASSIGN:
       case PNK_BITXORASSIGN:
       case PNK_BITANDASSIGN:
       case PNK_LSHASSIGN:
@@ -1315,25 +1439,17 @@ Fold(ExclusiveContext* cx, ParseNode** p
       case PNK_STRICTNE:
       case PNK_NE:
       case PNK_LT:
       case PNK_LE:
       case PNK_GT:
       case PNK_GE:
       case PNK_INSTANCEOF:
       case PNK_IN:
-      case PNK_LSH:
-      case PNK_RSH:
-      case PNK_URSH:
       case PNK_ADD:
-      case PNK_SUB:
-      case PNK_STAR:
-      case PNK_DIV:
-      case PNK_MOD:
-      case PNK_POW:
       case PNK_COMMA:
       case PNK_NEW:
       case PNK_CALL:
       case PNK_GENEXP:
       case PNK_ARRAY:
       case PNK_STATEMENTLIST:
       case PNK_ARGSBODY:
       case PNK_ARRAYCOMP:
@@ -1567,67 +1683,35 @@ Fold(ExclusiveContext* cx, ParseNode** p
             } else if (!pn2) {
                 pn->pn_tail = &pn1->pn_next;
             }
         }
 
         break;
       }
 
-      case PNK_SUB:
-      case PNK_STAR:
-      case PNK_LSH:
-      case PNK_RSH:
-      case PNK_URSH:
-      case PNK_DIV:
-      case PNK_MOD:
-      case PNK_POW:
-        MOZ_ASSERT(pn->getArity() == PN_LIST);
-        MOZ_ASSERT(pn->pn_count >= 2);
-        for (pn2 = pn1; pn2; pn2 = pn2->pn_next) {
-            if (!FoldType(cx, pn2, PNK_NUMBER))
-                return false;
-        }
-        for (pn2 = pn1; pn2; pn2 = pn2->pn_next) {
-            /* XXX fold only if all operands convert to number */
-            if (!pn2->isKind(PNK_NUMBER))
-                break;
-        }
-
-        // No constant-folding for (2**3**5), because (**) is right-
-        // associative. We would have to reverse the list. It's not worth it.
-        if (pn->getKind() == PNK_POW && pn->pn_count > 2)
-            break;
-
-        if (!pn2) {
-            JSOp op = pn->getOp();
-
-            pn2 = pn1->pn_next;
-            pn3 = pn2->pn_next;
-            if (!FoldBinaryNumeric(cx, op, pn1, pn2, pn))
-                return false;
-            while ((pn2 = pn3) != nullptr) {
-                pn3 = pn2->pn_next;
-                if (!FoldBinaryNumeric(cx, op, pn, pn2, pn))
-                    return false;
-            }
-        }
-        break;
-
       case PNK_TYPEOFNAME:
       case PNK_TYPEOFEXPR:
       case PNK_VOID:
       case PNK_NOT:
       case PNK_BITNOT:
       case PNK_POS:
       case PNK_NEG:
       case PNK_CONDITIONAL:
       case PNK_IF:
       case PNK_AND:
       case PNK_OR:
+      case PNK_SUB:
+      case PNK_STAR:
+      case PNK_LSH:
+      case PNK_RSH:
+      case PNK_URSH:
+      case PNK_DIV:
+      case PNK_MOD:
+      case PNK_POW:
         MOZ_CRASH("should have been fully handled above");
 
       case PNK_ELEM: {
         // An indexed expression, pn1[pn2]. A few cases can be improved.
         PropertyName* name = nullptr;
         if (pn2->isKind(PNK_STRING)) {
             JSAtom* atom = pn2->pn_atom;
             uint32_t index;