930565 - Allow to concatenate if any term is not a string or number literal in frontend

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Masaya Iseki[:isk](UTC+9)]

This idea is another approach to resolve Bug 852791.
> I noticed while looking at iongraph output[1] (can also be viewed with the JIT Inspector) that we are not doing any 
> compile time optimizations on string concatenation following a non-constant string concatenation.  The following code
>
>  var s = "f" + "oo" + x + "b" + "ar";
>
> should produce the same code as:
>
>  var s = "foo" + x + "bar";
>
>where both "foo" and "bar" constants are folded.

I tried to fix this bug  by changing MConcat.
But this approach has complex problem due to parallel compilation.
So I suggest another approach.

Fold which is in js/src/frontend/FoldConstants.cpp:562 can't concatenate if any term is not a string or number litetal.
If we can concatenate it, the following code 
       var s = "f" + "oo" + x + "b" + "ar";
produce the same code as:
     var s = "foo" + x + "bar";

Comment 1

[Nicolas B. Pierron [:nbp]]

Jason, can you mentor Iseki Masaya on this bug?

Comment 2

[Jason Orendorff [:jorendorff]]

Sure! Iseki, you can get in touch with me at my bugzilla email address.

I think your idea is a good one. Let me know if you have any questions.

Comment 3

[Masaya Iseki[:isk](UTC+9)]

Attachment: bug930565.patch

I check iongraph.
I confirm
     var s = "f" + "oo" + x + "b" + "ar";
produce the same code as:
    var s = "foo" + x + "bar";

Comment 4

[Jason Orendorff [:jorendorff]]

Comment on attachment 822067 [details] [diff] [review]
bug930565.patch

Review of attachment 822067 [details] [diff] [review]:
-----------------------------------------------------------------

Great work.

Please remove PNX_CANTFOLD entirely.

(Also remove PNX_STRCAT if you see an easy way to do it! I'm sure we don't really need it.)

Clearing the review flag for now. When you post a new patch, set r?me.

::: js/src/frontend/FoldConstants.cpp
@@ +568,5 @@
>              /* Ok, we're concatenating: convert non-string constant operands. */
> +            size_t cnt = 0;
> +            ParseNode *prev = NULL;
> +            bool isFold = false;
> +            // if fold point is last , we must change pn_tail.

A minor detail: English sentences start with a capital letter, and there's no space before a comma.

@@ +602,5 @@
> +
> +                prev->pn_next = pn2->pn_next;
> +                handler.freeTree(pn2);
> +                pn2 = prev->pn_next;
> +                ++cnt;

Since you're removing a node from pn's list, decrement pn->pn_count right here.

@@ +614,3 @@
>              }
>  
> +            //if we can fold one constant, arity is not PN_LIST.

Capital letter here, too. Also please put a space after '//'.

@@ +614,4 @@
>              }
>  
> +            //if we can fold one constant, arity is not PN_LIST.
> +            if (pn->pn_count == cnt + 1) {

Instead, say "if (pn->pn_count == 1) {"

This way I think you can remove the local variable 'cnt'.

@@ +616,5 @@
> +            //if we can fold one constant, arity is not PN_LIST.
> +            if (pn->pn_count == cnt + 1) {
> +                pn->pn_atom = pn1->pn_atom;
> +                if (!pn->pn_atom)
> +                    return false;

There is no need to check for null here.

@@ +619,5 @@
> +                if (!pn->pn_atom)
> +                    return false;
> +                pn->setKind(PNK_STRING);
> +                pn->setOp(JSOP_STRING);
> +                pn->setArity(PN_NULLARY);

The original code does this, but it is a little better to do

    ReplaceNode(pnp, pn1);
    pn = pn1;

since it can be tricky to copy all the fields correctly.

Comment 5

[Masaya Iseki[:isk](UTC+9)]

Attachment: bug930565.patch

I check each element in pn.
So I can remove PNX_STRCAT.

Comment 6

[Masaya Iseki[:isk](UTC+9)]

How to edit assigned to list?
I'd like to assign me.

Comment 7

[Masaya Iseki[:isk](UTC+9)]

How to edit assigned to list?
I'd like to assign me.

Comment 8

[Jason Orendorff [:jorendorff]]

You need the “editbugs” permissions bit in Bugzilla to do that. I'll get it for you on Monday. I would grant you that bit, but I don’t have the “editusers” bit myself...

Comment 9

[Jason Orendorff [:jorendorff]]

Comment on attachment 822897 [details] [diff] [review]
bug930565.patch

Review of attachment 822897 [details] [diff] [review]:
-----------------------------------------------------------------

Getting closer! :)

This patch only contains changes to FoldConstants.cpp. It should also contain changes to the other files where PNX_STRCAT and PNX_CANTFOLD are mentioned. It should be possible to remove them altogether.


I'd like to have some tests for this. You can test that two functions have the same bytecodes.

    function bytecode(f) {
        var d = disassemble(f);
        return d.slice(d.indexOf("main:"), d.indexOf("\n\n"));
    }
    assertEq(bytecode(() => "hello" + "world"),
             bytecode(() => "helloworld"));

::: js/src/frontend/FoldConstants.cpp
@@ +563,5 @@
>              /* Ok, we're concatenating: convert non-string constant operands. */
> +            ParseNode *prev = NULL;
> +            bool isFold = false;
> +            // If fold point is last, we must change pn_tail.
> +            bool isLast = false;

The logic about isLast is too subtle. Instead, at the end of the loop, when we have merged two adjacent nodes, if pn2 ends up being NULL, update pn_tail.

@@ +571,5 @@
> +                if (!prev) {
> +                    pn2 = pn2->pn_next;
> +                    prev = pn1;
> +                    continue;
> +                }

This is confusing. I would start like this:

    for (pn2 = pn1->pn_next; pn2;) {
        isLast = false;
        ...

and use pn1 and pn2 as the two nodes to try joining, rather than pn2 and prev. Then there's no need for this `if (!prev)` special case.

It's safe to do pn1->pn_next because we asserted that pn_count is at least 3.

@@ +572,5 @@
> +                    pn2 = pn2->pn_next;
> +                    prev = pn1;
> +                    continue;
> +                }
> +                if (!pn2->isKind(PNK_STRING) || !prev->isKind(PNK_STRING)) {

With the previous code, string + number would be folded:

  assertEq(bytecode(() => "x" + 3),
           bytecode(() => "x3"));      // passes!

  assertEq(bytecode(() => 2 + "2"),
           bytecode(() => "22"));      // passes!

This was done using FoldType. I think you can keep this working without any trouble.

@@ +583,5 @@
> +                RootedString left(cx, prev->pn_atom);
> +                RootedString right(cx, pn2->pn_atom);
> +                RootedString str(cx, ConcatStrings<CanGC>(cx, left, right));
> +                if (!str)
> +                    continue;

That's no good. You would be leaving an exception pending on cx. You have to return false.

@@ +587,5 @@
> +                    continue;
> +
> +                prev->pn_atom = AtomizeString<CanGC>(cx, str);
> +                if (!prev->pn_atom)
> +                    continue;

Same here.

@@ +591,5 @@
> +                    continue;
> +
> +                prev->setKind(PNK_STRING);
> +                prev->setOp(JSOP_STRING);
> +                prev->setArity(PN_NULLARY);

prev already has all those values. You can assert, if you want.

@@ +608,3 @@
>              }
>  
> +            // If we can fold one constant, arity is not PN_LIST.

Please use this comment instead:

// If we can reduce the list to one constant, there is no addition anymore.
// Replace the PNK_ADD node with the single PNK_STRING node.

@@ +610,5 @@
> +            // If we can fold one constant, arity is not PN_LIST.
> +            if (pn->pn_count == 1) {
> +                pn->pn_atom = pn1->pn_atom;
> +                if (!pn->pn_atom)
> +                    return false;

There's no need to do this pn->pn_atom assignment, since we're replacing pn entirely with pn1.

But anyway pn1->pn_atom can't be null. We checked.

@@ +618,3 @@
>              }
> +            if (isLast) {
> +                pn->pn_tail = &(prev->pn_next);

Style nit: The house style does not use extra parentheses here: just &prev->pn_next.

No curly braces, either, around a single line.

Comment 10

[Jason Orendorff [:jorendorff]]

(In reply to Jason Orendorff [:jorendorff] from comment #9)
> With the previous code, string + number would be folded:
> 
>   assertEq(bytecode(() => "x" + 3),
>            bytecode(() => "x3"));      // passes!
> 
>   assertEq(bytecode(() => 2 + "2"),
>            bytecode(() => "22"));      // passes!

Sorry, of course you have to have three or more things being added if you want a PN_LIST node, so:

    // passes before your patch, fails with your patch
    assertEq(bytecode(() => 2 + "2" + "2"), bytecode(() => "222"));

Comment 11

[Masaya Iseki[:isk](UTC+9)]

Attachment: bug930565.patch

Comment 12

[Masaya Iseki[:isk](UTC+9)]

This patch passes below test.

> function bytecode(f) {
>    var d = disassemble(f);
>    return d.slice(d.indexOf("main:"), d.indexOf("\n\n"));
> }
> assertEq(bytecode(() => "hello" + "world"),
>         bytecode(() => "helloworld"));
> assertEq(bytecode(() => 2 + "2" + "2"),
>         bytecode(() => "222"));
> assertEq(bytecode(() => "x" + "3"),
>          bytecode(() => "x3"));
> var s = "hoge";
> assertEq(bytecode(() => "fo" + "o" + s + "ba" + "r"),
>          bytecode(() => "foo" + s + "bar"));
> assertEq(bytecode(() => "fo" + "o" + 1 + s + 1 + "ba" + "r"),
>          bytecode(() => "foo1" + s + "1bar"));

I'd like to add this test case.
But I don't know where I should add.

Comment 13

[Jason Orendorff [:jorendorff]]

js/src/jit-test/tests/basic/constant-folding-1.js would be fine.

Comment 14

[Masaya Iseki[:isk](UTC+9)]

Attachment: bug930565-test.patch

Comment 15

[Jason Orendorff [:jorendorff]]

Comment on attachment 823786 [details] [diff] [review]
bug930565.patch

Review of attachment 823786 [details] [diff] [review]:
-----------------------------------------------------------------

This is almost done, but I found one more problem.

::: js/src/frontend/FoldConstants.cpp
@@ +568,3 @@
>                      return false;
> +                if (pn2->isKind(PNK_NUMBER) && !FoldType(cx, pn2, PNK_STRING))
> +                    return false;

This fails the following test:

    assertEq(1 + (2 * 2) + "x", "5x");
    typein:7:0 Error: Assertion failed: got "14x", expected "5x"

It converts both 1 and 2*2 to string nodes, "1" + "4" + "x".

In light of this, the comment and code at ParseNode.cpp:313-329 are wrong. Please delete them!

To fix this bug:

1. Convert each node from PNK_NUMBER to PNK_STRING *only* if the other node
   is a PNK_STRING.

2. If both nodes are PNK_NUMBER and we are at the beginning of the list,
   then add them together:

       pn1->pn_dval += pn2->pn_dval;

   and remove pn2 from the list.

Be sure to test that
    var s = "s";
    assertEq(s + 1 + 2, "s12");

@@ +596,1 @@
>              }

Style nit: Omit the curly braces here, since both the condition and the body of the if-statement fit on one line each.

@@ +596,4 @@
>              }
>  
> +            // If we can reduce the list to one constant, there is no addition anymore.
> +            // Replace the PNK_ADD node with the single PNK_STRING node.

With the above change, the single remaining node may be either PNK_STRING or PNK_NUMBER. Please update the comment.

@@ +607,1 @@
>              }

Great. Style nit: Skip the curly braces here, too, for the same reason.

Comment 16

[Jason Orendorff [:jorendorff]]

Comment on attachment 824403 [details] [diff] [review]
bug930565-test.patch

Review of attachment 824403 [details] [diff] [review]:
-----------------------------------------------------------------

Very nice tests.

Please put them into the same patch as the C++ changes they are testing. Tests should land at the same time as the work they are testing, so that we don't let something land (or remain in the tree) without tests or with broken tests.

Comment 17

[Masaya Iseki[:isk](UTC+9)]

Attachment: bug930565.patch

1) add test case below
assertEq(bytecode(() => 1 + (2 * 2) + "x"),
         bytecode(() => 5 + "x"));
assertEq(bytecode(() => s + 1 + 2),
         bytecode(() => s + 3));

2) fix a point that has been pointed out.

Thank you for pointing out that it is easy to understand.

Comment 18

[Masaya Iseki[:isk](UTC+9)]

Attachment: bug930565.patch

Sorry, previous patch didn't add test case.

Comment 19

[Jason Orendorff [:jorendorff]]

Comment on attachment 826217 [details] [diff] [review]
bug930565.patch

Review of attachment 826217 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit-test/tests/basic/constant-folding-1.js
@@ +15,5 @@
> +         bytecode(() => "foo1" + s + "1bar"));
> +assertEq(bytecode(() => 1 + (2 * 2) + "x"),
> +         bytecode(() => 5 + "x"));
> +assertEq(bytecode(() => s + 1 + 2),
> +         bytecode(() => s + 3));

This last assertion isn't right!

> Be sure to test that
>     var s = "s";
>     assertEq(s + 1 + 2, "s12");

I think you have a bug in the new `if (pn1->isKind(PNK_NUMBER) && pn2->isKind(PNK_NUMBER))` code. It should only fold if pn1 is the first node in the list.

Comment 20

[Masaya Iseki[:isk](UTC+9)]

Attachment: bug930565.patch

I fix new bug by using flags.

Comment 21

[Masaya Iseki[:isk](UTC+9)]

Attachment: bug930565.patch

I update this patch because this patch is old.
I have resolved confliction.

Comment 22

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8334497 [details] [diff] [review]
bug930565.patch

Review of attachment 8334497 [details] [diff] [review]:
-----------------------------------------------------------------

Old habits?

Comment 23

[Masaya Iseki[:isk](UTC+9)]

(In reply to Nicolas B. Pierron [:nbp] from comment #22)
> Comment on attachment 8334497 [details] [diff] [review]
> bug930565.patch
> 
> Review of attachment 8334497 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Old habits?

No.
I'd like you to review this patch because this patch was not reviewed for a several weeks.

Comment 24

[Nicolas B. Pierron [:nbp]]

(In reply to iseki.m.aa from comment #23)
> (In reply to Nicolas B. Pierron [:nbp] from comment #22)
> > Comment on attachment 8334497 [details] [diff] [review]
> > bug930565.patch
> > 
> > Review of attachment 8334497 [details] [diff] [review]:
> > -----------------------------------------------------------------
> > 
> > Old habits?
> 
> No.
> I'd like you to review this patch because this patch was not reviewed for a
> several weeks.

The reason I asked Jason to mentor you is because Jason knows more the internal of the front-end than me.  Thus he would be more suited to do the review than me.

Feel free to join on IRC and ask him in person.

Comment 25

[Jason Orendorff [:jorendorff]]

Comment on attachment 8334497 [details] [diff] [review]
bug930565.patch

Review of attachment 8334497 [details] [diff] [review]:
-----------------------------------------------------------------

Please put the tests back into this patch!

Also, add this test:
  assertEq(1 + 2 + {valueOf: () => 3, toString: () => 'x'} + 4 + 5, 15);
and fix the patch so that it passes.

Comment 26

[Masaya Iseki[:isk](UTC+9)]

Attachment: bug930565.patch

Thank you for reviewing.
Sorry for sending an incomplete patch.

I add test case and previous patch and fix to pass following test:
      assertEq(1 + 2 + {valueOf: () => 3, toString: () => 'x'} + 4 + 5, 15);

I found that following test is incorrect.
     assertEq(bytecode(() => s + 1 + 2),
         bytecode(() => s + 3));
This reason is that if "s" is value , later expression(addition) is value addition but if "s" is string , later expression(addition) is string addition. So "s + 1 + 2" can't be folded in FoldConsant because a type of "s" is ambiguous.
I fix it too.

Comment 27

[Jason Orendorff [:jorendorff]]

(In reply to iseki.m.aa from comment #26)

> I found that following test is incorrect.
>      assertEq(bytecode(() => s + 1 + 2),
>          bytecode(() => s + 3));

Right! If you like you can replace it with

    assertEq(bytecode(() => "s" + 1 + 2),
             bytecode(() => "s12"));

> This reason is that if "s" is value , later expression(addition) is value
> addition but if "s" is string , later expression(addition) is string
> addition. So "s + 1 + 2" can't be folded in FoldConsant because a type of
> "s" is ambiguous.

Right again. Great!

I think this patch is the one.  :)

Comment 28

[Jason Orendorff [:jorendorff]]

Comment on attachment 8335681 [details] [diff] [review]
bug930565.patch

Review of attachment 8335681 [details] [diff] [review]:
-----------------------------------------------------------------

r=me with these minor changes, and a quick test run to make sure everything is correct. Very nice patch!

::: js/src/frontend/FoldConstants.cpp
@@ +558,3 @@
>  
>              /* Ok, we're concatenating: convert non-string constant operands. */
> +            bool isFold = false;

Please rename isFold -> folded.

@@ +574,5 @@
> +                // Either pn1 or pn2 must be PNK_STRING.
> +                // pn1 and pn2 mest be either PNK_NUMBER or PNK_STRING.
> +                if ((!pn1->isKind(PNK_STRING) && !pn2->isKind(PNK_STRING)) ||
> +                    (!pn1->isKind(PNK_STRING) && !pn1->isKind(PNK_NUMBER)) ||
> +                    (!pn2->isKind(PNK_STRING) && !pn2->isKind(PNK_NUMBER)) ) {

I see that this is correct, but could you please say it like this instead?

    if (!((pn1->isKind(PNK_NUMBER) && pn2->isKind(PNK_STRING)) ||
          (pn1->isKind(PNK_STRING) && pn2->isKind(PNK_NUMBER)) ||
          (pn1->isKind(PNK_STRING) && pn2->isKind(PNK_STRING))))
    {
        pn1 = pn2;
        pn2 = pn2->pn_next;
        continue;
    }

I think this is easier to read. There are three cases where we can optimize.
If we don't match any of them, continue.

Also, note that the '{' character goes on its own line in SpiderMonkey style.

@@ +602,5 @@
> +                break;
> +            // If we can reduce the list to one constant, there is no addition anymore.
> +            // Replace the PNK_ADD node with the single PNK_STRING or PNK_NUMBER node.
> +            if (pn->pn_count == 1) {
> +                ReplaceNode(pnp, pn1);

The control flow here can be simplified. Please write it like this:

    if (folded) {
        if (pn->pn_count == 1) {
            // We reduced the list to one constant. There is no addition anymore.
            // Replace the PNK_ADD node with the single PNK_STRING or PNK_NUMBER node.
            ReplaceNode(pnp, pn1);
            pn = pn1;
        } else if (!pn2) {
            pn->pn_tail = &pn1->pn_next;
        }
    }
    break;
}

Comment 29

[Masaya Iseki[:isk](UTC+9)]

(In reply to Jason Orendorff [:jorendorff] from comment #28)
> Comment on attachment 8335681 [details] [diff] [review]
> bug930565.patch
> 
> Review of attachment 8335681 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> r=me with these minor changes, and a quick test run to make sure everything
> is correct. Very nice patch!

Thank you for reviewing.

Comment 30

[Masaya Iseki[:isk](UTC+9)]

I don't have access to the Try server. 
Would you push this to Try?

Comment 31

[Jason Orendorff [:jorendorff]]

Yep. I'll do this tomorrow. (Keeping the needinfo? request alive for now)

Comment 32

[Jason Orendorff [:jorendorff]]

Pushed to try server:
https://tbpl.mozilla.org/?tree=Try&rev=c3cd2a564a80

Comment 33

[Masaya Iseki[:isk](UTC+9)]

(In reply to Jason Orendorff [:jorendorff] from comment #32)
> Pushed to try server:
> https://tbpl.mozilla.org/?tree=Try&rev=c3cd2a564a80

Thanks.

Comment 34

[Jason Orendorff [:jorendorff]]

This test case causes an assertion to fail, because the stupid compiler does constant folding twice on that particular subexpression.

    var n = 42;
    var x = ["a" + "b" + n];
    assertEq(x[0], "ab42");

I'll remove the assertion -- the code works fine without it.

Comment 35

[Jason Orendorff [:jorendorff]]

Of course we probably shouldn't be doing constant folding twice. I'll look into that later.

Comment 36

[Jason Orendorff [:jorendorff]]

Found another bug:

    var n = 5;
    assertEq(1 + n + 1 + "ba" + "r", "7bar");

We erroneously fold `1 + "ba"` to `"1ba"`, so that this addition evaluates to "61bar" rather than "7bar".

I can fix.

Comment 37

[Jason Orendorff [:jorendorff]]

Attachment: v1

I really should get a third pair of eyes on the final patch, since I rewrote the condition that means "can we constant-fold these two things as strings?" yet again. Surprisingly tricky, that.

Now it looks like this:

>  } else if ((haveSeenString || (lhsIsNumber && pn2->isKind(PNK_STRING))) &&
>             (pn1->isKind(PNK_STRING) || pn1->isKind(PNK_NUMBER)) &&
>             (pn2->isKind(PNK_STRING) || pn2->isKind(PNK_NUMBER)))

Luke, I can vouch for all the rest, it's really just that one hunk in FoldConstants.cpp that needs re-review.

Still a nice simplification overall: +54 lines, -82, not counting the test.

Comment 38

[Luke Wagner [:luke]]

I think the loop in FoldConstants could be simplified by splitting it into two loops executed in sequence.  The first one would collapse numbers until it found a non-number.  The second one could just worry about folding strings.  In particular, it'd be nice to get away from the isAllNumber/lhsIsNumber bools.  I'm still not sure why lhsIsNumber is necessary (can't the condition just use pn1->isKind(PNK_NUMBER)?).

Comment 39

[Luke Wagner [:luke]]

Comment on attachment 8343907 [details] [diff] [review]
v1

Clearing r? pending response to comment 38.

Comment 40

[Jason Orendorff [:jorendorff]]

(In reply to Luke Wagner [:luke] from comment #38)
> I'm still not sure why lhsIsNumber is
> necessary (can't the condition just use pn1->isKind(PNK_NUMBER)?).

The distinction being made there was that "lhs" referred to the entire left-hand operand of "+", meaning the whole addition chain up to this point (JS addition being left-associative and non-transitive).

Which was a pretty ridiculous amount of semantic load for three letters to carry without a comment, I admit. Anyway, it's gone in the forthcoming patch.

Comment 41

[Jason Orendorff [:jorendorff]]

Attachment: Interdiff v1 -> v2

Comment 42

[Jason Orendorff [:jorendorff]]

Attachment: v2

Comment 43

[Luke Wagner [:luke]]

Comment on attachment 8345594 [details] [diff] [review]
v2

Review of attachment 8345594 [details] [diff] [review]:
-----------------------------------------------------------------

Ahh, so nice!

::: js/src/frontend/FoldConstants.cpp
@@ +554,5 @@
>  
> +            pn2 = pn1->pn_next;
> +            if (pn1->isKind(PNK_NUMBER)) {
> +                // Fold addition of numeric literals: (1 + 2 + x === 3 + x).
> +                // Note that we can only do this the front of the list:

s/this the front/this for the front/

Comment 44

[Jason Orendorff [:jorendorff]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/0e9e2d0e72c3

I managed to not land the comment change by mistake. I have it locally, so I'll land it sometime this week.

Comment 45

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/0e9e2d0e72c3